Разделы 
Дополнительно
Задача по математике - 3181
2019-05-27 
В квадрате клетчатой бумаги $10 \times 10$ нужно расставить один корабль $1 \times 4$, два - $1 \times 3$, три - $1 \times 2$ и четыре - $1 \times 1$. Корабли не должны иметь общих точек (даже вершин) друг с другом, но могут прилегать к границам квадрата. Докажите, что
а) если расставлять их в указанном выше порядке (начиная с больших), то этот процесс всегда удается довести до конца, даже если в каждый момент заботиться только об очередном корабле, не думая о будущих;
б) если расставлять их в обратном порядке (начиная с малых), то может возникнуть ситуация, когда очередной корабль поставить нельзя (приведите пример).
Решение:
В задаче «б» легко привести пример «непродолжаемой» расстановки девяти кораблей (рис. а).
В задаче «а» есть «подводный камень»: казалось бы достаточно доказать, что найдется место последнему одноклеточному кораблю. Но, на самом деле, нужно доказать, что в процессе расстановки найдется место каждому очередному кораблю.
Корабль $1 \times 4$ поставить можно. Докажем, что очередной корабль $1 \times 3$ поместится. Для этого отметим 8 вспомогательных кораблей $1 \times 3$, параллельных друг другу, с интервалом две клетки (рис. б). Каждый из поставленных кораблей может задеть (пересечь или коснуться) не больше двух отмеченных, поэтому останется незадетым отмеченный корабль, на место которого можно поставить очередной корабль $1 \times 3$.
Пусть уже расставлены следующие корабли: $1 \times 4$, два $1 \times 3$ и меньше трех $1 \times 2$. Докажем, что еще один корабль $1 \times 2$ поместится. Для этого отметим 12 вспомогательных кораблей $1 \times 2$, параллельных друг другу, с интервалом две клетки (рис. в). Каждый поставленный корабль может задеть не больше двух отмеченных, поэтому останется незадетым отмеченный корабль.
Аналогично поместится очередной одноклеточный корабль. Отметим 16 вспомогательных кораблей $1 \times 1$ с интервалом две клетки (рис. г). Поставленные корабли задевают не больше 15 отмеченных.
В квадрате клетчатой бумаги $10 \times 10$ нужно расставить один корабль $1 \times 4$, два - $1 \times 3$, три - $1 \times 2$ и четыре - $1 \times 1$. Корабли не должны иметь общих точек (даже вершин) друг с другом, но могут прилегать к границам квадрата. Докажите, что
а) если расставлять их в указанном выше порядке (начиная с больших), то этот процесс всегда удается довести до конца, даже если в каждый момент заботиться только об очередном корабле, не думая о будущих;
б) если расставлять их в обратном порядке (начиная с малых), то может возникнуть ситуация, когда очередной корабль поставить нельзя (приведите пример).
Решение:
В задаче «б» легко привести пример «непродолжаемой» расстановки девяти кораблей (рис. а).
В задаче «а» есть «подводный камень»: казалось бы достаточно доказать, что найдется место последнему одноклеточному кораблю. Но, на самом деле, нужно доказать, что в процессе расстановки найдется место каждому очередному кораблю.
Корабль $1 \times 4$ поставить можно. Докажем, что очередной корабль $1 \times 3$ поместится. Для этого отметим 8 вспомогательных кораблей $1 \times 3$, параллельных друг другу, с интервалом две клетки (рис. б). Каждый из поставленных кораблей может задеть (пересечь или коснуться) не больше двух отмеченных, поэтому останется незадетым отмеченный корабль, на место которого можно поставить очередной корабль $1 \times 3$.
Пусть уже расставлены следующие корабли: $1 \times 4$, два $1 \times 3$ и меньше трех $1 \times 2$. Докажем, что еще один корабль $1 \times 2$ поместится. Для этого отметим 12 вспомогательных кораблей $1 \times 2$, параллельных друг другу, с интервалом две клетки (рис. в). Каждый поставленный корабль может задеть не больше двух отмеченных, поэтому останется незадетым отмеченный корабль.
Аналогично поместится очередной одноклеточный корабль. Отметим 16 вспомогательных кораблей $1 \times 1$ с интервалом две клетки (рис. г). Поставленные корабли задевают не больше 15 отмеченных.
