admin2

Задача 00015

от

Тургор(весенний) 2024, 10-11, 6 задача.
В математическом кружке 45 школьников, некоторые дружат. Как ни разбивай их на тройки, в какой-то тройке все будут друг с другом дружить. Докажите, что всех школьников можно разбить на тройки так, чтобы в каждой тройке хотя бы какие-то двое дружили друг с другом.

Подсказка

Попробуйте набирать неполные тройки (в которых одно или 2 ребра из 3)

Решение

Обозначим школьников точками и каждых двух друзей соединим отрезком (ребром). Будем формировать «полуполные» тройки — в которых есть хотя бы одно ребро, но не все три ребра.

Пусть мы не можем из остатка сформировать очередную «полуполную» тройку. Тогда в остатке либо все попарно не дружат, либо все попарно дружат. (В самом деле, пусть в остатке есть и дружащие, и не дружащие. Выберем из них двоих друзей A и B. Тогда все другие люди из остатка дружат и с A, и с B (иначе возникнет полуполная тройка с ребром AB), но при этом в остатке имеется некто C, который с кем-то из остатка не дружит — скажем, с D. Тогда A, C, D — полуполная тройка.)

Если в остатке все попарно не дружат — получается разбиение без полных троек, что противоречит условию. Если в остатке все попарно дружат — получается разбиение из полуполных и полных троек, что решает задачу.

Задача 00013

от

В городе одна синяя площадь и n зелёных, причём каждая зелёная площадь соединена улицами с синей и с двумя зелёными, как показано на рисунке. На каждой из 2n улиц ввели одностороннее движение так, что на каждую площадь можно проехать и с каждой – уехать. Докажите, что с каждой площади этого города можно, не нарушая правил, доехать до любой из остальных.

Решение

Докажем, что
    а) от каждой зелёной площади можно доехать до синей;
    б) от синей площади можно доехать до любой зелёной.
  Условимся обозначать направление движения на улицах стрелками.

  а) Предположим, что от зелёной площади A1 нельзя доехать до синей площади. Поскольку уехать с площади A1 можно, то от неё, проехав по одной улице, мы доедем до зелёной площади A2. От площади A2 тоже нельзя доехать до синей площади. Выехав с неё, мы доедем до площади A3, потом до A4 и т.д. Проехав по n улицам, мы вернёмся на площадь A1 и убедимся, что стрелки в городе расставлены так, как на рисунке. Но тогда на синюю площадь нельзя приехать, что противоречит условию.

  б) Изменим направления всех стрелок. Полученная схема движения тоже удовлетворяет условию. Поэтому, как показано в а), при этой расстановке стрелок от каждой зелёной площади можно доехать до синей. Но это означает, что при старой расстановке стрелок от синей площади можно было доехать до любой зелёной.