Здравствуйте, каждый из двух игроков имеет одинаковую колоду карт от 1 до n. Далее ведется игра по обычным правилам игры в пьяницу.Опишу коротко правила, если достоинства карт совпадают, то карты выбрасываются и не участвуют в игре,иначе выложивший карту большего достоинства, забирает обе карты и подкладывает их под свою колоду так, что карта большего достоинства оказывается самой нижней, а меньшего достоинства — второй снизу. После этого игроки вновь открывают верхнюю карту своей колоды.Игрок у которого не осталось карт проигрывает. Если же ни у кого не осталось то ничья. Нужно ответить на вопрос сможет ли победить второй игрок перетасовывая свои карты любым образом зная карты первого игрока. Нужен алгоритм как это можно сделать. Спасибо.

задан 25 Янв '14 15:05

изменен 27 Янв '14 16:34

Deleted's gravatar image


126

Вообще говоря, здесь можно гарантировать лишь ничью, потому что другой игрок может "тайно" пользоваться таким же алгоритмом :) Но если считать его "простаком", то тогда можно подстроить всё так, чтобы тузами выловить всех королей, а потом "свести" тузов вместе и вывести их из игры. Короли останутся самыми старшими, и постепенно всё перетаскают (сначала всех дам, потом валетов, и так далее). Я, кстати, на практике так делал в "мягкой" форме: не имея возможности тасовать, я взятые карты клал вниз в выгодном для себя порядке: если туз забрал короля, то я его клал за тузом, а "мелочь" - наоборот.

