Each of 10 men is either a knight (always telling the truth) or a liar (who always lies). Each of them thinks of an integer number. The first man told: "My number is greater than 1", the second told: "My number is greater than 2", ..., the tenth told: "My number is greater than 10". After that, talking in a different order, they told ten sentences: "My number is less than 1", "My number is less than 2", ..., "My number is less than 10" (each man told exactly one of those phrases). Determine the maximal possible number of knights among the 10 men.
(O. Podlipsky)
Solution
Докажем, что ни один из рыцарей не мог сказать ни одной из фраз «Моё число больше 9» и «Моё число больше 10». В самом деле, если бы это было возможно, то задуманное рыцарем целое число было бы не меньше 10. Но тогда он не мог сказать ни одной из фраз «Моё число меньше 1», «Моё число меньше 2», ..., «Моё число меньше 10». Значит, рыцарей было не больше восьми.
Покажем, что рыцарей могло быть 8. Пусть первый рыцарь загадал число 2, второй — 3, ..., восьмой — 9, а лжецы загадали числа 5 и 6. Тогда -ый рыцарь мог сказать фразы «Моё число больше » и «Моё число меньше », а лжецы могли сказать фразы: один — «Моё число больше 9» и «Моё число меньше 1», а другой — «Моё число больше 10» и «Моё число меньше 2».
Замечание. Приведённый выше пример перестаёт быть верным, если лжецы задумывают числа вне отрезка , так как тогда некоторые их высказывания становятся верными.
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.