Математический форум Math Help Planet
http://mathhelpplanet.com/

Задачка про ведра
http://mathhelpplanet.com/viewtopic.php?f=10&t=40685
Страница 3 из 3

Автор:  Andy [ 28 апр 2015, 09:12 ]
Заголовок сообщения:  Re: Задачка про ведра

david1710, если задача "от Вас", то её нужно тщательно проанализировать. Вряд ли у меня это получится. Но в форуме участвуют профессиональные математики - им и флаг в руки! Успехов Вам! :)

Автор:  Andy [ 28 апр 2015, 09:14 ]
Заголовок сообщения:  Re: Задачка про ведра

Shadows, "ёмкость" была нужна мне для получения количества воды, выражаемого рациональным, не целым числом.

Автор:  andrei [ 28 апр 2015, 10:09 ]
Заголовок сообщения:  Re: Задачка про ведра

Рекомендую посмотреть решение задачи М129 из задачника "Кванта"."Квант" №11 1972 год,стр.42

Автор:  Shadows [ 28 апр 2015, 10:36 ]
Заголовок сообщения:  Re: Задачка про ведра

Пусть [math]m=tn-a, a<n,\gcd(n,a)=1[/math]
И [math]b_k[/math] - остаток в суде маленкой емкости ([math]n[/math]) после [math]k[/math] заполнения суда боьшой емкости ([math]m[/math])

[math]b_k=ka \bmod n[/math]

Действительно

[math]b_{k+1}=-[(m-b_k) \bmod n] \bmod n[/math]

[math]b_{k+1}=-[(tn-a-ka)\bmod n] \bmod n=(k+1)a \bmod n[/math]

Осталось доказать, что [math]ka[/math], где [math]k=1,2,\cdots n[/math] пробегает все остатки по модулю [math]n[/math]

От противного: Пусть [math]k_1a\equiv k_2a \pmod n[/math]. Тогда [math](k_2a-k_1a)\;\vdots\; n[/math]

[math]a(k_2-k_1)\;\vdots\; n[/math], что невозможно, т.к [math]a[/math] взаимнопростое с [math]n[/math] и [math]0<k_2-k_1<n[/math]

Автор:  Shadows [ 28 апр 2015, 12:36 ]
Заголовок сообщения:  Re: Задачка про ведра

Чуть проще, но на том же принципе. Наливаем из маленкого в большого суда. Пусть после [math]k[/math]-го заполнения большого суда в маленьком осталось [math]b_k[/math] литра воды. Общее количество использованной воды [math]km+b_k[/math] делится на [math]n[/math], следовательно [math]b_k \equiv -km \pmod n[/math]

Ну, а то что [math]-km(k=1,2\cdots n)[/math] пробегает все остатки по модулю [math]n[/math] доказал выше. Аналогично все.

Страница 3 из 3 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/