Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто.
Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Здравствуйте, nikholas, Вы писали:
N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто. N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Начинаем аукцион! Начальная цифра 50 (покрыть двумя слоями по 25 в каждом), кто меньше?
ЗЫ
снимать можно любой квадрат, или только тот, который не накрыт никаким другим?
Привет, Дмитро!
Д>Здравствуйте, nikholas, Вы писали:
N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто. N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Д>Начинаем аукцион! Начальная цифра 50 (покрыть двумя слоями по 25 в каждом), кто меньше?
Задача, НЕ в том, чтобы разместить N квадратов так, чтобы можно было снять один (было бы достаточно 26 квадратов), а в том, чтобы найти такое N, что как бы мы не разместили N квадратов, мы всегда найдем один, который можно снять без потери покрытия.
Хотя в любом случае аукцион со 100 начать можно было бы!
Как бы мы не разместили 100 квадратов всегда будет хотя бы один, который можно снять.
Д>ЗЫ Д>снимать можно любой квадрат, или только тот, который не накрыт никаким другим?
Здравствуйте, Apapa, Вы писали:
A>Привет, Дмитро!
Д>Здравствуйте, nikholas, Вы писали:
N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто. N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Д>Начинаем аукцион! Начальная цифра 50 (покрыть двумя слоями по 25 в каждом), кто меньше?
A>Задача, НЕ в том, чтобы разместить N квадратов так, чтобы можно было снять один (было бы достаточно 26 квадратов), а в том, чтобы найти такое N, что как бы мы не разместили N квадратов, мы всегда найдем один, который можно снять без потери покрытия.
Сорри. Но я все равно не понял, что надо найти. Во-первых, всегда можно сколь угодно большое число квадратов разместить так, чтобы они не покрывали поле вовсе. Во-вторых, если можно N квадратами покрыть все поле так, чтобы можно было снять один и поле при этом осталось бы открытым, то, очевидно, что это поле можно покрыть (N-1) квадратами. Если 25 -- это минимум количества квадратов, необходимых для покрытия (без того, чтобы можно было один снять), то чем 26 не решение?
A>Хотя в любом случае аукцион со 100 начать можно было бы! A>Как бы мы не разместили 100 квадратов всегда будет хотя бы один, который можно снять.
А почему 100?
25 (5x5) квадратов нужно для того, чтобы заполнить полностью все поле квадратами 2x2. Вторые 25 необходимы для того, чтобы покрыть это поле вторым слоем квадратов. При этом, какой бы квадрат мы не вытянули (из первого или второго слоя) все равно его площадь покрывается квадратом из другого слоя. Если же вытягивается не любой, а какой-нибудь (который, даже если он и один, но все равно существует), то, действительно, достаточно 26. 25 покрывают все, а один может находиться где-угодно и нужен только для того, чтобы его можно было снять.
... Во-вторых, если можно N квадратами покрыть все поле так, чтобы можно было снять один и поле при этом осталось бы покрытым, то, очевидно, что это поле можно покрыть (N-1) квадратами. ...
Здравствуйте, nikholas, Вы писали:
N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто. N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Экое запутанное условие. С первой рюмки и не разобрать.
Для упрощения, введём, в добавок к "мы", ещё одного действующего лица — Злодея.
Именно ему и поручим накрывать поле квадратами с уcловием полного покрытия.
Тогда задача сводится к тому, сколько квадратов 2х2 надо выдать Злодею, чтобы
при всём его противодействии, мы могли хотя бы один квадрат в последствии убрать.
Тогда очевидно, что 26 квадратов недостаточно.
Злодей нам может помешать так:
покрыв всё поле 25 квадратами, он одно поле (не угловое) открывает, и вновь закрывает его оставшимися двумя квадратами
Всего таких "дырок" на поле Злодей может найти 10 — два ряда по пять.
Поэтому и ответ: 25 + 10 + 1 = 36 квадратов.
PS. Сам я человек страшно добрый, поэтому трудно предугадать всё возможное коварство Злодея, так что ответ может быть и не такой.
В борьбе бобра с ослом всегда побеждает бобро.
Re[2]: Покрытие
От:
Аноним
Дата:
12.04.03 14:30
Оценка:
Здравствуйте, mrhru, Вы писали:
M>Поэтому и ответ: 25 + 10 + 1 = 36 квадратов.
M>PS. Сам я человек страшно добрый, поэтому трудно предугадать всё возможное коварство Злодея, так что ответ может быть и не такой.
Ну вот, хоть кто-то заинтересовался
Ответ, не побоюсь этого слова, неверный, хотя и близкий
ЗЫ А коварство злодея может быть поистине безгранично
Поле N x M, квадрат n x m (такой специальный квадрат... n на m ).
Задача сводится к отысканию такого покрытия, чтобы
а) Каждый "квадрат" покрывал хотябы одну клетку поля один.
б) Каждый "квадрат" покрывал как можно меньше клеток.
То есть надо максимизировать количество уложенных квадратов (2), без избыточности (1).
Выделими у "квадрата" одну клетку, назовем ее "занимающая" (а все остальные "покрывающими"). Занимающая клетка в итоговом покрытии в одиночестве занимает клетку поля (то есть ни под, ни над ней нет других квадратов).
Можно показать :), что для эффективного покрытия в этом случае следует выбирать занимающими угловые клетки "квадрата".
Таким образом у нас есть четыре типа "квадрата" (соответственно с занимающими по четырем углам), которые мы будем укладывать. Укладывать будем по следующему принципу:
1. занимающая следующего укладываемого "квадрата" должна занимать самую верхнюю самую правую пустую клетку поля
2. укладываемый "квадрат" должен занимать как можно меньше клеток, не забывая при этом, что укладываемый "квадрат" не может покрывать занимающих клеток уже уложенных.
2. если до левого или нижнего края перед укладкой остается n или m клеток поля (соответственно) или меньше, то укладываемый "квадрат" должен занять их всех (а иначе они остануться не занятыми).
После этого несложно установить, что такое покрытие обеспечивается:
// Cn - количество кластеров :), т.е. сдвоенных "квадратов"
// An - дополнительный "квадрат", если есть место
// div - целочисленное деление.
Cn = N div (n+1);
An = (N - (Cn * (n+1))) div n;
Cm = M div (m+1);
Am = (M - (Cm * (m+1))) div m;
K = (Cn * 2 + An) * (Cm * 2 + Am);
Итого, для случая 10x10, 2x2, имеем: K = 36. Добавление любого квадрата приведет к закрытию уже закрытых клеток, удаление любого из этих приведет к открытию дырки в покрытии.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, mrhru, Вы писали:
M>Поэтому и ответ: 25 + 10 + 1 = 36 квадратов.
M>PS. Сам я человек страшно добрый, поэтому трудно предугадать всё возможное коварство Злодея, так что ответ может быть и не такой.
А>Ну вот, хоть кто-то заинтересовался
А>Ответ, не побоюсь этого слова, неверный, хотя и близкий
А>ЗЫ А коварство злодея может быть поистине безгранично
Здравствуйте, nikholas, Вы писали:
N>Но не доказано, что не существует покрытия из большего кол-ва с тем же свойством
Это следует из того, что мы при добавлении всегда пытались покрыть наименьшую незалятую площадь.
N>PS да и насчет угловой клетки ты тоже не прав — покрой поле 5х3 квадратами 3х3 ...
Мой расчет дал K=2, то есть ответ 3. Эксперимент :) также не выявил ничего необычного.
P.S.
Мы правильно понимаем, что каждый из "квадратов" полностью лежит в поле?
Если нет, то количество дополнительных "квадратов" расчитываем как:
An = если (N - (Cn * (n+1))) > 0, то 1, иначе 0
Am = если (M - (Cm * (m+1))) > 0, то 1, иначе 0
Что дает в результате K=49, а ответ 50.
А иначе как я ни вертел 3x3 @ 5x3, а третий — лишний
Здравствуйте, Frostbitten, Вы писали:
F>Здравствуйте, nikholas, Вы писали:
N>Но не доказано, что не существует покрытия из большего кол-ва с тем же свойством F>Это следует из того, что мы при добавлении всегда пытались покрыть наименьшую незалятую площадь.
Да только видимо не особо то у нас это и получалось
Вот пример покрытия 37 квадратами так, что ни один убрать нельзя
Штрихами помечены "занимающие" клетки
(И это еще не предел!!!)
N>PS да и насчет угловой клетки ты тоже не прав — покрой поле 5х3 квадратами 3х3 ... F>Мой расчет дал K=2, то есть ответ 3. Эксперимент :) также не выявил ничего необычного.
Согласен, облажался
F>P.S. F>Мы правильно понимаем, что каждый из "квадратов" полностью лежит в поле?
Да
Здравствуйте, nikholas, Вы писали:
N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто. N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Сабж. (Полночи не спал — решал, полночи проверял решение на правильность, ещё полночи переживал — а не ответит ли кто раньше)
(Есть много решений в 37 (36 + 1) квадратов. У них у всех общее то, что остаётся много свободной площади, которую, тем не менее, не удаётся заполнить плотнее.)
Подсказкой же послужило: "коварство злодея может быть поистине безгранично".
Пришлось встать на место Злодея (теперь и я тоже безгранично коварен )
Если взять два квадрата 2х2, наложить один на другой, а потом немного сдвинуть верхний, то получим фигуру размером 2 х 2с хвостиком.
+-+----+
| | |
| | |
+-+----+
Вдоль хвостика, без перекрытия, на поле можно уложить не более 4-х таких фигур (8 квадратов) — как мал бы не был хвостик, пятая фигура (и даже просто квадрат) уже не поместится. Поэтому хвостик делаем размером 0.5.
Здравствуйте, mrhru, Вы писали:
M>Сабж. (Полночи не спал — решал, полночи проверял решение на правильность, ещё полночи переживал — а не ответит ли кто раньше)
M>(Есть много решений в 37 (36 + 1) квадратов. У них у всех общее то, что остаётся много свободной площади, которую, тем не менее, не удаётся заполнить плотнее.)
M>Подсказкой же послужило: "коварство злодея может быть поистине безгранично". M>Пришлось встать на место Злодея (теперь и я тоже безгранично коварен )
M>Если взять два квадрата 2х2, наложить один на другой, а потом немного сдвинуть верхний, то получим фигуру размером 2 х 2с хвостиком. M>
M> +-+----+
M> | | |
M> | | |
M> +-+----+
M>
Отдичная идея Действительно нигде не сказано, что границы квадратов должны совпадать с границами клеток!
А теперь доведем ее до логического конца.
Образуем две "полоски" из сдвинутых по диагонали квадратов со сдвигом d. Приставим одну к другой, чтобы боковые ступеньки "вошли" одна в другую без персечений.
Поскольку для каждого квадрата существует "непокрытая другими" зона "внутри" конфигурации, то мы всегда можем "выровнить" внешнюю границу другими квадратами. В частности, если верхняя граница правого верхнего квадрата находится на уровне верхней границы левого нижнего, мы всегда можем вписать данную конфигурацию в квадрат 3х3 квадрата (т.е. 6х6). На этот рисунок моих слабых художественных способностей не хватает .
Очевидно, что d мы можем сделать сколь угодно малым. Отсюда ответ — бесконечность.
...
MP>Отдичная идея Действительно нигде не сказано, что границы квадратов должны совпадать с границами клеток!
MP>А теперь доведем ее до логического конца. MP>Образуем две "полоски" из сдвинутых по диагонали квадратов со сдвигом d. Приставим одну к другой, чтобы боковые ступеньки "вошли" одна в другую без персечений.
...
MP>Очевидно, что d мы можем сделать сколь угодно малым. Отсюда ответ — бесконечность.
Смысл задачи именно в том, что квадраты ложатся по сетке поля, т.е. квадрат занимает ровно4 клети исходного поля, без пересечений границы.
Я считаю такого рода условия очевидными и не требующими быть описанными в условии, также ка и то, что действие происходит в Евклидовом пространстве, квадрат нельзя ставить на ребро, поворачивать относительно границ поля (странно, что никто еще такого не предлагал ), сворачивать в трубочку, складывать в несколько сложений...
Задача имеет решение и при очевидных условиях, хотя для поддержания разговора можно решить весь набор
M>(Есть много решений в 37 (36 + 1) квадратов. У них у всех общее то, что остаётся много свободной площади, которую, тем не менее, не удаётся заполнить плотнее.)
Есть решение в 38, когда ни одиен убрать нельзя
M>Подсказкой же послужило: "коварство злодея может быть поистине безгранично". M>Пришлось встать на место Злодея (теперь и я тоже безгранично коварен )
M>Если взять два квадрата 2х2, наложить один на другой, а потом немного сдвинуть верхний, то получим фигуру размером 2 х 2с хвостиком. M>
M> +-+----+
M> | | |
M> | | |
M> +-+----+
M>
M>Вдоль хвостика, без перекрытия, на поле можно уложить не более 4-х таких фигур (8 квадратов) — как мал бы не был хвостик, пятая фигура (и даже просто квадрат) уже не поместится. Поэтому хвостик делаем размером 0.5. M>
M>Всего потребуется 8 * 8 = 64 квадрата. Ну и плюс ещё один для последующего удаления.
Это всего лишь один из вариантов заполнения, а где док-во того, что больше нельзя?!!!!
(Ответ MichaelP показывает, что больше таким КОВАРНЫМ способом можно)
ЗЫ Эту задачку я решал на олимпиаде в 7 классе, больше таких сложных задавать не буду
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, mrhru, Вы писали:
N>...
N>Смысл задачи именно в том, что квадраты ложатся по сетке поля, т.е. квадрат занимает ровно4 клети исходного поля, без пересечений границы. N>Я считаю такого рода условия очевидными и не требующими быть описанными в условии, также ка и то, что действие происходит в Евклидовом пространстве, квадрат нельзя ставить на ребро, поворачивать относительно границ поля (странно, что никто еще такого не предлагал ), сворачивать в трубочку, складывать в несколько сложений...
Была мысль складывать квадратики...
N>Задача имеет решение и при очевидных условиях, хотя для поддержания разговора можно решить весь набор
N>Есть решение в 38, когда ни одиен убрать нельзя
... M>>Всего потребуется 8 * 8 = 64 квадрата. Ну и плюс ещё один для последующего удаления.
N>Это всего лишь один из вариантов заполнения, а где док-во того, что больше нельзя?!!!!
Так ответ MichaelP показывает, что и больше таким КОВАРНЫМ способом можно.
N>(Ответ MichaelP показывает, что больше таким КОВАРНЫМ способом можно)
Ой.
N>ЗЫ Эту задачку я решал на олимпиаде в 7 классе, больше таких сложных задавать не буду
Нет уж, дудки. Давай уж, будь добр быть больше таких сложных задачек быть задавать!
Все люди делятся на три категории, — на тех, кто знает математику и на тех, кто не знает.
Привет, nikholas!
N>Есть поле 10х10, на котором размещаются квадраты 2х2 таким образом, что все исходное поле покрыто. N>Каково минимальное число квадратов N такое, что как бы мы их не располагали на поле (с условием полного покрытия) всегда найдется хотя бы один квадрат такой, что его можно снять и при этом поле все равно останется полностью покрыто?
Необходимо, чтобы было возможно так разместить N-1 квадрат, чтобы каждый имел свое "собственное поле", не занятое другими, при этом N квадратов так разместить не должно получиться.
Рассмотрим центр квадрата. Поле центров имеет размер 9х9.
Рассмотрим центр квадрата (*) и места для центров квадратов, которые могут с ним пересекаться (.):
...
.*.
...
Чтобы квадрат имел собственное поле надо, чтобы три точки в любом углу не были заняты центрами других квадратов.
Например,
оо.
о*.
...
где о — пустая клетка
Наша задача расставить как можно больше центров так, чтобы у каждого был рядом пустой угол. Для этого надо как можно чаще пересекать эти углы. Оптимальная расстановка следующая:
*о*
ооо
*о*
Итого 4/9 от всех точек: максимум 81*4/9 = 36 квадратов с собственным полем.
Apapa.gif)
Во-первых, всегда можно сколь угодно большое число квадратов разместить так, чтобы они не покрывали поле вовсе. Во-вторых, если можно N квадратами покрыть все поле так, чтобы можно было снять один и поле при этом осталось бы открытым, то, очевидно, что это поле можно покрыть (N-1) квадратами. Если 25 -- это минимум количества квадратов, необходимых для покрытия (без того, чтобы можно было один снять), то чем 26 не решение?
В борьбе бобра с ослом всегда побеждает бобро.
Действительно нигде не сказано, что границы квадратов должны совпадать с границами клеток!
