Остатки и делимость по модулю степеней тройки

Число поэтому мы можем отдельно воспользоваться признаками делимости на 9 и на 25.

Начнем с признака равноостаточности при делении на 25: число дает такой же остаток при делении на 25, что и число, образованное его последними двумя цифрами. В нашем случае, чтобы число делилось на 25, оно должно оканчиваться либо на 00, либо на 25, либо на 50, либо на 75. Так как по условию число состоит только из нулей и единиц, подходит лишь 00. Итак, мы выяснили, что число оканчивается на 00.

Теперь, определив однозначно последние две цифры, чтобы сделать число минимальным, нужно минимизировать число без двух последних цифр. Воспользуемся признаком равноостаточности при делении на 9: число дает такой же остаток при делении на 9, что и его сумма цифр. В нашем случае необходимо, чтобы число делилось на 9, поэтому и сумма цифр должна делиться на 9. Нули в записи не меняют сумму цифр числа, поэтому сумму цифр, делящуюся на 9, мы можем получить только из единиц. Если сумма цифр числа будет 18 или больше, то нам придется использовать хотя бы 18 единиц, и тогда в числе будет 20 или больше знаков, а у нас есть пример на меньшее число. Если сумма цифр числа равна 9, то нужно использовать девять единиц. Так как наличие нулей в записи на делимость не повлияет, но лишь увеличит количество знаков в числе, а значит и его значение, то минимальным подходящим числом является 111111111. Приписав к этому числу два нуля в конец, мы получаем искомый ответ.

Замечание. Обратите внимание на два важных момента. Во-первых, мы можем минимизировать число без двух последних цифр только потому, что они определились однозначно. Если бы у нас получилось несколько вариантов последних двух цифр, то мы бы не могли так просто их отбросить, пришлось бы рассматривать несколько случаев и в каждом искать минимум, а уже потом выбирать самое маленькое число.

Во-вторых, было бы грубой ошибкой написать, что число тем меньше, чем меньше его сумма цифр. Это не правда: но Обратите внимание, как мы обошли эту проблему при написании решения: мы отдельно сказали, что случай с суммой цифр 18 или более нам не подходит, так как у нас есть пример на меньшее количество знаков. А уже потом объяснили, почему при сумме цифр 9 наше число минимальное.