$2000$ people are standing on a line. Each one of them is either a liar, who will always lie, or a truth-teller, who will always tell the truth. Each one of them says: "there are more liars to my left than truth-tellers to my right". Determine, if possible, how many people from each class are on the line.
Problem
Source: Argentina Cono Sur TST 2013, Problem 1
Tags: combinatorics proposed, combinatorics
vinayak-kumar
21.09.2014 02:47
Label the people from left to right as $P_1,P_2,...,P_{2000}$. I will first show that all $P_n$, where $1\le n\le 1000$, are a liar. We will start by proving a lemma.
Lemma: If $P_1,P_2,...,P_k$, where $1< k< 1000$, are all liars, then $P_{k+1}$ is indeed a liar.
Proof: Assume for the sake of contradiction that $P_{k+1}$ is a truth teller. Then he would record $k$ liars to his left and at most $k-1$ truth tellers to his right. This means there are more than $1999-2k$ liars to the right of him. Now consider the rightmost liar in the line of $2000$. This liar would record at least $1999-2k+k=1999-k$ liars to his left and at most $k-1$ truth tellers to his right. Since this person is a liar, we must have $1999-k\le k-1$. But that implies $k\ge 1000$, a contradiction. $\square$
Since there are no people to the right of $P_{1}$, there cannot be more liars to his left than truth tellers to his right. Therefore $P_1$ is a liar. Now, combining this with our lemma, we get the conclusion that the first $1000$ people in line from the left are liars.
Now I will show that the remaining $1000$ people are truth tellers.
Let us focus on a person $P_n$, where $1001\le n\le 2000$. $P_n$ will record at least $1000$ liars to his left, and since there are less than $1000$ people to his right, he will obviously record less than $1000$ truth tellers to his right. Therefore $P_n$ is a truth teller. That means the remaining $1000$ people are truth tellers.
Therefore there will be $1000$ liars and $1000$ truth tellers. $%Error. "Darksquare" is a bad command.
$
AnonymousBunny
27.09.2014 20:25
I claim that in any such arrangement with $2k$ people, the first $k$ people (from the left) shall be liars and the last $k$ people shall be truth tellers. Induct on $k$. Let's first deal with the base case $k=1$. There are 2 people. Consider the leftmost guy. There are no liars to his left, so the statement he says can't possibly be correct, so he must be a liar. Now consider the other guy. There are no truth tellers to his right but one liar to his left, so he does speak the truth. The base case is complete. Suppose our claim holds for some $k \geq 1$. The inductive step is solved by the same logic - consider the leftmost guy. He has no liars to his left, so the statement he speaks must be false, so he must be a liar. The rightmost guy has no truth tellers to his right, but at least one liar to his left, so he must be a truth teller. So now we have the configuration $LOT,$ where $L$ denotes a liar, $T$ denotes a truth teller, and $O$ is a configuration with $2k-2$ people. Notice that a person in configuration $O$ has more liars to his left than truth tellers to his right iff the same holds for configuration $LOT$. Hence, the configuration $O$ must be a valid configuration as well. By the inductive hypothesis, the first $k-1$ people of $O$ are liars and the rest are truth tellers. Hence, the first $k-1+1= k$ people of this configuration are liars and the rest are truth tellers. $\blacksquare$
raptorw
25.01.2015 05:05
vinayak-kumar wrote: Since there are no people to the right of $P_{1}$, there cannot be more liars to his left than truth tellers to his right. Do you mean there are no people to the left of $P_{1}$?