Форум умных людей

Как известно, далеко не все задачи из теории игр имеют свойство решаться. Шашки и шахматы тому примером, ня. В общем, я придумал задачку, но ещё не придумал решение. Если кто-то решит раньше, чем я выйду из запоя - честь ему и хвала.

Дан полный граф на эн вершинах. Играют двое, ходят по очереди. Каждый своим ходом удаляет рёбра, составляющие какой-либо простой цикл. Проигрывает тот, кто не может сделать ход. Классический вопрос: кто выиграет, как и почему?

Простой цикл - замкнутая ломаная?

Ау, шашки уже просчитали ;)

Без самопересечений, ня. Иначе выигрывает всегда первый ^^

Некрасиво сформулировал. "Без самопересечений". В общем, отсылаю к педивикии: Простой цикл - цикл, не содержащий других циклов. Цикл - замкнутая цепь. Цепь - маршрут, в котором все рёбра различны... Я не знаю, до какого уровня простоты нужно продолжать.

А что, если первый удаляет цикл из n-1 ребра?

Извините, фигню сказал.

Несомненно, первый может это сделать. Но для n>4 это не даёт ему немедленного выигрыша.

Ну, для пятерки дает выигрыш (второй берет один из оставшихся треугольников, первый - другой). Потому я и подумал.

А для шестерки дает немедленный проигрыш.

Да, здесь всё не настолько просто...

Для шестерки вроде тоже первый выигрывает, если ставит тройку первым ходом. Если не тройку - проигрывает (если я не ошибся).
Для n=3, 4, 5 первый тоже выигрывает, если первым ходом рисует цикл из трех вершин.

Вы тоже поняли, что для решения в тетради проще инвертировать задачу и рисовать рёбра, а не стирать их? =)

Типа того :)