Who's telling the truth? (Part 2)
Now we have $64$ people. Again, some of these always tell the truth and the rest always lie. Our task here is to find out the liar/s. Every person writes down each of these sentences:
At least one of these $64$ people is a liar
At least two of these $64$ people are liars
…
At least sixty four of these $64$ people are liars
Who is/are the liar/s? Why?
Solution
First, we'll show that the last thirty two people are lying. By induction, suposse
that the last i people are lying, and by contradiction suposse that the $(i+1)$th $\le 32$
is telling the truth, then at least $64-i > 32$ are lying, and as we know that $i$ are lying,
then $> 32-i > 0$ of the rest are lying, that is at least one of the rest is lying, but in that case $< 63-i$ are lying which is a contradiction. Finally, note that the first $32$ people are telling the truth as the last $32$ are lying, and that they can't be lying because this would imply that less than $i \le 32$ are lying which is a contradiction with the current $\ge 33$ liars.
Manuel Cáceres
Postdoctoral Researcher
My research interests include algorithmic bioinformatics, graph algorithms, string algorithms, algorithmic bioinformatics, compressed data structures, safe & complete algorithms and parameterized algorithms.