Задачи

«КВАНТ» ДЛЯ МЛАДШИХ ШКОЛЬНИКОВ

Электронные часы показывают время от 00:00 до 23:59. Поезд отправился утром, когда часы показывали время$^{ab}$ $:^{cd}$, а прибыл тогда, когда часы

В каждой клетке таблицы $3^{u} 3$ стоит по одному натуральному числу, причем все девять чисел различны. Известно, что можно вычеркнуть по одному показывали $время^{cd} :^{ab}$. Сколько времени поезд находился в пути, если известно, что он ехал больше 6, но меньше 7 часов? Н.Агаханов такому числу в каждой строчке, что в каждой строчке суммы двух оставшихся чисел будут равны одному и тому же числу x. Также можно вычеркнуть по одному такому числу в каждом столбце, что в каждом столбце суммы двух оставшихся чисел будут равны одному и тому же числу y. Может ли оказаться, что x = y? А.Терёшин

Клетчатый квадрат $27 см^{u} 27$ см (длина стороны клетки 1 см) разрезали на 5 клетчатых прямоугольников одинакового периметра. Могло ли оказаться, что суммарная длина разрезов внутри квадрата равна 82 см? Фольклор

Эти задачи предлагались на муниципальном этапе Всероссийской олимпиады по математике в Московской области.

На столе лежат 90 карточек с числами от 1 до 90. Двое играют в следующую игру. Ходят по очереди. За один ход можно взять со стола любую карточку. Игра заканчивается, когда на столе останется две карточки. Второй выигрывает, если числа на оставшихся карточках отличаются ровно на 10. Иначе выигрывает первый. Кто выигрывает при правильной игре? О.Подлипский

Иллюстрации Д.Гришуковой

Задачи

37

МАТЕМАТИЧЕСКИЙ

написал Петя, цифры, которые будет печатать компьютер по его программе, также начнут периодически повторяться. Итак, компьютер может печатать десятичные разложения только рациональных чисел. Как видите, Петино намерение неосуществимо из-за ограниченности размеров реального компьютера. Если бы число ячеек памяти компьютера было не ограничено, то составить программу для вычисления корня из двух было бы несложно.

Упражнение 10. Для какой последовательности цифр можно сконструировать автомат, имеющий не более 100 состояний, который может ее напечатать?

Однако бывают такие задачи, с которыми не справится и компьютер бесконечных размеров. Такие задачи называют алгоритмически неразрешимыми. Возможно, вы уже имели дело с уравнениями в целых числах и знаете, как трудно бывает найти решение. Это не случайно – как показывает замечательная теорема Матиясевича (см. «Квант» №5 за 1975 г.), задача решения таких уравнений алгоритмически неразрешима. Впрочем, и не прибегая к услугам компьютера, можно продемонстрировать, что даже автоматическое устройство, умеющее выполнять программы любой сложности и длины, все равно не способно решить многие очень просто формулируемые задачи. В этом нам снова поможет идея периодичности. Рассмотрим совсем простой с виду автомат – Чертежник. Он может передвигаться по клетчатому листу бумаги, закрашивая клетки. Будем изображать направление движения Чертежника стрелкой. Для Чертежника допустимы всего три действия: 1. «ЗАКРАСИТЬ» – закрасить клетку. 2. «НАЛЕВО» – повернуться на 90 градусов налево вокруг начала стрелки. 3. «ПРЫГНУТЬ» – перепрыгнуть в центр соседней клетки по направлению стрелки. Кроме того, Чертежник умеет проверять условие «ВПЕРЕДИ КРАЙ». На первый взгляд кажется, что Чертежник еще примитивнее, чем Минотавр: он даже не понимает команду «НАПРАВО». Но простота обманчива. Чтобы привыкнуть к Чертежнику и убедиться в его нетривиальности, попробуйте справиться с упражнениями 10–11.

КРУЖОК

