** поле 10Х10 для игры в морской бой необходимо расставить один корабль 1Х4, два корабля...

Question

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

Answer 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 свободных клетках.