Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: Sirion от Июнь 21, 2011, 22:13:23



Название: На этот раз - теория игр.
Отправлено: Sirion от Июнь 21, 2011, 22:13:23
Как обычно, от балды придумал условие, а решать прямо сейчас лень. Впрочем, я почти уверен, что задача решаемая, и если никто меня не опередит - займусь сам.

Есть палка целой длины N, которая в процессе игры разламывается на палки также целой длины. Каждый игрок своим ходом может взять несколько палок одинаковой длины (возможно, одну), сложить из вместе и переломить одинаковым образом. Проигрывает тот, кто не может сделать ход (т.е. тот, на чьём ходу палка уже разломана на N палок длины 1).

Думаю, не нужно объяснять, что обычно требуется в игровых задачах  8)


Название: Re: На этот раз - теория игр.
Отправлено: Um_nik от Июнь 22, 2011, 05:32:32
Ухожу, не могу заняться.
Пока лишь рез-ты небольшого перебора: -+-++-+-+-+
(от N=1 до N=11)


Название: Re: На этот раз - теория игр.
Отправлено: Sirion от Июнь 22, 2011, 08:56:33
Ну, из очевидных вещей: если для  N первый проигрывает, то для N+1 первый выигрывает. А если игрок проигрывает в случае, когда одновременно разрешается переламывать лишь одну палку, единственный для него способ выиграть - создать ситуацию, когда на его ходу возникают три палки равной длины.


Название: Re: На этот раз - теория игр.
Отправлено: Um_nik от Июнь 22, 2011, 15:28:06
Ой, ошибся в самом начале, потом все неправильно пошло :(
Видимо спал еще, хотя это не оправдание, конечно.

Пока что первый выигрывает при четных N


Название: Re: На этот раз - теория игр.
Отправлено: Um_nik от Июнь 22, 2011, 16:36:27
Пока сумбурно основные моменты того, что когда-то станет доказательством (скорее всего, не моим))

1. Начинающий выигрывает при четных N и проигрывает при нечетных.

2. План выигрыша за Начинающего при четных N - первым ходом отломить палку длиной 1, таким образом приведя игру к началу, только N - нечетное, а он сам - Второй.

3. Тот, после чьего хода сумма длин палок с длиной не меньше 2 ("значащие" палки) равна утроенному кол-ву таких палок, выигрывает.

4. План выигрыша за Второго при нечетных N - стремиться к выполнению п.3

5. При увеличении кол-ва "значащих" палок сумма их длин не увеличивается, при уменьшении на n - сумма уменьшается на 2n, если кол-во не изменяется, то сумма уменьшается на k, где k - число разломанных палок.

6. В соответствии с п.5 при нечетных N после хода Начинающего четность суммы длин "значащих" палок не совпадает с четностью их утроенного кол-ва, т.е. равны они быть не могут. И наоборот, после хода Второго они совпадают, значит когда-то будут равны.
Кроме случаев, когда за ход ломается четное кол-во палок. Соответственно, Второй, в свой ход, должен в первую очередь уничтожать скопления палок длиною 2 в кол-ве более одной штуки путем разламывания максимального возможного нечетного числа таких палок. А на отламывания единичных палок от четного числа палок длиной более 2 отвечать тем же. Одновременно эти проблемы возникнуть, по понятным причинам, не могут.

ЗЫ. Вполне строго получилось, вроде как (:


Название: Re: На этот раз - теория игр.
Отправлено: Лев от Июнь 22, 2011, 16:59:51
По мне, тоже имеют место вопросы чета/нечета, надо бы усложнить игру.

Сирион, а почему идеи на фабрику не выкладываешь? :)


Название: Re: На этот раз - теория игр.
Отправлено: moonlight от Июнь 22, 2011, 19:17:15
если есть несколько палок одинаковой длины, и я хочу сломать палку этой длины, я не обязан ломать их все?


Название: Re: На этот раз - теория игр.
Отправлено: BIVES от Июнь 23, 2011, 08:11:00
Чтобы выиграть достаточно чтобы сопернику всегда доставались все палки нечетной длины.
Так как в этом случае возможны 3 варианта
1) сопернику достались все палки длины 1 - он проиграл
2) после хода соперника образовалась 1 палка четной длины тогда отламывая от нее палку длины 1 отдаем сопернику все палки нечетной длины
3)  после хода соперника образовалось несколько палок одинаковой четной длины (было несколько палок одинаковой нечетной длины он сложил вместе какое-то число из них и сломал) тогда складываем все эти палки четной длины вместе и отламывая от них палки длины 1 отдаем сопернику все палки нечетной длины.
Таким образом если изначально было четное число палок, то выигрывает 1 игрок иначе 2 игрок.


Название: Re: На этот раз - теория игр.
Отправлено: Лев от Июнь 23, 2011, 08:13:25
Еще раз повторю предложение перенести идейку на фабрику, чтобы сделать посложнее (совместными усилиями).


Название: Re: На этот раз - теория игр.
Отправлено: BIVES от Июнь 23, 2011, 08:15:37
Усложнить повидемому можно, но скорее всего случая всеравно будет 2 четный и нечетный.
Хотя, можно усложнить, например, так если после вашего хода есть нескольео палок длиной большей 1, то вы можете запретить сопернику ломать одну из них.


Название: Re: На этот раз - теория игр.
Отправлено: Sirion от Июнь 23, 2011, 12:38:02
Еще раз повторю предложение перенести идейку на фабрику, чтобы сделать посложнее (совместными усилиями).
А стоит? Я имею в виду, что простая задача порой лучше, чем искусственно усложнённая. Что касается естественного усложнения - я его уже давно придумал. Собственно, текущая задача является лишь упрощением изначальной, где два игрока ломали шахматную доску)


Название: Re: На этот раз - теория игр.
Отправлено: ☭-Изделие 20Д от Июнь 25, 2011, 11:54:55
Игра - правда не от балды, а из Форта Баярд. Наверное все помнят:
14 палочек, 2 человека берут по очереди 1-3 штуки.
Найдите - беспроигрышную тактику игры.
Т.е. доказать , что с этой игрой в Баярде игроков просто кидают
В качестве подсказки если кому надо
Показать скрытый текст


Название: Re: На этот раз - теория игр.
Отправлено: Sirion от Июнь 25, 2011, 13:13:04
Но это же совсем просто...


Название: Re: На этот раз - теория игр.
Отправлено: ☭-Изделие 20Д от Июнь 25, 2011, 14:01:18
Но это же совсем просто...
Я тоже так думаю, но самое сложное объяснить домашним то что ведётся нечестная игра. Главное уметь считать до 4-х. Правда у меня из скачанных по просьбе игр, попалась одна где Повелитель темрявы(так называют играющего от форта) умудрился как-то проиграть игроку :ass:


Название: Re: На этот раз - теория игр.
Отправлено: Sirion от Июнь 25, 2011, 14:18:28
Помню, когда я был в шестом классе, у нас во дворе была традиция играть на фишки с покемонами в различные игры (не считая собственно игры в фишки). Так, кстати, я научился карточному шулерству. Но суть не в этом.

Я придумал игру. В верхнем левом углу доски стоит король, игроки двигают его поочерёдно. Для хода доступно только пять направлений - те, при которых сумма расстояний до нижнего и правого края не уменьшается. Выигрывает тот, кто приведёт короля в правое нижнее поле.

В общем, моя коллекция существенно пополнилась, ня.


Название: Re: На этот раз - теория игр.
Отправлено: Лев от Июнь 26, 2011, 09:14:32
Ч-ч-чего?


Название: Re: На этот раз - теория игр.
Отправлено: Alex2R от Июнь 26, 2011, 09:29:45
В задании не сказано, что игроков двое, но я так понимаю все в своих решениях от этого отталкиваются?


Название: Re: На этот раз - теория игр.
Отправлено: ☭-Изделие 20Д от Июнь 26, 2011, 09:43:01
Ну, из очевидных вещей: если для  N первый проигрывает, то для N+1 первый выигрывает. А если игрок проигрывает в случае, когда одновременно разрешается переламывать лишь одну палку, единственный для него способ выиграть - создать ситуацию, когда на его ходу возникают три палки равной длины.
Извиняюсь, если в условии , чтото сам запутал, но вроде не вижу
А с ЧЕГО ВЫ ВЗЯЛИ, ЧТО ПАЛОЧКИ ПЕРЕЛАМЫВАЮТСЯ? Ничего подобного - Изначально 14 штук - ДВА человека берут поочерёдно произвольное количество 1-4 шт. Проигрывает тот кто должен вытащить последнюю, ПРОПУСКАТЬ ХОД НЕ РАЗРЕШАЕТСЯ!!!


Название: Re: На этот раз - теория игр.
Отправлено: ☭-Изделие 20Д от Июнь 26, 2011, 09:43:47
имхо - Ходящий первым проиграет всегда


Название: Re: На этот раз - теория игр.
Отправлено: moonlight от Июнь 27, 2011, 18:43:18
Наверное имеется ввиду что сумма расстояний не должна увеличиваться. Стратегия состоит в том чтобы с красного поля перемещать короля на синее. Тот кто двигает короля с синего поля проигрывает.
(http://s51.radikal.ru/i132/1106/df/7fd6a211f268.jpg) (http://www.radikal.ru)


Название: Re: На этот раз - теория игр.
Отправлено: Sirion от Июнь 27, 2011, 23:57:55
moonlight, именно.


Название: Re: На этот раз - теория игр.
Отправлено: Um_nik от Июнь 28, 2011, 20:05:14
Сирион, ты как-то условие коряво написал))
А задачку такую нам давали на доп.занятиях в школе. Ничего сложного.


Название: Re: На этот раз - теория игр.
Отправлено: Игорь... от Июнь 29, 2011, 10:07:53
с 14-ью палочками есть беспроигрышная стратегия если ты второй))))


Название: Re: На этот раз - теория игр.
Отправлено: Sirion от Июнь 29, 2011, 10:34:17
Сирион, ты как-то условие коряво написал))
Хм, а ведь действительно.


Название: Re: На этот раз - теория игр.
Отправлено: ☭-Изделие 20Д от Июнь 29, 2011, 17:11:25
с 14-ью палочками есть беспроигрышная стратегия если ты второй))))
Насчет второго это ясно - сначала всегда добивать до 4, а вот что делать первому?


Название: Re: На этот раз - теория игр.
Отправлено: moonlight от Июль 02, 2011, 20:08:38
В игре с 14 палочками очевидно выигрывает первый. Сначала берёт 1, а потом 3 раза столько чтобы в сумме со вторым было по 4. Остаётся 1 которую берёт второй.
Или я условие неправильно понял?


Название: Re: На этот раз - теория игр.
Отправлено: ☭-Изделие 20Д от Июль 02, 2011, 20:36:59
В игре с 14 палочками очевидно выигрывает первый. Сначала берёт 1, а потом 3 раза столько чтобы в сумме со вторым было по 4. Остаётся 1 которую берёт второй.
Или я условие неправильно понял?
Всё почти так, НО когда первый берет - 1, второй отвечает тем, что добивает до 4 нк и т.д по Вапшему сценарию. Т.е. первый всегда обречен.


Название: Re: На этот раз - теория игр.
Отправлено: moonlight от Июль 02, 2011, 21:12:52
Добивать до 4 будет не второй а первый. Если второй в ответ на взятую 1 палку возьмет 3 то первый возьмет снова 1. 1+(3+1)+(3+1)+(3+1). Последнюю 1 берет второй.


Название: Re: На этот раз - теория игр.
Отправлено: Лев от Июль 03, 2011, 12:56:02
Всё почти так, НО когда первый берет - 1, второй отвечает тем, что добивает до 4 нк и т.д по Вапшему сценарию. Т.е. первый всегда обречен.

Первый обречен не всегда, а в том случае, если палочек изначально 1+4n. В других случаях - обречен второй  :yesgirl: