Задачка с кредитной карточкой

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
molch64
Литератор-любитель
Литератор-любитель
Сообщения: 266
Зарегистрирован: 08 июн 2006, 11:05
Пол: Мужской

Re: Задачка с кредитной карточкой

Сообщение molch64 »

Юляша писал(а):Я пока не вижу, что можно противопоставить "сложной версии" molch64. В конкретном варианте "легкой версии" в связи с этим разбираться не хочется).
А придется :D Шутка :) Но, шутка шуткой, а доля правды в ней есть (см ответ на следующий абзац).
Юляша писал(а):В связи с этим у меня возник более сложный вопрос. Имеет ли решение (при трех компьютерах) более сложная задача: сдаются _не все_ карты, а игроки в дальнейшем должны иметь возможность _брать карты из колоды втемную_?
"Конкретный вариант" "легкой версии" такого делать не запрещает.

Разумеется, при условии того, что информация о том, что данный компьютер взял карту втемную (и потом открыл, получив некую дополнительную информацию) является общеизвестной для всех компьютеров.
*а никто не запрещал игры, где игрок может брать от 1 до 3х карт из колоды, например, не показывая никому сколько конкретно карт он взял. Общеизвестной была бы только информация о том, что колода кончилась.
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задачка с кредитной карточкой

Сообщение Юляша »

molch64 писал(а):
Юляша писал(а):В связи с этим у меня возник более сложный вопрос. Имеет ли решение (при трех компьютерах) более сложная задача: сдаются _не все_ карты, а игроки в дальнейшем должны иметь возможность _брать карты из колоды втемную_?
"Конкретный вариант" "легкой версии" такого делать не запрещает.

Разумеется, при условии того, что информация о том, что данный компьютер взял карту втемную (и потом открыл, получив некую дополнительную информацию) является общеизвестной для всех компьютеров.
*а никто не запрещал игры, где игрок может брать от 1 до 3х карт из колоды, например, не показывая никому сколько конкретно карт он взял. Общеизвестной была бы только информация о том, что колода кончилась.
Вообще-то, имелись в виду игры традиционного плана, для которых типичны следующие действия: "Игрок NN берет две карты из колоды", "Игрок NN сбрасывает К карт, не показывая их другим игрокам, и берет столько же карт из колоды", "Игрок NN берет из колоды столько карт, чтобы на руках у него стало 6 карт", "Игрок NN берет карты, отложенные в прикуп, не показывая их другим игрокам".

К тому же, как оказалось, мое решение также легко приводится к случаю трех игроков.

1. Игрок А задает присваивает каждой карте номер и создает набор I уникальных XOR-шифров для каждой карты. Это набор шифров передается игроку С.

2. Все карты шифруются шифрами I и передаются игроку B, который становится "хранителем колоды".

3. Игрок B создает свой набор XOR-шифров II и никому его не передает.

4. Чтобы сдать карту игроку A или С, игрок B выбирает случайным образом нужное число карт из колоды и передает их соответствующему игроку. Тот игрок расшифровывает их шифром I и узнает, какие карты ему пришли (игрок A может ничего не расшифровывать, он и так знает соответствие между картами и их номерами).

5. Чтобы сдать карту себе, игрок B зашифровывает ее шифром II и передает игроку С. Игрок С расшифровывает ее шифром I и возвращает игроку B. B расшифровывает ее шифром II и узнает, какую карту он получил.


В результате:

Игрок A знает соответствие между номерами и картами, но получает от игрока B только собственные карты и не имеет информации о том, какие карты у других.

Игроки B и С не знают соответствия между картами и номерами и способны расшифровать только полагающиеся им карты и поэтому не могут определить, какие карты достались другим игрокам.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
molch64
Литератор-любитель
Литератор-любитель
Сообщения: 266
Зарегистрирован: 08 июн 2006, 11:05
Пол: Мужской

Re: Задачка с кредитной карточкой

Сообщение molch64 »

Юляша писал(а): К тому же, как оказалось, мое решение также легко приводится к случаю трех игроков.
Это, практически, совпадает с моей конкретно версией легкого решения. Единственное - нужно удостовериться, что если для каждой карты, сданной игроком A хоr шифр был разным (иначе B может что-то узнать), то при расшифровке сданных карт все игроки (кроме B) не знают, какой конкретно xor-шифр расшифрует карту => мы должны быть уверенными, то если расшифруем не подходящим xor-шифром, получим бред, не являющийся картой.
Это /придумать такие шифры/ - задача компьютера А.

