Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

ещё одна задачка

Вот ещё одна милая задачка (надеюсь, не надоел ещё?).

(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим знакомым и коллегам. В собрании этом есть немало интересного. Я впервые нашёл его в начале августа, после смерти Дейкстры, и тогда немного там пошарил, а сегодня опять вспомнил благодаря записи smilga с переводом одного такого письма)

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

Доказать, что игра закончится при любом выборе p и q и любом начальном состоянии мешка.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments