Название: На этот раз - теория игр. Отправлено: 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: |