Доказать существование числа с определённым свойством

[Ktina]

Дано натуральное число $k$.
Доказать, что существует натуральное число, кратное $k$, сумма цифр которого (в десятичной записи) даёт остаток 1 при делении на 4.

У этой задачи существует короткое и красивое решение. Скажем так, достаточно талантливый пятиклассник смог бы её решить.
Решение помещаю в оффтоп, дабы желающие подумать получили такую возможность:

(Решение)

Есть такая древняя задача: "Первоклассник Петя знает только цифру 1, сможет ли он написать число, делящееся на... скажем, 2018?".
Вспомнив эту древнюю задачу, я предпочитаю решать по аналогии.

Рассмотрим числа:

$$5, 54, 544, 5444, \dots $$

Отдирихлим их на остаток по модулю $k$ - какие-то два из них дадут одинаковый остаток. Возьмём эти два и вычтем из большего меньшее - получим число, кратное $k$, сумма цифр которого даёт остаток 1 при делении на 4, как и требовалось в исходной задаче.

[Pphantom]

Тема перемещена из форума «Загадки, головоломки, ребусы» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»

[Shadow]

Добавим условие:

Ktina в сообщении #1328878 писал(а):

"Первоклассник Петя знает только цифры 1 и 0

(Извиняюсь за изменеие цитата)

[JohnDou]

Практичное решение

(Оффтоп)

$s(n)$ - сумма цифр числа $n$
$c(n)$ - кол-во цифр числа $n$
Пусть $x\geq c(k)$ тогда $s(k\cdot 10^x - k)\equiv s(k)-1+9n+9(x-c(k))+9(c(k)-n-1)+10-s(k)\equiv x \text{ mod } 4$ (где $n$ максимальная степень 10 на которую делится $k$)

Т.е. для получения любого остатка нам нужно лишь выбрать подходящий $x$.

Рассмотрим примеры чтобы было понятнее.
1)$k=1234$
Пусть мы хотим чтобы сумма цифр кратного $k$ числа имела остаток $1$ при делении на $4$. Выберем $x$ так чтобы $x\geq c(k)=4$ и $x\equiv 1 \mod 4$. Одно из возможных решений этой системы $x=5$ и действительно $s(1234\cdot 10^5-1234)=s(123398766)= 1+2+3+3+9+8+7+6+6 \equiv 1 \text{ mod } 4$

2)$k=100$ и нам нужен остаток $2$
$x\geq c(k)=3$ и $x\equiv 2 \mod 4$. Возможное решение $x=6$: $s(100\cdot 10^6-100)=s(99999900)=4\cdot 9+2\cdot 9\equiv 2\mod 4$

Замечу что с помощью этого метода можно получить любой остаток $\mod n$ для суммы цифр числа кратного $k$ если выполняется $99...9\equiv 1 \mod n$(нужно лишь немного изменить $x$). Иными словами вышеупомянутая теорема верна для $2,5,7,10,100,8,98,998$ итп.

[Shadow]

JohnDou в сообщении #1329105 писал(а):

Рассмотрим примеры чтобы было понятнее.
1)$k=1234$
Пусть мы хотим чтобы сумма цифр кратного $k$ числа имела остаток $1$ при делении на $4$. Выберем $x$ так чтобы $x\geq c(k)=4$ и $x\equiv 1 \mod 4$. Одно из возможных решений этой системы $x=5$ и действительно $s(1234\cdot 10^5-1234)=s(123398766)= 1+2+3+3+9+8+7+6+6 \equiv 1 \pmod 4$

Другое возможное решение этой системы $x=21$ и тогда сумма цифр будет $189$. Увы.

А вообще для практичного решения достаточно проверить $k,2k,3k,\cdots$ недолго придется проверять. В первом примере будет $7k$, во втором - $2k$.

А как насчет нулей и единиц? Сможет ли Петя написать такое число?

UPD

Все правильно, $189\equiv 1 \pmod 4$. Я почему-то продолжал сумировать:)