Разбиение доски на части

Подсказка 1:

Нам необходимо сделать оценку снизу, то есть предъявить набор доминошек (возможно, просто доказать его существование), которые точно попадут в квадраты разбиения. Подумайте, как можно "ловить" подобные доминошки?

Подсказка 2:

Находить их в явном виде плохо, это просто не сделать (разбиений на домино очень много). Значит, нужно найти некоторые объекты, которые будут их "детектировать", то есть просто говорить, что они точно есть. Подумаем, какие самые тривиальные детекторы могут быть?

Подсказка 3:

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

Подсказка 4:

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

Подсказка 5:

В такие моменты полезно попробовать обобщить идею! Как же будет звучать наше предположение?

Подсказка 6:

Для каждого квадрата с нечётной стороны, который исходит из левого нижнего угла, найдётся доминошка на его границе. Таким образом, мы сможем найти 50 нужных доминошек.

Подсказка 7:

Теперь нужно доказать, что для любого квадрата такая доминошка найдётся. Сделайте это самостоятельно, но скажем следующее: квадраты нечётные, а в доминошке ровно 2 клетки).

Подсказка 8:

Итого, мы нашли 50 требуемых доминошек. Кажется, можно найти больше...

Подсказка 9:

Осознайте, каким образом можно найти ещё 50 доминошек. Итого, есть оценка на 100 доминошек. Может, можно ещё больше?

Подсказка 10:

Спустя несколько попыток Вы, скорее всего, потерпели неудачу. Может, тогда пора переходить к примеру?

Подсказка 11:

Пример за Вами, однако скажем, что он достаточно "однородный"... Успехов!