Программы для Чертежника можно записывать в любом удобном для вас виде, используя любые способы записи ветвлений, циклов и подпрограмм. Нельзя только заставлять Чертежника выполнять невыполнимые для него команды (например, «НАПРА- ВО») и проверять непонятные ему условия (например, условие «СЛЕВА КРАЙ»). И что еще очень важно – Чертежник не умеет считать. Он не способен выполнять циклы с параметрами и работать с числовыми (а также с любыми другими) переменными. Если читателю неуютно работать с программой на «произвольном» языке, то будем пользоваться ЧЕР-БЕЙСИКОМ: в каждой строке стоит номер команды и команда только вида GOTO N (перейти к команде номер N), «ЗАКРАСИТЬ», «НАЛЕВО», «ПРЫГ- НУТЬ» или условный переход ЕСЛИ КРАЙ, ТО GOTO N. И если нет перехода, то следующей будет выполняться команда, имеющая следующий номер.

Упражнения

11. Напишите программу для Чертежника, по которой он на любом листе бумаги: а) дойдет до угла листа, куда бы мы его не поместили; б) закрасит все клетки листа; в) отойдет от края листа, если его поместить у края; г) определит, в углу он находится или нет, закрасит угловую клетку, если он в углу, и останется в исходном положении, если нет. 12. Напишите программу для Чертежника, по которой он на любом квадратном листе бумаги: а) начав из положения на рисунке 2, нарисует полосу из k 2 клеток, если k четно, и вернется в исходное положение, ничего не закрасив, если k нечетно; б*) закрасит все клетки квадрата, кроме клеток, содержащих его центр (в зависимости от четности длины стороны листа центр – это одна клетка или четыре клетки).

Рис. 2

40

К В А НT 2024/№3

Прилагательное «модельные» не случайно – это очень похоже на то, что делают естествоиспытатели, отбрасывая часть свойств явления природы, чтобы сделать его обозримым. На часто встречающиеся идеи, «стандартные рассуждения» (например, принцип Дирихле, цикличность) можно смотреть и как на модели ситуаций. Эти модели столь схематичны, что выглядят тривиальными, однако знание таких «тривиальностей» сильно облегчает жизнь.

Упражнения

16. Допустим, что Чертежник умеет не только закрашивать, но и стирать краску с закрашенной клетки (скажем, по команде «СТЕРЕТЬ»). а) Напишите программу для Чертежника, по которой он закрасит центральные клетки и только их. б) Докажите, что нельзя составить программу для «стирающего» Чертежника, по которой он на любом квадратном листе бумаги нарисует систему вложенных квадратов (рис. 5).

Рис. 4

но моделировать с помощью показателей степеней при простых числах – где есть один индекс, там есть и много. Из этого факта можно извлечь алгоритмическую неразрешимость ряда утверждений – например, уже упомянутую теорему Матиясевича. Вы видели, как работает идея цикличности. Хотя она и выглядит довольно просто, задачи, в которых эта идея является основной, не всегда легкие. В чем же здесь дело? Оказывается, что даже очень простые ключевые идеи хорошо знать заранее, иначе их трудно обнаружить среди других идей и технических сложностей. Если ключевая идея неизвестна, а технические сложности присутствуют, то идею надо «добыть», но не прямо, а с помощью других задач. Ведь задача существует не сама по себе, а в окружении ей родственных (даже для решения «одноклеточной» задачи 1 понадобилось рассмотреть последние цифры всех степеней двойки). Поэтому изучают задачи, идейно связанные с данной (так было придумано решение задачи 13 про центр квадрата). Часто для этой цели рассматривают важнейшие частные случаи или другие модельные задачи, в которых трудности присутствуют в «ослабленном виде» и меньше технических сложностей.

Рис. 5

17. Напишите интерпретаторы языков Минотавра и Чертежника.

Обобщение идеи цикличности

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

42

КВАНТ 2024/№3

