Морской бой

[Ktina]

На поле для игры в "морской бой" размером 10x10 Ксюша расставляет корабли 1x1,1x2, ..., 1xn. После этого Катенька пытается разместить на этом же поле корабль 1x(n+1). При каком наименьшем n Ксюша сможет помешать Катеньке?

Рассмотреть три случая:

а) Корабли могут соприкасаться.
б) Корабли могут соприкасаться углами, но не сторонами (и не частями сторон).
в) Корабли не могут соприкасаться даже углами.

[hippie]

а) $n=6;$
б) $n=5;$
в) $n=4.$

[Ktina]

hippie в сообщении #678762 писал(а):

а) $n=6;$
б) $n=5;$
в) $n=4.$

У меня в первом тоже шесть.

-- 01.02.2013, 14:00 --

Разобьём всю не всю доску на 16 прямоугольников $1\times 6$, в каждом из них есть хотя бы одна клетка, но всего клеток 15. Противоречие.

-- 01.02.2013, 14:01 --

Это доказывает, что при $n=5$ Катя всегда сможет поставить шестой.

-- 01.02.2013, 14:04 --

Контрпример для $n=6$: можно запихать кораблики так, чтобы оказались целиком заполненными одна вертикаль и одна горизонталь.

-- 01.02.2013, 14:05 --

Тогда седьмому места не останется.

-- 01.02.2013, 14:07 --

hippie, что у нас с пунктами б) и в)?

[hippie]

Расположение кораблей:



-- 01.02.2013, 13:21 --

Доказательства для пунктов (а) и (в). (Для (б) простого доказательства пока нет.)

[Ktina]

(Оффтоп)

Пункт (в) на самом деле даже легче, чем (а).
Просто я на (б) застряла (доказать не смогла), а за (в) даже браться не стала, предположив, что пункты расположены по возрастанию сложности.