Номер 13.14, страница 120 - гдз по алгебре 11 класс учебник Мерзляк, Номировский

Глава 3. Элементы комбинаторики. Бином Ньютона. Параграф 13. Метод математической индукции. Готовимся к изучению новой темы - номер 13.14, страница 120.

Учебник.

13.14. В селе 3000 жителей. Докажите, что по крайней мере у трёх из них одинаковые инициалы.

Решение 2.

13.14. Для решения этой задачи воспользуемся обобщенным принципом Дирихле. В этой задаче жителями села являются «голуби», а все возможные уникальные инициалы — «клетки».

1. Определим количество «клеток» (возможных инициалов). Инициалы обычно состоят из первых букв имени и фамилии (или имени, отчества и фамилии). Будем исходить из наиболее консервативной оценки, предполагая, что инициалы состоят из двух букв (например, первая буква имени и первая буква фамилии), чтобы максимизировать вероятность совпадения. В русском алфавите 33 буквы. Однако имена, фамилии и отчества не начинаются с букв «ь» (мягкий знак) и «ъ» (твёрдый знак). Таким образом, для каждой буквы в паре инициалов есть $33 - 2 = 31$ возможный вариант. Общее количество возможных уникальных пар инициалов равно: $M = 31 \times 31 = 961$ Итак, у нас есть 961 «клетка».

2. Применим принцип Дирихле. В селе $N = 3000$ жителей («голубей»), которых нужно «рассадить» по $M = 961$ «клетке». Мы хотим доказать, что хотя бы в одной «клетке» окажется не менее трёх «голубей».

Воспользуемся методом доказательства от противного. Предположим, что утверждение неверно, то есть у любых трёх жителей села инициалы различны. Это означает, что каждую возможную комбинацию инициалов имеют не более двух человек.

При таком предположении максимальное количество жителей в селе можно рассчитать, умножив количество всех возможных инициалов на 2: Максимальное число жителей = $M \times 2 = 961 \times 2 = 1922$ человека.

Однако по условию в селе проживает 3000 человек. Получаем противоречие, так как фактическое число жителей больше максимально возможного при нашем предположении: $3000 > 1922$

Это противоречие доказывает, что наше исходное предположение было неверным. Следовательно, по крайней мере одна комбинация инициалов должна принадлежать как минимум трём жителям.

Ответ: Утверждение доказано. Так как максимальное число людей при условии, что инициалы совпадают не более чем у двоих, составляет $1922$, а в селе живёт $3000$ человек ($3000 > 1922$), то по принципу Дирихле обязательно найдутся по крайней мере трое жителей с одинаковыми инициалами.