Всероссийская олимпиада школьников по математике, 9 класс, 2016 год
дата проведения: 10 октября 2016 - 16 октября 2016
Задача 6.
На шахматной доске стоял 21 король. Каждый из королей находился под боем хотя бы одного из остальных. После того как несколько королей убрали, никакие два из оставшихся королей друг друга не бьют. Какое наибольшее число королей могло остаться?
- Приведите пример исходной расстановки и отметьте убранных королей.
- Докажите, что большее число королей остаться не могло.
Ответ на Задачу 6.
Ответ: 16 королей могло остаться.
Решение:
Заметим, что каждый король, снятый с доски, мог бить не более 4 из оставшихся (иначе и некоторые из оставшихся били бы друг друга). Поэтому число оставшихся королей не может превосходить число снятых более чем в 4 раза, то есть не может быть больше 16. Пример приведён на рисунке: серым обозначены короли, которых необходимо убрать.
