Sirion
Гений-Говорун
 Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
 |
� : Май 16, 2011, 11:36:52 � |
|
Как известно, далеко не все задачи из теории игр имеют свойство решаться. Шашки и шахматы тому примером, ня. В общем, я придумал задачку, но ещё не придумал решение. Если кто-то решит раньше, чем я выйду из запоя - честь ему и хвала.
Дан полный граф на эн вершинах. Играют двое, ходят по очереди. Каждый своим ходом удаляет рёбра, составляющие какой-либо простой цикл. Проигрывает тот, кто не может сделать ход. Классический вопрос: кто выиграет, как и почему?
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Um_nik
Гений-Говорун
Offline
Сообщений: 1161
СПАСИБО
-вы поблагодарили: 277
-вас поблагодарили: 342
Любовь - дело техники
|
|
� Ответ #1 : Май 16, 2011, 11:42:37 � |
|
Простой цикл - замкнутая ломаная?
|
|
|
|
|
Записан
|
|
|
|
Лев
Из мудрейших мудрейший
Offline
Сообщений: 2906
СПАСИБО
-вы поблагодарили: 1229
-вас поблагодарили: 1168
Искренне Ваш...
|
|
� Ответ #2 : Май 16, 2011, 11:46:00 � |
|
Ау, шашки уже просчитали  |
|
|
|
|
Записан
|
В действительности все не так, как на самом деле
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #3 : Май 16, 2011, 11:51:38 � |
|
Простой цикл - замкнутая ломаная?
Без самопересечений, ня. Иначе выигрывает всегда первый ^^ |
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #4 : Май 17, 2011, 22:22:27 � |
|
Некрасиво сформулировал. "Без самопересечений". В общем, отсылаю к педивикии: Простой цикл - цикл, не содержащий других циклов. Цикл - замкнутая цепь. Цепь - маршрут, в котором все рёбра различны... Я не знаю, до какого уровня простоты нужно продолжать.
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Аш
Новенький
Offline
Сообщений: 5
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3
|
|
� Ответ #5 : Май 17, 2011, 22:48:10 � |
|
А что, если первый удаляет цикл из n-1 ребра?
Извините, фигню сказал.
|
|
|
|
� Последнее редактирование: Май 17, 2011, 22:51:53 от Аш �
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #6 : Май 17, 2011, 23:19:48 � |
|
Несомненно, первый может это сделать. Но для n>4 это не даёт ему немедленного выигрыша.
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Аш
Новенький
Offline
Сообщений: 5
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3
|
|
� Ответ #7 : Май 17, 2011, 23:30:08 � |
|
Ну, для пятерки дает выигрыш (второй берет один из оставшихся треугольников, первый - другой). Потому я и подумал.
А для шестерки дает немедленный проигрыш.
|
|
|
|
� Последнее редактирование: Май 17, 2011, 23:33:03 от Аш �
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #8 : Май 17, 2011, 23:42:42 � |
|
Да, здесь всё не настолько просто...
|
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Аш
Новенький
Offline
Сообщений: 5
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3
|
|
� Ответ #9 : Май 18, 2011, 12:42:14 � |
|
Для шестерки вроде тоже первый выигрывает, если ставит тройку первым ходом. Если не тройку - проигрывает (если я не ошибся).
Для n=3, 4, 5 первый тоже выигрывает, если первым ходом рисует цикл из трех вершин.
|
|
|
|
|
Записан
|
|
|
|
Sirion
Гений-Говорун
Offline
Сообщений: 1095
СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278
|
|
� Ответ #10 : Май 18, 2011, 13:21:55 � |
|
Для шестерки вроде тоже первый выигрывает, если ставит тройку первым ходом. Если не тройку - проигрывает (если я не ошибся).
Для n=3, 4, 5 первый тоже выигрывает, если первым ходом рисует цикл из трех вершин.
Вы тоже поняли, что для решения в тетради проще инвертировать задачу и рисовать рёбра, а не стирать их? =) |
|
|
|
|
Записан
|
sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
|
|
|
Аш
Новенький
Offline
Сообщений: 5
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3
|
|
� Ответ #11 : Май 18, 2011, 14:44:02 � |
|
Типа того  |
|
|
|
|
Записан
|
|
|
|
|
