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

Притворитесь, что угадываете их мысли, и скажите, что три цифры — это слишком просто. Чтобы усложнить задачу, нужно увеличить числа. Чтобы им было проще, а вам — сложнее, они должны еще раз ввести то же самое трехзначное число, и тогда у каждого получится шестизначное. Например, если изначально они ввели 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, а это слишком очевидно, чтобы казаться волшебным.