Дано несколько белых и несколько чёрных точек. Из каждой белоснежной точки
Дано несколько белоснежных и несколько чёрных точек. Из каждой белоснежной точки идет стрелка в каждую чёрную, на каждой стрелке написано естественное число. Знаменито, что если пройти по хоть какому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, одинаково творенью чисел на стрелках, идущих против направления движения. Непременно ли тогда можно поставить в каждой точке естественное число так, чтоб число на каждой стрелке приравнивалось творению чисел на ее концах?
Задать свой вопрос1 ответ
Борис Марквит
Проведём индукцию по произведению чисел на всех ребрах.
База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 1. Тогда можно поставить и в каждой точке число 1.
Шаг индукции. Пусть творение равно nbsp;ngt; 1, nbsp;и для всех меньших творений утверждение теснее доказано. Возьмём случайный обычный делитель n, обозначим его через p. Светло, что p делит число на какой-то стрелке из точки A в точку B.
Докажем, что числа на всех стрелках, выходящих из A, делятся на p, или числа на всех стрелках, входящих в B, делятся на p. Пусть это не так. Тогда есть стрелка из A в C, число на которой не кратно p, и стрелка из D в B, число на которой не кратно p. Пройдём по замкнутому маршруту nbsp;A B D C A. nbsp;По условию, творенье чисел на стрелках AB и DC одинаково творенью чисел на стрелках DB и AC. Но 1-ое из творений кратно p, а 2-ое не кратно. Противоречие.
nbsp;Пусть все числа на всех стрелках из A кратны p. Поделим их все на p. Заметим, что расстановка чисел на стрелках все еще удовлетворяет условию. Действительно, в каждом замкнутом маршруте, проходящем через A ровно k раз, произведение чисел на стрелках по направлению движения и творение чисел на стрелках против направления движения уменьшились ровно в pk раз. Так как творенье чисел на стрелках при этой операции уменьшилось, можно пользоваться предположением индукции и подабающим образом расставить числа в точках. После этого увеличим число в точке A в p раз. Получившаяся расстановка чисел решает начальную задачку.
nbsp;Случай, в котором числа на всех стрелках в B кратны p, разбирается подобно.
Ответ. Обязательно.
База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 1. Тогда можно поставить и в каждой точке число 1.
Шаг индукции. Пусть творение равно nbsp;ngt; 1, nbsp;и для всех меньших творений утверждение теснее доказано. Возьмём случайный обычный делитель n, обозначим его через p. Светло, что p делит число на какой-то стрелке из точки A в точку B.
Докажем, что числа на всех стрелках, выходящих из A, делятся на p, или числа на всех стрелках, входящих в B, делятся на p. Пусть это не так. Тогда есть стрелка из A в C, число на которой не кратно p, и стрелка из D в B, число на которой не кратно p. Пройдём по замкнутому маршруту nbsp;A B D C A. nbsp;По условию, творенье чисел на стрелках AB и DC одинаково творенью чисел на стрелках DB и AC. Но 1-ое из творений кратно p, а 2-ое не кратно. Противоречие.
nbsp;Пусть все числа на всех стрелках из A кратны p. Поделим их все на p. Заметим, что расстановка чисел на стрелках все еще удовлетворяет условию. Действительно, в каждом замкнутом маршруте, проходящем через A ровно k раз, произведение чисел на стрелках по направлению движения и творение чисел на стрелках против направления движения уменьшились ровно в pk раз. Так как творенье чисел на стрелках при этой операции уменьшилось, можно пользоваться предположением индукции и подабающим образом расставить числа в точках. После этого увеличим число в точке A в p раз. Получившаяся расстановка чисел решает начальную задачку.
nbsp;Случай, в котором числа на всех стрелках в B кратны p, разбирается подобно.
Ответ. Обязательно.
, оставишь ответ?
Похожие вопросы
-
Вопросы ответы
Новое
NEW
Статьи
Информатика
Статьи
Последние вопросы
Упражнение 2 Выпишите глаголы и вставьте пропущенные буквы
Русский язык.
Радиус окружности, описанной около равностороннего треугольника, равен 6. Найдите сторону треугольника
Геометрия.
Вычислите силу с которой при давлении 100 КПа атмосфера давит на
Физика.
Синтаксический разбор и схема Но мы сказали, что нам ничего не
Русский язык.
Массовая доля целлюлозы в древесине составляет 50%. Какая масса спирта может
Химия.
помоги мне пожалуста прш
869*(61124-488*125)-50974
Математика.
по шкале высот определить ,в каком направлении происходит понижение релефа уральских гор
География.
Помогите пожалуйста написать Сочинение Овчинникова "победитель'
Литература.
Здравствуйте. Нужен цитатный план испытания лётчика в лесу главы2-13 по повести
Разные вопросы.
Я хочу найти решение и ответ для этой задачи и получить
Математика.
Облако тегов