(25 Янв '14 17:09) falcao

первый не может пользоваться таким алгоритмом,а второй знает его карты,допустим у первого игрока следущая последовательность карт 2 3 4 1 в порядке сверху вниз.Как должен растосавать карты второй игрок,зная карты первого,чтобы выиграть,и есть у данной задачи алгоритм?

(25 Янв '14 17:19) ivan145

@ivan145: давайте уточним постановку задачи. Если второй игрок может перетасовывать свои карты в любой момент игры, зная карты первого, то алгоритм тривиален. Например, для Вашего примера я расставляю карты в порядке 2 4 1 3. У первого остаются 4 и 1, и я под них подкладываю нужные карты. Тогда 4 и 4 выходят, а 1 я забираю. Но если имелось в виду, что я имею право свои карты тасовать как угодно лишь перед началом игры, а дальше всё идёт "на автомате", то тогда задача делается более интересной. Правда, здесь тогда надо уточнить порядок складывания карт вниз.

(25 Янв '14 19:54) falcao

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

(25 Янв '14 20:37) ivan145

@ivan145: в таком виде задача приобрела точную и интересную формулировку. Я подумаю над возможным алгоритмом. Я проверил, что при n=3 исход ничейный, а что будет при больших n, я пока не знаю.

P.S. На данный момент проверено, что при n=4 порядок карт у первого игрока 1 4 2 3 "непобедим", то есть при любом выборе порядка карт вторым игроком, ничья первому игроку гарантирована. Сейчас буду смотреть случай n=5 (на компьютере, конечно же).

(26 Янв '14 0:38) falcao

@ivan145: я придумал "ручной" алгоритм игры, который можно описать в простом виде (с доказательством, что он работает). При $%n\ge5$% это всегда возможно; при $%n\ge4$% есть две "ничейные" ситуации (против 1423 и против 4123 выиграть нельзя). При $%n=3$% выигрыш возможен против 213, 231, 321. Завтра (то есть уже фактически сегодня) постараюсь описать всё в деталях.

(27 Янв '14 4:21) falcao

Falcao,жду детального разбора)

(27 Янв '14 14:10) ivan145
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
1

Очевидно, что при n=2 все исходы ничейные. При n=3 выиграть можно против трёх конфигураций: 213, 231, 321. Стратегия везде одинаковая: мы каждой карте противопоставляем следующую, где считается, что за $%n$% следует 1. Например, в первом случае надо перетасовать свои карты в порядке 321. Позиции 123, 132, 312 ничейные: против них не выиграть.

Теперь проанализируем случай $%n=4$%. Здесь из 24 конфигураций имеются ровно две ничейные: это 1423 и 4123. Проверка того, что никакая стратегия для них не подходит, осуществляется прямым перебором. В остальных случаях есть выигрышная стратегия, которую сейчас и опишем. Прежде всего, можно выделить те случаи, когда стратегию можно сформировать на основе предыдущей. Это те ситуации, когда среди карт первого игрока можно выделить три, расположенные по одному из типов 213, 231, 321. Здесь важен порядок следования чисел, а не сами числа. Например, 214 или 324 относятся к тому же типу, что и 213. Во всех таких случаях, где мы можем подобную подпоследовательность выделить, у нас есть стратегия. Например, для всех перестановок из списка 3214, 2314, 2134, 2143 мы можем свести вместе число 3, которое выйдет из игры, не влияя на её ход, и итогом будет то же, что было бы при игре с 214, что аналогично 213. В последнем случае мы бы использовали порядок карт 321. Против 214 это будет 421 (замена 3 на 4). Соответственно, против 3214 мы ставим 3421, против 2314 -- 4321 и так далее.

Посмотрим, какие перестановки не подходят под эту стратегию. Их имеется четыре. Все они должны начинаться с 1 или 4, потому что цифру 2 или 3 в начале мы можем сделать "средней", исключая одну из цифр, сводя всё к стратегии для 213 или 231. Далее, если в начале идёт 1, то дальше не должно идти 3 (она будет "средней" для 2, 3 и 4), а если идёт 4, то за ней будут идти 2 и 3 (ввиду того, что 432 "подобно" 321). Итого мы имеем три варианта: 1234, 1243, 1423, где к прежним стратегиям игру не свести. И есть ещё четвёртый вариант 4123. Больше с 4 ничего не начинается, так как если дальнейшие цифры не расположены в порядке возрастания, то мы берём 4 с двумя убывающими, что "подобно" 321.

Из перечисленных четырёх наборов можно выиграть против 1234 и 1243. Здесь уже не действует замена, основанная на переходе к следующей цифре, но годится замена (одна и та же для обоих случаев), где 1 заменяется на 3, 2 на 1, 3 на 4 и 4 на 2. То есть играем 3142 против 1234 и 3124 против 1243. Надо отметить, что выиграть при другом порядке карт не удастся.

Итак, случай $%n=4$% проанализирован, и теперь надо показать, что при $%n=5$% выигрыш всегда возможен. Ясно, что тогда он возможен и при $%n > 5$% -- карты старше 5 мы подкладываем точно такие же, как и у противника. Сейчас осталось проверить, что из любой перестановки пяти элементов мы можем оставить три или четыре так, что против такой конфигурации нам уже известна выигрышная стратегия (с учётом "подобия" конфигураций). Проверка тут достаточно простая. Если перестановка начинается с цифры от 2 до 4, то вычёркиванием одной из цифр мы делаем её "средней", сводя всё к 213 или 231. Если в начале стоит 1, то её вычёркивание приводит к успеху во всех случаях кроме 12534 и 15234 (когда на цифрах от 2 до 5 возникает то, против чего мы не умеем выигрывать). Но здесь в обоих случаях можно исключить 5, играя против 1234. Если же в начале стоит 5, до в двух заслуживающих рассмотрения случаях 51423 и 54123 мы умеем выигрывать против 543.

ссылка

отвечен 27 Янв '14 15:42

Falcao,я забыл сказать,что помимо исхода,нужно еще знать как именно будут расположены карты при выигрыше второго игрока.при n=2,3,4 вы расписали,а как именно раскладывать карты при n>=5,допустим есть перестановка 1 3 2 5 4 и по какому правилу надо растосавать свои карты второму игроку,чтобы выиграть.Т.к. при n>=5,вы сказали,что выигрыш есть всегда

(27 Янв '14 16:54) ivan145

@ivan145: у меня эта информация косвенно содержится в описании. См. то место, где я анализирую случай n=5 и перестановки, начинающиеся с 1. Далее я говорю, что при "списании" 1 возникает игра на 4 символах, и там мы умеем побеждать во всех случаях кроме двух. Это значит, что из 13254 делаем 3254, оно "подобно" 2143. Этот случай разобран: выделяем 213, где мы побеждаем при помощи 321. Тогда против 2143 мы побеждаем, "сводя" 4 и 4, то есть 3241. Увеличиваем всё на 1, и тогда 4352 побеждает против 3254. Наконец, 14352 выигрывает у 13254. Здесь все нужные приёмы описаны, и их хватает.

(27 Янв '14 18:37) falcao

Не совсем понял,а какая перестановка выигрышная,например для 6 5 7 1 4 2 3?Хотелось бы еще разбора этого,а то пока не совсем понимаю в чем фишка

(27 Янв '14 18:48) ivan145

@ivan145: как свести случай $%n > 5$% к случаю $%n=5$%, у меня сказано. Это совсем просто: под 6 кладём 6, под 7 кладём 7 и так далее, и сводим задачу к игре на пяти картах. Её мы уже умеем решать. В Вашем примере это будет 51423. Это один из двух особых случаев, и в тексте сказано, что за основу берём 543 и играем так, как играли против 321. Здесь будет 354, и итоговый порядок карт таков: 6371524 (543 заменили на 354, остальное на тех же местах).

Да, ещё по поводу убыстрения алгоритма с простыми числами: я предлагаю Вам оформить новый вопрос на эту тему со ссылкой. Там мне есть что сказать.

(27 Янв '14 19:12) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,850

задан
25 Янв '14 15:05

показан
626 раз

обновлен
27 Янв '14 19:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru