помогите решить олимпиадную задачу

[math_seeker]

Здравствуйте! Подскажите как решить такую задачу: можно ли покрыть плоскость конечным числом полос (прямоугольников с конечной шириной и бесконечной длиной)?
для меньшей размерности решение очевидно, но как-то свести к ней (индукций по размерности или проекцией на оси) не удается.

[SpBTimes]

Ну по рациональной точке возьмите

[Brukvalub]

Нужно "от противного" доказывать, что такое покрытие невозможно. Сначала можно взять произвольный конечный набор полос и при наличии в нем параллельных друг другу полос заполнить пространство между их краями, сведя задачу к набору попарно не параллельных полос. Затем можно рассмотреть единичные векторы, параллельные сторонам полос (по одному для каждой полосы), стащить эти векторы к одному началу, рассмотреть два "соседних" вектора, после чего доказать, что между полосами, соответствующими этим "соседним" векторам обязательно образуется угол, часть которого ничем не покроется.

[ИСН]

Слишком много букв. Возьмём тупо большой, большой, совсем большой круг. Его площадь столько-то, а каждая полоса вырезает максимум столько-то. Упс.

-- менее минуты назад --

Интереснее с параболами.

[Brukvalub]

ИСН в сообщении #911074 писал(а):

Слишком много букв. Возьмём тупо большой, большой, совсем большой круг. Его площадь столько-то, а каждая полоса вырезает максимум столько-то. Упс.

-- менее минуты назад --

Интереснее с параболами.

Имеется в виду, что площадь пересечения полосы с кругом с какого-то момента растет как линейная функция от радиуса круга?

[ИСН]

Не то что с какого-то момента, а с самого начала она мажорируется очевидной линейной функцией.

[Brukvalub]

ИСН в сообщении #911083 писал(а):

Не то что с какого-то момента, а с самого начала она мажорируется очевидной линейной функцией.

С самого начала и ОЧЕНЬ долго еще большой круг может находиться все еще целиком внутри полосы, и тогда никто ничем, кроме площади круга, не мажорируется. Но Ваша идея - явно красивее моей!

[ewert]

math_seeker в сообщении #911057 писал(а):

для меньшей размерности решение очевидно, но как-то свести к ней

Тривиально свести: существует ли линия, не параллельная ни одной из полос?...

-- Ср сен 24, 2014 07:37:18 --

ИСН в сообщении #911074 писал(а):

Интереснее с параболами.

Ровно аналогично.

[ИСН]

А, ну да, так ещё очевиднее.

[TOTAL]

Если лень искать линию, не параллельную никакой полосе, то можно взять произвольную толстую полосу (толще суммы толщин всех полос)

[ewert]

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

Если лень искать линию, не параллельную никакой полосе,

как может быть лень делать то, что делать вовсе не нужно

[TOTAL]

Если $n$ полосами можно замостить целую плоскость, то $n-1$ полосами можно замостить половину плоскости, $n-2$ полосами можно замостить четвертину плоскости и т.д. Противоречие, т.к. последней полосой можно будет замостить уголок, хоть и очень острый.

[Sender]

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

[ИСН]

Нет.

-- менее минуты назад --

Upd. Ах, выпуклым. Тогда да, наверное.

[Skeptic]

Укладывать полосы надо, начиная с границ плоскости.