У нас в гостях журнал «Квант»

Они хорошо помнят, как 30 лет назад любители математики и физики получили этот чудесный подарок из рук ученых и педагогов, во главе которых стояли академики И. К. Кикоин и А. Н. Колмогоров. Тем, кто в школьные годы испытал удовольствие от решения красивых задач по математике и физике и от чтения интересных статей, кому «Квант» помог определиться и поступить в институт, будет приятно узнать, что любимый журнал до сих пор «...жив и даже неплохо выглядит». Возможно, такой поклонник «Кванта» не только расскажет об этом друзьям и знакомым, но и подумает: «А не подписаться ли на «Квант» для моего сына (дочери, племянника, внука)?» Наверное, ему захочется побольше узнать о современном «Кванте», о составе и рубриках журнала, о его Приложениях (теперь у «Кванта» есть Приложения!). Если у ваших друзей или в вашей библиотеке нет «Кванта» за последние годы, приезжайте к нам в редакцию (Москва, Ленинский проспект, 64-А) или позвоните нам по телефонам (095) 930-56-48 и (095) 930-56-41. Информацию о «Кванте» можно также найти в Интернете: в журнале «Курьер образования» (www.courier.com.ru) и на сайте Vivos Voco (www.accessnet.ru/vivovoco). А можно подписаться и на один номер (индекс 70465) – надеемся, после этого вам не захочется с нами расстаться.

Сегодня мы предлагаем читателям журнала «Компьютер в школе» два фрагмента (с небольшими изменениями) из статей, опубликованных в «Кванте» (№ 6, 1998, и № 4, 5, 1999). В первой обсуждались три задачи, в постановке и анализе которых участвовал компьютер. А во второй, ответной, была защищена честь человеческого рода (уже ранее ущемленная суперкомпьютером, бессовестно обыгравшим Каспарова): для решения этих задач достаточно головы на плечах!

Ум хорошо, а пять лучше

Говорят, математика наиболее быстро развивается в периоды кризиса экономики, потому что для неe не требуется дорогостоящее оборудование, а лишь карандаш, бумага да голова на плечах. Так-то оно так, но, право, наличие компьютера ничуть не повредит, лучше всего – с процессором Pentium. Ведь что такое Pentium? В переводе «пенти» – это, несомненно, пять, а «ум» – он и есть ум. Таким образом, Pentium означает ни много ни мало пять умов, и, имея его в своем распоряжении, мы сразу как бы становимся во главе целого ученого совета, который способен на великие дела под нашим руководством!

Шутки шутками, но компьютер может многое, и, видимо, зря некоторые математики относятся к нему с некоторым пренебрежением. Каспаров тоже, помнится... Но не будем о грустном. В этой статье вниманию читателя предлагаются три задачи, которые не то что решить, но даже толком сформулировать без компьютера было бы невозможно.

Рассмотрим разбиение натурального ряда на две возрастающие непересекающиеся последовательности a₁23<... и b₁23<..., которые при любом натуральном n удовлетворяют условию b_n=a_n+n. Двигаясь по натуральному ряду, можно последовательно вычислять члены обеих последовательностей. А именно, поскольку a_nn, наименьшее натуральное число, то есть 1, должно равняться a1, откуда немедленно b₁=1+1=2. Теперь ясно, что наименьшее свободное число, то есть 3, это a₂, откуда b₂=3+2=5. После этого наименьшим неиспользованным числом оказывается a₃=4, откуда b₃=4+3=7. Так можно действовать бесконечно, каждый раз выбирая наименьшее неиспользованное натуральное число и именно его полагая равным an, а затем вычисляя b_n=a_n+n. (Советую выписать через запятую первые 50 натуральных чисел и применить этот алгоритм – сразу увидите, насколько все просто!)

