№4
из шахматной доски вырезали 8 клеток. для какого наибольшего числа из оставшейся части можно вырезать прямоугольник площадью этого числа? ​

1) Искомое число > 8. Контрпример приведен на рис.1

2) Проверим, возможно ли это для числа 8.

Попробуем найти такую расстановку вырезанных клеток, чтобы из остатка доски нельзя было вырезать прямоугольник площади 8.

Заметим, что в каждой строке и столбце должно быть ровно по одной вырезанной клетке[1]. И правда, если в каком-то столбце/строке будет более одной дыры, то какая-то строка/столбец не будет содержать вырезов, то есть её/его можно будет взять за прямоугольник 1*8/8*1 площади 8.

Рассмотрим столбец А. Пусть вырезана клетка Аk, 2≤k≤7. Тогда, с учетом [1] и того, что прямоугольник 4*2 имеет площадь 8, единственным решением для k-1ой строки будет вырезать клетку Е3 , тем самым не давая возможности разместить в строках k и k-1 указанный прямоугольник. Для строки k+1 придется вырезать клетку Е5, тем самым не давая возможности разместить в строках k и k+1 указанный прямоугольник. Но тогда мы получаем, что два выреза находятся в одном столбце - противоречие с [1].

Значит вырез или в клетке А1, или в клетке А8. Не нарушая общности, допустим, что это А1.

Аналогично для столбца H получаем вырез в H8.

Для столбцов А и B, учитывая [1] и то, что прямоугольник 2*4 имеет площадь 8, необходим вырез в B5 (иначе останется прямоугольник A2A5B5B2). Аналогично для столбцов G и H вырез в G4, для строк 1 и 2 вырез E2, для строк 7 и 8 вырез D7.

Теперь осталось два выреза и 4 свободных клетки. 2 варианта: С3 и F6 или С6 и F3.

Нетрудно убедиться, что, вне зависимости от выбора, из центра доски мы можем вырезать прямоугольник 2*4 или 4*2.

Для выреза А8 рассуждения абсолютно аналогичны.

А значит в любом случае для числа 8 условие выполнимо.

Значит максимальное число - 8