100-значные числа, которые делятся на 3

Назовем интересными 100-значные числа, в записи которых нет нулей, а каждая цифра встречается не более 20 раз. Докажите, что ровно треть из этих чисел делятся на 3.

Задача была предложена на 53 Уральском турнире юных математиков.

Разобьём все такие числа на 9 групп: которые начинаются на 1, на 2, на 3, ..., на 8, на 9.

Каждому числу из первой группы сопоставим такое число: ко всем цифрам, меньшим 9, прибавим по 1, а вместо девяток запишем единицы. В получившемся числе каждая цифра тоже встретится не более 20 раз. При этом мы получим число из второй группы. При этом каждому числу из второй группы сопоставим число аналогичным образом: из всех цифр, кроме 1, вычтем по 1, а вместо единиц напишем девятки. Опять же, В получившемся числе каждая цифра тоже встретится не более 20 раз.

Таким образом, мы нашли взаимно однозначное соответствие числам из первой и второй групп, т.е. в этих группах поровну чисел.

Ну, а мы по числу из первой группы так можем получить число из второй группы. По числу из второй группы так получим число из третьей. И так далее. Таким образом, все наши числа разбились на 9 групп, в которых поровну элементов.

Теперь рассмотри произвольное число. Каждый раз после преобразования остаток числа при делении на 3 увеличивается на 1 (потому что 100 имеет остаток 1 при делении на 3). Из каждого числа такими преобразованиями мы получаем цикл из 9 чисел, по одному из каждой группы, удовлетворяющих условиям задачи. Ровно три из них делится на 3.

Значит, ровно треть всех интересных чисел делится на 3.