А так, нужно подумать, как ВТЕМНУЮ сдать карты в колоду. Остальное делается приведенными методами.
Проблему вижу в том, что карты нужно перешифровать, не открывая никому секрета (в т.ч. шифратору) секрета, а что же за карты в колоде. Проблема усугубляется тем, что карты зашифрованы разными шифрами, иначе раздающий что-то может узнать. Так что вариант - раздающий шифрует заново, передает другому для раздачи, назначая раздающим, раздающий снимает изначальный шифр не проходит, ибо он не знает теперь при снятии шифров получилась ли карта или получилась хрень :(
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задачка с кредитной карточкой

Сообщение Юляша »

Итак, предлагается найти возможность для компьютеров сыграть в только что изобретенную игру "темный пьяница".

Правила игры. В игре участвуют К игроков (K>=3) с использованием N 52-карточных колод (число N оговорено заранее).

Все карты (N*52) замешиваются в общую колоду из которой каждому игроку сдается по одной карте (вариант - по M карт). Ходы делаются по очереди.

Игрок смотрит свои карты, выбирает одну из них и берет из колоды столько карт, каково значение выбранной (Туз - одну, от двойки до девятки - соответствующее число, картинки - 10 карт). Эту стопку карт он не глядя кладет перед собой, а все прежние карты сбрасывает. Другие игроки не знают, сколько именно карт было взято. Ход затем переходит к следующему игроку.

Тот, кто не может забрать из колоды заявленное число карт (колода кончилась), - проигрывает.

Как обычно, у нас имеется сервер, на который копируются все действия, выполняемые компьютерами, что позволяет впоследствии проверить соблюдение правил.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задачка с кредитной карточкой

Сообщение Dendr »

Юляша писал(а):Итак, предлагается найти возможность для компьютеров сыграть в только что изобретенную игру "темный пьяница".

Правила игры. В игре участвуют К игроков (K>=3) с использованием N 52-карточных колод (число N оговорено заранее).

Все карты (N*52) замешиваются в общую колоду из которой каждому игроку сдается по одной карте (вариант - по M карт). Ходы делаются по очереди.

Игрок смотрит свои карты, выбирает одну из них и берет из колоды столько карт, каково значение выбранной (Туз - одну, от двойки до девятки - соответствующее число, картинки - 10 карт). Эту стопку карт он не глядя кладет перед собой, а все прежние карты сбрасывает. Другие игроки не знают, сколько именно карт было взято. Ход затем переходит к следующему игроку.
Промоделировать можно ли?
Для примера (масти неважны, поэтому пишу только значения), раздали 4-м игрокам по 2 карты из четверной колоды:
Север: 4, 9
Восток: A, 3
Юг: 5, J
Запад: 8, 9.
В колоде осталось 200 карт. Начинаем с севера, и идем по часовой стрелке.

Север берет из колоды 9 карт и, для удобства, раскладывает их по возрастанию (например, 2, 4, 5, 6, 6, 8, J, J, J) в "руке". А четверку и девятку кидает в "отбой". В колоде остается 191 карта. Но остальным игрокам неизвестно, что Север выбрал девятку (!).
Вопрос первый - таким образом, Востоку неизвестно, что осталась 191 карта? Условно, пусть они выбирают, по очереди: туз, валет, восемь, и тем самым скидывают из колоды 1+10+8=19 карт, оставляя 172. И, следовательно, Север (чей ход настал) не знает, что их 172?

Если ответ "да", то после ряда кругов приходим к возможному состоянию: ход Юга, у него 5 карт (A, 3, 8, K, K). А в колоде (Юг этого не знает) - осталось 6 карт. Значит ли это (и это второй вопрос), что Юг проиграет с вероятностью 3/5? Ведь если он выберет короля, то он проиграл. Но если тройку - то игра продолжается, и все зависит от того, какие карты у Запада и Севера, и их выбора.
Тактика случайного выбора работает нечестно. То есть либо ИИ выбирает всегда наименьшую карту, либо произвольную, но только до какого-то момента, а потом - только наименьшую. Но это тактика, а не техническое воплощение...

Если использовать сервер, который будет крупье - все легче легкого. Но если крупье нет, то кто-то должен стать дилером, и нужно шифровать больше, чем раньше.

Попробую объяснять "на пальцах". Может быть, путано, но как есть.
Поскольку длинно и текстово, то не прячу шрифт.

Пусть каждый из компьютеров придумает свой собственный шифр на всю колоду: переводит одну карту в другую. Главное условие - коммутативность шифров и единственность обратного перехода. И еще такой же шифр - на этот раз на "мегаколоду" 52*N+1 (N стандартных колод плюс джокер - ниже будет понятно, зачем это). В принципе, это может быть и единый шифр - но у каждого игрока свой.
Ремарка про коммутативность важна: дешифровка должна работать в любом порядке (пусть алгоритм шифровки прописная буква, дешифровки - строчная): Пусть З(Ю(В(С(карта X))))=карта Y, тогда карта X=з(с(в(ю(карта Y))))=в(ю(з(с(карта Y))))=ю(в(с(з(карта Y))))=...

Итак, к раздаче карт из колоды. Север шифрует всю колоду (можно стасовать, чтобы не дать подсказки сопернику), потом Восток, потом Юг, потом Запад. Потом, уже зашифрованную колоду тасует Север, и создает список из записей (пользуясь паскалевской терминологией).
Каждая запись состоит из: ID (он же UIN, является одной из карт "мегаколоды" - в том числе и джокер), значения карты (4-жды зашифрованного, помните?) и ссылки на ID "следующей" карты. В самый "низ" колоды он "кладет" джокера (его не шифровали ну и пусть), у которого тоже будет свой ID, а поле "ID следующей" можно оставить и пустым.
ID "верхней" карты Север просто запоминает и никому не говорит. Потом Север берет все ссылки на ID "следующей" и шифрует их, потом передает по кругу на шифровку и заменяет все ссылки на зашифрованные ссылки. Список из записей в таком виде выкладывается в открытом доступе. Теперь он устроен так, что без знания дешифровки ссылки узнать, какая карта идет за какой - невозможно. А расшифровать ее можно только всем сразу.

Раздача происходит следующим образом:
Север "берет" себе верхнюю карту (ID он помнит - см. выше), запоминает ее значение и ID следующей - пока зашифрованные! Пускает их по кругу для дешифровки. При этом значение "сданной" ему карты дешифрует первым Восток, потом Юг, потом Запад, а последним - сам Север (путь ВЮЗС). Таким образом, узнает истинное значение своей первой карты. А вот ID следующей карты дешифруется в порядке: Север-Запад-Юг-Восток (СЗЮВ). Таким образом, ID "новой верхней" карты знает только Восток. Он повторяет действия Севера в точности, пока у каждого игрока не будет по M карт, причем по секрету от других. И истинный ID "верхней" карты знает теперь только Север.

Взятки
Север выбирает одну из своих карт (некая тактика пусть заложена, на этом мы не зацикливаемся) и, согласно ее значению (например, 6), повторяет одно и то же действие несколько раз: снимает "верхнюю" карту и читает "запись":
* смотрит зашифрованное значение - дешифрует его в порядке ВЮЗС (так он узнает дешифрованное значение), запоминает себе в руку
если нужное число "взятых" карт (в нашем примере 6) не достигнуто, то:
** Север смотрит зашифрованный ID "следующей", дешифрует его по ВЮЗС, снимает "следующую верхнюю" карту - возврат в начало цикла
если нужное число карт достигнуто:
*** Север запоминает зашифрованный ID "следующей" в отдельную ячейку памяти, далее имитирует дешифровку по ВЮЗС всех последующих карт и ID, так, как будто бы он хочет взять 10 карт (отсылает случайные значения, не запоминая дешифровку, в нашем примере это будет 5 "следующих ID" и 4 карты).

Потом - запомненный выше ID Север отправляет на дешифровку в порядке СЗЮВ. Теперь Север (и только он) знает 6 своих новых карт, Восток (и только он) - ID "верхней карты", и никто, кроме Севера, не знает, что он "снял" именно 6 карт. Секретность соблюдена.

Конечно, игроки, когда будут получать для дешифровки повторяющиеся карты, что-то заподозрят. Но это не страшно.
Если Восток, допустим, получил при первой взятке Севера, значение "8 червей", которое перевел в "туз пик", а потом то же самое случилось на третьей взятке Севера, то он не может наверняка знать, где именно Север имитировал взятку, а где по-настоящему снимал карту. Так что секретность соблюдена. Север не станет попадаться "глупо" и на одной взятке повторять значения, так что секретность соблюдена.

Если на каком-то этапе, взяв "верхнюю" ("следующую верхнюю") карту, игрок обнаруживает, что это - джокер, то он объявляет, что проиграл. В процессе дешифровки никто не должен догадаться, что ему выпадет именно джокер. Именно для этого в перетасованной колоде лежат записи из 3 полей, а не двух - чтобы в каждой взятой карта дешифровка велась дважды и независимо.

Вот как-то так получается. Вроде.

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задачка с кредитной карточкой

Сообщение Юляша »

Dendr писал(а): Вопрос первый - таким образом, Востоку неизвестно, что осталась 191 карта? Условно, пусть они выбирают, по очереди: туз, валет, восемь, и тем самым скидывают из колоды 1+10+8=19 карт, оставляя 172. И, следовательно, Север (чей ход настал) не знает, что их 172?
Да, неизвестно.
Dendr писал(а): Если ответ "да", то после ряда кругов приходим к возможному состоянию: ход Юга, у него 5 карт (A, 3, 8, K, K). А в колоде (Юг этого не знает) - осталось 6 карт. Значит ли это (и это второй вопрос), что Юг проиграет с вероятностью 3/5? Ведь если он выберет короля, то он проиграл. Но если тройку - то игра продолжается, и все зависит от того, какие карты у Запада и Севера, и их выбора.
Предполагается, что игроки выбирают карты не случайным образом. Но в случае случайного выбора - именно так и будет. Тактика игры (если вообще тут есть разумная тактика - цели придумать интересную игру не ставилось)) не важна.
Dendr писал(а): Вариант решения
Тут есть одна сложность (или мне не все понятно). Тот игрок, который упорядочивал список, имеет возможность по ID карты определить ее порядковый номер в колоде, что означает, что он может определить число карт, оставшихся в колоде (возможно с опозданием на один цикл).
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задачка с кредитной карточкой

