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

Логическая задача, но требует обьяснения
http://mathhelpplanet.com/viewtopic.php?f=10&t=35153
Страница 2 из 2

Автор:  ivashenko [ 27 июл 2014, 13:28 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

Задача будет решаться для всех множеств четного размера>2 и не иметь решения для множеств нечетного размера, потому что для выравнивания всех чисел необходимо привести множество модулей вычетов к виду: a0a0a0.....a0, в множествах четного размера это произойдет обязательно, в множествах нечетного размера это невозможно, их можно привести лишь к виду а0a0...0a и задача решается лишь в тривиальном случае, когда начальные цифры равны между собой.

Автор:  ivashenko [ 27 июл 2014, 13:33 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

Почему это произойдет в множествах четного размера?

Автор:  Andy [ 27 июл 2014, 13:37 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

ruslan1111 писал(а):
То есть, допустим наши числа - 4,5,6,7.
1,1,1,3
0,0,2,2
0,2,0,2
2,2,2,2 - числа сравнялись!!!! Будет ли так, для любых чисел??? Если да, то почему?

ruslan1111, извините, что не удержался и опять "влез" в тему. Но продолжая дальше, получим четыре нуля. Процесс завершён. Остаётся либо доказать, что в любом случае процесс завершится за конечное число шагов, либо привести контрпример. Здесь нужно думать.

Если же чисел три, то легко находится пример, показывающий, что процесс может и не завершиться:
[math]1~2~3[/math]

[math]1~1~2[/math]

[math]0~1~1[/math]

[math]1~0~1[/math]

[math]1~1~0[/math]

[math]0~1~1[/math]


Чтобы объяснить это, нужно углубиться в изучение теории чисел. Её, кстати, на математическом факцльтете ЛГУ раньше изучали только в седьмом семестре. :crazy:

Наверняка, натаскивая ваш класс к олимпиаде, преподаватель уделил время изложению свойств чётности-нечётности или даже элементам теории групп. :shock:

Автор:  ivashenko [ 27 июл 2014, 13:43 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

Уважаемый Andy, я вполне логично обосновал, почему невозможны варианты с нечетным количеством цифр в том числе и количеством 3. Теория чисел здесь нипричем.

Автор:  Andy [ 27 июл 2014, 13:45 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

ivashenko, а я Вам ничего и не писал.

Автор:  Andy [ 27 июл 2014, 14:01 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

ruslan1111, по-видимому, мой пример с тремя числами неверен. Ведь [math]0[/math] не является положительным числом. Как только мы его получаем, процесс следует считать завершённым на предыдущем шаге. Тогда, я думаю, в любом случае процесс завершится за конечное число шагов, потому что заменяя числа модулями их разностей, мы при каждой итерации сужаем располагаемое подмножество натуральных чисел. Это пока интуитивная гипотеза.

Полагаю, что тут то же обоснование, что и у алгоритма Евклида. :oops:

Автор:  Shadows [ 28 июл 2014, 09:12 ]
Заголовок сообщения:  Re: Логическая задача, но требует обьяснения

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

С тремя числами еще проще.

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