ещё одна задачка
Вот ещё одна милая задачка (надеюсь, не надоел ещё?).
(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим знакомым и коллегам. В собрании этом есть немало интересного. Я впервые нашёл его в начале августа, после смерти Дейкстры, и тогда немного там пошарил, а сегодня опять вспомнил благодаря записи smilga с переводом одного такого письма)
Даны два натуральных положительных числа: p и q. Кроме того, дан мешок, в котором лежит некоторое конечное количество целых чисел ("мешок" в отличие от "множества" символизирует тот факт, что они могут повторяться, т.е. там могут быть, например три тройки). Играем в следующую игру. Если в мешке есть два одинаковых числа, например два числа X, то достаём их из мешка, а вместо них кладём числа X+p и X-q (если в мешке есть несколько разных пар одинаковых чисел, выбираем любую). Затем повторяем ту же процедуру снова и снова. Если после какого-то шага в мешке не осталось пары одинаковых чисел, игра заканчивается.
Доказать, что игра закончится при любом выборе p и q и любом начальном состоянии мешка.
(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим знакомым и коллегам. В собрании этом есть немало интересного. Я впервые нашёл его в начале августа, после смерти Дейкстры, и тогда немного там пошарил, а сегодня опять вспомнил благодаря записи smilga с переводом одного такого письма)
Даны два натуральных положительных числа: p и q. Кроме того, дан мешок, в котором лежит некоторое конечное количество целых чисел ("мешок" в отличие от "множества" символизирует тот факт, что они могут повторяться, т.е. там могут быть, например три тройки). Играем в следующую игру. Если в мешке есть два одинаковых числа, например два числа X, то достаём их из мешка, а вместо них кладём числа X+p и X-q (если в мешке есть несколько разных пар одинаковых чисел, выбираем любую). Затем повторяем ту же процедуру снова и снова. Если после какого-то шага в мешке не осталось пары одинаковых чисел, игра заканчивается.
Доказать, что игра закончится при любом выборе p и q и любом начальном состоянии мешка.