Liars, Liars, Everywhere

The first thing we need to see is that we can actually get any piece of information we want from any councilmen, regardless of whether they are a liar or not. For any proposition $P$ of which we want to know its truthiness, simply ask the question:

$\text{"If I were to ask you if }P\text{ was true, would you say 'yes'?"}$

Go ahead and walk through the cases to see for yourself. Both truthtellers and liars will reply 'yes' if $P$ is true, and 'no' otherwise. If you have ever studied the hardest logic puzzle ever , this might be familiar to you.

So what can we verify? Well, we can let $P$ be, for each councilmen, $\text{"Are you a liar?"}$ , and in so doing we could determine who's who in not $100$ , but $99$ questions, since the alignment of the last councilman can always be determined by knowing the alignments of the other $99$ . However, this isn't optimal - we can do better.

We are given at the start that exactly $50$ of the councilmen are liars. Therefore, there are not $2^{100}$ unique possibilities, but rather $\binom{100}{50}$ . And a calculator will show that:

$2^{96} < \binom{100}{50} < 2^{97}$

So, from an information theory perspective, we only need $97$ bits of information to uniquely identify the alignments of all of the councilmen - this is a lower bound on the number of questions we must ask, as, mathematically, it's not possible to produce greater than $2^{96}$ possible answers with only $96$ questions.

Because we can determine the truthfulness of any proposition $P$ , we can easily identify the answer in $97$ questions! We simply ask questions akin to binary search.

First, we enumerate all $\binom{100}{50}$ possible alignment patterns, give each one a number in binary, and ask any councilmen, using the previously described format, of the proposition $P = \text{"Is the }n\text{-th bit of the correct configuration }1\text{?"}$ . Since there are only $97$ bits to consider, asking these $97$ questions will uniquely determine the answer.

Since the theoretic lower bound is $97$ , and a strategy exists to get the answer in $97$ questions, the minimum number of questions we must ask is precisely $\boxed{97}$ .

Firstly, we know that there are $\binom{100}{50}$ way to arrange the liars and truth tellers. Each question we asked only have two possible outcomes either $YES$ or $NO$ . The $n$ question we asked, we have $2^n$ possible outcomes.

$2^n\geq\binom{100}{50}$

Since the equation contains the factorial of larger number, we can use $Stirling's approximation$ during calculation. Lastly, we get

$n\geq96.35 , \boxed{n =97}$

Let's assume you're really good at thinking up questions, what's the mininum number of questions you would need to ask in order to distinguish between all the possibilities?

Well, how many possibilities are there? First, give the panel an arbitrary ordering, say there is some 1st member, some 2nd member, and so on.

If there are only 2 people and 1 of them is a liar, there are only two possibilities. Either the first person is a liar, or the first person tells the truth. So theoreticially, it should take just one question solve the problem. (It turns out asking the first guy "if I asked the second guy whether you were a liar, would he say yes?" works)

Now, say there are 4 people, and 2 of them are liars. There are 6 possible orderings those people could have; it is impossible to solve by asking fewer than $log_2(6) = 2.58$ questions.

With 100 people, 50 of which are liars, there are $log_2( \binom{100}{50}) \approx 96.3$ possibile orderings, so with 97 perfectly chosen questions you ought to find the answer.