19**. Пусть a – иррациональное число, а b – произвольное число из интервала 0; 1, q m есть минимум дробной части n ˜ a, где $n <^{m}$ целое. Аналогично, r m есть минимум дробной $части^{b} n ˜^{a}$. Докажите, что q m! r m при бесконечно $многих^{m.} 20.$ а) Докажите, что числа, кратные 2, сколь угодно близко подходят к числам $вида^{n} 1 2$, где n – натуральное. б*) Докажите, что степень двойки может начинаться с любого числа девяток. Указание. Прологарифмируйте по основанию 10 неравенство $0,9^{…} 9$ ˜ $10^{k} 2^{l} 10^{k}$. Воспользуйтесь иррациональностью log 2. в*) С какой вероятностью наугад взятая степень двойки начинается с единицы? г*) Докажите, что найдется такое n, что числа $2^{n}$ и $3^{n}$ одновременно начинаются с цифр $1000...^{21*.}$ Пусть отображение F переводит единичный квадрат K в себя и сохраняет площадь каждого его подмножества. Докажите, что для любого подмножества квадрата U, площадь которого больше нуля, найдется точка x из U такая, что при некотором $n > 0 точка^{F} …^{x}$ … (n раз) тоже принадлежит U. Несколько более общее утверждение называется теоремой Пуанкаре о возвращении. Эта теорема приводит к несколько неожиданному выводу: если в герметичной комнате открыть флакон с духами, то почти наверняка через некоторое время все молекулы пахучего вещества снова соберутся во флаконе (правда, «некоторое» время намного превышает время жизни Вселенной). Доказательство этого факта напоминает рассуждения в задачах про стадо минотавров или кентавров: положение всех молекул примерно так же описывается точкой пространства состояний (фазового пространства), возвращение устанавливается с помощью теоремы Пуанкаре. Часто причина периодичности в природе состоит в том, что если множество состояний ограничено, то два состояния «почти повторятся» и будут еще близки некоторое время. Об этом задумывались еще древние. Статью о возвращении мы закончим возвращением к Екклесиасту: «Восходит солнце, и заходит солнце, и спешит к месту своему, где оно восходит. Идет ветер к югу, и переходит к северу, кружится, кружится на ходу своем и возвращается ветер на круги

свои. Все реки текут в море, но море не переполняется; к тому месту, откуда реки текут они возвращаются, чтобы опять течь… Что было, то и будет; и что делалось, то и будет делаться, и нет ничего нового под солнцем».

• • • Приведем еще несколько задач на рассмотренные темы.

1*. Периодична ли функция y cos $x cos^{5} 2 x cos^{5} 4x cos^{5} 8x$?

2. Может ли сумма двух периодических функций с наименьшими периодами 1 и 2 снова быть периодической функцией? 3**. Общее утверждение: пусть $a_{1}$, … $, a_{n}$ – действительные числа такие, что никакие из них не выражаются через другие с помощью линейной комбинации с рациональными коэффициентами. Тогда для любого набора $0 b_{i} 1$ и любого H! 0 найдется такое L, что при всех i верно неравенство L ˜ a i b i H (для наугад выбранного L это выполнено с вероятностью $H^{n} ). 4.$ Дана бумага в клетку. Через два узла проведены параллельные прямые. Докажите, что в образовавшейся замкнутой полосе лежит бесконечно много узлов сетки. 5. а) Докажите, что если радиус окружности стремится к бесконечности, то расстояние от нее до ближайшей целой точки стремится к нулю. б) К нулю стремится также отношение числа целых точек, попавших на окружность, к ее радиусу. 6. Вдоль коридора института МИМИНО гуляют пять ученых, дойдя до конца коридора, каждый поворачивает назад. Пока Главный проходит коридор один раз, Ведущий проходит два раза, Старший – три, Средний – пять, Младший – семь раз. Докажите, что найдется момент, когда все они движутся к одному концу. 7. Укажите явно такую степень пятерки, что в ее десятичной записи встретится подряд более 1000 нулей. А такую, чтобы встретилась комбинация ровно из 1000 нулей, идущих подряд? 8. Докажите, что найдется степень тройки, которая начинается теми же 1000 цифрами, что и кончается. 9. Даны две прямые, образующие угол M. На одной взята точка M и в этой точке сидит блоха, которая прыгает с одной прямой на другую ровно на 1 см, причем всегда в точку, отличную от предыдущей. Докажите, что если блоха снова оказалась в исходной точке, то число M S рационально. 10. Если косинус угла равен 1 3, то его градусная мера иррациональна. Докажите это. Обобщите задачу.