ещё одна задачка
Вот ещё одна милая задачка (надеюсь, не надоел ещё?).
(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим ( Read more... )
(сначала несколько слов, откуда она. Я её нашёл сегодня, гуляя наугад по архиву неформальных статей, заметок и наблюдений покойного Эдгара Дейкстры, знаменитого учёного в области программирования. Дейкстра писал их (обычно, кстати, от руки или на пишущей машинке), размножал и посылал своим ( Read more... )
Comments 11
Reply
Я тут уже собрался решение давать, т.к. не заинтересовала задача людей, видимо.
Reply
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. так как сумма квадратов монотонно увеличивается, то циклов быть не может. а так как количесвто комбинаций ограничено, то игра закончится.
уфф. конечно, может и красивее можно доказать - мозги уже все сломал ж)
Reply
уфф. конечно, может и красивее можно доказать
Вот как можно проще, или, скажем так, "абстрактнее". Начинаем с Ваших первых двух пунктов:
1. разбиение пары либо не изменяет мин и макс границы мешка (крайнее числа), либо расширяет их.
2. разбиение не приводит к появлению 'дыр' больше чем p+q, а следовательно, границы мешка не могут бесконечно удаляться друг от друга.
И заканчиваем так:
3. Если какое-то число X входит в мешок неограниченное кол-во раз в течение игры, то оно обязано и выходить из него неограниченное кол-во раз, т.к. кол-во чисел в мешке постоянно. Если X выходит неограниченное кол-во раз, то X+p входит неограниченное кол-во раз; начиная с X+p, получаем X+2p, и так продолжаем, пока не пересечём максимальную верхнюю границу в п. 2.
Значит, такого числа X вообще быть не может.
4. Раз каждое число X входит в мешок конечное число раз, и все эти X приходят из конечного интервала (п. 2), то есть конечное число ходов.
Reply
Не давайте пока решения, интересно.
Reply
А опровержение пункта 2, например p = 1, q = 1, а мешок таков:
число: 0 1 2 3 4 5 6
количество: 1 0 0 0 0 0 64
Видно, что дыра явно превышает p + q, но при этом через 63 хода у нас будет два нуля.
Reply
pohozhe, vedet kuda -to ne tuda. Vi ne mogli bi popravit'?
Ochen' hotelos' bi zaglianut'...
Reply
Reply
Leave a comment