25
$\begingroup$
  • There are 2014 persons in a row
  • Each of them is either a Knave (who always lies) or a Knight (who always tells the truth).
  • Each person says 'There are more knaves to my left than knights to my right'.
  • How many knaves are there in the row?

Source : (Math Kangaroo competition for parents)

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Some more complicated scenario: You ask everyone whether there are more knaves to his left than knights to his right, and everyone answers yes or no. Can you always find out who is a knave and who is a knight? (This puzzle is the special case where each answer is "yes"). $\endgroup$
    – gnasher729
    Commented Jan 19, 2015 at 14:53
  • 2
    $\begingroup$ @gnasher I edited my answer to address the general case as well. $\endgroup$
    – Milo Brandt
    Commented Jan 20, 2015 at 0:51

5 Answers 5

Reset to default
25
$\begingroup$

For a group of $2n$ $(n\geq1)$ knights and knaves satisfying the puzzle conditions, there must be exactly $n$ knaves. Moreover, all knaves must occupy the first $n$ positions in the row (left to right direction)

We can provide a very elegant proof of this fact by considering this situation if there were $2n$ people in a row. Clearly, for $n\geq 1$, there is at least one knight and one liar, as otherwise the situation would obviously be untrue. From this, consider the leftmost person - there are no liars to his left (which is obviously not more than the number of knights to his right). Thus, he is a liar. The rightmost person obviously has no knights to his right and at least that liar to the left - so he must be a knight.

How do we use this? Take the original $2014$ people. The leftmost is a liar, the rightmost is a knight. If we exclude these two people, we don't modify the situation - we've removed a liar from the left and a knight from the right, so everyone's counts on both sides decrease by one. Thus, we have the $2012$ people in the middle remaining - and the leftmost must be a liar and the rightmost is a knight. Remove them. There are now $2010$ people left. We continue in this manner, pairing liars and knights and, at the end, we have proven that the 1007 leftmost people were liars and the 1007 rightmost were knights.

We can generalize this answer to handle the case where there are $n$ people and we ask everyone in the line whether there there are more knaves to their left than knights to the right and receive a "yes" or "no" answer from each person. In particular, let's consider cases:

  • If the leftmost person in line says "no", he is a knight (since there are no knaves to his left). We can remove him without affecting the relevant counts of everyone else, so this reduces it to the $n-1$ person case.

  • If the leftmost person says "yes" and the rightmost says "no", then both are knaves; we can safely remove the rightmost one without affecting anyone's counts.

    • If the leftmost and rightmost people say "yes", then the leftmost is a knave and the rightmost is a knight; we can remove both people, decreasing everyone's count by $1$ on both sides and not affecting their answers.

Therefore, every case can be reduced to a smaller case and we can thusly identify everyone.

A more elegant proof of the same more general fact as in the previous section is that there must be some $k$ such that the first $k$ people have more knaves to their left than knights to the rest, and this is not true for the rest of the people. This $k$ satisfies that must be more knaves (who answer "yes") among the first $k-1$ as knights (who also answer "yes") among those at position $k+1$ and beyond and that there must be at least as many knights (who answer "yes") in positions $k+2$ and beyond as knaves among the first $k$ (who answer "yes").

This is to say, if you proceed through the line left to right and receive the answer "yes" $2c+1$ times, then everyone before the $c^{th}$ person to say "yes" had fewer knaves to their left than knights to their right and everyone after had the opposite - this suffices to figure out who lied, as you know the truth. Similarly, if you get an answer of "yes" $2c$ times, then the $c^{th}$ person (and everyone before, but no one after) had fewer knaves to their left than knights to their right.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ "We can provide a very elegant proof of this fact" - what fact? $\endgroup$
    – Joe Lee-Moyet
    Commented Jan 19, 2015 at 13:37
  • 3
    $\begingroup$ @yjo Yes, Meelo forgot to state the fact, but it's implicit: For a group of $2n$ ($n\geq 1$) knights and knaves satisfying the puzzle conditions, there must be exactly $n$ knaves. Moreover, all knaves must occupy the first $n$ positions in the row (left to right direction). $\endgroup$
    – ir7
    Commented Jan 19, 2015 at 14:25
  • 1
    $\begingroup$ @ir7 - I submitted an edit to the question to include that. $\endgroup$
    – Bobson
    Commented Jan 19, 2015 at 20:11
