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