Обязательно ли останется место для трёхпалубного корабля?

[gipokrat]

Для игры в «Морской бой» на поле $9\times 9$ клеток расставили 18 двухпалубных кораблей. Обязательно ли останется место для трёхпалубного корабля?

("Двухпалубный" корабль – прямоугольник $1\times 2$, а "трёхпалубный" – $1\times 3$. Корабли могут соприкасаться, но накладываться друг на друга не должны.)

[Gagarin1968]

gipokrat в сообщении #1727274 писал(а):

Обязательно ли останется место для трёхпалубного корабля?

Нет, не обязательно.
Я нашел поистине чудесную расстановку, но поля для неё здесь слишком узки!

(Поистине чудесная расстановка)

Делим всё поле на 9 квадратов $3\times 3$ и заполняем их одинаково. Вот так:

$$\begin{pmatrix} X & X & -\\ -&- & X\\ - & - & X \end{pmatrix}$$

Места для трёхпалубного не остаётся.

А вообще-то это, сдаётся мне, задача из глухих застойных времён класса эдак для 5-го.

[gipokrat]

Gagarin1968 в сообщении #1727276 писал(а):

...но поля для неё здесь слишком узки!

Поля, кажется, всё-таки не такие уж узкие. Полная расстановка:

$$ \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline A&A&\cdot&B&B&\cdot&C&C&\cdot\\ \hline \cdot&\cdot&D&\cdot&\cdot&E&\cdot&\cdot&F\\ \hline \cdot&\cdot&D&\cdot&\cdot&E&\cdot&\cdot&F\\ \hline G&G&\cdot&H&H&\cdot&I&I&\cdot\\ \hline \cdot&\cdot&J&\cdot&\cdot&K&\cdot&\cdot&L\\ \hline \cdot&\cdot&J&\cdot&\cdot&K&\cdot&\cdot&L\\ \hline M&M&\cdot&N&N&\cdot&O&O&\cdot\\ \hline \cdot&\cdot&P&\cdot&\cdot&Q&\cdot&\cdot&R\\ \hline \cdot&\cdot&P&\cdot&\cdot&Q&\cdot&\cdot&R\\ \hline \end{array} $$

Одинаковые буквы обозначают клетки одного двухпалубного корабля.
Всего здесь $18$ кораблей $1\times2$. В каждой строке и в каждом столбце нет трёх подряд свободных клеток, поэтому трёхпалубный корабль поставить нельзя.