Falcão (falcao) wrote,
Falcão
falcao

  • Mood:
  • Music:

фокус с угадыванием

На днях я продемонстрировал своим студентам один фокус с угадыванием чисел. Он был придуман мной на основе задачи, предлагавшейся несколько лет назад на "Турнире городов". Оригинал условия можно найти здесь -- речь идёт о последней задаче под пунктом б). Однако по ссылке можно не ходить, так как я сейчас опишу суть фокуса в слегка видоизменённом и "усиленном" виде. Вместо игральных карт можно иметь дело с числами, причём в более широком диапазоне. Роль моего "ассистента" играла простенькая компьютерная программа, написанная мной в Maple. Выглядело это всё следующим образом.

Я предлагаю студентам назвать мне пять номеров в пределах от 1 до 100 (можно даже до 124). Например, пусть мне назвали числа 13, 34, 36, 81, 95 (они могут быть совершенно произвольными). Я выбираю из них одно, которое далее надлежит угадать моей программе. В данном случае я скрываю число 81, а оставшиеся четыре числа располагаю в некотором порядке и предлагаю ввести эти данные в программу. Студенты вводят числа таким образом: 36, 34, 95, 13, нажимают клавишу Enter, и программа тут же выдаёт на экран "спрятанное" число 81! Хочу обратить внимание, что введённые четыре числа никак вроде бы не указывают именно на 81 -- с равным успехом можно было бы подумать на любое другое число.

Далее под "катом" я объясняю механизм угадывания. Он основан на чисто математических соображениях. Никаких "левых" подсказок программа не получает, то есть тут всё исключительно "по-честному". Более того, любой желающий сможет сам продемонстрировать такой фокус после моего разъяснения.

Прежде всего, давайте вдумаемся в то, что же я сообщаю своей программе помимо набора из четырёх чисел. Я ведь их располагаю в определённом порядке, и этим даю некую вполне конкретную информацию. Если имеются числа a, b, c, d, упорядоченные по возрастанию, то расположить их в каком-то порядке я могу в точности 24 различными способами, в чём легко убедиться непосредственно.

Можно составить полную таблицу всех таких перестановок, занумеровав их каким-либо способом, например:

1) abcd
2) abdc
3) acbd
4) adbc
.......
23) dcab
24) dcba

В примере выше мы имеем дело с перестановкой типа cbda, и она в таблице (которую я привёл в сокращённом виде) имеет номер 16. То есть фактически можно считать, что я сообщил программе четыре числа по порядку, но дополнительно передал некую специфическую информацию, указав на один номер из 24.

Теперь не было бы никакой проблемы, если бы изначально выбирались числа в небольших пределах -- скажем, от 1 до 28. Тогда я мог бы просто указать на один номер из 24 оставшихся, и в угадывании не было бы никакого "чуда". Но в нашем случае, даже если брать числа от 1 до 100, то я при помощи номера от 1 до 24 указываю каким-то орбразом на одно число из 96 (а если брать числа от 1 до 124, то и вообще на одно из 120). Каким же образом это удаётся делать, то есть откуда ещё программа берёт информацию?

Напомню, что тот номер, который мне надлежит спрятать, выбирается мной самим. Я не могу спрятать что попало -- такой фокус не может быть осуществлён. У меня есть некое правило, согласно которому я убираю один из пяти номеров. Мой "ассистент" (или составленная мной программа), разумеется, знает, каким именно правилом я руководствуюсь. И это как раз служит источником дополнительной информации.

Важно здесь то, что обсуждаемое правило не может быть каким попало. Например, если я буду прятать самый большой из номеров, то угадывание станет невозможным. Действительно, пусть мне назвали числа 1, 2, 3, 4, N, где N есть какое-то число от 5 до 100. Спрятав его и сообщив программе числа 1, 2, 3, 4 в каком-то выбранном мной порядке, я цели не добьюсь, так как роль числа N может играть слишком много чисел (а именно, более 24).

Каким же условиям должно удовлетворять правило? Критерий не так трудно сформулировать.

Пусть имеются четыре числа a, b, c, d. Пятое число e назовём подходящим для набора a, b, c, d, если согласно правилу, именно число e надлежит спрятать при заданном наборе a, b, c, d, e из пяти чисел. (Замечу во избежание недоразумений, что числа набора здесь не предполагаются расположенными по возрастанию.)

Любой человек, знающий правило, может к полученным им числам a, b, c, d "примерить" каждое из оставшихся чисел в следующем смысле: добавить его мысленно к a, b, c, d и посмотреть, а они ли должно быть выброшено согласно правилу? Если да, то оно будет одним из возможных "кандидатов" на ответ, а если нет, то не будет. То есть таким способом "ассистент" сможет составить список всех "подходящих" для данного набора чисел.

Критерий состоит в том, что список не должен быть слишком длинным. А именно, в нём не должно быть более 24 чисел. Если это условие выполнено, то фокус удался: получив в качестве "дополнительной информации" одно число от 1 до 24 (в примере выше это было 16), "ассистент" просто укажет на 16-е по порядку число в списке "подходящих". И наоборот: если в списке более 25 чисел, то угадывание принципиально невозможно.

Вспомним то правило, которое мы отвергли (скрывать самое большое число). Оно не годится, так как к набору 1, 2, 3, 4 оказыватся слишком много "подходящих" чисел! Это наводит на мысль, что нельзя прятать самое большое число слишком часто. И то же самое касается любого числа вот в каком смысле: скажем, если мы возьмём за правило всегда прятать второе по счёту число из пяти (при расположении чисел по порядку), то к набору 1, 98, 99, 100 опять-таки будет подходить любое из промежуточных чисел!

Поэтому выход состоит в том, чтобы иногда прятать первое по счёту число набора, иногда -- второе, иногда -- третье, и так далее, и чтобы этот выбор происходил в некотором смысле "равномерно". Однако номер изымаемого числа должен быть строго предопределён числами набора, и в качестве своего рода "рулетки" представляется подходящим сделать вот что: сложить все числа, а затем рассмотреть остаток при делении на 5. Его очень легко установить по последней цифре (то есть складывать достаточно лишь последние цифры), и далее принимается решение выбрасывать k-е число, если остаток равен k. Тут, правда, нужна оговорка, что если сумма делится на 5, то остаток равен нулю, но мы удаляем последнее по величине, пятое число набора.

Вернёмся к примеру выше, когда у нас имелись числа 13, 34, 36, 81, 95. Почему я решил скрыть именно 81? Потому что сумма этих пяти чисел оканчивается на 9, то есть при делении на 5 в остатке получается четыре, и я принимаю решение скрыть четвёртое по счёту число в упорядоченном списке.

И вот теперь осталось показать, что данное правило всегда работает. То есть к любому набору из четырёх чисел подходит не более 24 "кандидатов". Я сначала продемонстрирую это на примере, из которого общая закономерность должна стать ясной.

Итак, поместим себя на роль "ассистента", или компьютерной программы -- кому что нравится. Мы получили числа 13, 34, 36, 95, о порядке следования которых можно сейчас не думать, так как от него зависит лишь информация о номере "спрятанного" числа в списке "подходящих". У нас этот номер равен 16, и он пригодится нам на самом последнем шаге, когда из списка мы выделим 16-е по счёту число. А пока надо составить сам этот список. Что в него войдёт?

Итак, пусть спрятано число s. Оно может располагаться а) до 13 б) между 13 и 34 в) между 34 и 36 г) между 36 и 95 д) после 95. Каждый из этих случаев мы и проанализируем.

Итак, если s меньше 13, то в списке оно расположено первым. Это значит, что сумма s + 13 + 34 + 36 + 95 при делении на 5 даёт в остатке 1, так как s расположено первым. Отсюда легко понять, что s должно давать в остатке 3, то есть оканчиваться на 3 или на 8 (проверьте!). Таким свойством будут обладать числа 3, 8 и никакие другие, так как в пункте а) речь идёт о числах меньших 13. Важно отметить, что расстояние между соседними числами списка в каждом из пунктов в точности равно 5.

Пусть теперь s расположено строго между 13 и 34, то есть по счёту идёт вторым. Тогда, согласно правилу, сумма 13 + s + 34 + 36 + 95 даёт в остатке 2, а это означает, что в пункте б) число s даёт в остатке 4 -- на единицу больше, чем в предыдущем пункте! (Это сравнение важно для того, чтобы не производить лишних вычислений.) Таким образом, s здесь оканчивается на 4 или 9, и полный список для пункта б) получается такой: 14, 19, 24, 29.

В пункте в) получается, что s оканчивается на 0 или 5, и в качестве такового подходит как раз 35. Заметим, что когда диапазон очень узок, как здесь, то чисел с требуемым свойством может просто не оказаться.

Для пункта г) будут подходить числа, оканчивающиеся на 1 или 6, и их список таков: 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, 91. Отметим, что "угаданное" впоследствии число 81 как раз тут и находится, но пока это ничем особым из списка не выделяется.

Наконец, в пункте д) подходят числа, оканчивающиеся на 2 или 7, и потому в самом широком диапазоне (до 124 включительно) мы получаем здесь 97, 102, 107, 112, 117, 122.

Итак, все "подходящие" для набора 13, 34, 36, 95 числа нами выявлены. Составим их единый список:

3, 8, 14, 19, 24, 29, 35, 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, 91, 97, 102, 107, 112, 117, 122.

Легко видеть, что в нём ровно 24 числа, и что 16-м по счёту следует как раз 81. Именно его программа и выдаёт в качестве ответа. Осталось понять, почему же список получился именно такой. И почему эта закономерность сохранится всегда.

Обратим внимание на то, что разность между соседними числами списка здесь почти всегда равна 5. Это будет так для чисел из одного промежутка между четырьмя предъявленными программе числами 13, 34, 36, 95. Однако между определёнными соседними числами списка разность может увеличиваться. Скажем, почему она равна 6 между 8 и 14? Потому, что происходит "перескакивание" через 13. При переходе в следующий из "промежутков" (в данном случае -- между 13 и 34) остаток при делении на 5 увеличивается на 1, а потому "скачок" становится равен 6. То же самое касается "скачков" между 29 и 35, далее между 35 и 41, а потом между 91 и 97.

Напрашивается теперь вот какой приём. Выпишем все числа от 1 до 124, вычеркнув из них четыре уже использованных, то есть 13, 34, 36, 95. Останется 120 чисел, которым дадим теперь новые номера по порядку. Легко понять, что новый номер получается из старого при помощи вычитания количества "пропущенных" чисел из списка 13, 34, 36, 95, которые стоят перед данным. Например, новый номер числа 10 останется прежним, новый номер числа 50 уменьшится на 3 и станет равным 47, а новый номер числа 100 превратится в 96.

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

3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58, 63, 68, 73, 78, 83, 88, 93, 98, 103, 108, 113, 118.

Напомню, что это будут уже числа, не превосходящие 120, и поэтому их будет не более 120:5=24, что и требовалось установить.

Проведённый анализ показывает, что фокус способен работать "на пределе возможностей", то есть в диапазоне от 1 до 124. В более широком диапазоне он уже не может быть организован, что не так трудно понять на основе проведённого выше анализа.

В заключение добавлю, что для выявления числа 81, которое требуется угадать, нет необходимости составлять весь список. На основе того, что было сказано выше, можно понять, что искомый номер приблизительно будет равен 16*5=80, то есть содержаться он будет в диапазоне от 36 до 95. Зная это, можно выявить, какой остаток он должен давать при делении на 5: он равен 4, так как удаляется 4-е по счёту число из пяти.

Для тех, кто пожелает себя проверить, приведу один "контрольный" пример. Я возьму наугад 5 чисел: 3, 14, 15, 65, 92 (их я как бы "сконструировал" из десятичных знаков числа "пи" и далее упорядочил). Что из них следует скрыть? Сумма оканчивается на 9, то есть опять прячем 4-е число -- в данном случае это будет 65. Его номер в списке "подходящих" чисел можно быстро вычислить вот по какому правилу: прибавим к нему количество чисел в "пятёрке", которые его превышают, получая 66, и далее делим на 5, округляя "с недостатком", получая 13. Это значит, что именно 13-ю по счёту перестановку оставшихся чисел 3, 14, 15, 92 надо продемонстрировать. Можно выписать таблицу всех перестановок по несложному правилу и увидеть, что 13-й будет перестановка вида cabd, то есть в нашем случае это есть 15, 3, 14, 92.

Программа (или "ассистент"), получив эти числа, прежде всего увидит перестановку указанного вида и найдёт её в таблице, восстановив нашу "скрытую подсказку" в виде номера 13. Далее, если действовать "ускоренно", то надо умножить 13 на 5 и получить приблизительное значение спрятанного числа, равное 65. Поскольку оно находится между 15 и 92, то его номер в "пятёрке" равен 4. Тогда число s обладает тем свойством, что сумма 3 + 14 + 15 + s + 92 даёт в остатке 4 при делении на 5, откуда понятно, что s должно оканчиваться на 0 или 5. Это позволяет заключить, что наше число s в точности равно 65, после чего на всякий случай можно произвести ещё и проверку, поставив себя на место "фокусника" и убедившись в том, что именно оно приводит к перестановке под номером 13, как и ожидалось.

Комментарии, вопросы по разъяснению и всё прочее, как всегда, приветствуются.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 40 comments