Question

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

Answer 1

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

Answer 2

Шахматная доска состоит из 64 клеток, каждая клетка имеет площадь 1. Нам нужно вырезать 8 клеток, что означает, что общая площадь вырезанных клеток равна 8. Для того чтобы найти максимальную площадь прямоугольника, который можно вырезать из оставшейся части доски, мы должны использовать такую комбинацию клеток, которая максимизирует площадь. Так как мы не можем сложить две клетки друг на друга, площадь прямоугольника будет равна произведению длины и ширины прямоугольника. Таким образом, нам нужно найти такие числа x и y, где x*y = 8 и x, y >= 1. Мы можем представить это в виде таблицы: 1 x 8 2 x 4 4 x 2 8 x 1 Самый большой прямоугольник будет иметь площадь 4 * 2 = 8.