|
|
 |
Условие
В квадрате клетчатой бумаги 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 отмеченных.
Замечания
баллы: 5 + 2
Источники и прецеденты использования
| олимпиада | |
| Название | Московская математическая олимпиада |
| год | |
| Номер | 57 |
| Год | 1994 |
| вариант | |
| Класс | 9 |
| задача | |
| Номер | 6 |
| журнал | |
| Название | "Квант" |
| год | |
| Год | 1994 |
| выпуск | |
| Номер | 4 |
| Задача | |
| Номер | М1447 |
| олимпиада | |
| Название | Турнир городов |
| Турнир | |
| Номер | 15 |
| Дата | 1993/1994 |
| вариант | |
| Вариант | весенний тур, основной вариант, 8-9 класс |
| Задача | |
| Номер | 7 |
