Всесиб 2022, 10 класс, задача 2
( баллов) Найти необходимые и достаточные условия, которым должны удовлетворять натуральные числа , , такие, что можно записать по кругу в некотором порядке раз букву , раз букву и раз букву так, чтобы никакие две одинаковые буквы не были написаны рядом (не были соседними).
Ответ. Каждое из чисел , , не больше суммы двух других.
Решение. ) Необходимость условия. По условию, между каждыми двумя ближайшими буквами на круге должна быть хотя бы одна из букв или . Поэтому суммарное количество букв и не меньше, чем количество букв . Аналогично с остальными буквами.
) Достаточность условия. Пусть каждое из чисел , , не больше суммы двух других. Можно считать , тогда условие эквивалентно единственному неравенству . Запишем сначала по кругу все букв , затем, начиная с некоторой «первой», будем, двигаясь по часовой стрелке, вставлять между буквами по одной букве , пока они не кончатся. Ввиду того, что букв не больше, чем букв , они закончатся не позже, чем перед первой буквой , и соседних букв не появится. Между каждыми ближайшими буквами будет стоять буква . После окончания букв продолжим тот же процесс с буквами , которые будем писать сразу после очередной или сочетания , если мы уже прошли полный оборот и достигли места, следующего за первой вставленной . Ввиду того, что , в сумме букв и хватит, чтобы вставить их между всеми буквами , пройдя не меньше, чем полный оборот. С другой стороны, букв не больше, чем букв , они закончатся не позже, чем перед последней буквой , и соседних букв тоже не появится. Скажем, если каждой буквы будет поровну, по кругу будет раз записано сочетание из трёх букв .
Доказана необходимость условия
Сформулирован алгоритм правильной записи букв при соблюдении условия
Обосновано, что при применении алгоритма не возникает соседних букв
Обосновано, что при применении алгоритма не возникает соседних букв
Обосновано, что при применении алгоритма не возникает соседних букв