Сообщение Инна »

Я прошу прощения, но с теорией у меня всегда хуже, чем с практикой.
Я всё насчет трех компьютеров.
В решении от Юляша » 10 фев 2012 09:15 - все понятно на пальцах.
Здесь (де)кодирование - это операция, применимая только к массиву (упорядоченной колоде).
И, как я поняла, когда передают, например, лишь половину карт, это означает, что передают тот же массив из 54 6-битовых чисел, в половине элементов которого стоят прочерки.
Можно попросить Юляшу или molch64 так же на пальцах описать раздачу карт на троих (хотя бы трех карт на троих). Вот что-то я туплю с решением molch64. "Легкое" мне не нравится, потому что там кодируются не массивы, а отдельные карты (как?).
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Юляша
Популярный автор
Популярный автор
Сообщения: 3352
Зарегистрирован: 15 янв 2009, 12:32
Пол: Женский

Re: Задачка с кредитной карточкой

Сообщение Юляша »

Инна писал(а):Я прошу прощения, но с теорией у меня всегда хуже, чем с практикой.
Я всё насчет трех компьютеров.
В решении от Юляша » 10 фев 2012 09:15 - все понятно на пальцах.
Здесь (де)кодирование - это операция, применимая только к массиву (упорядоченной колоде).
И, как я поняла, когда передают, например, лишь половину карт, это означает, что передают тот же массив из 54 6-битовых чисел, в половине элементов которого стоят прочерки.
Можно попросить Юляшу или molch64 так же на пальцах описать раздачу карт на троих (хотя бы трех карт на троих). Вот что-то я туплю с решением molch64. "Легкое" мне не нравится, потому что там кодируются не массивы, а отдельные карты (как?).
На пальцах. Пусть есть Валет (В), Дама (Д) и Король(К).

