Разбиение доски на части
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
У Васи есть словарь, состоящий из нескольких стобуквенных слов, содержащих только буквы 
и 
В каждую клетку таблицы
Вася хочет вписать либо букву 
либо букву 
так, чтобы каждый столбец таблицы был словом из словаря при чтении
сверху вниз, и каждая строка таблицы была словом из словаря при чтении слева направо. Чему равно наименьшее натуральное число 
такое, что если в словаре есть не менее 
различных слов, то Вася заведомо сможет заполнить таблицу нужным образом, независимо от
того, какие слова находятся в словаре?
Подсказка 1
Для начала давайте попробуем построить пример на как можно больше слов в словаре, чтоб таблицу составить было нельзя. Для этого попробуйте рассмотреть слова с определённым началом.
Подсказка 2
Давайте рассмотрим слова, которые начинаются на букву A, кроме слова из 100 букв A. Можно ли для таких слов составить таблицу?
Подсказка 3
Правильно, нельзя! А сколько же слов в этом словаре?
Подсказка 4
Верно, 2⁹⁹ - 1! Теперь попробуйте доказать, что для словаря из 2⁹⁹ слов всегда можно составить таблицу. Для начала разберемся со словами из 100 одинаковых букв. Если в словаре такое слово присутствует, то можно ли составить таблицу?
Подсказка 5
Ага, можно! Просто возьмем и заполним таблицу буквами этого слова. Теперь давайте забудем про слова из 100 одинаковых букв. Попробуйте разбить оставшиеся слова на пары так, чтобы если мы возьмем два слова из любой из этих пар, то таблицу мы сможем составить.
Подсказка 6
Попробуйте рассмотреть пары слов, которые получаются заменой всех букв B на A, а всех букв A на B.
Рассмотрим следующий словарь из 
слов: все слова, начинающиеся с буквы 
кроме слова из 100 букв 
Тогда Вася не сможет
заполнить таблицу. Действительно, в верхней строке будет какое-то слово, содержащее букву 
но тогда в столбце с этой буквой слово
должно начинаться на 
Докажем, если в 
не менее 
слов, то Вася сможет заполнить таблицу. Если в 
есть слово из ста букв 
то можно заполнить
всю таблицу только буквами 
Аналогично с 
Разобьем все остальные слова на пары: слово и инверсное ему (то есть получающееся
заменой всех 
на 
и всех 
на 
). Пар 
а слов в словаре 
Следовательно, найдутся два слова из одной пары. Пусть это
слова 
(начинается с 
) и 
(начинается с 
). Запишем в верхнюю строку слово 
Далее в каждом столбце, если он начинается с
запишем 
если он начинается с 
запишем 
Нетрудно проверить, что во всех строках также будут записаны 
или
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
