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

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

Автор:  david1710 [ 28 апр 2015, 03:59 ]
Заголовок сообщения:  Задачка про ведра

Помогите, пожалуйста, с доказательством:

Даны два ведра по m и n литров. Известно, что НОД (m,n)=1. Как доказать, что с помощью этих ведер можно отмерить любое кол-во воды <=Min {m,n}?

Cпасибо!

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

david1710, Вы дословно привели условие задачи?

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

Да. Естественно, что имеются в виду натуральные величины.

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

david1710, хорошо, спасибо! Значит, имеется одно ведро ёмкостью [math]m[/math] литров и одно ведро ёмкостью [math]n[/math] литров. При этом ёмкости вёдер выражаются взаимно простыми числами. Требуется доказать, что с помощью этих вёдер можно отмерить любое количество воды, выражаемое положительным рациональным числом, не превосходящим меньшую из ёмкостей. Я правильно понимаю?

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

Andy писал(а):
david1710, хорошо, спасибо! Значит, имеется одно ведро ёмкостью [math]m[/math] литров и одно ведро ёмкостью [math]n[/math] литров. При этом ёмкости вёдер выражаются взаимно простыми числами. Требуется доказать, что с помощью этих вёдер можно отмерить любое количество воды, выражаемое положительным рациональным числом, не превосходящим меньшую из ёмкостей. Я правильно понимаю?


Да, только выражаемое кол-во воды должно быть натуральное.

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

david1710, почему натуральное? Об этом в условии задачи ничего не сказано.

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

Давайте начнем хотя бы с этого.

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

david1710, пожалуйста, давайте начнём с уточнения условия задачи. Зачем выполнять лишние действия? Итак, количество воды выражается положительным рациональным числом, не превосходящим меньшую из ёмкостей вёдер? В частности, оно может выражаться натуральным числом.

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

Если [math]m[/math] и [math]n[/math] - натуральные взаимно простые числа,то по моему,для доказательства можно использовать алгоритм Евклида.
В частности,доказав,что уравнение [math]am+bn=1[/math] имеет решение.([math]a[/math] и [math]b[/math]-целые числа.)

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

david1710, и, наверное, нужно полагать, что у нас, помимо вёдер и источника воды, есть ещё и некоторая ёмкость (неограниченной вместимости?)?.. Похоже, для решения задачи нужно применить теорему о делении с остатком.

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

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