Question

Какое наименьшее количество клеток в таблице 194х194 надо закрасить, чтобы в любом прямоугольнике, стороны которого равны 1 и 6, была хотя бы одна закрашенная клетка

Answer 1

Надо закрасит минимум 4 клетки

Answer 2

Ответ:

надо как миниму

4 клетки закрасить я так думаю

Answer 3

Для решения этой задачи мы можем воспользоваться методом отрицания: мы будем искать минимальное количество закрашенных клеток так, чтобы в "плохом" случае, когда все внутренние клетки прямоугольников размером 1x6 не закрашены, прямоугольники все равно не содержали закрашенной клетки.

Обозначим каждую клетку таблицы как A[i, j], где i - номер строки, j - номер столбца. Пусть A[1,1] - незакрашенная клетка.

Рассмотрим прямоугольник со сторонами 1 и 6, который должен содержать хотя бы одну закрашенную клетку. Пусть закрашена клетка A[p,q], где p - номер строки, q - номер столбца.

Так как каждый прямоугольник имеет сторону 1, то он состоит из одного из двух вариантов:

1) Прямоугольник имеет вертикальную сторону 1. Тогда на прямой линии, на которой находится клетка A[p,q], должны быть закрашены все клетки с номерами столбцов от q-1 до q+1, чтобы не было "плохого" случая для этого прямоугольника.

2) Прямоугольник имеет горизонтальную сторону 1. В этом случае на строке, на которой находится клетка A[p,q], должны быть закрашены все клетки с номерами строк от p-1 до p+1, чтобы не было "плохого" случая для этого прямоугольника.

Таким образом, нам нужно закрасить несколько клеток по следующему правилу:

- Закрасить все клетки с номерами строк от p-1 до p+1 и номерами столбцов от q-1 до q+1.

- Затем закрасить все клетки с номерами строк от p-1 до p+1 и номерами столбцов от q+2 до q+7 (так как стороны прямоугольника равны 1 и 6).

Таким образом, имеем закрашенные клетки со следующими номерами строк и столбцов: p-1, p, p+1, q-1, q, q+1, q+2, q+3, q+4, q+5, q+6.

Имеем закрашенные клетки в количестве 11.

Ответ: наименьшее количество клеток, которое нужно закрасить, равно 11.

Answer 4

Чтобы решить эту задачу, нужно рассмотреть несколько случаев.

Возможно, что самый маленький прямоугольник с со сторонами 1 и 6 займет всю таблицу 194x194. В таком случае, нам надо закрасить все клетки, то есть 194 * 194 = 37636 клеток.

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

Таким образом, чтобы гарантировать наличие хотя бы одной закрашенной клетки в любом прямоугольнике со сторонами 1 и 6, нужно закрасить 194 клетки.

Итак, наименьшее количество клеток, которое нужно закрасить, равно 194.