Игрок А присваивает картам номера в случайном порядке например 1 - Д, 2 - К, 3 - В. номер - это маркер, всегда передаваемый в открытом виде.

Он также задает набор XOR-шифров 1<->1*, 2<->2*, 3<->3* и передает их игроку C. Зашифрованные карты 1*, 2*, 3* передаются игроку B.

Игрок B задает свой набор XOR-шифров 1<->1+, 2<->2+, 3<->3+ и никому его не передает. Он выбирает случайным образом, что, например, карта 1 идет игроку B, карта 2 - игроку С, карта 3 - игроку A.

Он возвращает карту 3* игроку A и пишет - это твоя карта. Игрок A расшифровывает ее или просто по номеру определяет, что ему достался Валет.

Игрок B также шлет карту 2* игроку С и пишет что это - его карта. Игрок С дешифрует ее и получает Короля.

Кроме того игрок B шифрует карту 1* своим шифром и пересылает карту 1*+ игроку С. Игрок С дешифрует ее и возвращает карту 1+ игроку B. Игрок B дешифрует ее и узнает, что у него Дама.

В результате.

Игрок A знает соответствие номеров и карт, но не знает, карта с каким номером кому досталась.
Игроки B и C знают, какой номер у кого, но могут определить значение только собственной карты.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задачка с кредитной карточкой

