Question

Как в квадрате 10x10 закрасить минимум клеток что бы где не нарисовали прямоугольник 2х5 или 5х2 в этом квадрате в была хоть одна закрашенная клетка пж быстро)

Answer 1

Исходя из того, что в строках закрашено обязательно либо 3 либо 4, то количество закрашенных будет от 30 до 40 теперь надо набрать х столбцов по 7 и 10-х по 1 чтобы попасть в этот диапазон

сделаем простым перебором значений там мало

2х7+8х1=22 не подходит

3*7+7*1=28

4*7+6*1=34

5*7+5*1=40

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

ОТВЕТ 34

Answer 2

Для того чтобы в квадрате 10x10 закрасить минимальное количество клеток, при условии, что не должно быть прямоугольника размером 2x5 или 5x2, можно воспользоваться следующей стратегией:

1. Закрасьте первую клетку в верхнем левом углу квадрата.

2. Закрасьте клетку справа от первой клетки и клетку ниже первой клетки.

3. Закрасьте клетку, находящуюся на третьей строке, втором столбце.

4. Повторяйте следующий шаблон закрашивания для оставшихся строк и столбцов:

   • Закрасьте клетку справа от предыдущей закрашенной клетки.
   • Закрасьте клетку ниже предыдущей закрашенной клетки.
   • Перейдите к следующей строке и повторите шаги 1 и 2, начиная с первой закрашенной клетки.

5. Продолжайте повторять шаг 4 до тех пор, пока не закрасите все клетки квадрата или пока не достигнете строки, которая уже содержит две закрашенные клетки.

Следуя этой стратегии, вы закрасите минимальное количество клеток, не образуя прямоугольника размером 2x5 или 5x2.