ещё одна задачка
Dec. 5th, 2002 10:03 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот ещё одна милая задачка (надеюсь, не надоел ещё?).
(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим знакомым и коллегам. В собрании этом есть немало интересного. Я впервые нашёл его в начале августа, после смерти Дейкстры, и тогда немного там пошарил, а сегодня опять вспомнил благодаря записи![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
smilga с переводом одного такого письма)
Даны два натуральных положительных числа: p и q. Кроме того, дан мешок, в котором лежит некоторое конечное количество целых чисел ("мешок" в отличие от "множества" символизирует тот факт, что они могут повторяться, т.е. там могут быть, например три тройки). Играем в следующую игру. Если в мешке есть два одинаковых числа, например два числа X, то достаём их из мешка, а вместо них кладём числа X+p и X-q (если в мешке есть несколько разных пар одинаковых чисел, выбираем любую). Затем повторяем ту же процедуру снова и снова. Если после какого-то шага в мешке не осталось пары одинаковых чисел, игра заканчивается.
Доказать, что игра закончится при любом выборе p и q и любом начальном состоянии мешка.
(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим знакомым и коллегам. В собрании этом есть немало интересного. Я впервые нашёл его в начале августа, после смерти Дейкстры, и тогда немного там пошарил, а сегодня опять вспомнил благодаря записи
smilga с переводом одного такого письма)Даны два натуральных положительных числа: p и q. Кроме того, дан мешок, в котором лежит некоторое конечное количество целых чисел ("мешок" в отличие от "множества" символизирует тот факт, что они могут повторяться, т.е. там могут быть, например три тройки). Играем в следующую игру. Если в мешке есть два одинаковых числа, например два числа X, то достаём их из мешка, а вместо них кладём числа X+p и X-q (если в мешке есть несколько разных пар одинаковых чисел, выбираем любую). Затем повторяем ту же процедуру снова и снова. Если после какого-то шага в мешке не осталось пары одинаковых чисел, игра заканчивается.
Доказать, что игра закончится при любом выборе p и q и любом начальном состоянии мешка.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Уточнение
Date: 2002-12-06 05:56 am (UTC)Re: Уточнение
Date: 2002-12-06 06:01 am (UTC)Я тут уже собрался решение давать, т.к. не заинтересовала задача людей, видимо.
доказательство
Date: 2002-12-06 06:09 am (UTC)2. разбиение не приводит к появлению 'дыр' больше чем p+q, а следовательно, границы мешка не могут бесконечно удаляться друг от друга.
для p <> q. каждое действие езменяет общую сумму всех чисел на p-q. так как общих интервал ограничен, общая сумма не может бесконечно увеличиваться или уменьшаться => игра заканчивается.
для p=q. сумма квадратов монотонно увеличивается. вместо x^2+x^2 после итерации получаем (x+p)^2+(x-q)^2 = (x+p)^2+(x-p)^2 = 2x^2+4p^2. так как сумма квадратов монотонно увеличивается, то циклов быть не может. а так как количесвто комбинаций ограничено, то игра закончится.
уфф. конечно, может и красивее можно доказать - мозги уже все сломал ж)
Re: доказательство
Date: 2002-12-06 06:21 am (UTC)уфф. конечно, может и красивее можно доказать
Вот как можно проще, или, скажем так, "абстрактнее". Начинаем с Ваших первых двух пунктов:
1. разбиение пары либо не изменяет мин и макс границы мешка (крайнее числа), либо расширяет их.
2. разбиение не приводит к появлению 'дыр' больше чем p+q, а следовательно, границы мешка не могут бесконечно удаляться друг от друга.
И заканчиваем так:
3. Если какое-то число X входит в мешок неограниченное кол-во раз в течение игры, то оно обязано и выходить из него неограниченное кол-во раз, т.к. кол-во чисел в мешке постоянно. Если X выходит неограниченное кол-во раз, то X+p входит неограниченное кол-во раз; начиная с X+p, получаем X+2p, и так продолжаем, пока не пересечём максимальную верхнюю границу в п. 2.
Значит, такого числа X вообще быть не может.
4. Раз каждое число X входит в мешок конечное число раз, и все эти X приходят из конечного интервала (п. 2), то есть конечное число ходов.
Re: доказательство
Date: 2002-12-06 06:30 am (UTC)Не давайте пока решения, интересно.
Re: доказательство
Date: 2002-12-06 07:03 am (UTC)А опровержение пункта 2, например p = 1, q = 1, а мешок таков:
Видно, что дыра явно превышает p + q, но при этом через 63 хода у нас будет два нуля.
Re: доказательство
Date: 2002-12-06 07:12 am (UTC)"наибольшая дыра никогда не будет больше максимума двух чисел: p+q и наибольшей начальной дыры".
док-во: посмотрите на любое содержимое мешка, отвечающее этому условию, и на то, как он будет выглядеть после следующего хода.
"следовательно, границы мешка не могут бесконечно удаляться друг от друга"
док-во: количество чисел в мешке конечно, длина дырок между ними ограничена, значит, "растянуть" их можно только на конечный промежуток.
"более того, эту границы можно заключить в одном постоянном промежутке (т.е. они не путешествуют во времени, например, так: 1-10, 2-11, 3-12 итп.)"
док-во: следует из ограниченности промежутка между границами и п. 1 .
Супер, спасибо!
Date: 2002-12-06 07:54 am (UTC)Re: доказательство
Я тут голову ломаю - как интервал выражается через p+q и начальный...
Кто б подумал, что просто максимальное из двух!
Да-а, у страха глаза-то велики...
Ну хоть до остального сам додумался - уже хорошо;(
From S.Lvovski
Date: 2002-12-06 06:49 am (UTC)pohozhe, vedet kuda -to ne tuda. Vi ne mogli bi popravit'?
Ochen' hotelos' bi zaglianut'...
Re: From S.Lvovski
Date: 2002-12-06 06:56 am (UTC)