Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Инвариант игра II
СообщениеДобавлено: 19 сен 2019, 19:45 
Не в сети
Продвинутый
Зарегистрирован:
11 ноя 2018, 20:08
Сообщений: 96
Cпасибо сказано: 50
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
По кругу висят 20 лампочек. За один ход можно соединить проводом 2 любых лампочки, не пересекая ранее проведённых проводов. Проигрывает тот игрок, который не может сделать ход. Какой игрок победит, первый или второй?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 19 сен 2019, 20:02 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7026
Cпасибо сказано: 110
Спасибо получено:
1637 раз в 1489 сообщениях
Очков репутации: 278

Добавить очки репутацииУменьшить очки репутации
-

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 19 сен 2019, 21:13 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 4048
Cпасибо сказано: 255
Спасибо получено:
706 раз в 663 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Второй выиграет.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 19 сен 2019, 21:14 
Не в сети
Продвинутый
Зарегистрирован:
11 ноя 2018, 20:08
Сообщений: 96
Cпасибо сказано: 50
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
Второй выиграет.

Как это объяснить?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 19 сен 2019, 21:23 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 4048
Cпасибо сказано: 255
Спасибо получено:
706 раз в 663 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
В планарном графе из 20 вершин 54 ребра.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 19 сен 2019, 21:37 
Не в сети
Продвинутый
Зарегистрирован:
11 ноя 2018, 20:08
Сообщений: 96
Cпасибо сказано: 50
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
В планарном графе из 20 вершин 54 ребра.

То есть, если чётное количество рёбер, значит победит второй (чётный)?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 20 сен 2019, 07:11 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7026
Cпасибо сказано: 110
Спасибо получено:
1637 раз в 1489 сообщениях
Очков репутации: 278

Добавить очки репутацииУменьшить очки репутации
Ответил моментально центральная симметрия, потом подумал что не обязательно точки равномерно расположены и стер. Потом футбол начался и не до задачи. А сейчас понял, что точки можно двигать.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 20 сен 2019, 12:02 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 4048
Cпасибо сказано: 255
Спасибо получено:
706 раз в 663 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Задача, очевидно, про графы и про их планарность, поэтому расположение лампочек и проводов не имеет значения. Если имеет, то неинтересно — сразу побеждает первый, соединяя две соседние лампочки проводом, который делает петли вокруг всех остальных лампочек.
swan писал(а):
ну вот первый проводит ребро не из этого графа, что делать?

А можно привести пример на графе меньшей размерности? На графах из 5 и 6 вершин я поигрался, на них возможности у теоретически проигрывающего воспрепятствовать проигрышу я не смог найти.
Вообще, у планарного графа с [math]n \geqslant 3[/math] вершинами наибольшее число рёбер равно [math]3n-6[/math], поэтому при чётном количестве вершин выигрывает второй, при нечётном — первый. Строгое доказательство на ум не приходит пока (и это я ещё футбол не смотрел, только счёт знаю :( ).

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Booker48 "Спасибо" сказали:
alinamu
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 20 сен 2019, 12:40 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 4048
Cпасибо сказано: 255
Спасибо получено:
706 раз в 663 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Доказывать надо вот что: если в планарном графе с [math]n[/math] вершинами число рёбер [math]l < 3n-6[/math], то в него можно добавить ещё одно ребро, не нарушая планарности.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Инвариант игра II
СообщениеДобавлено: 20 сен 2019, 12:55 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7026
Cпасибо сказано: 110
Спасибо получено:
1637 раз в 1489 сообщениях
Очков репутации: 278

Добавить очки репутацииУменьшить очки репутации
То есть получается, что второй выигрывает как угодно?
Выглядит очень лихо. Если правда, то не знал такого факта про планарные графы (да я и вообще про них мало знаю), но кажется что доказать это достаточно сложно.
Путь с симметрией выглядит в этом плане более привлекательным

P.S. А утверждение выглядит действительно правдоподобным. Я для проверки взял граф Петерсена, удалил 3 "лишних" ребра для планарности и начал добавлять ребра. И, к своему удивлению, действительно до 24 ребер удалось добить...

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 17 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Инвариант игра

в форуме Начала анализа и Другие разделы школьной математики

alinamu

1

197

16 сен 2019, 23:31

Метод инвариант

в форуме Задачи со школьных и студенческих олимпиад

alinamu

1

257

11 сен 2019, 20:49

Новый инвариант СТО? Почему нет?

в форуме Палата №6

ivashenko

1

296

17 сен 2018, 13:06

Игра

в форуме Задачи со школьных и студенческих олимпиад

vredinka-kate

3

397

11 сен 2016, 15:07

Игра в рулетку

в форуме Палата №6

elnino

7

531

21 авг 2015, 17:57

Игра в кости

в форуме Теория вероятностей

themechanic

4

379

29 янв 2015, 13:42

Игра в бридж

в форуме Теория вероятностей

[dominika]

10

832

06 ноя 2014, 13:30

Математическая игра

в форуме Начала анализа и Другие разделы школьной математики

zakharova-forum

4

382

11 июл 2020, 15:23

Игра Эренфойхта

в форуме Дискретная математика, Теория множеств и Логика

Hnoy

1

92

20 дек 2020, 13:49

Игра 2048

в форуме Размышления по поводу и без

Nataly-Mak

5

792

02 авг 2021, 16:57


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2022 MathHelpPlanet.com. All rights reserved