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