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

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

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

Аватара пользователя
Шшок
Акула пера
Акула пера
Сообщения: 9061
Зарегистрирован: 28 ноя 2003, 14:05
Пол: Мужской
Откуда: С большой дороги.

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

Сообщение Шшок »

Аскет писал(а):

Это ж компы, а не люди. Они не могут взять НЕ глядя :) А уж дать после этого НЕ глядя, это совсем из разряда фантастики :)
Ну извините...
Комп - это кусок железа. А вот программируют их - люди. Разве трудно программисту написать программу, делящую карты поровну между четырьмя компами так, чтобы каждый комп знал только те карты, которые достались ему, и не знал, какие карты находятся у других?
А если серьезно, я, увы, не математик. И не компьютерщик. И я действительно не понял условий задачи...
В борьбе бобра с козлом побеждает бобро. Или козло.

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

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

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

Аскет, никакого смысла. Я писала по памяти, по очень давно забытой памяти.
Возможно, это уточнение про "вслух" вообще не нужно.
Шшок, на формальном языке "закрытая карта" может означать только "как-то зашифрованная информация".
И тут же возникает вопрос: кем и как зашифрованная? У компьютеров нет ничего дополнительного, кроме них самих: ни внешнего генератора случайных чисел, ни программиста, который написал бы программу.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

Аватара пользователя
Аскет
Графоман со стажем
Графоман со стажем
Сообщения: 988
Зарегистрирован: 09 апр 2006, 20:47
Пол: Мужской

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

Сообщение Аскет »

Шшок писал(а):Комп - это кусок железа. А вот программируют их - люди. Разве трудно программисту написать программу, делящую карты поровну между четырьмя компами так, чтобы каждый комп знал только те карты, которые достались ему, и не знал, какие карты находятся у других?
В целом логичное заблуждение, есть же масса карточных игр, где компьютер играет за трех участников, а человек за одного. Комп, конечно, знает что он раздал каждому, но грамотно "симулирует" незнание за каждого своего игрока :)
Просто, если предположить, что компьютер может сдать в темную, задачка не имеет смысла, мы возвращаемся к обычной человеческой сдаче по одной карте в темную, ну или по 13 в темную.
Инна писал(а): И тут же возникает вопрос: кем и как зашифрованная? У компьютеров нет ничего дополнительного, кроме них самих: ни внешнего генератора случайных чисел, ни программиста, который написал бы программу.
Даже если бы компьютер из этой задачи обладал некой шифровальной программой, он бы все равно знал, что конкретно он зашифровал :)
Тут задачка сформулирована правильно, 4 компа и ничего более, откуда может прийти некая дополнительная (например, зашифрованная) информация.

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

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

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

Я при решении подобных задач считаю традиционными следующие условия.

1. Каждый из компьютеров - супер-пупер-мегапроизводительный, мгновенно выполняет сколь угодно сложные действия.
2. За клавиатурой каждого компьютера сидит человек, который одновременно является великим программистом, великим математиком, великим хакером и великим шулером. Ничто из того, что происходит в его компьютере, не является для него тайной. Если некая задача математически разрешима, то объем вычислений не является ограничением. Ну и, если имеется возможность сжульничать, незаметно для остальных или "в соответствии с правилами", он не преминет ею воспользоваться.
3. Все обмены данными проводятся через сервер и регистрируются на нем. Так что по окончании "партии" имеется возможность убедиться, что передача данных производилась в соответствии с ранее оговоренными правилами.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

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

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

Сообщение molch64 »

О, тут форум задачек возродился? :shock:
Насчет первой задачи: ну, если практически нужно передать любое 16-значное число, то действительно можно менять 3 цифры и гулять.
Если это действительно номер карты, то первую цифру, конечно, лучше не менять - поймут :D
Здрасьте, у меня тут mastercard с тремя ошибками, итак, номер 8222 2343 1274 4723
Ещё не каждое число является номером карты - контрольная сумма должна сойтись, можно считать, что на карте есть только 14 значащих цифр.
Но и их, в принципе, хватит вполне.
Желающие могут проверить практически, что хватит - тут номер моей карты с ошибками

Насчет задачи про тасование карт - а есть ли решение для общего числа компьютеров? N компьютеров, нужно раздать N карт.
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

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

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

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

molch64 писал(а):
Насчет задачи про тасование карт - а есть ли решение для общего числа компьютеров? N компьютеров, нужно раздать N карт.
От количества карт мое решение не зависит и даже не требует, чтобы карт было поровну (можно в преферанс вчетвером играть))). Метод легко обобщается на случай произвольного числа компьютеров (четыре и больше). Компьютеры E, F и т.д. получают шифр II (так же как D) и игрок С пересылает им карты после первичной расшифровки.

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

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

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

Сообщение molch64 »

Юляша писал(а):
molch64 писал(а): А вот можно ли добиться того же при трех компьютерах? Если нет, то можно ли это доказать?
Бейте, сколько хотите, но я не понимаю, почему нельзя раздать трем компам.

