Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн

Предложите трем друзьям ввести произвольное число в калькуляторы (или мобильные телефоны, если в них есть калькулятор). Скажите, что вы в точности предскажете, на какие числа будет делиться выбранное произвольное число. В калькуляторе можно указать абсолютно любое трехзначное число. Это их выбор. Однако этот выбор нужно держать в тайне от вас.

Притворитесь, что угадываете их мысли, и скажите, что три цифры — это слишком просто. Чтобы усложнить задачу, нужно увеличить числа. Чтобы им было проще, а вам — сложнее, они должны еще раз ввести то же самое трехзначное число, и тогда у каждого получится шестизначное. Например, если изначально они ввели 345, их новым числом будет 345 345.

Вы напрягаете свои телепатические возможности и сразу же называете разные маленькие числа, на которые их личные шестизначные числа делятся без остатка. Вы ответственно заявляете, что, хотя совершенно не представляете, что за числа они ввели, у первого друга число точно делится на 7, у второго — на 11, а у третьего — на 13. Остатка не будет. Друзья выполняют деление на калькуляторе, проверяют результат и показывают, что вы правы. Как вы и предсказали, остатка нет.

В заключительной части фокуса вы говорите, что моментально вычислите шестизначное число, которое будет без остатка делиться на три маленьких числа, которые вы уже дали, — три «случайных» числа, полученных из других, которые в начале выбрали ваши друзья. Вы называете шестизначное число, и снова калькулятор показывает, что вычисления в уме оказались абсолютно верными.

Магические совпадения совершенно случайны?

Секрет в том, что три названных вами маленьких числа — это всегда 7, 11 и 13. В остальном фокус является алгоритмическим и работает сам — он основан на математическом факте. Если записать число из трех цифр и дописать к нему те же самые три цифры, то у нас получится тот же результат, что и при умножении этого трехзначного числа на 1001. Почему? Умножая число на 1000, нужно поставить в конце три ноля. Умножая на 1001, мы умножаем на 1000 и приписываем в конце изначальное трехзначное число вместо трех нолей.

Например, 345 345 — это 345 × 1001 (345 000 + 345). Маленькие числа, которые вы используете в предсказании, — 7, 11 и 13. Однако 7 × 11 × 13 = 1001. Это значит, что, когда вы таким образом дублируете число, например 345, вы умножаете его на эти три числа. То есть 345 345 = 345 × 1001 — это абсолютно то же самое, что 345 345 = 345 × 7 × 11 × 13. Отсюда следует, что полученное шестизначное число будет делиться без остатка на любой из этих множителей, а потом на два оставшихся.

Благодаря этому математическому факту фокус срабатывает всегда, если вы используете числа 7, 11 и 13. На них будут без остатка делиться любые шестизначные числа из повторяющегося сочетания трех цифр. В заключительной части фокуса, когда вы продемонстрируете ваши поразительные математические способности, просто нужно получить любое шестизначное число такого рода, например 765 765. Конечно, оно будет делиться на 7, 11 и 13. Это неизбежно благодаря все тому же математическому принципу. Таким образом, за фокусом стоит математика, но волшебным его делает ваше выступление.

Выявление закономерности в математике привело к созданию обобщенного правила (математической теоремы), которое используется как алгоритм — в нашем случае для фокуса, а в других ситуациях оно служит основой для программы или разработки аппаратной части. Например, аппаратные модули, выполняющие быстрое умножение, часто используют похожий трюк, основанный на похожей теореме. Числа, записанные двоичным кодом, можно быстро умножить на два, просто сдвинув влево, то есть поставив в конце 0. Фактически никакого умножения не требуется.

Простые множители

Числа 7, 11 и 13 — это простые числа. То есть они делятся только на 1 и на самих себя. Проверьте: ни одно из них не делится на 2, на 3, на 4 и так далее. Эти три числа называются простыми множителями для 1001. Простые множители положительного целого числа — это простые числа, на которые оно делится без остатка.

Древнегреческий математик Евклид открыл, что каждое целое число больше 1, которое не относится к простым числам, можно получить, перемножив простые числа. Более того, для каждого целого числа существует только один набор простых множителей — эта комбинация уникальна. Этот факт называется теоремой о разложении на простые множители или основной теоремой арифметики.

Отсюда следует, что для числа 1001 существуют определенные простые числа, на которых основан наш фокус, — и это единственное такое сочетание. В нашем случае это 7, 11 и 13.

Тестируем математические закономерности

Знание математических закономерностей, лежащих в основе фокуса, поможет нам понять, что будет, если условия изменятся. Например, сработает ли фокус для однозначного числа — например, 3 и, соответственно, 33? Ответ отрицательный. Чтобы удвоить однозначное число, его нужно умножить на 11, а не на 1001. Число 33 — это 11, умноженное на 3. Пока все хорошо, но 11 — это простое число, а значит, оно не делится ни на что, кроме 1 и 11. Больше простых множителей нет. Фокус работает только для 11 и 1, а это слишком очевидно, чтобы казаться волшебным.

Получится ли фокус с удвоенным двузначным числом, например 3434? Ответ снова будет отрицательным, потому что 3434 — это 34, умноженное на 101, а 101 — тоже простое число. Математические знания позволяют нам предсказать, какие закономерности сработают, а какие необходимо проверить.

Вы сделаете фокус еще более надежным, если попросите друга быстро прочитать число вслух и моментально назовете, на что оно делится. Если друг сделает ошибку и, например, скажет 123124, вы сразу же ее исправите, указав на последнюю 4, и все же дадите правильный ответ с быстротой молнии. Это уже будет сопоставление с образцом как часть алгоритма проверки. Вы знаете, что здесь должно быть, и проверяете соответствие. Некоторые программы в системах с особыми требованиями к безопасности осуществляют схожую проверку. Программисты включают в код утверждения, которые являются истинными в момент работы программы в этой точке. Если утверждение неожиданно оказывается ложным, можно запустить специальный код, чтобы разобраться с проблемой. Правильный ввод чисел играет большую роль, и, если люди вводят неверные числа, очень важно, чтобы программа не игнорировала их, но указывала на проблему и давала человеку возможность исправить ошибку (в отличие от нашего фокуса). Это лишь некоторые из многочисленных способов писать надежные программы, чтобы избежать катастроф.

Поиск по запаху: фокус с пахнущей картой

Вот еще один фокус, который кажется невозможным и при этом весьма увлекателен. Чтобы его показать, нужно найти исключение из известной вам математической закономерности, одновременно скрывая его от аудитории. Вы используете способность «находить карту по запаху человека, выбравшего ее». Очевидно, показывая этот фокус, нужно действовать очень тактично!

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