Дано несколько белых и несколько чёрных точек. Из каждой белой точки идет стрелка в каждую чёрную, на каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на её концах?

   Решение

Темы:    [ Обход графов ] [ Делимость чисел. Общие свойства ] [ НОД и НОК. Взаимная простота ] [ Индукция (прочее) ]

Сложность: 4 Классы: 9,10,11

Прислать комментарий

Условие

Дано несколько белых и несколько чёрных точек. Из каждой белой точки идет стрелка в каждую чёрную, на каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на её концах?

Решение 1

  Проведём индукцию по произведению чисел на всех стрелках.
  База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 1. Тогда можно поставить и в каждой точке число 1.
  Шаг индукции. Пусть произведение равно  n > 1,  и для всех меньших произведений утверждение уже доказано. Возьмём произвольный простой делитель p числа n. Ясно, что p делит число на какой-то стрелке из точки A в точку B.
  Докажем, что числа на всех стрелках, выходящих из A, кратны p, или числа на всех стрелках, входящих в B, кратны p. Пусть это не так. Тогда есть стрелка из A в C, число на которой не кратно p, и стрелка из D в B, число на которой не кратно p. Пройдём по замкнутому маршруту  A → B → D → C → A.  По условию, произведение чисел на стрелках AB и DC равно произведению чисел на стрелках DB и AC. Но первое из произведений кратно p, а второе не кратно. Противоречие.
  Пусть все числа на всех стрелках из A кратны p. Поделим их все на p. Заметим, что расстановка чисел на стрелках все ещё удовлетворяет условию. Действительно, в каждом замкнутом маршруте, проходящем через A ровно k раз, произведение чисел на стрелках по направлению движения и произведение чисел на стрелках против направления движения уменьшились ровно в p^k раз. Так как произведение чисел на стрелках при этой операции уменьшилось, можно воспользоваться предположением индукции и должным образом расставить числа в точках. После этого увеличим число в точке A в p раз. Получившаяся расстановка чисел решает исходную задачу.
  Случай, в котором числа на всех стрелках в B кратны p, разбирается аналогично.

Решение 2

  Для начала сделаем расстановку рациональных чисел в точках, удовлетворяющую условию. Выберем произвольную точку O и поставим в ней 1. Для любой другой точки X применим следующий алгоритм. Пройдём каким-нибудь путем от точки O до точки X и поставим в X произведение всех чисел на стрелках по направлению пути, делённое на произведение всех чисел на стрелках против направления пути. Из условия следует, что число, поставленное в точку X, не зависит от выбора пути от O до X. После того как мы поставили в каждую точку по числу, обратим все числа, написанные в белых вершинах. Теперь число на каждой стрелке будет являться произведением чисел на её концах.
  Пронумеруем каждую белую точку и каждую чёрную точку. Пусть в i-й белой точке W_i записана несократимая дробь  ^a_i/_bi,  в j-й чёрной точке B_j – несократимая дробь  ^c_j/_dj, . Так как произведение  ^a_ic_j/_bidj  является целым, то c_j делится на b_i, а a_i – на d_j. Пусть b – НОК всех b_i, а d – НОК всех d_j. Тогда каждое c_j делится на B, а каждое a_i – на d. Теперь поставим в W_i целое число  ^ba_i/_bid,  а в B_j – целое число  ^dc_j/_djb.  Ясно, что такая расстановка чисел в точках удовлетворяет требованиям.

Ответ

Обязательно.

Замечания

7 баллов

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