Сообщение Инна »

Да, Юляша, огромное спасибо.
Не знаю, откуда у меня была уверенность, что с 3 нельзя.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Инна
Популярный автор
Популярный автор
Сообщения: 1434
Зарегистрирован: 18 июл 2006, 18:44
Пол: Женский
Откуда: Калифорния

Re: Задачка с кредитной карточкой

Сообщение Инна »

Теперь постараюсь осилить рассуждения Дендра :-)
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задачка с кредитной карточкой

Сообщение Dendr »

Юляша писал(а):Тут есть одна сложность (или мне не все понятно). Тот игрок, который упорядочивал список, имеет возможность по ID карты определить ее порядковый номер в колоде, что означает, что он может определить число карт, оставшихся в колоде (возможно с опозданием на один цикл).
Да, похоже на правду. Даже если моделировать ситуацию, когда колоду "снимают": остальные игроки, по секрету от генератора колоды, выбирают случайное начало... Тогда генератор все равно узнает, сколько было снято за круг (по разнице ID).

А если "тасовать колоду" будут все по очереди (ну, неким образом), то все равно он сможет, узнав ID первой снимаемой им карты, (хотя бы примерно) оценить количество оставшихся карт.
Конечно, приблизительная оценка есть всегда (за один круг вычитается конечное число карт от 3 до 30), но мы не можем давать точнее.

Можно сгенерировать список из списков, и "актуализировать" только один. Но это (52N+1)! вариантов - с ума сойдут считать.


Что-то витает в воздухе... Может быть, пусть Север - генератор, а Восток - раздатчик? Сумбурно, но это пока только идея.
1. То есть, ID "верхней карты" сообщается ему,
2. он "вскрывает" первую карту - получает зашифрованное значение и зашифрованный же ID "следующей" карты.

3. Посылает эту информацию на расшифровку таким путем, чтобы истинное значение карты пришло к "берущему", а значение "ID следующего" - ему самому.
Причем - и это важно для секретности - начинает не с Севера. Из-за условия коммутативности шифров-дешифров порядок будет не важен, главное, чтобы участвовали все четверо, а тот, кому надо знать истинное значение, расшифровывал последним.

4. Берущий смотрит в карту (ему придет расшифрованное значение) и кладет ее в руку. Если он не набрал еще нужного ему количества, то передает, как "ID следующей" (недорасшифрованное!), то, что поступило по цепочке от раздатчика. Конечно, предварительно расшифровав его. Если набрал - то случайное значение, чтобы имитировать набор 10 карт.
В последний раз он передает раздатчику то значение недорасшифрованного ID следующего, которое пришло с последней картой, положенной в руку (тоже расшифровав своим декодером, конечно), а так же условное сообщение "я закончил".

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

6. Возврат в п.1.

Теперь Север не знает ID ни одной из полученных им карт, не знает зашифрованных значений карт, которые сдавал Восток, соответственно, Север никак не может оценить число оставшихся.
А Восток - знает все ID, но не знает, сколько карт кто взял. Он, конечно, может помечать карты, чьи ID ему поступали. Но реально ли их "положили себе в руку" остальные? Он не знает. Стало быть, он не может оценить число оставшихся карт.
Рядовые игроки (Юг и Запад, хотя уже одного для партии достаточно) тем более не знают ничего.

Вроде теперь работает. План воплощения... вот тут я затруднюсь. Главное, придумать такие шифраторы. А уж тактику игры насадить можно всегда.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задачка с кредитной карточкой

Сообщение Dendr »

Еще одну ошибку нашел - и теперь исправил. Ведь если Север (из моего примера) получит какую-то карту, то он узнает ее номер в колоде просто потому, что он ее пускал на круг шифровки, а потом сортировал.

Поэтому нужно три "роли" (буду называть их так, уйдя от сторон света):
1. Шифровщик. Он берет карты по одной и шифрует их - берет в произвольном порядке из колоды и передает по кругу, чтобы все шифры сработали на каждой карте. Начинает он с себя и кончает на Сортировальщике. Ни Ш, ни С не знают соответствия "исходная карта - зашифрованная карта", то есть секретность не нарушена нигде.

