О самовольстве феодалов и их раздорах. Это слова аббата Сугерия, могущественного советника французских королей Людовика VI и Людовика VII. Тиранами он называет феодалов, «раздиравших страну» войнами и ослаблявших ее неподчинением королю. Больше всего от этой анархии страдал простой народ, крестьянство. Против выступали церковь и королевская власть. Аббат Сугерий, родившийся в крестьянской семье и, вероятно, видевший все это с детства, плохо относится к этому явлению. Будучи образованным человеком и умным государственным деятелем, он понимал пагубность ситуации, призывая королевскую власть решительно бороться с произволом «баронов»
Проведём индукцию по произведению чисел на всех ребрах.
База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 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, разбирается аналогично.
Ответ. Обязательно.
а) Рассмотрим граф с четырьмя вершинами A, B, C, D, соответствующими людям, и соединим ребрами людей, знающих общий язык. Условие означает, что каждая тройка вершин соединена хотя бы двумя рёбрами. А доказать нужно, что есть два ребра без общих вершин. Пусть это неверно.
Первый способ. Если в тройке (A, B, C) проведены рёбра AB и AC, то рёбер BD и CD нет. Но тогда в тройке (B, C, D) не больше одного ребра. Противоречие.
Второй способ. Всего есть 4 тройки. Каждое ребро входит в две тройки. Следовательно, рёбер не менее 4•2 : 2 = 4. С другой стороны, каждому ребру соответствует отсутствующее "противоположное" ребро. Следовательно, рёбер не более трёх. Противоречие.
в) Отделим двух человек, говорящих на одном языке, а остальных разобьём на четвёрки. Согласно а) каждую четвёрку можно разбить на две пары с общим языком.