Не получится ли так, что очередное вычисленное значение a_n или b_n окажется уже занято каким-то ранее определенным a_m или b_m, где m12<...n-1 и от b₁2<...n-1, и потому an не может совпадать ни с одним из них; число b_n=a_n+n>a_n-1+n-1=b_n-1 тоже не может ни с чем совпасть.

Назовем натуральные числа, принадлежащие последовательности an, A-числами, а принадлежащие последовательности b_n – B-числами. Вот как выглядит начало натурального ряда после замены каждого числа соответствующей буквой A или B:

Как видите, между соседними буквами B всегда располагается одна или две буквы A. Интересно выяснить, к какому пределу стремится отношение количества A-чисел к количеству B-чисел. Тут на помощь пришел компьютер. Первые несколько миллионов натуральных чисел были распределены между последовательностями, а затем найдено отношение количеств A и B чисел. Оно оказалось равно 1,618033...

Да ведь это же... Ну, конечно! Грех не узнать знаменитое золотое сечение, т. е. (1 +5^1/2)/2. Откуда оно взялось?.

Pentium хорошо, а ум лучше

Проделав при помощи Pentium’а вычисления для первых нескольких миллионов натуральных чисел, И. Ф. Акулич пришел к красивой и смелой гипотезе: отношение количества A-чисел к количеству B-чисел стремится к «золотому сечению».

Эта гипотеза верна. Более того, a_n = [(1+5^1/2)n/2], b_n = a_n+n =[(1+5^1/2)n/2],+ n = [(3+5^1/2)n/2], где квадратные скобки обозначают целую часть, т. е. [x] — это наибольшее целое число, не превосходящее числа x.

Как же доказать эти замечательные формулы? И неужели я первый догадался рассмотреть выражения [ n] и [ n]? Нет, в 1877 году в «Теории звука» лорд Рэлей писал: «Если x есть некоторое положительное иррациональное число, меньшее единицы, то можно взять два ряда величин n/x и n/(1--x), где n=1, 2, 3,...; каждое число, принадлежащее к тому или иному ряду, и только оно одно, будет заключено между двумя последовательными натуральными числами». Другими словами, последовательности a_n=[n/x] и b_n=[n/(1-x)] заполняют без пропусков и перекрытий весь натуральный ряд, если 0

Интересующие нас явные формулы получаются из формул Рэлея при x = 2/(1+5^1/2), поскольку при этом величина 1-x равна как раз x = 2/(1+5^1/2) (проверьте!).

В общем случае, обозначив a = =1/x и b = 1/(1-x), можно переформулировать утверждение Рэлея следующим образом (с этого момента, заметьте, числа a и b не обязательно суть (1+5^1/2) /2 и (3+5^1/2)/2):

Теорема. Если и – положительные иррациональные числа, связанные соотношением 1/+1/=1, то среди чисел вида [ n] и [ n], где n [ N, каждое натуральное число встречается ровно один раз.

Доказательство. Левее любого натурального числа N лежат [N/] членов последовательности [], [2], [3],...и [N/] членов последовательности [], [2], [3],... Поскольку и иррациональны, числа N/ и N/ имеют ненулевые дробные части. Далее, сумма

является целым числом, так что дробные части слагаемых дополняют друг друга, т. е. в сумме дают в точности 1. Значит, сумма целых частей [N/]+[N/] равна N-1, то есть левее числа N лежит в точности N-1 членов этих последовательностей. Как легко понять, просматривая натуральный ряд слева направо (любитель строгости сказал бы: применяя индукцию), это как раз означает, что рассматриваемые последовательности однократно покрывают натуральный ряд.

Упражнения

1. Убедитесь, что из формул для a_n и b_n следует утверждение И. Ф. Акулича.

Указание. Количество А-чисел, не превосходящих an, равно n, а количество В-чисел равно a_n- n.

2. Докажите, что последовательности, заданные формулами a_n = n2^1/2 и b_n = a_n+2n, заполняют весь натуральный ряд без пропусков и перекрытий.

Указание.