Разделы 
Дополнительно
Задача по математике - 1712
2019-01-20 
В языке жителей Банановой Республики количество слов превышает количество букв в их алфавите. Докажите, что найдется такое натуральное $k$, для которого можно выбрать $k$ различных слов, в записи которых используется ровно $k$ различных букв.
Решение:
Пусть в алфавите жителей Банановой Республики $n$ букв. Занумеруем их по порядку. Выпишем на доску слово, содержащее первую букву. Затем выпишем на доску слово, содержащее вторую букву. Затем - третью, и т. д. до тех пор, пока не выпишем на доску слово, содержащее $n$-ю букву. Таким образом мы выпишем на доску $n$ слов, в записи которых используется ровно $n$ различных букв. Сотрем с доски повторяющиеся слова (т. е. если какое-то слово написано $m$ раз, то сотрем $m - 1$ такое слово). Вместо стертых слов выпишем на доску новые так, чтобы на доске оказалось написано ровно $n$ различных слов. Это можно сделать, поскольку слов больше $n$. При этом мы не используем новых букв, так как букв всего $n$, и каждая из них где-то записана на доске. В записи этих $n$ слов используется ровно $n$ различных букв, что и требовалось.
Замечание. Приведенное решение показывает, что в утверждении задачи можно взять $k = n$ - числу букв в алфавите.
В языке жителей Банановой Республики количество слов превышает количество букв в их алфавите. Докажите, что найдется такое натуральное $k$, для которого можно выбрать $k$ различных слов, в записи которых используется ровно $k$ различных букв.
Решение:
Пусть в алфавите жителей Банановой Республики $n$ букв. Занумеруем их по порядку. Выпишем на доску слово, содержащее первую букву. Затем выпишем на доску слово, содержащее вторую букву. Затем - третью, и т. д. до тех пор, пока не выпишем на доску слово, содержащее $n$-ю букву. Таким образом мы выпишем на доску $n$ слов, в записи которых используется ровно $n$ различных букв. Сотрем с доски повторяющиеся слова (т. е. если какое-то слово написано $m$ раз, то сотрем $m - 1$ такое слово). Вместо стертых слов выпишем на доску новые так, чтобы на доске оказалось написано ровно $n$ различных слов. Это можно сделать, поскольку слов больше $n$. При этом мы не используем новых букв, так как букв всего $n$, и каждая из них где-то записана на доске. В записи этих $n$ слов используется ровно $n$ различных букв, что и требовалось.
Замечание. Приведенное решение показывает, что в утверждении задачи можно взять $k = n$ - числу букв в алфавите.
