На плоскости отмечены 100 точек. Игра.

[karandash_oleg]

Здравствуйте, помогите, пожалуйста, разобраться задачей.

На плоскости отмечены 100 точек. Играют двое, ходят по очереди. За один ход можно соединить стрелкой две точки, если
их не соединяли раньше. При этом запрещается проводить стрелку, после появления которой из любой точки можно будет добраться
по стрелкам до любой другой. Проигрывает тот, кто не может сделать очередного хода без нарушения правил. Кто выиграет при
правильной игре: тот, кто ходит первым, или его партнер?

Имеет ли здесь значение ориентация ребер? Рассмотрим три точки, подразумевая, что ориентация важна. Если там возникнет такая ситуация $1\to 2, 3\to 2$, то как бы не походил первый игрок, невозможно будет попасть из $3\to 1$ никаким путем, но при этом все ходы уже сделаны. Получается, что первый проигрывает, потому как походить не сможет.

Если рассмотреть игру с $3$ точками, то всегда выигрывает второй игрок. Если с четырьмя, то первый. Далее я рассмотрел пока что игру без ориентированных ребер. Для образования полного графа требуется $99\cdot 50$ ходов, значит последний ход придется сделать второму игроку, значит он проигрывает. Но как тут учесть ориентацию ребер, мне пока что не очевидно.

[iancaple]

karandash_oleg в сообщении #1040506 писал(а):

За один ход можно соединить стрелкой две точки, если
их не соединяли раньше...

...в этом направлении. То есть после АВ можно провести еще ВА.
Увы. это не спасло задачу, 2й выиграет при любом числе $n$ точек. Пока не скажу как

[grizzly]

iancaple в сообщении #1040513 писал(а):

...в этом направлении.

Вы уверены? Я тоже успел подумать об этом и задача в формулировке ТС мне показалась интереснее (но я ещё не решал).

[iancaple]

Не уверен. Я тоже на это надеюсь
UPD: Нет, не интереснее. То,что точки можно соединять стрелкой только в одном направлении, один раз за игру, приводит к выигрышу 2-го, так как четно число ребер в полном неориентированном графе. Предположим, пути из $A$ в $B$ еще не было, точки $X,Y$ еще не соединены никаким ребром, и очередной ход игрока $X\to Y$ проигрывающий, так как он делает путь из $A$ в $B$. Это значит, что из $A$ уже можно пройти в $X$, и из $Y$ уже можно пройти в $B$. Тогда ход $Y\to X$ не проигрывающий, из $A$ по-прежнему нельзя пройти в $Y$, и новая стрелка не может быть составной частью важного пути.
Значит, на каждом ходу каждый игрок может уклониться от проигрыша, и кончится тем, что ТС и предсказывал
Неясно осталось: какую же версию имели в виду? Решения по длине и по "идейному наполнению" одинаковы.

[karandash_oleg]

Все-таки имелось ввиду ровно то, что написано в условии задачи.

Цитата:

Предположим, пути из $A$ в $B$ еще не было, точки $X,Y$ еще не соединены никаким ребром, и очередной ход игрока $X\to Y$ проигрывающий, так как он делает путь из $A$ в $B$

Кстати, вот при игре из трех точек первый может выигрывает.

Первый расклад (второй ход $A\to B$ или $B\to A$ первого игрока приведет его к победе)



Второй расклад



Остальные расклады симметричны