Этап 1. Раздача слонов всему населению, кроме себя.
Компьютер B шифром 1 зашифрует названия карт, отдаст это A. Свой шифр сообщит всем, кроме А.
Затем A перетасует карты и каждому по закрытому каналу сообщит эти карты.
Таким образом, все, кроме А знают свою карту в шифрованном и от B получили к ней шифр => расшифруют карту.
Более ничего они не знают.
А же знает свою карту в шифрованном виде, но передача ему кода расшифровки приведет к фэйлу : (


Этап 2. Узнай свою карту. Легкая версия.
Компьютер A говорит компьютеру B "братан, помоги узнать какая у меня карта".
Для этого применяется схема из задачи с дорогущей посылкой: А имея зашифрованную карту шифрует ещё своим шифром 2,
передаёт товарищу B, чтобы последний снял шифр 1. Затем, получает обратно и снимает свой шифр.


Этап 2. Узнай свою карту если тебе вообще ничего не известно (сложная версия).
Компьютер А говорит всем "товарищи, а ну быстро мне сказали все свои карты!"
Здесь нужен особый шифр, например, побитовое сложение, оно же - xor.
Тогда компьютер B записывает свою карту/карты в виде характеристического n-значного числа (1 - такая карта у меня, 0 - не у меня, всего n карт).
Это число он xor'ит со своим n-значным двоичным ключем 2 и посылает компьютеру C.
Компьютер C полученное число ксорит с числом, полученным из своих карт, затем со своим ключем, передает D и так далее.
Последний компьютер передает полученный результат обратно компьютеру A.
Таким образом, т.к. xor - операция переставляемая, то А будет иметь характеристическое число всех компов (вида 1 - карта у кого-то есть, 0 - нет ни у кого), зашифрованное всеми компами. Причем у кого именно - он знать не будет. Для расшифровки от каждого по отдельности нужно получить его ключ.
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

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

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

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

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

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

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

Сообщение molch64 »

Я вижу только одну оговорку в легкой версии: если мне нужно расшифровать несколько карт, то мне нужно либо просить расшифровывать их разных людей, либо, что лучше, для расшифровки каждой новой карты придумывать новый ключ.
Иначе снимающий может сделать какие-то вывод не относительно каждой карты, а относительно совокупности.
Если после этого не проходит, то почему?
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

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

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

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

molch64 писал(а):Я вижу только одну оговорку в легкой версии: если мне нужно расшифровать несколько карт, то мне нужно либо просить расшифровывать их разных людей, либо, что лучше, для расшифровки каждой новой карты придумывать новый ключ.
Иначе снимающий может сделать какие-то вывод не относительно каждой карты, а относительно совокупности.
Если после этого не проходит, то почему?
Пусть мы хотим раздать 3 карты: Валета, Даму и Короля - трем игрокам A, B и С.
В обозначил Валета - зю, Даму - ню, Короля - мю, передал "зю, мю, ню" игроку А, расшифровку - игроку С.

А отдал зю - игроку B, ню - игроку С, оставил себе мю.

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

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

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

Сообщение molch64 »

Юляша писал(а): Пусть мы хотим раздать 3 карты: Валета, Даму и Короля - трем игрокам A, B и С.
В обозначил Валета - зю, Даму - ню, Короля - мю, передал "зю, мю, ню" игроку А, расшифровку - игроку С.

А отдал зю - игроку B, ню - игроку С, оставил себе мю.

Как ему "легким способом" узнать, какая у него карта?
А, вот в каком смысле :oops:
Хорошо, нужна одна из двух оговорок ниже :)

Версия 1. Оговорка про шифры.

Нам нужны такие шифры А, B, чтобы
а) по нескольким зашифрованным картам шифра А никакую информацию узнать было нельзя, что это за карты.
б) A*B*A^(-1) = B (т.е. расшифровка шифром А того, что было шифрами A, затем B должна привести к слову, зашифрованному шифром B, а не к какой-то хрени.


Версия 2. Конкретный алгоритм, издевательский.

Давайте теперь шифратор B возьмет довольно большие двоичные числа (например, с количеством цифр n^2) и зашифрует названия этих карт этими числами. После этого, во всеуслышание объявит этот шифр.
Затем зашифрует все карты методом xor шифрами (каждую - своим) так, чтобы расшифровка полученного шифра не своим ключем приводила бы к числу, НЕ являющемуся картой (это знают все компы).
Эти шифры (все!) в произвольной последовательности передаются всем, кроме A.
Компьютер А, получив от B зашифрованные индивидуальными шифрами карты тасует карты, раздает, все пытаются применять к раздаче все возможные шифры и лишь один из них для каждой карты приводит к успеху.

Осталось разобраться, как А должен узнать свою карту. Он берет свои зашифрованные карты, сам их ксорит (разными шифрами), и отдает компьютеру А (итого k шифров, но разберем на примере одной карты)
Компьютер B не знает, каким своим шифром шифровал эту карту. Ничего страшного, расшифрует всеми возможными ; ) .
Но ему не дано понять, каким именно расшифровка шифром привела к успеху - у него получились n значений карт, зашифрованные ключом компьютера А. Узнать, какие из них получены от "настоящих" карт он не может, поэтому тупо передает обратно это все, А расшифровывает, получает n чисел, ровно одно из которых является картой. Win ?
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

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

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

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

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

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

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

Сообщение molch64 »

Инна писал(а):Юляша, насколько помню, с тремя компьютерами нельзя, но доказывать это строго я не умею...
Инна, буду тогда благодарен за облом моих опусов :wink:
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

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

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

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

Прошу прощения, почему-то не увидела последние посты molch64.
Буду разбираться.
Я эту задачку знаю еще со школы то есть как минимум четверть века назад, причем как околоолимпиадную, а не профессионально-кодировальную.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

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

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

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

Я пока не вижу, что можно противопоставить "сложной версии" molch64. В конкретном варианте "легкой версии" в связи с этим разбираться не хочется).

В связи с этим у меня возник более сложный вопрос. Имеет ли решение (при трех компьютерах) более сложная задача: сдаются _не все_ карты, а игроки в дальнейшем должны иметь возможность _брать карты из колоды втемную_?
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.

Ответить

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