Задача № 2077598, 9, 10 классы3 / 5

Олимпиадная задача по комбинаторной геометрии для 8-10 классов от Игнатьева К. А.

В квадрате клетчатой бумаги 10×10 нужно расставить один корабль 1×4, два – 1×3, три – 1×2 и четыре – 1×1. Корабли не должны иметь общих точек (даже вершин) друг с другом, но могут прилегать к границам квадрата. Докажите, что

а) если расставлять их в указанном выше порядке (начиная с больших), то этот процесс всегда удается довести до конца, даже если в каждый момент заботиться только об очередном корабле, не думая о будущих;

б) если расставлять их в обратном порядке (начиная с малых), то может возникнуть ситуация, когда очередной корабль поставить нельзя.

Разобрать решение

б) Пример "непродолжаемой" расстановки девяти кораблей см. на рисунке.

а) Корабль 1×4 поставить можно. Докажем, что очередной корабль 1×3 поместится. Для этого отметим 8 вспомогательных кораблей 1×3, параллельных друг другу, с интервалом две клетки (рис. слева). Каждый из поставленных кораблей может задеть (пересечь или коснуться) не больше двух отмеченных, поэтому останется незадетым отмеченный корабль, на место которого можно поставить очередной корабль 1×3.

Пусть уже расставлены следующие корабли: 1×4, два 1×3 и меньше трёх 1×2. Докажем, что еще один корабль 1×2 поместится. Для этого отметим 12 вспомогательных кораблей 1×2, параллельных друг другу, с интервалом две клетки (рис. в центре). Каждый поставленный корабль может задеть не больше двух отмеченных, поэтому останется незадетым отмеченный корабль.

Аналогично поместится очередной одноклеточный корабль. Отметим 16 вспомогательных кораблей 1×1 с интервалом две клетки (рис. справа). Поставленные корабли задевают не больше 15 отмеченных.