вотэтазадача 21. Жуки на многограннике.

Видел эту задачу, когда проверял какую-то ММО, впечатлился. Авторство, если не ошибаюсь Антона Клячко, видел еще название лемма Винберга.

По ребрам выпуклого многогранника ползают жуки, при этом каждый жук всё время остаётся в одной грани (в каждой грани - свой жук). Каждый жук обходит границу своей грани в определенном направлении, причём так, что любые два жука по общему для них ребру ползут в противоположных направлениях. Скорость каждого жука может быть непостоянной, но скорости не меньше 1. Доказать, что когда-нибудь какие-нибудь два жука встретятся.

На ММО давали вариант этой задачи, где жуки ползают по ребрам тетраэдра, но общая формулировка, конечно, интереснее.

1 комментарий:

  1. Идея доказательства: поместим в каждую грань i по точке A_i. Если в данный момент частица i-й грани двигается по ребру между i-й и j-й гранью, нарисуем ориентированное ребро из точки A_i в точку A_j. В итоге получим ориентированный граф (на остове двойственного многогранника). Этот граф представляет из себя набор ориентированных циклов, так как граней многогранника конечное число и цепочка ор.ребер должна замкнуться. Рассмотрим какой-нибудь цикл и посмотрим на его динамику. Можно доказать, что с течением времени этот цикл ужимается и в итоге обязан прийти к виду A_i-->A_j-->A_i. Но это и означает, что частицы, бегущие вдоль границ i-й и j-й граней столкнутся на ребре между этими гранями. Технические детали можно доработать самостоятельно. Тут, конечно, неявно используется топология сферы: аналогичный факт на многограннике в виде тора не верен. Пример легко придумывается.

    ОтветитьУдалить