Угу, хотела написать то же самое, только подробнее). Надо только еще упомянуть, что при N=2 задача заведомо не имеет решения - карта блокируется после первой же попытки.Инна писал(а):Все то же самое будет при любом N.
Если в таблице Дендра по две невыбитые клетки не только в каждом столбике, но и в каждой строке, то легко находится дуальный цикл.
Если есть строка с одной невыбитой клеткой, вычеркнув ее и соответствующий столбик, спустимся на шаг индукции.
Задачка с кредитными карточками
Модераторы: Азарапетыч, Администрация
Re: Задачка с кредитными карточками
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Задачка с кредитными карточками
Все, доказательство проверено, я даже набрала его, но случайно не сохранила(.
Есть еще одна тонкость, нужная, чтобы распространить его на случай типа
+++-
+--+
-+-+
--++
(+ - допустимая клетка, - - недопустимая)
но эта проблема решаема.
Я не исключаю, что в исходной задаче есть секретный подвох, позволяющий-таки обойти заявленные ограничения, но при формальной постановке ("сферический конь в вакууме") решения точно не существует.
Есть еще одна тонкость, нужная, чтобы распространить его на случай типа
+++-
+--+
-+-+
--++
(+ - допустимая клетка, - - недопустимая)
но эта проблема решаема.
Я не исключаю, что в исходной задаче есть секретный подвох, позволяющий-таки обойти заявленные ограничения, но при формальной постановке ("сферический конь в вакууме") решения точно не существует.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
-
St_Angelo
- Белинский по натуре
- Сообщения: 43
- Зарегистрирован: 30 янв 2006, 15:01
- Пол: Мужской
- Откуда: Казань
- Контактная информация:
Re: Задачка с кредитными карточками
Подвоха нет, т.к. задачку придумали в башорге. Кто-то написал, что у его жены было три карты и 3 пин-кода перепутанные. Эту задачку легко все решили. Потом кто-то вздумал усложнить и добавил еще по одной карте и пин-коду, но условия блокировки (2 попытки) остались прежними. Спустя некоторое время несколько людей "решили" эту задачу, но решения их неверны, хотя они этого не знаютЮляша писал(а): Я не исключаю, что в исходной задаче есть секретный подвох, позволяющий-таки обойти заявленные ограничения, но при формальной постановке ("сферический конь в вакууме") решения точно не существует.
Re: Задачка с кредитными карточками
Формальное доказательство
Задача.
Имеется N кредитных карт и список из N пин-кодов, относящихся к этим картам. При вводе неверного пин-кода для определенной карты N-1 раз, соответствующая карта блокируется. Есть ли возможность гарантированно установить пин-коды для всех карт, не заблокировав ни одной карты? Если да, то как это сделать?
Ответ.
Нет, это невозможно.
Доказательство.
Обозначим карты буквами (A, B, C и т.д.), а пин-коды - цифрами (1, 2, 3 и т.д.)
Любое соответствие может быть записано в матрицу NxN, где строки соответствуют картам, а столбцы пин-кодам. В этом случае в каждой строке и в каждом столбце имеется ровно одна заполненная клетка. Клетки, не входящее в верное соответствие, назовем запрещенными.
Видно, что для матрицы 2х2 решения не существует. Существуют ровно два возможных соответствия пин-кодов (A1+B2 или B1+A2), любая попытка может оказаться ошибочной, после чего карта немедленно блокируется.
Пусть для N=k решения не существует. Докажем, что для N=k+1 решение также невозможно.
Рассмотрим поиск решения как игру. Игрок A должен установить соответствие между картами и пин-кодами, для этого он может запросить содержимое любой клетки. Игрок B отвечает игроку A, используя следующую стратегию: если существует хотя бы одно допустимое соответствие, в котором данная клетка является запрещенной, он отвечает, что клетка запрещенная. При этом, если клетка заведомо входит в соответствие, то игроку A незачем задавать соответствующий вопрос - он и так может это установить.
Таким образом, после серии вопросов игрока A в матрице появится семейство запрещенных клеток, которые однозначно определяют правильное соответствие. При этом в каждой строке может быть не более N-2 запрещенных клеток, в противном случае соответствующая строка заблокируется. В каждом столбце также может быть не более N-2 запрещенных клеток, так как в противном случае мы сможем выбросить одну строку и и один столбец из соответствия и получим решение для N-1, что, по предположению, невозможно.
Для строк, в которых менее N-2 запрещенных клеток, дополнительно пометим те клетки, которые потом окажутся запрещенными, так, чтобы их стало N-2. При этом не может произойти блокировки карт и, следовательно, мы не ухудшили ситуации.
Таким образом, в каждой строке у нас ровно 2 неотмеченные клетки. То же самое должно быть верно и в отношении столбцов. А теперь пометим все клетки предполагаемого решения как запрещенные!!! При этом в каждой строке и в каждом столбце остается ровно одна свободная клетка. А значит, эти клетки также образуют корректное соответствие. Следовательно, предполагаемое соответствие - не единственное, а стало быть, исходная задача решения не имеет.
Задача.
Имеется N кредитных карт и список из N пин-кодов, относящихся к этим картам. При вводе неверного пин-кода для определенной карты N-1 раз, соответствующая карта блокируется. Есть ли возможность гарантированно установить пин-коды для всех карт, не заблокировав ни одной карты? Если да, то как это сделать?
Ответ.
Нет, это невозможно.
Доказательство.
Обозначим карты буквами (A, B, C и т.д.), а пин-коды - цифрами (1, 2, 3 и т.д.)
Любое соответствие может быть записано в матрицу NxN, где строки соответствуют картам, а столбцы пин-кодам. В этом случае в каждой строке и в каждом столбце имеется ровно одна заполненная клетка. Клетки, не входящее в верное соответствие, назовем запрещенными.
Видно, что для матрицы 2х2 решения не существует. Существуют ровно два возможных соответствия пин-кодов (A1+B2 или B1+A2), любая попытка может оказаться ошибочной, после чего карта немедленно блокируется.
Пусть для N=k решения не существует. Докажем, что для N=k+1 решение также невозможно.
Рассмотрим поиск решения как игру. Игрок A должен установить соответствие между картами и пин-кодами, для этого он может запросить содержимое любой клетки. Игрок B отвечает игроку A, используя следующую стратегию: если существует хотя бы одно допустимое соответствие, в котором данная клетка является запрещенной, он отвечает, что клетка запрещенная. При этом, если клетка заведомо входит в соответствие, то игроку A незачем задавать соответствующий вопрос - он и так может это установить.
Таким образом, после серии вопросов игрока A в матрице появится семейство запрещенных клеток, которые однозначно определяют правильное соответствие. При этом в каждой строке может быть не более N-2 запрещенных клеток, в противном случае соответствующая строка заблокируется. В каждом столбце также может быть не более N-2 запрещенных клеток, так как в противном случае мы сможем выбросить одну строку и и один столбец из соответствия и получим решение для N-1, что, по предположению, невозможно.
Для строк, в которых менее N-2 запрещенных клеток, дополнительно пометим те клетки, которые потом окажутся запрещенными, так, чтобы их стало N-2. При этом не может произойти блокировки карт и, следовательно, мы не ухудшили ситуации.
Таким образом, в каждой строке у нас ровно 2 неотмеченные клетки. То же самое должно быть верно и в отношении столбцов. А теперь пометим все клетки предполагаемого решения как запрещенные!!! При этом в каждой строке и в каждом столбце остается ровно одна свободная клетка. А значит, эти клетки также образуют корректное соответствие. Следовательно, предполагаемое соответствие - не единственное, а стало быть, исходная задача решения не имеет.
Нас двое - я и папа
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
И погромче нас были витии Да не сделали пользы пером. Дураков не убавим в России, А на умных тоску наведем.
Re: Задачка с кредитными карточками
Доказательство наверняка не работает при N>9999 <пинкоды четырёхзначныеЮляша писал(а):Формальное доказательство
Задача.
Имеется N кредитных карт и список из N пин-кодов, относящихся к этим картам. При вводе неверного пин-кода для определенной карты N-1 раз, соответствующая карта блокируется. Есть ли возможность гарантированно установить пин-коды для всех карт, не заблокировав ни одной карты? Если да, то как это сделать?
Ответ.
Нет, это невозможно.
Доказательство...
>