Число, делящееся на 79, с как можно меньшей суммой цифр

[gipokrat]

Придумайте натуральное число, делящееся на 79, с как можно меньшей суммой цифр.

[Rak so dna]

Num = 120001, Sum = 4
Num = 1200010, Sum = 4
Num = 10010011, Sum = 4
Num = 12000100, Sum = 4
Num = 100100110, Sum = 4
Num = 120001000, Sum = 4
Num = 1000000012, Sum = 4
Num = 1001001100, Sum = 4
Num = 1200010000, Sum = 4

[gipokrat]

Rak so dna
Удалось ли Вам доказать, что суммы 2 и 3 невозможны?

[worm2]

Ну что тут можно сказать?
Остатки от деления чисел с суммой цифр 1 (ну то есть степеней десятки) на 79 могут принимать значения из множества $A=\{1, 10, 21, 52, 46, 65, 18, 22, 62, 67, 38, 64, 8\}$.
Не то, чтобы я ожидал увидеть в этом множестве нулик. Или даже 78. Мне больше интересно, как бы половчее это множество получить вручную, без калькулятора (иначе задача стремительно теряет в интересности).
Идём дальше. Если мы хотим, чтобы число с суммой цифр два делилось на 79 нацело, нам достаточно проверить числа $10^k+1$, т.е. из этого множества плюс единичка (благодаря тому, что 10 и 79 взаимно просты).
Как мы уже заметили, 78 не принадлежит множеству, а поэтому счастья здесь нету.
Но нет его и дальше Чтобы это заметить, нужно от множества $A$ взять сумму каждого элемента с каждым по модулю 79, и искать среди них 78 (чтобы, добавив единичку, получить ноль).
Этот процесс, кажется, уже совершенно не поддаётся ручному счёту (в объёме, приличествующем для олимпиадной задачи). Могу только сообщить, что по результатам расчётов 78 не найдено, зато найдено 77, что закрывает вопрос о минимальной сумме на числе 4. Конкретное число искать совершенно не интересно.
gipokrat, у вас есть короткое ручное решение?

[gipokrat]

worm2 в сообщении #1719415 писал(а):

...
gipokrat, у вас есть короткое ручное решение?

Увы, пока нет.
Но любопытно, что если в условии заменить 79 на меньшее натуральное число, то ответ никогда не будет равен 4.
Зато для числа 41 ответ будет 5. А для чисел 158 и 187 ответ тоже 4.

[waxtep]

Я, конечно, понимаю, что эта шутка уже могла приесться, но раз задача решена, то почему бы не $\overline{10}_{79}$

[lel0lel]

Лишние нули в младших разрядах можно отбросить, это не меняет делимости и суммы цифр. Далее, поочерёдно рассмотреть следующие сравнения: $10^k\equiv -1\pmod{79}, 10^k\equiv -2\pmod{79}, 2\cdot 10^k\equiv -1\pmod{79}$. В каждом из них у левой и правой частей различные символы Лежандра. Левая часть -- вычет, правая -- невычет. Поэтому решений у этих сравнений нет. Остаётся рассмотреть $10^k+10^m+1\equiv 0\pmod{79}$. Можно просто все остатки $10^k$ по модулю $79$ выписать, последовательно умножая единицу на $10$, и вычисляя остаток, получим $\{{1, 10, 21, 52, 46, 65, 18, 22, 62, 67, 38, 64, 8}\}$. Остаётся немного проверок. В принципе, даже символы Лежандра ни к чему, просто перебор остатков.

(Оффтоп)

Сейчас вижу, что переписал решение worm2