?

Log in

No account? Create an account
математика, задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

математика, задачка [июл. 12, 2001|01:47 am]
Anatoly Vorobey
Вспомнилась милая задачка с элементарным условием. Надо записать, чтобы на этот раз не забыть (я её знал года 4 назад, потом забыл, мне недавно опять напомнили). Если кто не знал, и интересно, пробуйте.

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

Решение, пожалуй, введу в привате.
СсылкаОтветить

Comments:
(Удалённый комментарий)
[User Picture]From: avva
2001-07-11 04:17 pm
Отрезки параллельны внешним сторонам, но они необязательно тянутся на всю длину/ширину внешнего прямоугольника. Т.е. вполне могут быть пересечения внутри, где сходятся несколько прямоугольников разных размеров; любая внутренняя сторона не обязана доходить до внешней. "Полос" таким образом нет в общем случае.
(Ответить) (Parent) (Thread)
[User Picture]From: talash
2001-07-12 04:08 am

Reshenie

chtoby pryamougolnick byl razdelen tolko na pryamougolnicki, gran' hotya by odnogo iz nih dolzhna byt' ot kraju do kraju (to est ravna grani vneshnego pryamougolnicka). esli ona tselaya- to zhe samoe spravedlivo dlya vneshnego pryamougolnicka (QED). esli ona ne tselaya, ona dolzhna byt chastju dvuh pryamougolnickov na kotorye ona razdelyaet vneshnij pryamougolnick. vtoraya gran' u kazhdogo iz etih dvuh pryamougolnickov tselaya po usloviju. summa etih dvuh tseluh granej daet vtoruju storonu vneshnego pryamougolnicka, kotoraya dolzhna byt tselaya v etom sluchae (QED).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-07-13 02:09 am

Re: Reshenie

chtoby pryamougolnick byl razdelen tolko na pryamougolnicki, gran' hotya by odnogo iz nih dolzhna byt' ot kraju do kraju (to est ravna grani vneshnego pryamougolnicka).

Нет, это уже неверно. Даже если просто разрубить внешний прямоугольник двумя линиями крест-накрест, это условие не будет выполняться. Но конечно, там может быть и сложнее. К примеру:

|--------|-----------|----|
| | |----|
|--------|-----|--|--|----|
| | | |
|--------------|--|-------|

(в условии, когда говорится о внутренних прямоугольниках, имеются в виду минимальные внутренние прямоугольники в делении, которые уже ни на что не делятся).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-07-13 02:10 am

Re: Reshenie

chtoby pryamougolnick byl razdelen tolko na pryamougolnicki, gran' hotya by odnogo iz nih dolzhna byt' ot kraju do kraju (to est ravna grani vneshnego pryamougolnicka).

Нет, это уже неверно. Даже если просто разрубить внешний прямоугольник двумя линиями крест-накрест, это условие не будет выполняться. Но конечно, там может быть и сложнее. К примеру:


|--------|-----------|----| 
|        |           |----| 
|--------|-----|--|--|----| 
|              |  |       | 
|--------------|--|-------| 


(в условии, когда говорится о внутренних прямоугольниках, имеются в виду минимальные внутренние прямоугольники в делении, которые уже ни на что не делятся).
(Ответить) (Parent) (Thread)
From: ex_udod985
2001-07-12 04:46 am
Пардон, недочитал,
поздно, старый,
удалил.

Такие дела


(Ответить) (Parent) (Thread)
From: ex_tipharet
2001-07-11 04:18 pm

Была у нас в 8-м классе на матбое.

Привет
Миша.
(Ответить) (Thread)
[User Picture]From: avva
2001-07-11 04:21 pm
Да и на олимпиадах небось, где-нибудь высвечивалась, выглядит, как типичная олимпиадная задачка.
(Ответить) (Parent) (Thread)
[User Picture]From: dm_lihachev
2001-07-11 08:15 pm

ага, смотрится классически

типа как шприц с дрянью :)

удалил -- но оно в кассу?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-07-12 01:05 am

Re: ага, смотрится классически

Ну это начало одного из возможных решений. Нужно как следует оформить покраску ребер и доказать, что действительно есть путь - при правильной окрасе это не очень сложно.
(Ответить) (Parent) (Thread)
[User Picture]From: dm_lihachev
2001-07-12 02:27 am

ни, зачем ребра красить -- квадратики и красить

если есть цепочка из белых квадратиков (с горизонтальными целыми) - от левого края до правого - то и горизонталь большого - целая.

а ежли - нету - то тогда обязательно должна быть цепочка из черных квадратиков (с верт. целыми) -- тогда у большого - вертикаль целая

чтобы ни белой цепочки не было, ни черной - так не бывает - або как - топология :))

ну ежли строго - можно от противного

все
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2001-07-12 02:35 am

Re: ни, зачем ребра красить -- квадратики и красить

Ну дык докажите, в этом-то и вся соль. То, что квадратики раскрасили и назвали белыми-черными, в этом никакой новой информации нет, просто по-другому назвали то же самое :)
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-07-12 09:04 pm

Гнусная провокация. Вместо того, чтобы заниматься делом, два дня решал Вашу задачку. Действительно, очень красиво решается.

А вот такая (была на союзной олимпиаде). К целому числу прибавляется произведение его цифр (в десятичное записи), к результату – произведение его цифр, и т.д. Доказать, что получающаяся последовательность стабилизируется.
(Ответить) (Thread)
[User Picture]From: avva
2001-07-13 02:02 am
Задачка ещё интересна тем, что у неё есть много очень разных доказательств - не знаю, какое Вы нашли. Была статья даже где-то (кажется в Am. Math. Monthly) с 15-ю разными доказательствами; если интересно, я откопаю ссылку.

А Ваша задачка кажется простой, или я чего-то не понимаю? Если, скажем, добрались до числа из миллиона цифр, то возможный прирост на каждом шаге имеет куда меньше чем миллион цифр, поэтому нам не удастся перескочить через 9->10 при переносе на миллион-первую цифру, когда он случится.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-07-13 03:53 am
Задачка ещё интересна тем, что у неё есть много очень разных доказательств - не знаю, какое Вы нашли.
....................................................
Я напишу (чуть попозже) в своем ЖЖ для friends. Т.к. friends у меня только Вы да хатуль, это будет достаточно приватно.

................................................
Была статья даже где-то (кажется в Am. Math. Monthly) с 15-ю разными доказательствами; если интересно, я откопаю ссылку.
..................................................................
Да нет, пожалуй неинтересно. Я не верю, что возможны разные принципы решения. Скорей всего, отличия в несущественных деталях. Что мне более интересно, это как задача была придумана, откуда она возникла.

..............................................................
А Ваша задачка кажется простой, или я чего-то не понимаю? Если, скажем, добрались до числа из миллиона цифр, то возможный прирост на каждом шаге имеет куда меньше чем миллион цифр, поэтому нам не удастся перескочить через 9->10 при переносе на миллион-первую цифру, когда он случится.
................................................................
Именно так. К своему стыду, тогда я ее не решил.
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2001-07-13 09:37 am
Записал
(Ответить) (Parent) (Thread)