|
|
 |
Условие
На доске n×n расставлено n – 1 фишек так, что никакие две из них не стоят на соседних (по стороне) клетках.
Докажите, что одну из них можно передвинуть на соседнюю клетку так, чтобы снова никакие две фишки не стояли на соседних клетках.
Подсказка
Предположите противное и докажите, что число пустых меньше числа пустых столбцов.
Решение
Предположим противное. Ясно, что в таблице есть пустые столбцы. Заметим, что пустой столбец не может быть крайним. Действительно, если, скажем, правый столбец пуст, то из самого правого непустого столбца можно сдвинуть фишку вправо. Аналогично доказывается, что не может быть двух пустых столбцов подряд. Итак, слева от каждого пустого столбца есть фишка. Её нельзя сдвинуть вправо, значит, в той же строке справа через одну от неё стоит фишка. Таким образом, каждая "левая" фишка находится в строке, где есть другие фишки.
Пусть всего пустых столбцов k. Тогда соответствующих "левых" фишек не меньше k. Следовательно, все фишки занимают не более n – 1 – k строк, и пустых строк не меньше k + 1, то есть больше чем пустых столбцов.
Но аналогично можно доказать, что пустых столбцов больше, чем пустых строк. Противоречие.
Замечания
Ср. с задачей 109441.
Источники и прецеденты использования
| web-сайт | |
| задача |
