Ukrainian Mathematical Olympiad

Question

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?

Accepted Answer

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