Competition problem — Combinatorics

Library / /21 of 61

Combinatorics Difficulty 5.3 AIME, harder Prove it Ukraine

2012 people stand in a line. Each of them is either a knight (and always tells truth) or a knave (and always lies). Each of the people announced: «There are more knaves on my left than knights on my right». How many knaves are in the line?

Solution

Нехай у шерензі стоять $b$ брехунів та $r$ лицарів. Оскільки найлівіший з лицарів сказав правду, маємо $b > r - 1$ . Оскільки найправіший з брехунів збрехав, то маємо $b - 1 \le r$ . Отже, $r = b$ або $r = b - 1$ . Другий випадок неможливий, оскільки загальна кількість людей парна. Тому $r = b = 1006$ .

*Відповідь:* 1006 брехунів.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.