МОШ 2022, 10 класс, задача 6

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