Задача для 9 класса (делимость чисел...)

[Helga007]

В середине числа 1996(между 19 и 96) вставить несколько цифр так, чтобы получившееся число делилось на 1997. При этом надо обойтись наименьшим количеством цифр. Помогите, пжлс

[nnosipov]

Обозначьте через $x$ число, которое образовано вставленными цифрами (пусть этих цифр будет $n$). Попробуйте составить какое-нибудь соотношение с этим $x$.

[Helga007]

Я так и сделала, у меня вот что получилось: итак между 19 и 96 вставляем число из m цифр. Получаем число $19\cdot 10^{m+2}+k\cdot 100+96$ которое должно делиться на 1997. Сл-но, $19\cdot 10^{m+2}+k\cdot 100+96=1997y$. Далее, преобразуем $19(10^{m+2}-100y)+k\cdot 100+96-97y=0$. Отсюда $96-97y$ делится на 100, сл-но, $100-4-(100-3)y=100\cdot l\to 100-100y-4+3y=100l\to 3y-4=100l\to y=(100l+4)/3$

-- Чт окт 06, 2011 18:42:27 --

А вот дальше не пойму, надо еще как-то ограничить перебор.

[nnosipov]

Helga007, Вам бы про сравнения по модулю узнать. Тогда эта задачка очень легко бы решилась. В любом случае забудьте про $y$, а думайте, как определить $k$ --- вот Ваша цель. Вот если бы Вы сумели поделить 96 на 100 по модулю 1997 ... Это $k$ тогда и нашлось бы (не сразу, конечно, а, так скажем, с 3-й попытки).

[Klad33]

for x from 99 to 999 do z := 1000000+900000+100*x+96: if z mod 1997 = 0 then print(z); fi: od:

Это прога в Maple

Ответ такой: 1933096

[nnosipov]

Klad33, это совершенно неправильный подход. Задачу можно и должно решать вручную.

[Helga007]

так и я могу)))))))) весь смысл в док-ве

[Klad33]

nnosipov в сообщении #490095 писал(а):

Klad33, это совершенно неправильный подход. Задачу можно и должно решать вручную.

Это подход конца 19 века.
Принимал участие в конференции в Сколково, там эта тема была очень остро поставлена. Похожие примеры как раз и рассматривали (речь шла об обычных вузах, а не академиях имени Стеклова).

[nnosipov]

Klad33 в сообщении #490100 писал(а):

Принимал участие в конференции в Сколково, там эта тема была очень остро поставлена. Похожие примеры как раз и рассматривали.

Вы о чём? В Сколково обсуждают, как нужно решать школьные олимпиадные задачи? Или Вы полагаете, что Maple всегда выручит? Использовать здесь компьютер просто бессмысленно.

[Helga007]

только не дискуссию по Сколково, лучше помогите))))Кстати, я не знаю такого понятия делить число на число по модулю, что такое сравнение по модулю я представляю, а вот....нет

[Toucan]

Klad33, как Вам было справедливо замечено

nnosipov в сообщении #490095 писал(а):

Задачу можно и должно решать вручную.

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

[nnosipov]

Helga007 в сообщении #490105 писал(а):

что такое сравнение по модулю я представляю

То есть, Вы понимаете смысл записи $a \equiv b \pmod{m}$? Если да, то мы Вас быстренько обучим делению по модулю.

[Helga007]

конечно понимаю, это значит что числа а и b имеют одинаковые остатки от деления на m)

[nnosipov]

Helga007 в сообщении #490113 писал(а):

конечно понимаю, это значит что числа а и b имеют одинаковые остатки от деления на m)

Хорошо. Вот простейшие правила действий со сравнениями: сравнения по одному и тому же модулю можно почленно складывать (вычитать), а также умножать. (А вот делить почленно, вообще говоря, нельзя.) Выше Вы получили равенство $19\cdot 10^{m+2}+k\cdot 100+96=1997y$. Давайте запишем его в виде сравнения:

$$ 19 \cdot 10^{m+2}+k \cdot 100+96 \equiv 0 \pmod{1997} $$

и попробуем отсюда найти $k$. Вот если бы это было не сравнение, а обычное уравнение, то как бы Вы выразили $k$?

[Helga007]

Может так, $100k\equiv -96-19\cdot 10^{m+2}(\mod 1997)$. Но 100 взаимно просто с 1997 значит можно разделить на 100 обе части сравнения. $k\equiv (-96-19\cdot 10^{m+2})/100(\mod 1997)$ Так?