2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 На плоскости отмечены 100 точек. Игра.
Сообщение25.07.2015, 17:53 


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

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

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

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

 Профиль  
                  
 
 Re: На плоскости отмечены 100 точек. Игра.
Сообщение25.07.2015, 18:18 


29/06/15
270
[0,\infty )
karandash_oleg в сообщении #1040506 писал(а):
За один ход можно соединить стрелкой две точки, если
их не соединяли раньше...
...в этом направлении. То есть после АВ можно провести еще ВА.
Увы. это не спасло задачу, 2й выиграет при любом числе $n$ точек. Пока не скажу как :D

 Профиль  
                  
 
 Re: На плоскости отмечены 100 точек. Игра.
Сообщение25.07.2015, 18:22 
Заслуженный участник
Аватара пользователя


09/09/14
6086
iancaple в сообщении #1040513 писал(а):
...в этом направлении.

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

 Профиль  
                  
 
 Re: На плоскости отмечены 100 точек. Игра.
Сообщение25.07.2015, 18:26 


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

 Профиль  
                  
 
 Re: На плоскости отмечены 100 точек. Игра.
Сообщение25.07.2015, 19:36 


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

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


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

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

Изображение

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

Изображение

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group