ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116236
Темы:    [ Комбинаторика (прочее) ]
[ Перебор случаев ]
[ Пирамида (прочее) ]
Сложность: 5
Классы: 10,11
В корзину
Прислать комментарий

Условие

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


Решение

  Будем обозначать каждого жука буквой, соответствующей вершине, не входящей в его грань: жук D обходит грань ABC, жук C – грань ADB, жук B – грань ACD, жук A – грань BDC, причём в указанном порядке. Из-за ограничения на скорость ни один из жуков не может бесконечно долго находиться на одном ребре. Поэтому настанет такой момент, когда каждый из них хотя бы раз пройдёт через некоторую вершину. Рассмотрим возможные варианты расположения жуков в некоторый следующий момент после этого. Если при этом какой-либо жук находится в вершине, то считаем, что он находится на двух рёбрах: с которого он пришёл и на которое пойдёт.
  Вот все возможные случаи.
  а) Какие-либо два жука оказались на одном ребре. Если они движутся навстречу друг другу, то они встретятся. Если же они расходятся в разные стороны, то они уже встретились на этом ребре, так как каждый из них уже проходил через одну из вершин этого ребра.
  б) Какие-либо три жука находятся на рёбрах с общей вершиной, и все они движутся в её сторону. Рассмотрим первый из следующих за этим моментов времени, при котором один из этих жуков попадёт в вершину. Тогда какие-то два жука окажутся на одном ребре, и мы приходим к случаю а).
  в) Все четыре жука находятся на четырёх рёбрах, из которых никакие три не имеют общей вершины. Тогда оставшиеся два ребра не имеют общих вершин. С точностью до переименования вершин получаем только один вариант такого расположения: жуки находятся на рёбрах AB, AC, BD, CD, причём жук D движется по AB (от A к B). Значит, в данный момент по AC движется жук B, по DC – жук A, по DB – жук C. Если первым в вершину попадёт жук B или C, то приходим к случаю а). Если первым вершины (B) достигнет жук D, то три жука будут двигаться к вершине C. Если первым в вершину (C) попадёт жук A, то три жука будут двигаться к B. В обоих случаях приходим к пункту б).
  г) Какие-либо три жука находятся на рёбрах при одной вершине, но не все из них ползут в её сторону. Тогда с точностью до переименования вершин это рёбра AB, AC и AD, причём жук D движется по AB. Нетрудно проверить, что тогда все эти три жука движутся от вершины A (B – по AC, а C – по AD). Не ограничивая общности, можем считать, что первым из этих жуков достигнет вершины жук D. При этом он переползёт на ребро BC. Если жук A находится в этот момент на ребре BC, то приходим к случаю а). Если же он находится на CD, то три жука движутся в направлении C, и приходим к случаю б). Наконец, если он находится на BD, то жуки находятся на рёбрах AC, AD, BC и BD. Приходим к случаю в).

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

Замечания

Утверждение о том, что два жука обязательно встретятся, останется верным и в том случае, если они будут ползать по рёбрам произвольного выпуклого многогранника. При этом, естественно, предполагается выполнение остальных условий задачи: в каждой грани ползает свой жук, по каждому из рёбер два проползающих по ним жука двигаются в разных направлениях, и скорость жуков ограничена снизу. Доказательство см. на странице http://avva.livejournal.com/2132856.html.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2011
Номер 74
класс
Класс 11
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .