Небольшое вступление:
...все карты колоды можно расположить по порядку. Сам порядок неважен, главное, чтобы он был одинаков у помощника и фокусника. Для меня, например, естественен «преферансный» порядок, по старшинству от двойки до десятки, затем от валета к королю, затем туз. Среди карт одного значения — например, среди шестерок — самая младшая шестерка пик, затем, по порядку старшинства, треф, червей и бубен. Если вы играете в бридж, удобный порядок для вас будет другой. Сейчас важно, что порядок возможно установить.
...Итак, если у нас колода с 52 картами, то мы можем заменить карты на числа от 1 до 52 (по установленному выше порядку). Можно пойти ещё дальше и взять "колоду" с 124 числами.
Теперь, собственно, фокус:
Я предлагаю студентам назвать мне пять номеров в пределах от 1 до 100 (можно даже до 124). Например, пусть мне назвали числа 13, 34, 36, 81, 95 (они могут быть совершенно произвольными). Я выбираю из них одно, которое далее надлежит угадать моей программе. В данном случае я скрываю число 81, а оставшиеся четыре числа располагаю в некотором порядке и предлагаю ввести эти данные в программу. Студенты вводят числа таким образом: 36, 34, 95, 13, нажимают клавишу Enter, и программа тут же выдаёт на экран "спрятанное" число 81! Хочу обратить внимание, что введённые четыре числа никак вроде бы не указывают именно на 81 -- с равным успехом можно было бы подумать на любое другое число.
Далее под "катом" я объясняю механизм угадывания. Он основан на чисто математических соображениях. Никаких "левых" подсказок программа не получает, то есть тут всё исключительно "по-честному". Более того, любой желающий сможет сам продемонстрировать такой фокус после моего разъяснения.
Здесь, я полную разгадку не привожу, а только начальные рассуждения и ссылку для тех, кто хочет прочитать всё. Советую перед кликом на ссылку ещё раз попытаться решить самому.
В третьей части я приведу обобщение этой задачи на n выбранных карт.
Ниже есть продолжение.
Прежде всего, давайте вдумаемся в то, что же я сообщаю своей программе помимо набора из четырёх чисел. Я ведь их располагаю в определённом порядке, и этим даю некую вполне конкретную информацию. Если имеются числа a, b, c, d, упорядоченные по возрастанию, то расположить их в каком-то порядке я могу в точности 24 различными способами, в чём легко убедиться непосредственно.
Можно составить полную таблицу всех таких перестановок, занумеровав их каким-либо способом, например:
1) abcd
2) abdc
3) acbd
4) adbc
.......
23) dcab
24) dcba
В примере выше мы имеем дело с перестановкой типа cbda [36, 34, 95, 13, в том смысле, что 13(a)<=34(b)<=36(c)<=95(d)] и она в таблице (которую я привёл в сокращённом виде) имеет номер 16. То есть фактически можно считать, что я сообщил программе четыре числа по порядку, но дополнительно передал некую специфическую информацию, указав на один номер из 24.
Теперь не было бы никакой проблемы, если бы изначально выбирались числа в небольших пределах -- скажем, от 1 до 28. Тогда я мог бы просто указать на один номер из 24 оставшихся, и в угадывании не было бы никакого "чуда". Но в нашем случае, даже если брать числа от 1 до 100, то я при помощи номера от 1 до 24 указываю каким-то орбразом на одно число из 96 (а если брать числа от 1 до 124, то и вообще на одно из 120). Каким же образом это удаётся делать, то есть откуда ещё программа берёт информацию?
Далее решение, см. тут http://falcao.livejournal.com/180432.html
http://my-tribune.blogspot.com/2011/08/blog-post_12.html
http://falcao.livejournal.com/180432.html
http://fregimus.livejournal.com/145468.html
No comments:
Post a Comment