Задачка про лягушек и Маленького принца
Aug. 18th, 2016 11:45 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
ermouthХорошая задачка вот с международной математической олимпиады 2016 (все задачки за все года вот тут).
Задача 6. На плоскости расположено n ⩾ 2 отрезков так, что любые два из них пересекаются по внутренней точке, а никакие три из них не имеют общей точки. Иван выбирает один из концов каждого отрезка и сажает в него лягушку лицом к другому концу этого отрезка. Затем он n − 1 раз хлопает в ладоши.
При каждом хлопке каждая из лягушек немедленно прыгает вперёд в следующую точку пересечения на её отрезке. Лягушки никогда не меняют направления своих прыжков. Иван хочет изначально рассадить лягушек так, чтобы никакие две из них никогда не оказались в одной точке пересечения одновременно.
(a) Докажите, что Иван всегда может добиться желаемого, если n нечётно.
(b) Докажите, что Иван никогда не сможет достичь желаемого, если n чётно.
----
Есчо, справедливо и для построения на 2-сфере (типа Иван – Маленький принц и живёт на маленькой планетке с жабами ггг). Соответственно вместо отрезков –ортодромы дуги геодезических линий (не обязательно кратчайшие).
Задача 6. На плоскости расположено n ⩾ 2 отрезков так, что любые два из них пересекаются по внутренней точке, а никакие три из них не имеют общей точки. Иван выбирает один из концов каждого отрезка и сажает в него лягушку лицом к другому концу этого отрезка. Затем он n − 1 раз хлопает в ладоши.
При каждом хлопке каждая из лягушек немедленно прыгает вперёд в следующую точку пересечения на её отрезке. Лягушки никогда не меняют направления своих прыжков. Иван хочет изначально рассадить лягушек так, чтобы никакие две из них никогда не оказались в одной точке пересечения одновременно.
(a) Докажите, что Иван всегда может добиться желаемого, если n нечётно.
(b) Докажите, что Иван никогда не сможет достичь желаемого, если n чётно.
----
Есчо, справедливо и для построения на 2-сфере (типа Иван – Маленький принц и живёт на маленькой планетке с жабами ггг). Соответственно вместо отрезков –
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2016-08-18 06:47 pm (UTC)no subject
Date: 2016-08-18 06:56 pm (UTC)По условию: «Иван выбирает один из концов каждого отрезка». Лягушки сидят на концах, в вершины треугольника сажать нельзя.
Задачка кста хорошая, мне доставила массу удовольствия ) В рамках времени олимпиады я бы её не решил.
no subject
Date: 2016-08-18 10:45 pm (UTC)Но я правильно понял, что варианты, когда лягушкам больше некуда прыгать, а хлопки ещё не кончились, мы считаем не валидными и не рассматриваем?
no subject
Date: 2016-08-18 10:50 pm (UTC)7 отрезков, у каждого 2 точки пересечения, т.е. как не посади лягушку, она выживет только 3 хлопка. Потом она упрётся в противопложный конец отрезка и на четвёртом хлопке умрёт. А хлопков будет 6. Вот тебе и обломинго:
Или я опять не так понял условие?
no subject
Date: 2016-08-18 10:51 pm (UTC)no subject
Date: 2016-08-18 11:10 pm (UTC)1) Для каждого N существует ровно 1 способ (с точностью до гомеоморфных преобразований) нарисовать отрезки, чтобы они пересекались попарно, но не имели точек пересечения с 3 или больше отрезками.
2) Невозможность (б) практически очевидна, вечером распишу.
3) Для (а) существует не более двух неизоморфных способов расставить жаб, чтобы не было быстрого облома (может, даже и один способ, я ещё не понял, сводятся ли эти два друг к другу, но могут). Осталось лишь доказать, что условия выполнятся во время всех хлопков.
Я бы пробовал доказывать по индукции, добавляя по два отрезка.
Вечером, может, попробую.
no subject
Date: 2016-08-18 11:27 pm (UTC)no subject
Date: 2016-08-18 11:41 pm (UTC)UPD. Пока я рисовал ты и сам сообразил )