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

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

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

Аватара пользователя
Katrine
Литератор-любитель
Литератор-любитель
Сообщения: 395
Зарегистрирован: 18 апр 2005, 17:05
Пол: Женский
Откуда: Чебоксары

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

Сообщение Katrine »

- Здравствуйте, фирма Хрень.Василий.. Бла-бла. Номер кредитной карточки?
- бла-бла-5...
- (перебивая) Бла-бла 5???
- Бла-бла- 5!
- Извините, это не ваша кредитная карточка, мошенник.
Пик-пи-пик...
чебуреки... Чебурашка... чемодан... Э-э-э, а куда Чебоксары подевали?

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

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

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

Katrine писал(а):- Здравствуйте, фирма Хрень.Василий.. Бла-бла. Номер кредитной карточки?
- бла-бла-5...
- (перебивая) Бла-бла 5???
- Бла-бла- 5!
- Извините, это не ваша кредитная карточка, мошенник.
Пик-пи-пик...
О чем это?
В борьбе бобра с козлом побеждает бобро. Или козло.

Аватара пользователя
Katrine
Литератор-любитель
Литератор-любитель
Сообщения: 395
Зарегистрирован: 18 апр 2005, 17:05
Пол: Женский
Откуда: Чебоксары

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

Сообщение Katrine »

Шшок писал(а):
Katrine писал(а):О чем это?
О том, что меня цифру в номере, особенно 1-3, его уже и слушать не будут дальше. Не совпало - значит, не тот номер.
чебуреки... Чебурашка... чемодан... Э-э-э, а куда Чебоксары подевали?

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

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

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

Инна писал(а): 120*9*9*9 способами.
Мда...
У меня получилось 560*9*9*9=408240
В борьбе бобра с козлом побеждает бобро. Или козло.

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

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

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

Katrine писал(а):
Шшок писал(а):
Katrine писал(а):О чем это?
О том, что меня цифру в номере, особенно 1-3, его уже и слушать не будут дальше. Не совпало - значит, не тот номер.
Дык я ж говорю, что Василий должен назвать ТОЧНЫЙ номер карточки. А номер с заменой цифр называет Хрень.
Или ты хочешь сказать, что таким образом мошенник может узнать у фирмы Хрень, на каких местах стоят неверные цифры? Дескать, его перебили на третьей цифре... Ага! Значит, позвоним еще раз, назовем какую-то другую третью цифру - авось угадаем? Так, что ли? :lol:
В борьбе бобра с козлом побеждает бобро. Или козло.

Аватара пользователя
Katrine
Литератор-любитель
Литератор-любитель
Сообщения: 395
Зарегистрирован: 18 апр 2005, 17:05
Пол: Женский
Откуда: Чебоксары

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

Сообщение Katrine »

Шшок писал(а):Дык я ж говорю, что Василий должен назвать ТОЧНЫЙ номер карточки. А номер с заменой цифр называет Хрень.
Не важно, я бы сразу перебила Хрень и сказала "тусуйтесь, мошенники" 8)
короче, в России это точно не прокатило бы.
Можно перебить и на пятой :)

Второй раз позвонили бы - уже не прокатило бы. сразу бы трубку бросила. :)
чебуреки... Чебурашка... чемодан... Э-э-э, а куда Чебоксары подевали?

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

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

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

Шшок писал(а): И учтите еще вот что: и Иван и Вася не хотят передавать друг другу номер карточки даже частично. Иначе было бы примитивное решение: Вася диктует Ивану первые 8 цифр номера, а Иван Васе в ответ - последние 8 цифр (или наоборот).
Шшок писал(а):Иван: Хорошо, я тебе сейчас его продиктую. Но умышленно поменяю в нем три цифры на неправильные. (диктует 16 цифр).
Что-то я не замечаю принципиальной разницы... Что назвать правильно 8 цифр, причем можно не говорить, первые они, или средние. Что 16 цифр с 3-мя ошибками.
И там и там идет ЧАСТИЧНОЕ сообщение номера.
Dendr писал(а): Ну вот. Я же об этом и хотел написать первым же сообщением... Только фраза о том, что нельзя передавать цифры кредитки сбила с правильного пути. :(
+1. Та же фигня.
Первая мысль у меня была назвать часть номера или в обратную сторону и т.п. варианты, но замечание приведенное выше, полностью сбило с толку.

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

Леша
Писатель на заборах
Писатель на заборах
Сообщения: 150
Зарегистрирован: 20 июл 2004, 21:12

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

Сообщение Леша »

По-моему Юля права. Если Хрень звонит сначала лже-Василию с сообщает номер карточки с 3 ложными цифрами. Тогда лже-Василий может позвонить настоящему Василию и представиться фирмой Хрень, потому что он знает номер карточки с 3 ложными цифрами. Тогда Василий сообщит лже-Василию оставшиеся три цифры.

Леша
Писатель на заборах
Писатель на заборах
Сообщения: 150
Зарегистрирован: 20 июл 2004, 21:12

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

Сообщение Леша »

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

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

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

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

Инна писал(а): Вторая гораздо сложнее, одна из самых ярких и красивых задач в моей жизни. Не уверена, что здесь обсуждалась.
Итак, 4 компьютера играют в карты между собой. Они должны разложить колоду на четверых (каждому - равное число карт).
Каждый компьютер может передать информацию любому другому так, что двое остальных ее не узнают. Можно еще сообщать что-то вслух, и больше ничего.
Никаких сторонних источников нет. Как им договориться, чтобы каждый знал свои карты, и не имел НИКАКОЙ информации о картах других (то есть любой расклад между тремя другими для четвертого компьютера был возможен).
Для однозначности считаем, что компьютеры играют в бридж и сдать им надо по 13 карт из 52-карточной колоды. Каждая карта кодируется 6 битами.

Обозначим "компьютеры" буквами А, В, С, D.

Вводим два ключа шифрования I и II длиной 312 (6*52) бит. Ключи генерируются случайным образом компьютерами A и B и передаются, соответственно, компьютерам С и D. То есть, ключ I известен компьютерам A и С, ключ II - компьютерам B и D. Для шифрования используется сложение значения с ключом по модулю 2 (XOR). Длина ключа позволяет "необратимо" зашифровать полностью упорядоченую колоду (расшифровка без знания ключа принципиально невозможна).

При этом, как известно (х хor у) xor y = x; (x xor y) xor z = (x xor z) xor y

Далее компьютеры действуют следующим образом.

1. A "тасует" колоду - присоединяет к каждой карте номерок от 1 до 52.

2. A шифрует значения всех карт при помощи ключа I.

3. А передает зашифрованную последовательность компьютеру B.

4. B повторно шифрует уже зашифрованную последовательность при помощи ключа II.

5. B передает дважды зашифрованные карты игроку С.

6. С "раздает карты" - присоединяет к 13 случайно выбранным картам маркер A, к другим 13 картам - маркер B и т. д.

7. С повторно зашифровывает ключом I карты, маркированные B и D, что эквивалентно их расшифровке.

8. С передает карты, маркированные A и B, игроку B, а карты, маркированные С и D, - игроку D.

9. B дешифрует полученные карты ключом II. При этом карты, маркированные B, уже расшифрованы и игрок B оставляет их себе, а карты, маркированные А, он пересылает игроку A.

10. Игрок D аналогично дешифрует полученные карты, возвращая затем карты, маркированные С, игроку С.

11. Игроки A и С дешифруют свои карты ключом I.

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

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

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

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

Юляша, респектище!
Очень красивое решение.
Навскидку, все правильно.
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

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

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

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

560*9*9*9=408240
Да, С(16, 3)*9*9*9
Вы только что начали читать фразу, чтение которой Вы уже заканчиваете...

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

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

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

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

1. Хрень должна ошибиться номером. Все-таки наиболее вероятно, что Хрень попадет именно к Васе.
2. Хрень должна, ошибившись номером, нарваться не на простого обывателя, а именно на жулика. Наиболее вероятно, что, ошибившись номером, Хрень услышит в трубке: "Нет, я не Вася, вы ошиблись".
3. Если Хрень все-таки нарвется на жулика, то этот жулик должен мгновенно сориентироваться и сообразить, какую выгоду он сможет извлечь из этого звонка. Такая молниеносная сообразительность лже-Васи далеко не гарантирована.
4. И наконец самое главное: жулик должен после всего этого дозвониться до настоящего Васи, то есть найти каким-то образом его телефон. А это (по крайне мере, в Израиле) далеко не так просто. Для этого надо сообщить телефонному провайдеру по крайней мере фамилию и дату рождения Васи. И если фамилию Васи он может услышать от Хрени, то угадать его дату рождения - навряд ли.
5. И даже это еще не все. Ведь в ответ на "пароль" (то есть, номер с тремя измененными цифрами), Хрень должна услышать "отзыв" (то есть, правильный номер). Если лже-Вася не назвал Хрени правильный номер, а вместо этого тупо повесил трубку, то Хрень по закону должна во-первых уточнить через телефонную компанию, на какой номер телефона она нарвалась (естественно телефонная компания это ей сообщит, не уточняя имя владельца номера), мгновенно оповестить настоящего Васю и заявить в полицию. Лже-Вася может очень здорово пострадать.

Так что практическая вероятность такого сценария крайне мала. Думаю, она сравнима с вероятностью наугад набрать правильный пин-код найденной на улице чужой кредитной карты. :)
Последний раз редактировалось Шшок 12 фев 2012, 17:02, всего редактировалось 1 раз.
В борьбе бобра с козлом побеждает бобро. Или козло.

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

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

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

