Клетки в квадрате

[Ktina]

В квадрате $100\times100$ отмечены $k$ клеток таким образом, что при любом разрезании квадрата по линиям сетки на два прямоугольника один из прямоугольников содержит хотя бы 100 отмеченных клеток.

При каком наименьшем $k$ это возможно?

[TOTAL]

133

[Ktina]

TOTAL в сообщении #642559 писал(а):

133

(Оффтоп)

Ответ верный (во всяком случае, у меня такой же). У меня есть очень красивое решение (в смысле, доказательство того, что меньше нельзя), но торопиться не стану, дам всем возможность попытаться.

[_Ivana]

Чтобы не смущать продолжающих решать самостоятельно, свое решение оформляю в оффтоп

(Оффтоп)

диагонально симметричный крест, сумма любых трех ветвей плюс центральная клетка больше или равна 100, откуда минимальная длина любой ветви креста равна 33 (крест получается правильным), соответственно всего клеток в кресте 33*4+1=133. Размер и квадратность исходного квадрата (поля) значения не имеет, пока в него помещается этот крест. Если минимальное число клеток в любом прямоугольнике задать другим, то крест соответственно пересчитается и может оказаться неправильным, оставаясь диагонально симметричным

[TOTAL]

_Ivana в сообщении #642762 писал(а):

Чтобы не смущать продолжающих решать самостоятельно, свое решение оформляю в оффтоп

Тем более что это не решение, а пример со 133 клетками.

[Ktina]

Основная идея решения:

(Оффтоп)

Если закрашено не более 132 клеток, то хотя бы на одной горизонтали и хотя бы на одной вертикали должно быть не менее 68 клеток (в силу соображений непрерывности). Но тогда всего будет не менее 135 -- противоречие.

[TOTAL]

Ktina в сообщении #642950 писал(а):

(в силу соображений непрерывности)

Если двигаться по доске слева направо непрерывно соображая, то сначала перед тобой будет по крайней мере 100 отмеченных, а потом позади тебя.

[Ktina]

TOTAL в сообщении #642967 писал(а):

Ktina в сообщении #642950 писал(а):

(в силу соображений непрерывности)

Если двигаться по доске слева направо непрерывно соображая, то сначала перед тобой будет по крайней мере 100 отмеченных, а потом позади тебя.

Верно.
Тут одно маленькое исключение имеется, но оно подтверждает правило.