I am working on a homework problem which is similar to this post:- Quickest algorithm to find at most (n/2)-1 liars in n people

The problem is given below:- This problem is couched in terms of liars and truth tellers, but it has real applications in identifying which components of a complex system are good (functioning correctly) and which are faulty. Assume we have a community of n people and we know an integer number t < n/2, which has the property that most t of the n people are liars. This does not say that there actually are t liars, but only that there are at most t liars.

The difference in my case is that the truth-tellers are always truthful and correct and a liar always speaks a lie.

We will identify the liars in the community by successively picking pairs of people, (X, Y) say, and asking X: Is Y a liar?. The response is either “yes” or “no";

What is the optimum algorithm(minimum number of steps) to find all the liars?

CodePudding user response：

One possible algorithm for finding the liars in a community is to first select a random person and ask them whether the next person in the community is a liar. If they say "yes," then the next person is a liar. If they say "no," then the first person is a liar.

Next, select the first non-liar and ask them whether the next non-liar is a liar. If they say "yes," then the next non-liar is a liar. If they say "no," then the first non-liar is a liar.

Continue this process until all the liars have been identified. The total number of steps required to identify all the liars will be equal to the number of liars, plus one additional step to determine whether the first person selected is a liar.

const int MAX_N = 100;
int n;
int t;
bool people[MAX_N]; // True if the person is a liar, false otherwise

void findLiars(void)
{
   // Select a random person and ask them about the next person
   int p = rand() % n;
   if (people[p] != people[(p   1) % n])
   {
      // The next person is a liar
      people[(p   1) % n] = true;
   }
   else
   {
      // The first person is a liar
      people[p] = true;
   }

   // Select the first non-liar and ask them about the next non-liar
   for (int i = 0; i < n; i  )
   {
      if (!people[i])
      {
         p = i;
         break;
      }
   }

   while (true)
   {
      // Find the next non-liar
      int q = (p   1) % n;
      while (people[q])
      {
         q = (q   1) % n;
      }

      if (people[p] != people[q])
      {
         // The next non-liar is a liar
         people[q] = true;
      }
      else
      {
         // The first non-liar is a liar
         people[p] = true;
         break;
      }

      p = q;
   }
}

In this example, the findLiars function uses the described algorithm to identify all the liars in the community. It first selects a random person and asks them whether the next person in the community is a liar. If they say "yes," then the next person is a liar. If they say "no," then the first person is a liar.

Next, the function selects the first non-liar and asks them about the next non-liar. If they say "yes," then the next non-liar is a liar. If they say "no," then the first non-liar is a liar. This process is repeated until all the liars have been identified. The people array is used to keep track of which people have been identified as liars.

CodePudding user response：

The answer to every question gives you a relationship: either X = Y or X = ~Y. Both kinds of relationships are still true if you invert X and Y, so no matter how many questions you ask, you can't figure the answer out without using the constraint.

There are 2ⁿ possible assignments of truther/liar to the n people, so you need n answers. One of those is the constraint, and the other n-1 can be questions.

The simplest way is to ask everyone else about Bob. Everyone will then be in the "same as Bob" group, or the "different than Bob" group. Then you choose whether Bob is a liar or not according to which choice implies fewer liars than truth tellers.

Note that if n is even, then you might get lucky -- you can skip the last question if one of the answers would make the two groups the same size.

CodePudding user response：

Matt has the answer when t ~ n/2 (visualizing the questions as a graph, every arbitrarily directed spanning tree will provide enough info), but in general we don't need n−1 questions for smaller t. We can divide the n people into groups of 2t or larger and query a spanning tree in each group. At most one group may split 50/50, which we can resolve by asking one more question. Ignoring lower order terms, we need about ((2t−1)/2t) n queries.