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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Теория игр
СообщениеДобавлено: 30 окт 2019, 07:11 
Не в сети
Начинающий
Зарегистрирован:
15 окт 2019, 19:31
Сообщений: 15
Cпасибо сказано: 6
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Петя и Вася играют в следующую игру. Вася заполняет числами от 1 до 100 клетки
таблицы 10 × 10 (каждое — по одному разу). Петя хочет пройти шахматным королём от левого края доски до правого. При этом если он ставит короля на какую-то
клетку, то он обязан заплатить Васе такое число рублей, которое на ней написано. Сколько Петя заплатит Васе при правильной игре? (Петя хочет заплатить как
можно меньше, Вася — получить как можно больше.)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 08:39 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5771
Cпасибо сказано: 90
Спасибо получено:
1272 раз в 1161 сообщениях
Очков репутации: 246

Добавить очки репутацииУменьшить очки репутации
Интересно ваши мысли по задаче услышать

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 09:03 
Не в сети
Начинающий
Зарегистрирован:
15 окт 2019, 19:31
Сообщений: 15
Cпасибо сказано: 6
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Интересно ваши мысли по задаче услышать

Ну я вчера 30 минут думал над задачей, у меня были такие мысли : я хотел придумать такую расстановку чисел, при которой Вася получит наибольшую прибыль, я думал что Пети, дабы минимизировать свои затраты достаточно ходить на клетки с наименьшим номером, тогда Вася может разбить доску на два треугольника, в треугольник в котором будет находиться король, расставить числа от 99 до 49, а во втором остальные числа, конечная клетка с номером сто. У меня просто нет опыта в решении таких задач, она мне показалась достаточно сложной, поэтому решил спросить тут.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 09:05 
Не в сети
Оракул
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 875
Cпасибо сказано: 27
Спасибо получено:
101 раз в 97 сообщениях
Очков репутации: 9

Добавить очки репутацииУменьшить очки репутации
Это игра в 2 хода: сначала Вася пишет числа, потом Петя выбирает маршрут. Задача Пети несравненно проще Васиной.
Похоже, задача NP-полная. Т.е. перебором, а на ТИ с прибором.
Кто лучше?Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 09:31 
Не в сети
Начинающий
Зарегистрирован:
15 окт 2019, 19:31
Сообщений: 15
Cпасибо сказано: 6
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
atlakatl писал(а):
Это игра в 2 хода: сначала Вася пишет числа, потом Петя выбирает маршрут. Задача Пети несравненно проще Васиной.
Похоже, задача NP-полная. Т.е. перебором, а на ТИ с прибором.
Кто лучше?Изображение

А я думал таблица сначала полностью заполняется, а потом Петя начинает делать ходы.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 10:36 
Не в сети
Оракул
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 875
Cпасибо сказано: 27
Спасибо получено:
101 раз в 97 сообщениях
Очков репутации: 9

Добавить очки репутацииУменьшить очки репутации
dakanjadatut писал(а):
таблица сначала полностью заполняется, а потом Петя начинает делать ходы.

Так и есть. Приведите маршрут Пети дешевле моего.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 12:39 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 5771
Cпасибо сказано: 90
Спасибо получено:
1272 раз в 1161 сообщениях
Очков репутации: 246

Добавить очки репутацииУменьшить очки репутации
dakanjadatut писал(а):
Ну я вчера 30 минут думал над задачей

dakanjadatut писал(а):
У меня просто нет опыта в решении таких задач, она мне показалась достаточно сложной


Ха. Если уделять олимпиадной задаче 30 минут, то никогда опыта не наберете. Самый значительный прогресс наблюдается только при самостоятельном решении. И не стесняйтесь тратить на задачу (не только эту) по несколько часов в день. И если за 2 недели не получилось решить, то тогда уже обращайтесь за помощью.
Задача, не сказать, чтобы простая, но и не сложная, решение доступно восьмикласснику.

Подобные задачи решаются путем последовательных шагов с разных сторон, приближаясь к оптимальному значению. Сначала попробуем очень грубо прикинуть какая сумма гарантированно позволит Пете пройти королем. Самая примитивная стратегия: у нас есть 10 строк, выберем строку с наименьшей суммой. Сумма чисел в таблице 5050, значит сумма в минимальной строке не превышает 5050/10=505.
Дальше заходим с другой стороны. Какую сумму может себе гарантировать Вася? Этот шаг за вас тоже проделали. Вам осталось показать, что в приведенной таблице любой путь обойдется не менее чем в 500 рублей.
И следующий шаг: улучшите стратегию Пети.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
dakanjadatut
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 16:17 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 5364
Cпасибо сказано: 506
Спасибо получено:
403 раз в 379 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
atlakatl писал(а):
Кто лучше?


Я Вася )))

Изображение

Наверное можно немного улучшить с 765 где-то до 800 с хвостиком.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 17:24 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 2676
Cпасибо сказано: 164
Спасибо получено:
448 раз в 418 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
А что такое 765?
Здесь, Василий Иванович, Петька потратит существенно меньше, пройдя хотя бы по нижней строке.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Теория игр
СообщениеДобавлено: 30 окт 2019, 21:53 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 5364
Cпасибо сказано: 506
Спасибо получено:
403 раз в 379 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
Booker48 писал(а):
А что такое 765?
Здесь, Василий Иванович, Петька потратит существенно меньше, пройдя хотя бы по нижней строке.


Вот блин, а я почему-то домыслил, глядя на предыдущий рисунок, что Петька должен пройти из левого верхнего в правый нижний угол! Так вот я и пытался ошкурить его по полной на этом маршруте.

Кстати, такая задача будет поинтереснее и мой результат можно улучшить.

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Теория Демпстера-Шафера (теория доверия)

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

Yaroslav555

0

537

02 янв 2014, 01:13

Теория вероятности или теория вероятностей?

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

Gagarin

19

362

09 май 2020, 08:57

Теория игр

в форуме Исследование операций и Задачи оптимизации

maked0n

6

675

30 янв 2014, 20:52

Теория игр

в форуме Исследование операций и Задачи оптимизации

youi

0

129

14 ноя 2018, 19:20

Теория L

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

remarka

0

247

26 дек 2015, 13:01

Теория

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

qwerty12317140

3

142

10 дек 2018, 19:39

Теория вер-ти

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

nATALE

7

387

03 мар 2014, 19:47

ФСР. (теория)

в форуме Линейная и Абстрактная алгебра

Silas

1

317

11 фев 2012, 11:28

Теория

в форуме Пределы числовых последовательностей и функций, Исследования функций

Mathnope

4

168

24 апр 2018, 15:30

Теория Игр

в форуме Исследование операций и Задачи оптимизации

ANDREYBRO

6

321

24 фев 2018, 23:47


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



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

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


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

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

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

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