Всесиб 2026, 9 класс, задача 5
( баллов) В группе учащихся, каждый из которых дружит ровно с тремя другими. Некоторые пятеро из них марта купили билет на концерт апреля. Дальше в каждый следующий день, начиная со марта, ровно один из тех, кто еще не купил билет, но, как минимум двое из его друзей к этому моменту уже купили, тоже покупает билет.
а) Может ли случиться так, что в итоге все учащиеся купят билет?
б) Известно, что, если разбить всю группу произвольным образом на две подгруппы, то всегда найдутся двое дружащих учащихся из разных подгрупп. Найдите минимальное такое, что при любой схеме знакомств в группе, и любом выборе учащихся, купивших билет марта, в итоге описанного выше процесса все учащиеся группы купят билет на концерт.
Ответ
Ответ. а) Нет, б) .
Решение. а) Рассмотрим множество пар друзей (Р-пары), в которых один из них купил билет, а второй - нет, марта их не больше . В очередной день, если покупает билет учащийся, у которого все три друга уже с билетом, количество Р-пар уменьшается на . Если покупает билет учащийся , у которого ровно два друга и уже с билетом, а - нет, то количество Р-пар уменьшается на : пропадают пары и , но появляется пара . Следовательно, если процесс не остановится раньше, то через дней, марта, останется не более - одной Р-пары, и процесс на этом остановится. Обилеченными будут всегда не более учащихся, то есть не все.
б) Если марта обилечены не меньше учащихся, то не обилечены всего не более двух. Если таковой всего один, у него три обилеченных друга и марта он тоже купит билет. Если их два, то они либо не дружат и у каждого по три обилеченных друга, либо они дружат, тогда у каждого по два обилеченных друга. В любом случае, марта они тоже купят билеты. Осталось построить пример схемы дружб между учащимися и указать обилеченных из них так, чтобы каждый из трёх оставшихся имел ровно одного обилеченного друга. Всё изобразим в виде графа, где вершины - учащиеся, а рёбра - дружбы. Рассмотрим сначала два правильных семиугольника, один из которых расположен внутри другого, соединим рёбрами вершины первого и второго с одинаковыми номерами, получится кольцо, составленное из четырёхугольников (это рёбра и грани семиугольной призмы). Внутри меньшего семиугольника возьмём треугольник, и соединим его первую вершину с серединой первой стороны внутреннего семиугольника, вторую вершину - с серединой третьей стороны семиугольника и третью вершину - с серединой пятой его стороны. Обилетим всех, кроме , и , тогда у каждого из , и только по одному обилеченному другу и процесс дальнейшего обилечивания даже не начнётся. Если марта обилечены некоторые учащихся, кроме , и , в итоге ни один из , и обилечен не будет. В противном случае в момент, когда обилетится первый из них, он не может иметь больше одного обилеченного друга - противоречие. Это только один из множества возможных примеров такого рода.