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

Доказать, что если расставлять корабли в указанном порядке начиная с больших, то каждому кораблю найдётся место как бы их ни ставили на любое свободное место.

Нужно подсчитать суммарную площадь кораблей с окантовкой в один ряд.

у четырехпалубного 1x4 - 3x6 - 18

у двух трехпалубных 1x3 - 3x5 - 2*15=30

у трёх двухпалубных 1x2 - 3x4 - 3*12=36

у четырёх однопалубных 1x1 - 3x3 - 4*9 = 36

суммарная площадь больше ста, значит существуют нерасстовляемые в любом порядке варианты. Но мы начинаем с большого корабля. после него останется 100-18 = 82 свободных клетки.

после трехппалубных 82-30 = 52 свободных клетки

после двухпалубныx 52-36 = 16 свободных клеток.

Очевидно что можно разместить четыре квадрата 1x1 на любом сочетании 16 свободных клетках.