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

Супер1009 Супер1009    2   16.04.2019 23:20    5

Ответы
lizashevchuk664 lizashevchuk664  16.04.2019 23:20
Проведём индукцию по произведению чисел на всех ребрах.
База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 1. Тогда можно поставить и в каждой точке число 1.
Шаг индукции. Пусть произведение равно  n> 1,  и для всех меньших произведений утверждение уже доказано. Возьмём произвольный простой делитель n, обозначим его через p. Ясно, что 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 раз, произведение чисел на стрелках по направлению движения и произведение чисел на стрелках против направления движения уменьшились ровно в pk раз. Так как произведение чисел на стрелках при этой операции уменьшилось, можно воспользоваться предположением индукции и должным образом расставить числа в точках. После этого увеличим число в точке A в p раз. Получившаяся расстановка чисел решает исходную задачу.
 Случай, в котором числа на всех стрелках в B кратны p, разбирается аналогично.
Ответ. Обязательно.
ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Другие предметы