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