Задача 67170
|
|
 |
Условие
Фигура «скрипач» бьёт клетку слева по стороне (локтем) и справа вверху по диагонали (смычком), если он правша, и, наоборот, правую клетку по стороне и левую верхнюю по диагонали, если левша (все скрипачи сидят лицом к нам). Посадите как можно больше «скрипачей» в «оркестр» 8×8 клеток, чтобы они не били друг друга. (Вы можете использовать любое количество как правшей, так и левшей.)Решение
Разместить 32 скрипача несложно: например, можно заполнить четыре столбца через один (неважно, правшами или левшами). Однако можно разместить и больше. Возможный пример с 34 скрипачами приведён на рисунке.Замечания
Можно доказать, что более 34 скрипачей разместить не удастся. В самом деле, рассмотрим вертикальную полосу шириной в две клетки. Всякий скрипач, стоящий в этой полосе и при этом не в верхней строке, бьёт одну какую-то клетку в этой же полосе. Мы можем поставить эту пустую клетку в соответствие данному скрипачу. Если при этом оказалось, что два скрипача бьют одну и ту же пустую клетку (возможны два аналогичных друг другу варианта этого, один из них показан на рисунке), то клетка, расположенная под дважды побитой, тоже обязана быть пустой, поэтому её можно поставить в соответствие одному из двух скрипачей, допустим, нижнему. Если же эту клетку бьёт смычком скрипач, стоящий ещё ниже, поставим ему в соответствие соседнюю с ним по горизонтали клетку (она заведомо пустая), и так далее.Итак, в полосе может быть максимум 9 скрипачей — двое в верхних клетках и ещё семеро в оставшихся 14 клетках, потому что каждому скрипачу там соответствует пустая клетка, то есть занятых клеток не более половины.
Однако две полосы с девятью скрипачами не могут соседствовать, иначе в верхней строке четыре скрипача сидели бы подряд. Поэтому таких полос не более двух, в оставшихся двух полосах максимум по 8 скрипачей, так что всего в оркестре не более чем 9+9+8+8=34 музыканта.
