ВСОШ 2025, 11 класс, задача 10

Ответ. При .

Решение. Положим . Покажем сначала, как выложить карточки так, чтобы больше попарно не пересекающихся идеальных наборов не нашлось. Для удобства обозначим буквы в алфавитном порядке через ; через будем обозначать последовательность из карточек, на каждой из которых написана буква .

Наш ряд будет состоять из блоков , выписанных друг за другом в этом порядке. Блок выглядит как

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

Действительно, предположим, что нашёлся идеальный набор, в котором нет особых карточек. Найдётся индекс такой, что буква этого набора встречается не правее блока (подходит хотя бы ); выберем наименьшее такое . Если карточка нашего набора встречается левее , то , и также встречается в наборе левее , то есть не правее ; это противоречит минимальности . Значит, встречается именно в блоке , то есть написана на особой карточке, что и требовалось.

Осталось показать, что попарно не пересекающихся идеальных наборов выбрать всегда можно. При обозначим через множество из идеальных наборов, не имеющих общих букв, кроме, возможно, (оно существует по условию). Мы выберем из каждого множества по набору так, чтобы в них не было общих карточек.

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

Пусть наборы из уже выбраны. Если не существует полезной карточки с буквой , то уже выбранные наборы содержат карточек с буквой , каждая из которых встречается меньше раз в наборах в . Выкинув эти наборы, будем считать, что карточки с в наборах из не содержатся в уже выбранных наборах (если полезная карточка с буквой есть, это уже выполнено), и в не меньше наборов.

Далее, выбранный набор содержит других карточек, каждая из которых содержится максимум в одном наборе из ; выкинув все эти наборы, оставим в как минимум наборов, не пересекающихся с уже выбранными. Среди этих наборов максимум содержат полезные карточки с буквами, отличными от ; выбрав любой набор, не содержащий такой карточки, мы завершим шаг.

После завершения -го шага мы получим попарно не пересекающихся идеальных набора, что и требовалось.