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