ещё одна задачка
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}
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 и начальный...
Кто б подумал, что просто максимальное из двух!
Да-а, у страха глаза-то велики...
Ну хоть до остального сам додумался - уже хорошо;(