Инна писал(а): Итак, 4 компьютера играют в карты между собой. Они должны разложить колоду на четверых (каждому - равное число карт).
Каждый компьютер может передать информацию любому другому так, что двое остальных ее не узнают. Можно еще сообщать что-то вслух, и больше ничего.
Никаких сторонних источников нет. Как им договориться, чтобы каждый знал свои карты, и не имел НИКАКОЙ информации о картах других (то есть любой расклад между тремя другими для четвертого компьютера был возможен).
Я не уверен, что правильно понял условие задачи. Но:
Комп А случайным образом выбирает из закрытой колоды 13 карт и оставляет у себя в закрытом виде (то есть, не глядя в них). Остальные карты (в которые он не смотрел, и которые, соответственно, ему не известны) передает компу B.
Комп В, не открывая полученную от А колоду, выбирает из нее случайным образом 13 карт, оставляет себе, а оставшиеся карты в закрытую передает компу С.
Комп С делает то же самое и отдает оставшиеся 13 карт компу D.
После этого все компы одновременно смотрят в свои карты.
И всё. Теперь каждый комп знает только свои карты и не знает чужие.
Не пойму, что тут не так...
В борьбе бобра с козлом побеждает бобро. Или козло.

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

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

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

Шшок писал(а):Комп А случайным образом выбирает из закрытой колоды 13 карт и оставляет у себя в закрытом виде (то есть, не глядя в них).
Это ж компы, а не люди. Они не могут взять НЕ глядя :) А уж дать после этого НЕ глядя, это совсем из разряда фантастики :)
Иначе задачка так бы и звучала: "4 человека..." :) А ответ был бы "сдает не глядя каждому по одной карте".
Я правда не совсем понимаю формулировку "Можно еще сообщать что-то вслух", видимо имеется в виду "широковещательный запрос" на все устройства в сети :) Необходимость замечания не ясна, возможность сообщить что-то одному ПК есть, следовательно, есть возможность сообщить это каждому. Но зачем это может понадобиться, загадка.

Ответить

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