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