Question

11. Все натуральные числа покрасили в пять цветов. Докажите, что найдётся миллион чисел одного цвета с одинаковой суммой цифр.

Answer 1

Числа 1, 10, 100, 1000, ... все имеют одинаковую сумму цифр (1). Их бесконечно много, значит, среди них найдется миллион чисел, раскрашенных одинаково (в противном случае каждого из пяти цветов было бы не больше 999999, а всего - не более 4999995).

Answer 2

Для доказательства этого утверждения мы можем воспользоваться принципом Дирихле (или принципом ящиков и шаров). Принцип Дирихле гласит, что если n объектов размещаются в большем числе, чем n мест, то как минимум одно из мест должно содержать два или более объекта.

В данном случае, каждое натуральное число можно рассматривать как последовательность его цифр. Поскольку у нас есть пять различных цветов, мы можем рассматривать числа как объекты, которые мы размещаем в пяти "ящиках" (цветах) в зависимости от суммы их цифр.

Мы можем определить "сумму цифр" числа как сумму всех его цифр. Теперь, давайте рассмотрим миллион чисел (1, 2, 3, ..., 1,000,000). Эти числа могут иметь суммы цифр от 1 до 45 (потому что наибольшая сумма цифр у числа 1,000,000 равна 9 + 9 + 9 + 9 + 9 = 45).

Если мы разместим каждое из этих миллиона чисел в одном из пяти "ящиков" в зависимости от суммы их цифр, то по принципу Дирихле как минимум один из "ящиков" должен содержать как минимум 1,000,000 / 5 = 200,000 чисел. Эти числа имеют одинаковую сумму цифр, и их миллион.

Таким образом, мы доказали, что найдется миллион чисел одного цвета с одинаковой суммой цифр.