Здравствуйте, Apapa, Вы писали:

A>Привет, nikholas!

N>>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто.
N>>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?

A>Необходимо, чтобы было возможно так разместить N-1 квадрат, чтобы каждый имел свое "собственное поле", не занятое другими, при этом N квадратов так разместить не должно получиться.

A>Рассмотрим центр квадрата. Поле центров имеет размер 9х9.

Почему? Почему не 10х10?

A>Рассмотрим центр квадрата (*) и места для центров квадратов, которые могут с ним пересекаться (.):
A>...
A>.*.
A>...

A>Чтобы квадрат имел собственное поле надо, чтобы три точки в любом углу не были заняты центрами других квадратов.
A>Например,
A>оо.
A>о*.
A>...
A>где о — пустая клетка

A>Наша задача расставить как можно больше центров так, чтобы у каждого был рядом пустой угол. Для этого надо как можно чаще пересекать эти углы. Оптимальная расстановка следующая:
A>*о*
A>ооо
A>*о*

A>Итого 4/9 от всех точек: максимум 81*4/9 = 36 квадратов с собственным полем.

A>Ответ: 37 квадратов.

Имхо, это наиболее плотная упаковка для поля 9х9. Для поля 10х10 (экий неудобный размер ),
вот таких конструкций

*о*
ооо
*о*

помещается всего 4. Если их установить 9, останутся незаполняемые зазоры.
А для 4 (16 квадратов), остаётся довольно много свободного места, которое, имхо, более чем 20 квадратами не закрыть.

Остаётся вариант с несимметричной структурой (теоретический максимум 100*4/9 = 44 квадрата).

PS. Блин, Pushkin'а съели.

Здравствуйте, Apapa, Вы писали:

...

Оптимальная расстановка следующая:
A>*о*
A>ооо
A>*о*

A>Итого 4/9 от всех точек: максимум 81*4/9 = 36 квадратов с собственным полем.

A>Ответ: 37 квадратов.

А как же быть с этим

Автор: nikholas
Дата: 13.04.03

решением?

Налицо недооценка граничных условий!

С учетом их я, если не ошибаюсь, 41(42) насчитал.

Привет, MichaelP!

MP>Здравствуйте, Apapa, Вы писали:
MP>...
MP>Оптимальная расстановка следующая:
A>*о*
A>ооо
A>*о*
A>Итого 4/9 от всех точек: максимум 81*4/9 = 36 квадратов с собственным полем.
A>Ответ: 37 квадратов.

MP>А как же быть с этим

Автор: nikholas
Дата: 13.04.03

решением?
MP>Налицо недооценка граничных условий!
MP>С учетом их я, если не ошибаюсь, 41(42) насчитал.

Я тоже подумал о краях... когда нажал отправить...

MP>А как же быть с этим

Автор: nikholas
Дата: 13.04.03

решением?

MP>Налицо недооценка граничных условий!

MP>С учетом их я, если не ошибаюсь, 41(42) насчитал.

Соврал — там меньше получается...

N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто.
N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?

Назовем занимающей клеткой квадрата такую клетку, котороую занимает только этот квадрат и никакой другой

Каждая угловая клетка поля покрыта => покрыты 3 прилегающие тем же самым квадратом => они не могут быть занимающими ни для какого другого квадрата
Если крайняя клетка поля покрыта некоторым квадратом, то также покрыта и 2 клетка от края тем же самым квадратом.
Рассмотрим некоторую сторону с клетками 1 — 10. клетки 1,2,9,10 покрыты угловыми квадратами. Клетка 4 покрыта некоторым квадратом =>тем же самым квадратом покрыта либо 3-я либо 5-я клетка, аналогично для 7-ой клетки, итого остается 2 незанятых клетки, которые могут быть занимающими не более чем для 2 квадратов
Итого на наружном периметре поля шириной 2 занимающие клетки могнут иметь не более чем 1*4 (угловые) + 4 * 4(по сторонам) = 20 квадратов.
Остается незанятым квадрат 6х6 в центре поля. разоб'ём его на 4 поля 3х3. Центральная клетка каждого такого поля занята каким-либо квадратом => 3 другие клетки этого поля также заняты тем же самым квадратом и не могут быть занимающими. Из оставшихся 5 клеток:


клетка 2 занята => занята либо 1 либо 3 тем же квадратом => на поле 3х3 занимающие клетки могут иметь не более 1 + 4 = 5 квадратов.
Итого: на поле 10х10 занимающие клетки могут иметь неболее чем 20 + 5*4 = 40 квадратов

На самом деле правильный ответ 38+1, доказательство я приведу в понедельник, если конечно никто не сделает это раньше
А вот вариант расположения 38 квадратов:



Всем удачи и спокойных снов