8
$\begingroup$

The answer is

1007.

reasoning:

There are 1007 liars followed by 1007 knights. Each liar has 1007 knights to their right and at most 1006 liars to their left, while the knights are in the opposite situation.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @Len, thanks for the typo correction. I must have misread the question as having 2024... $\endgroup$
    – frodoskywalker
    Commented Jan 19, 2015 at 7:46
  • 1
    $\begingroup$ Although you give the correct answer I think your reasoning is not complete. You reason that it is a correct answer but not that it is the only correct answer. Who says that all knaves need to be in a row and all knights are in a row? Meelo's answer provides proof that it must always be so. $\endgroup$
    – Ivo
    Commented Jan 19, 2015 at 12:10
  • 1
    $\begingroup$ @IvoBeckers that's right. My answer was intended as a provably correct answer, but not a proof that it was the only correct answer. In fact, I suspected (wrongly) that there would be some other valid configuration of the knights and knaves. $\endgroup$
    – frodoskywalker
    Commented Jan 19, 2015 at 15:35
5
$\begingroup$

If the statement is true for one person, then everyone to the right of that person has possibly more knaves to his left, and possibly fewer knights to his right, so the statement is true for everyone on the right of that person.

If the statement is false for one person, then everyone to the left of that person has possibly fewer knaves to his left, and possibly more knights to his right, so the statement is true for everyone on the left of that person.

Every person actually makes that statement. So if the statement is true/false for a person, then that person is a knight/knave. So if anyone is a knight, then everyone to the right of that knight is also a knight. If anyone is a knave, then anyone to the left of that knave is also a knave.

For the leftmost person, the statement is false, so he is a knave. If there was only one person, that person would be a knave. If we have more than one person (we have 2014 actually), then the statement is true for the rightmost person, which has at least one knave to his left and no knight to his right. We now assume we have two or more people.

Combining what we know, the row consists of a number of x knaves at the left, and y knights at the right. The last knave has x-1 knaves to his left and y knights to his right, and he is lying, so x-1 <= y. The first knight has x knaves to his left and y-1 knights to his right, so x > y-1. This is equivalent to x ≤ y + 1 and x ≥ y; the number of knaves and knights are either equal, or there is one more knave than knights.

If the number of people n is even, then there are n/2 knaves and n/2 knights. If the number of people n is odd, then there are (n + 1) / 2 knaves and (n - 1) / 2 knights.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 nice. In other words, if we start with one person, she has to be a knave. Why? For a knave "more" means "less than or equal", while for a knight "more" means "more"! Using @Meelo 's reduction technique (eliminating two boundary persons, one of each type, at a time), we will be left with one person. The fact you add is then: For a group of 2n+1 (n≥0) knights and knaves satisfying the puzzle conditions, there must be exactly n+1 knaves. Moreover, all knaves must occupy the first n+1 positions in the row (left to right direction). $\endgroup$
    – ir7
    Commented Jan 19, 2015 at 17:47
2
$\begingroup$

One doesn't need maths to solve this, all you need is logic, imagination and intuition maybe:] It's easier to start from knights, because their statement is true, so we divide 2014 in two, here is a visual:

enter image description here

So, the place marked as "Your are here" is the last position for the knight where his statement is true, and at this point we have 1007 knaves to the left. So the answer is:

1007
Improve this answer
$\endgroup$
3
  • 6
    $\begingroup$ "logic, imagination and intuition maybe" sounds like maths to me. $\endgroup$
    – JiK
    Commented Jan 19, 2015 at 10:53
  • 2
    $\begingroup$ How do you demonstrate that there is no other solution? $\endgroup$
    – gnasher729
    Commented Jan 19, 2015 at 14:48
  • $\begingroup$ Well, we don't need for another solutions if 1007 is correct, because this question lets us assume that there is only one solution;] And yeahh, i can't demonstrate other potential solutions visually because it's too complicated, but mixing knights and knaves isn't a good choice because if i send some knights to the left - they statement may still be true but for knaves who are on the right side would be a different story, their statement would also be true, but that's too bad because they are liars:D $\endgroup$
    – pauliuso
    Commented Jan 19, 2015 at 15:22
1
$\begingroup$

Answer is

1007

Logic -

At any person in the row, the knaves on the left should be > than knights on the right.

So Only FFFFF.....(1007)TTTTT...(1007) combination makes it possible.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.