Пятничная задачка

← →
default © (2005-06-10 19:02) [0]

http://www.webfile.ru/347515

← →
GuAV © (2005-06-10 21:23) [1]

+---+---+---+---+---+---····· | | | | | | : | +---+---+---+---+---·····---+ | | | | | : | | +---+---+---+---·····---+---+ | | | | : | | | +---+---+---·····---+---+---+ | | | : | | | | +---+---·····---+---+---+---+ | | : | | | | | +---·····---+---+---+---+---+ | : | | | | | | ·····---+---+---+---+---+---+ : | | | | | | | ·---+---+---+---+---+---+---+

Видно, что линия, которая обозначена точками, имеет n углов в одной половине и n-1 в другой.
Эти углы должны являтся углами прямоугольников. Т.к. прямоугольников 2n, то одна из половин
непременно имеет только прямоугольники, одним из углов которых является угол разделяющей линии.
Рассмотрим эту половину.

b···· : | ·····---+ : | | ·····---+---+ : | | | ·····---+---+---+ : | | | | ·····---+---+---+---+ : | | | | | ·····---+---+---+---+---+ : | | | | | | a····---+---+---+---+---+---+ : | | | | | | 1 | ·---+---+---+---+---+---+---+

Клетка 1 принадлежит какому-то прямоугольнику.
Если это прямоугольник с углами a или b, то остальные расположены в такой же "половине квадарта", но с меньшим на 1 числов углов. Если любой другой прямоугольник, тогда остаются две таких "половины квадарта" с меньшим числов углов. Рассмотрев расположение последующих прямоугольников, приходим, что остаётся хотя бы одна "половина квадарта", размером 1х1.

← →
default © (2005-06-10 22:11) [2]

GuAV © (10.06.05 21:23) [1]
верно
я правда, по-другому, 2n вообще не использовалось
если интересно напишу

← →
default © (2005-06-10 22:36) [3]

очевидно, что если мы докажем неразбиваемость фигуры выше ломаной(для определённости так взял, можно было взять ниже ломаной или обе рассматривать по очереди - но это было бы лишним) на прямоугольники площади большей чем 1x1, то мы решим задачу
(поскольку в самом условии разбиение уже произведено и если
мы докажем то, что выше сказано, то ясно что хотя бы один прямоугольник площади 1x1 будет)
рассмотрим рисунок

+---+---+---+---+---+---·····
| 1 | 2 | 3 | 4 | 5b| 6a: |
+---+---+---+---+---·····---+
| 1 | 2 | 3 | 4b| 5a: | |
+---+---+---+---·····---+---+
| 1 | 2 | 3b| 4a: | | |
+---+---+---·····---+---+---+
| 1 | 2b| 3a: | | | |
+---+---·····---+---+---+---+
| 1b| 2a: | | | | |
+---·····---+---+---+---+---+
| 1a: | | | | | |
·····---+---+---+---+---+---+
: | | | | | | |
·---+---+---+---+---+---+---+

смотрим на клетку 1a
эта клетка по условию входит в какой-то прямоугольник
левая, нижняя и правые стороны этого прямоуг-ка заданы, не задана только верхняя(и так же у всех остальных рассм-ых прямоуг-ов)
ясно, что минимум этот прямоугольник может состоять из клеток
1a,1b(то есть постоянная составляющая возможного прямоугольника)
теперь смотрим на клетку 2a
аналогично, прямоуг-ик содержащий эту клетку минимум может состоять из клеток 2a,2b и тд
и видим что наша процедура останавливается на прямоугольнике в одну клетку 6a, тем самым доказываем то, что хотели и решаем задачу
можно более формально, алгебраически показать что так будет для всех квадратов nxn, НО это слишком очевидно для привлечения алгебры...

default © (10.06.05 22:36) [3]
Тоже вариант, а я и не подумал.
Просто сразу стало понятно зачем 2n, вот и из него исходил...

Пятничная задачка Найти похожие ветки