Есть идея! - [27]
Неожиданные решения арифметических задач
Говоря об арифметике, разные люди вкладывают в это понятие различное содержание. Мы будем понимать под арифметикой все, что так или иначе связано с изучением свойств целых чисел и операций сложения, вычитания, умножения и деления, производимых над числами.
Когда-то, на заре человечества (точную дату не может назвать ни один антрополог), первобытные люди открыли, что предметы можно считать и результат счета не зависит от того, в каком порядке сосчитаны предметы. Например, если вы приметесь считать двух овец по пальцам, то результат будет одним и тем же независимо от того, с какой овцы вы начнете считать и будете ли вы загибать пальцы с мизинца или с большого пальца. У вас всегда получится 2, а если вы сосчитаете две овцы, а потом еще одну, то у вас всегда получится 3.
Такие арифметические теоремы, как «2 + 1 = 3», созревали и становились достоянием умов на протяжении нескольких столетий. Если бы мы могли прокрутить назад пленку, на которой была бы запечатлена история человечества, то вряд ли нам удалось найти какой-то век, о котором можно было бы с уверенностью сказать: «Именно тогда человечество открыло арифметику». Маленькие дети овладевают понятием числа так же постепенно и незаметно. В один прекрасный день ребенок может впервые заявить изумленным родителям: «Один плюс один — два», но смысл этого утверждения ясен малышу задолго до того, как он выскажет свою первую арифметическую теорему.
Все истинные теоремы арифметики следуют непосредственно из аксиом и определений числовой системы, но это отнюдь не означает, будто истинность или ложность любого арифметического утверждения легко распознается на слух. Если кто-нибудь скажет, что при умножении 12345679 на 9 получается 111111111, вы можете не верить ему до тех пор, пока сами не умножите одно число на другое. Существуют арифметические теоремы, которые просто сформулировать, но так трудно доказать, что никто пока не знает, верны ли они. Примерам таких утверждений может служить знаменитая гипотеза Гольбаха: всякое четное число больше 2 представимо в виде суммы двух простых чисел. Никому до сих пор не удалось ни доказать ее, ни построить контрпример.
В этой главе мы рассмотрим несколько задач о числах, допускающих неожиданно простые решения, додуматься до которых не так-то просто. При выборе задач мы отдавали предпочтение таким, которые при всей элементарности служили бы ступенькой, позволяющей читателю подняться на более высокую ступень арифметики, получившей название теории чисел. Например, рассказ-задача «Разбитые грампластинки» вводит в круг простейших идей диофантова анализа — решения уравнений в целых числах. Другая задача «Один лишний» познакомит вас с важным понятием наименьшего общего кратного и интересным фокусом, основанным на замечательной «китайской теореме об остатках».
Дихотомия (последовательное разбиение множества на 2 части), играющая важную роль в вычислительной технике и теории автоматической сортировки данных, лежит в основе задачи об угадывании номера телефона Элен и позволяет читателю войти в круг вопросов, связанных с двоичной системой счисления. Принцип «птичка в клетке», известный также под названием принципа Дирихле, позволяет доказывать многие важные факты из теории чисел. Мы используем его для доказательства двух забавных утверждений: о бумажных долларах и о числе волос на голове человека. Свойство двух целых чисел быть взаимно простыми (не иметь общих делителей, кроме единицы) позволяет доказать, что, за исключением 12 часов, часовая, минутная и секундная стрелки часов никогда не совпадают (обычно это вычисление доказывают, проделывая довольно громоздкие выкладки).
Задача о счете по бутылкам легко решается, если воспользоваться понятием сравнения по модулю, и заставляет вспомнить о знаменитой задаче Иосифа Флавия, которую можно удивительно наглядно продемонстрировать при помощи колоды игральных карт.
Хотя задачи, собранные в этой главе, математики сочли бы тривиальными, открываемые ими направления для исследований в теории чисел далеко не тривиальны и не могут не поражать изяществом и идейным богатством древнейшей из всех дедуктивных систем — системы, оперирующей с символами, обозначающими знакомые всем числа.
Разбитые грампластинки
Больше всего на свете Боб и Элен любили всякого рода головоломки. Особенно им нравилось ставить в тупик друг друга и своих друзей каверзными вопросами.
Однажды, когда Боб и Элен проезжали мимо магазина грампластинок, Боб задал Элен вопрос.
Боб. Ты все еще собираешь пластинки с джазовой музыкой?
Элен. Нет, половину всех пластинок и еще полпластинки я подарила Сьюзен.
Элен. Половину оставшихся пластинок и еще полпластинки я подарила Джо.
Элен. После этого у меня осталась одна пластинка. Я подарю ее тебе, если ты скажешь, сколько пластинок было у меня в коллекции до того, как я начала ее раздавать.
Боб не сразу смог решить задачу, так как не мог понять, зачем Элен понадобилось дарить друзьям половинки пластинок.
Внезапно его осенила блестящая мысль, и он понял, что ни одна пластинка не была разбита на половники. Боб ответил на вопрос Элен, и та подарила ему последнюю пластинку из своей коллекция.
