我有以下问题。在给定的山上，一个女孩被卡住了，有两条路。一条路径将她带到救援者（左转），第二条路径（右转）将她带到没有机会回来的丛林。现在她遇到了一群说 n 的人，他们总是说实话，有些人说 m 可能/可能不会说实话。给定 n 大于 m。所以女孩可以随便问一个人——救援人员是哪一种方式，问题是她不知道她问的是哪一个人（n 或 m）。我想知道是否有一个 Big Theta (n + m) 算法来找出有多少人说真话？或者严格来说n的值？
我可以自己解决一个更简单的版本。说只有两个人，一个总是说真话，另一个总是说谎。她可以问一个他们都会给出相同答案的问题。例如：对说真话的人，她可以问——“嘿，根据对方的说法，救援者走哪条路？”。说真话的人会说——右转（因为对方说谎）。现在她可以向骗子问同样的问题——他会回答说——右转（因为真正的答案是左转，但由于他总是撒谎，他会说右转）。现在她可以向左走，知道这是正确的答案。
问题在于，在第一种情况下 - 第二组人可能/可能不会撒谎。但我认为关键是 n > m 即总是说真话的人数大于可能/可能不说真话的人数。所以看起来这会抵消一些东西。
任何帮助将不胜感激。谢谢。