Разбиение доски на части

Рассмотрим следующий словарь из слов: все слова, начинающиеся с буквы кроме слова из 100 букв Тогда Вася не сможет заполнить таблицу. Действительно, в верхней строке будет какое-то слово, содержащее букву но тогда в столбце с этой буквой слово должно начинаться на

Докажем, если в не менее слов, то Вася сможет заполнить таблицу. Если в есть слово из ста букв то можно заполнить всю таблицу только буквами Аналогично с Разобьем все остальные слова на пары: слово и инверсное ему (то есть получающееся заменой всех на и всех на ). Пар а слов в словаре Следовательно, найдутся два слова из одной пары. Пусть это слова (начинается с ) и (начинается с ). Запишем в верхнюю строку слово Далее в каждом столбце, если он начинается с запишем если он начинается с запишем Нетрудно проверить, что во всех строках также будут записаны или