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

[St_Angelo]

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

Ситуация: у Вас есть 4 карточки разных банков, и есть 4 пин-кода от них, но какой пин-код от какой карточки вы забыли. Можно ли обналичить все 4 карты, при условии, что банкомат при 3 неверных ввода пин-кода заблокирует карту.

[St_Angelo]

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

Ситуация: у Вас есть 4 карточки разных банков, и есть 4 пин-кода от них, но какой пин-код от какой карточки вы забыли. Можно ли обналичить все 4 карты, при условии, что банкомат при 3 неверных ввода пин-кода заблокирует карту.

Ах да забыл, если я прав, что решения нет, можно ли доказать, что решения нет? Это как задачка про 3 колодца и 3 дома, где надо от каждого колодца прочертить линию до каждого дома, так чтобы линии не пересекались (там как-то доказали, что решения нет)(вот ссылка на ту задачку http://www.eblog.ru/index.php?newsid=781).

[Dendr]

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

Что-то там хитрой с комбинаторикой, как во взвешиваниях.

[team55]

Задача решается. Главное карты менять почаще.

[Dendr]

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

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

По строкам, как можно догадаться, у нас "стоят" кредитки, по столбцам - PIN'ы к ним. Помеченные клетки - это реальные соответствия, которых Игрок исходно не знает.
Черные шашки показывают ошибки при вводе PIN, белые - правильно угаданные соответствия кредитка-PIN.


Доказательство, что 100%-го выигрыша Игрок не добьется.
1. Очевидно, что максимально допустимое число ошибок - 8. При следующей ошибке карта наверняка заблокируется.
2. Так же очевидно, что какой бы ни была тактика Игрока, может произойти так, что Ведущий будет отвечать только "Нет" на все его вопросы.

Допустим, что Игрок все-таки совершил эти 8 ошибок (расставил в таблице 8 черных шашек) и ни разу еще не угадал хоть одну правильную комбинацию. Он теперь не может опрашивать Ведущего, а только логическим путем расставить белые шашки по остальным клеткам.
Видно, что в каждой строке только две черные шашки (третья шашка означает третью ошибку и блокировку карты).
Распределение по столбцам может быть двояким, в зависимости от выбранной Игроком тактики - либо во всех столбцах по 2 (и только по две) черных шашки, либо существует столбец, в котором есть три черных шашки.

Рассмотрим первую возможность (везде по 2 на столбец).Без ограничения общностей можно считать, что шашки стоят в следующих клетках (если не так, переставляем постепенно столбцы и строки матрицы):
A1-A2-*-**
B1-**-B3-*
*-C2-**-C4
**-*-D3-D4
Теперь видно, что белые шашки должны стоять либо в клетках, помеченных одной звездочкой, либо двумя. Шанс 50/50, и чтобы угадать, придется пожертвовать одной из карт.

Рассмотрим вторую возможность (есть столбец с тремя).Опять же, без ограничения общности, можем считать, что это первый столбец, и шашки занимают первые три строки. (остальные клетки пока помечу вопросительными знаками)
A1-?-?-?
B1-?-?-?
C1-?-?-?
!-?-?-?
Клетку D1 я нарочно пометил восклицательным знаком, потому что Игрок может прийти к логическому выводу, что там должна быть белая шашка.
В строке D, может быть, и стоят уже черные шашки, но они не особо важны... Незанятые клетки этой строки Игрок может закрыть серыми фишками. Но нас интересует квадрат A2-A4-C4-C2.
Там (по условию доказательства) не стоят белые шашки. И также там не стоят серые фишки. Но там могут быть черные шашки - максимум три (чтобы полная строка имела не более двух черных шашек). Опять же перестановками получим, что табличка Игрока выглядит так:
A1-a2-*-**
B1-**-b3-*
C1-*-**-c3
!-?-?-?
Опять видно, что началась угадайка, которая с вероятностью 50% кончится потерей карты.

[Юляша]

Доказательство, что 100%-го выигрыша Игрок не добьется.

В доказательстве есть дырки. Не решение пока не нашлось...

[Dendr]

В доказательстве есть дырки. Не решение пока не нашлось...

А где дырки? Ведь аналогия с игрой в шашки на доске 4х4 точная, тут придраться не к чему?

Вероятность того, что при следующей попытке Игрок ошибется, не равна нулю на любом этапе. Следовательно, вероятность того, что он сделает 8 ошибок подряд нулю не равна. Осталось разобрать все случаи, как он эти ошибки набрал (независимо от тактики, между прочим!) и показать, что вероятность того, что ему придется сделать еще ошибку тоже ненулевая.
Итого - доказывается, что вероятность блокировки одной из карт при любой из тактик Игрока не равна нулю. А это значит, что гарантированной стратегии победы у него нет.
Точно как в покере в варианте Texas Hold'em - ведь наличие в руке двух тузов (или же одномастных туза и короля - вообще любимой комбинации новичков) не гарантирует победы даже против разномастных двойки и девятки. Второй игрок с ненулевой вероятностью может заработать на ривере две пары и забрать банк.

Вариантов ветвлений ходов у Игрока немного.
1. Сначала выбираются любая карта и любой PIN, они обозначаются буквой A и цифрой 1 соответственно. (когда Игрок берет новую карту, она обозначается следующей буквой алфавита вплоть до D, а PIN - следующей цифрой вплоть до 4).
Это ход (проверка) A1
Если он угадал, то задача свелась к 3-м нетронутым картам и 3-м PIN'ам, а она очевидным образом решается. Если нет - следующий ход.
2. Дальше начинается очень простое ветвление: надо заменить только карту, только PIN, или и то, и другое. То есть перейти по вертикали, горизонтали или диагонали. Соответственно, это ходы A2, B1 или B2.
При успехе A2 задача опять сводится к 3-м парам. При успехе B1/B2 - немного сложнее, но тоже решается (карту A отложим и решаем для C и D с PIN-ами 2-3-4/1-3-4).
3. А при неудаче любого из ходов на 2-м этапе - новые ветвления...
A1-A2-B1 (сменили карту и взяли один из использованных PIN - без ограничения общностей это первый)
A1-A2-A3 (карту все еще не меняем... но это очень рисковый вариант)
A1-A2-B3 (сменили и карту и PIN)
*
A1-B1-A2 (новый PIN и одна из проверенных карт)
A1-B1-C1 (тот же PIN на третьей карте - глупый вариант)
A1-B1-C2 (сменили и карту и PIN)
*
A1-B2-A2 (берем какую-то из уже проверенных карт и проверяем на ней PIN, проверенный на второй карте)
A1-B2-A3 (берем одну из уже проверенных карт и новый PIN)
A1-B2-C1 (берем новую карту и проверенный PIN)
A1-B2-C3 (новая карта и новый PIN)

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

"Рисковый" вариант, при очередном провале, может лишить нас карты A - поэтому он не годится.
"Глупый" вариант дает нам без проверки карты D результат, что у нее - первый PIN. Но нам теперь можно ошибаться на остальных трех картах только единожды, и как-то распределить их по кодам. А там придется рисковать.
Вариант "диагональ": A1-B2-C3... Он интересный. Но бесполезный. Во-первых, придется взять либо новую карту (выбрав один из уже проверенных кодов), либо PIN (соответственно, карт), - возвращаясь к "цветным" тактикам. Либо же закончить диагональ: если D4 совпало, то за один ход можно разобрать все PIN'ы по картам. А если опять нет? Уже лень проверять, но там тоже риск потери карты. Здесь не учтен еще вариант, когда мы берем одну проверенную карту и сверяем с проверенным PIN'ом - но это опять к развитию "цветных" тактик.

"Цветные" тактики тоже не работают...
* проверенный - (зд.) PIN или карта, которые уже использовались на предыдущих этапах (возможно, неудачно).

[Юляша]

Неучтенная "дырка" в рассуждениях - это возможность цикла 3х2 (циклы 2х2 и 4х2 не дают решения).

То есть,

A1-A2-B2-B3-C3-C1. Есть ли решение в этом случае - я пока не знаю.

[St_Angelo]

Огромное спасибо Dendr!!! Благодаря таблички 4х4 становится всё понятно

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

Что-то там хитрой с комбинаторикой, как во взвешиваниях.

Сообственно друг говорил, что эта задачка появилась в просторах башорга.

[St_Angelo]

Задача решается. Главное карты менять почаще.

Dendr доказал, что не решается.
Максимум можно обналичить только 3 карты, а четвертая заблокируется, зато мы будем точно знать какой пин-код к нему.

[Dendr]

Неучтенная "дырка" в рассуждениях - это возможность цикла 3х2 (циклы 2х2 и 4х2 не дают решения).

То есть,

A1-A2-B2-B3-C3-C1. Есть ли решение в этом случае - я пока не знаю.

Если хотя бы один раз угадали (например, С1), то дальше точно находится код для карты D (у нас есть три попытки и 3 кода). И автоматически становятся известны остальные пары:
- D4: тогда A3 и B2
- D3: тогда A4 и B2
- D2: тогда B4 и A3

А если не угадали ни разу? Посмотрим, какие, в принципе, остались комбинации...
A3, B1, C2, D4
A3, B1, C4, D2
A3, B4, C2, D1
A4, B1, C2, D3
У нас есть всего две попытки, и мы можем проверять только карточку D. Каждая проверка исключает ровно одну комбинацию. После двух проверок останется, очевидно, две комбинации, что нас не очень-то устраивает.

Вообще, логика в том, что изначально у нас 24 комбинации, и ровно одна верная. Каждая проверка исключает несколько комбинаций. Не было бы ограничения на использование карт - было б легче. Но не судьба, похоже.

Кстати, из этой логики становится ясно, что мы узнаем коды для двух карточек. И ясно почему.
Рассмотрим предельный случай: 100 карточек и перепутанные коды к ним. Мы берем один код, вводим его всем карточкам подряд, пока он не сойдется. Потом второй код, пока не сойдется. Третий нельзя: блокировки...
То есть - гарантированно узнается как раз те самые две карты. В случае с тремя картами получается следующее - мы гарантированно узнали коды для карт A и B, осталась карта C, и ровно одна бумажка с кодом. В этом и весь фокус - и никакой магии с числом "три".

[Инна]

У меня разница с Москвой 12 часов сейчас.
Думала утром написать, а уже решение обсуждено. Но все же хочу написать и мое.
Оно с маленьким перебором. Будем использовать терминологию морского боя.
Пусть злонамеренная фортуна отвечает "мимо", пока это возможно.
И в итоге должна получиться таблица 4х4, с не более чем 2 "выстрелами" в каждом столбике, дающая однозначное расположение кораблей.
Если в двух столбиках выстрелы произведены по одинаковым парам, то остается не обстреленый квадрат 2х2, где возможно дуаль.
То есть из возможных 6 пар должны быть прострелены 4.
Две непростреленные пары могут содержать элемент в одной строке, а могут не содержать.
В первом случае таблица будет изоморфна
xххо
xоох
oхох
oохо

во втором -
ххоо
хоох
оохх
оххо
В обоих - однозначности нет.

[molch64]

Приходилось мне как-то решать ровно эту задачу.
Практически...
Перевыпускал по утере 4 карточки одновременно, выдали 4 пин-кода, я их вытащил, посмотрел и забыл что от чего
Я понял, что смогу все восстановить без блокировок с вероятностью 15/16:
По порядку:
карта 1: пинкод 1, пинкод 2.
карта 2: пинкод 3, пинкод 4
карта 3: пинкод 3, пинкод 4.
Если какой-то код срабатывает, дальше все разгребается.
Если нет (вероятность 1/8), то дальше я угадываю 50/50, т.е. вероятность блокировки - 1/16.
К счастью, у меня реализовалась 15/16.

Однако, это всё фигня. Теперь, внимание, правильное практическое решение:
Берется первая карточка, проверяется на ней наугад 2 пин-кода. Если успех - добиваем. Если фэйл - звоним в банк, представляемся и просим обнулить счетчик неверных вводов пин-кода.

[Инна]

А если N карт и блокируется после N-1 неудачной попытки, возможно ли решение для бОльших N?

[Инна]

Все то же самое будет при любом N.
Если в таблице Дендра по две невыбитые клетки не только в каждом столбике, но и в каждой строке, то легко находится дуальный цикл.
Если есть строка с одной невыбитой клеткой, вычеркнув ее и соответствующий столбик, спустимся на шаг индукции.