Помогите с задачкой!!!, по программированию Опции

[Romix]

Может кто знает алгоритм А то я недогоняю
Задача такая:
Из 27 предметов, лежащих на столе двое играющих поочередно забирают не менее одного и не более четырех предметов. Игра заканчивается, когда будут забраны все предметы. Выигравшим считается тот игрок , у которого по окончинии игры остается четное количество предметов.


Нужно найти беспройгрышный алгоритм решения В зависимости от того кто первый ходит...

[lunatikov]

Обобщённый алгоритм.
n - макс. возможное число предметов за один ход (у тебя это 4),
i*(n+1) + 1 - формула для подсчета узловых точек или количества оставшихся предметов ( i*5+1 ), i=1,...до бесконечности,
У тебя получается такая последовательность: 6, 11, 16, 21, 26.
Задачей является первым захватить узловую точку. Если первый игрок знает эту стратегию он всегда выиграет. Если нет, второй игрок может перехватить инициативу.
Итак, первый ход: берём один предмет и попадаем в узловую точку.
Далее пусть х - количество предметов взятых противником, и берём (n+1)-x предметов, что обеспечивает попадание в след.узл.точку.
Последний ход: у тебя остаётся 6-х предметов, считаем свои предметы и забираем либо все, либо оставляем 1 предмет для четности.
Должно сработать.

p.s. Правда задачка осложняется тем, что в последнюю узловую точку 6 ты должен попасть имея четное количество предметов!

Сообщение было отредактировано lunatikov: 13.10.2005 - 11:08

[lunatikov]

Предлагаю версию № 2 (улучшенную).
Узловые точки - это количество оставшихся предметов.
По формуле i*(n+1+1) получаем следующую последовательность:
6, 12, 18, 24
Основной стратегией для каждого игрока является захват узловой точки или ей предшествующей, имея у себя ЧЕТНОЕ количество предметов.
Итак для первого игрока, первый шаг: берём два предмета.
Далее на каждом интервале (который находится между узловыми точками и равен 6) : если начинаем ход с самого начала интервала, то берём один предмет, следующим ходом берём максимально возможное нечётное число предметов не выходя за рамки интервала, иначе сразу берём максимально возможное чётное число предметов также не выходя за рамки интервала.
То есть на каждом интервале имеем четное число предметов, что и приводит к победе первого игрока!
Второму игроку остаётся только ждать ошибки первого и придерживаться указанной выше основной стратегии.
Теперь точно должно сработать!

[boroda76]

выигрывает начинающий,но за первых ход он далжен взять 4 предмета.

[Romix]

Спасибо за алгоритм.
Вроде работает. Ща сижу комбинации все перебираю)))

[boroda76]

я уже перебрал , это единственный вариант
я такие задачи очень люблю и уважаю , можно ли разширить токую тему?

[lunatikov]

boroda76
Я тоже не против. Но для этого надо наполнить алгоритмами данную тему, а затем уже спросить модераторов о возможности организации раздела типа "Занимательные алгоритмы".

[Ann]

boroda76, lunatikov
Думаю, на отдельный раздел это не потянет. Развивайте темы в этом разделе.