2. Сортировальщик. Он выстраивает карты в некий порядок ("тасует"). Потом присваивает каждой карте UIN, и приписывает ссылку на "следующую карту". Ссылки пускает по кругу шифровки и "перезаписывает" вместо реальной ссылки. На "нижнюю" карту он прописывает джокера, предварительно зашифровав его по кругу.
Общий массив передает Раздатчику.
Если С узнает на каком-то этапе реальный UIN какой-то карты, попавшей к нему, зашифрованное значение этой карты или зашифрованную ссылку на UIN следующей - то он узнает и номер карты в колоде. То есть дешифровать карту первым он не может.
Р знает только UIN верхней карты, но о порядке карт ничего не знает. Секретность не нарушена.

3. Раздатчик. Получив от другого игрока UIN верхней карты (в первый раз - прямым текстом от Раздатчика, потом - путем дешифровки по цепочке), он "смотрит" карту, получает зашифрованное значение этой карты и зашифрованную ссылку на следующий UIN. Карту он пускает на дешифровку так, чтобы первым ее дешифровывал не Сортировальщик, а последним - Взяточник (которые сменяются периодически). UIN следующей карты - чтобы первым не Сортировальщик, а последним - сам Раздатчик. То есть Взяточник (и только он!) узнает истинное значение верхней карты, а Раздатчик (и только он) - UIN второй карты в стопке - теперь она становится верхней.

Четвертая, переходящая роль - Взяточник, тот, кто берет карты прямо сейчас:
4. Если Взяточник получил джокера, то тут же сообщает об этом: он проиграл. Если другую карту и считает, что ему нужно еще, то он передает UIN следующей по цепочке дальше. Если он считает, что хватит, то пускает по цепочке ложное значение UIN верхней, чтобы имитировать набор 10 карт. Если он набрал 10 карт (нужные ему плюс "ложные"), то пускает по цепочке UIN с последней нужной карты. Если среди "ложных" ему попадет джокер, то он игнорирует это явление.
Таким образом, Взяточник получает нужное ему число карт, не выдает, сколько он реально взял, и в итоге сообщает Раздатчику UIN верхней карты, оставшейся после его взятки. Сначала Раздатчик получает реально UIN верхней, потом черти что, потому что Взяточник путает карты. Но в итоге Взяточник пукает недорасшифрованный UIN верхней, так что все в порядке.

Ну и возвращаясь к Раздатчику: он, раздав 10 карт Взяточнику и получив в итоге UIN верхней карты, переключается на другого Взяточника и т.д. Порядок дешифровки определяет сам Раздатчик в зависимости от Взяточника.

Роль Шифровальщика и Раздатчика, кажется, можно совмещать. Но тогда обязательно должен быть Взяточник без других ролей. То есть минимум на троих можно сыграть.

ChaoCheese
Читатель
Читатель
Сообщения: 23
Зарегистрирован: 27 сен 2010, 12:30
Пол: Мужской

Re: Задачка с кредитной карточкой

Сообщение ChaoCheese »

Родилась идея про задачу, что описана в первом посту.
Итак.
И Иван, и "Хрень" пишут у себя на листиках 4 случайных 16-значных числа (из головы) и одно настоящее.
После чего диктуют друг другу записанные числа в случайном порядке.
Затем Иван говорит, что среди чисел "Хрени" есть номер карточки, а "Хрень" говорит, что среди чисел "Ивана" тоже есть этот номер...

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Задачка с кредитной карточкой

Сообщение Dendr »

ChaoCheese писал(а):И Иван, и "Хрень" пишут у себя на листиках 4 случайных 16-значных числа (из головы) и одно настоящее.
После чего диктуют друг другу записанные числа в случайном порядке.
Ну, совсем отлично. Теперь лжеоператор знает 4 числа, одно из которых - истинный номер карточки.
Ваня, конечно, не услышав правильного ответа, подскочит и засуетится, блокируя карточку, но оно ему надо?
Или даже хуже (!) лжеоператор назовет, например, на третьем этапе число, которое Иван диктовал вторым. С вероятностью 25% оно будет настоящим номером карточки, и Иван пропал.

И наоборот - лже-Иван узнает (или даже угадает) номер карты. Оператор если и догадается, что говорил с мошенником, то заблокирует карточку ни в чем не повинного Ивана. А тот ни сном, ни духом. Или если Иван решит пошутить... то и тут его ждет подлянка.

Так что ответ никуда не годится, я думаю.

Ответить

Вернуться в «Задачки»