Наша анкета

89

хватало журналных страниц, и многими темами приходилось жертвовать. Решая эту проблему, редакция приняла меры к увеличению в новом году числа страниц журнала до 80 в каждой номере. Большое внимание будет уделяться вопросом исследования космического пространства, астроνομии. Увеличится раздел «Искусство программирования», в котором основное внимание будет уделяться общим вопросом программирования (формализация задач, подготовка их к постановке на ЭВМ и т. п.). Обыт показывает, что те, кто имеет доступ к программируемому вычислительнойному устройству (от микрокалькулятора до персонального компьютера), очень быстро освивают техническую программирование, т. е. путь от алгоритма до программы. Сложнее оказывается путь от неформальной формулировки задачи до алгоритма.

Мы надемемся, что наши читатели еще активнее ответят на вопросы публикуемой ниже анкеты. При этом мы предлагаем вам проверки небольшой эксперимент. Возьмите монетку и подбросьте ее 9 раз (ровно девять!), записьвая при этом, что оказывается наверху — герб или цифра. Если все 9 раз наверху будет герб, то обязательно пришите нам анкету (хотя бы кратко ответив на все вопросы). Таким образом, «нулевым» вопросом анкеты будет следующий: сколько раз у вас выпал герб при 9 бросаниях.

Примечение. Каждый читатель этого номера журнала цикл из 9 бросаний может выполнять один раз.

А. Н. Виленкин

Наша анкета

Дорогие читатели! Для того чтобы при подготовке материалов к публикации в «Кванте» редакция могла учеть ваш интересы, уровень подготовки и вкусы, просим вас ответить на вопросы нашей традиционной анкеты.

Ответы высылайте на отдельном листе бумаги, сохранить numeraцию вопросов, до 10 января 1989 года. Наш адрес: 103006 Москва К-6, ул. Горького, д. 32/1, «Квант». На конверте сделайте пометку: «Анкета—88».

1. Фамилия, имя (не обязательно). Место учебы (город, сель; учебное заведение, класс, курс) или работы (профессия, специализность). Выписьайте вы журнал или берете у знакомых или в библиотеке?

2. Круг интересов (математика, физика, информастика, астроνομия). С какого года вы читаете наш журнал? Сколько человек читают ваш экземпляры «Кванта» (для подписчиков)?

3. Найболее и наименее интересные статьи по математике из числа опубликованных в 1988 году.

4. Найболее и наименее интересные статьи по физике из числа опубликованных в 1988 году.

5. Самая удачная и самая неудачная обложка журнала в 1988 году; ваше мнение об оформлении журнала.

6. Какие разделы журнала вам нравятся, а какие — нет? Какие новые разделы следовало бы ввести?

7. Какие материалы, опубликованные в «Кванте» в 1988 году, помогли в вашей работе или учете, что вы искали в «Кванте», но не нашли?

8. Общее мнение о журнале. О чем бы вы хотелиать на страницах нашего журнала в 1989—1990 годах?

90

О плоских кривых

1. См. табл.1.
2. См. рис. 1.
3. См. рис. 2.
4. Число точек пересечения прямой и кривой изменяется на 2 в момент касания. После повората на 180° это число остатуса прежним. Если сумма чисел, равных ±2, равна нулю, то чисел четное число.
5. Обойти каждую из кривых в двух направлениях и будем следить за числом точек пересечения касательного луча с другой кривой. Это число меняется при проходе точек пересечения кривых и точек касания двойных касательных с кривой. После обхода число точек пересечения не изменится. Получаем 4 равенства, сумма которых дает искомое соответствие.
6. Числа врашения равны 1, 1, 0, 2, 1, 3, 0, 0.
7. Кривую можно «раздуть» в окружность; число врашения равно 1.
8. Если точек перегиба нет, то кривая все время поворачивается в одну сторону и число врашения положительное.
9. При каждой перестройке четность числа кривых меняется. Поэтому четность числа кривых k, на которые расположется данная кривая, совпадает с четностью числа n+1, где n — число двойных точек. Четность числа врашения совпадает с четностью числа k.
10. См. рис. 3.
11. Каждый число встречется дважды, так как через каждую двойную точку мы проходим дважды. Выберем двойную точку с номером

Рис. 1. Рис. 2. Рис. 3.

Таблица.

| | | | | | |
| :— | :— | :— | :— | :— | :— |
| p | 0 | 2 | 2 | 1 | 5 |
| q | 0 | 0 | 0 | 0 | 2 |
| r | 0 | 4 | 2 | 0 | 2 |
| n | 0 | 0 | 1 | 1 | 2 |

k и сделаем в этой точке перестройку. Кривая распадется на две, и число их точек пересечения будет четным. В последовательности между двумя числами k будут стоять по одному разу как раз номера точек пересечения этих двух кривых.

Гармоническая колбания

1. $x + \frac{g}{l}x' = 0$. $W = \frac{mg}{2l}x^2 + \frac{m}{2}(x')^2$, $\omega = \sqrt{g/l}$.
2. $\omega = \sqrt{2g/(\pi R)}$.

XXII Всеюозная олимпиада по математике
8 класс

1. Ответ: 23 рассказа. Указание. После каждого расскада с нечетным числом страниц меняется четность начальной страницы следующего расскада, так что четность начальной страницы не меньше 14 раз.
2. Пусть [Ф] — площадь фигуры Ф. Обозначим точки, как показано на рисунке 4. Так как средняя линия треугольника отсекает одну четверту его площади,

$$[NSLT] = [ABCD] - \frac{3}{4}[ABC] - \frac{3}{4}[BCD] - \frac{1}{4}[ACD] - \frac{1}{4}[ABD], [MSKT] = [ABCD] - \frac{3}{4}[ABC] - \frac{1}{4}[ACD] - \frac{1}{4}[BCD] - \frac{3}{4}[ABD].$$

Из равенства $[NSLT] = [MSKT]$ получаем нуже утверждение: $[BCD] = [ABD]$.

3. Пусть $x = mn, y = nk, z = mk$, где $m, n$ и $k$ — натуральные числа. Тогда должно быть $n(k - m) = mk - 1$. Положив $k - m = 1$, получаем бесконечную серию решения:

$$x = m(m^2 + m - 1), y = (m + 1)(m^2 + m - 1); z = m(m + 1).$$

4. См. решения задачи M1115a).

5. Указание. Это отношение равно тангенсу угла, образуемого диагонального с бóльшим основанием трапеции.

6. См. решения задачи M1112.

7. Указание. Если $xy \neq 0$, то $1 - xy = \left(\frac{x^5 - y^5}{2x^2y^2}\right)^2$.

8. См. решения M1113.
   9 класс

9. Ответ: $m = -1989$. Указание. Уравнение приводится к виду

$$\frac{1989^{1988}}{1988^{1988}} = \frac{(m + 1)^{m + 1}}{m^{m + 1}}.$$

Обе дроби несократимы, так что $m^{m + 1} = 1988^{1988}$. Если $m \geq 1988$, то $m^{m + 1} > 1988^{1988}$. Если же $0 < m < 1988$, то $m^{m + 1} < 1988^{1988}$. Если $m < -1$, то при $n = -(m + 1)$ получим $1988^{1988} = n^n$, откуда $n = 1988$.

2. Указание. В треугольнике больший угол имеет больший синус, поэтому, например, $(\alpha - \beta)(\sin \alpha - \sin \beta) \geq 0$, или $\left(\frac{1}{\beta} - \frac{1}{\alpha}\right)(\sin \alpha - \sin \beta) \geq 0$.

3. Ответ. Нельзя. Предположим, что треугольник график дежурствует. Пусть согласно этот график $a$ раз меняется ученики 9 «А» и $b$ раз — ученики 9 «Б». Тогда, поскольку по условиям задачи ученик

91

9 «А» должен отделить с каждой учеником 9 «В», выполяется равенство $a+b=32\cdot 29$. При этом, поскольку по условию в конце должна выходить на дежурство первая пара, число $a$ кратно 32, а число $b$ кратно 29. Следовательно, $a=32\cdot 29-b$ кратно 29. Отсюда следует, что $a$ кратно 32\cdot 29, а так как, очевидно, $a>0$, то $a \geq 32\cdot 29$. Аналогично устанавливается, что $b \geq 32\cdot 29$, что противоречит равенству $a+b=32\cdot 29$.

4. Обозначим через $(l, n)$ наименьший угол, на котором надо повернуть прямую $l$ против часовой стрелки, чтобы она стала паралелова прямой $n$.
   Лемма. Точки $P, Q, R, S$, не лежащие на одной прямой, лежат на одной окружности тогда и только тогда, когда $(QP, QR) = (SP, SR)$ (рис. 5).
   Доказательство следует из теоремы о свойств углов, вписанных в окружность.
   Проведем теперь прямую $AK$, паралелную прямой $BC$ (точка $K$ принадлежит окружности $S$, рис. 6). Продолжим отрезок $KD$ за точку $D$ до пересечения с окружностью $S$ в точке $P_0$. Доказем, что для каждой точки $M$, удовлетворяющей условиям, точка $P$ совпадает с $P_0$. Возможны два случая.

1. Точки $N$ и $P_0$ различины. Так как точки $A, K, P_0, N$ лежат на окружности $S$, то $(AK, KP_0) = (AN, NP_0)$. Поскольку прямые $BC$ и $AK$ паралелны, $(AK, KP_0) = (BC, KP_0)$. Значит, $(MD, DP_0) = (MN, NP_0)$,
   т. е. точки $M, N, P_0, D$ лежат на одной окружности и, следовательно, паралелно, $P_0 = P$.
2. Точки $N$ и $P_0$ совпадают. При готовении с центром в точке $P_0$, переводящей точку $K$ в точку $D$, прямая $AP_0$ переходит в себя, а прямая $AK$ — в прямую $MD$ (поскольку $AK \parallel MD$). Значит, точка $A$ переходит в точку $M$. Поэтому окружность $S$ переходит в окружность, описанной около треугольника $NMD$. Поскольку центром готовится является точка $P_0 = N$, больше у этих окружностей общих точек нет, т. е. $P = P_0$.
   Теперь очень нужно использовать точка $M$ есть проекция точки $P_0$ на прямую $BC$. Эта проекция лежит внутри отрезка $BC$ (угол $A$ острый) и не совпадает с точкой $D$, так как угол $\angle KDC = \angle DKB + \angle KBD$ — туной.

5. Указание. При $n=4k+1$ числа $a_n$ нечетны. Рассматривая остатки от деления $a_n$ на 6, убедитесь, что $a_n$, например при $n=36p+17$ делится на 3.

6. См. решение M1111.

7. Ответ: $\sqrt{2}-\frac{1}{2}$. Указание. Можно считать, что $a+b \geq c+d$.
   Тогда $b+c \geq \frac{1}{2}(a+b+c+d)$ и $\frac{b}{c+d} + \frac{c}{a+b} = \frac{b+c}{c+d} - c\left(\frac{1}{c+d} - \frac{1}{a+b}\right) \geq \frac{1}{2}\frac{a+b+c+d}{c+d} - (c+d)\left(\frac{1}{c+d} - \frac{1}{a+b}\right) = \frac{1}{2}\frac{a+b+c+d}{c+d} - \frac{1}{2} \geq \sqrt{2}-\frac{1}{2}$.
   Значение $\sqrt{2}-\frac{1}{2}$ принимается, например, при $a=\sqrt{2}+1, b=\sqrt{2}-1, c=2, d=0$.

8. Переменную строки таблицы сверху вниз, столбцы — слева направо. Обозначим через $o_{i,k}^j$ операцию прибавления $i$-ой строки к $j$-му столбцу и вычитания этой строки из $k$-го столбца.
   Примена к данной таблице последовательно операции $o_{i,1}^1, o_{i,2}^2, \dots, o_{n,n-1}^1$, мы получим таблицу, в которой число, стоящее в $i$-ой строке и $j$-ом столбце, равно нулю, а остальные числа, не стоящие в последней строке или в последнем столбце, не изменились.
   Примена также последовательности операций для всех $i=1, 2, \dots, n-1$ и $j=1, 2, \dots, n-1$, мы получим таблицу, в которой числа, отличные от нуля, могут находиться только в последней строке или в последнем столбце. Но так как сумма чисел в любой строке и в любом столбце равна нулю (это свойство сохранения при применении операций), то в последней строке и в последнем столбце тоже стоит нулю.
   10 класс

9. Указание. Точки $B, E, D, C$ лежат на окружности с центром $O$ и диаметром $BC$, а перpendикulier $OH$ из $O$ на $ED$ делит этот отрезок пополам.

10. Ответ. $\sqrt{3}$. Указание. Рассмотрим $S^2$ и трижды примените неравенство о среднем арфметическом для двух чисел.

11. Ответ: 6 звеньев. Указание. Пусть ломана начинается в вершине $A$ и кончается в вершине $C$. Сфера радиусом 3 с центром в точке $A$ пересекает поверхность

92

Рис. 7.

Рис. 8.

куба по тем дугам: KL, LN и KN, где точки K, L, N — середины соответствующих ребер (рис. 7). Если точка M не совпадает с K, L, N и лежит на одной из дуг, то сфера радиусом 3 с центром в M проходит через точку A, а остальные точки куба содержит внутренние ребры. Поэтому ломана должна проходить через одну из точки K, L, N. На рисунке 8 показан пример ломаной из шести звенев.

4. См. решение M1115 6).

5. Указание. Без ограничения общности можно считать, что парабола имеет уравнение $y=ax^2$, а ломана имеет хотя бы одну вершину с положительной абсциссой. Доказите, что вершина с наиболее положительной абсциссой обязательно является конечной вершиной ломаной.

6. Ответ: $n=20$. Указание. Если $n<20$, то, вычитая из второго уравнения первое, умноженное на 10, получим, что модель левой части нового уравнения меньше 100.

7. См. решение M1120 a).

8. См. решение M1114.

9. Всегоозная olимпида школьников по информатике

T1. Будут напечатаны з неубывающим порядке простые числа, произведение которых равно n, т. е. разложение n на простые делители (с учетом кратности).

T2. Надо из площади Пр1 вычесть площадь пересечения Пр1 и Пр2, которое либо пусто, либо является прямогольником, координаты левого нижнего и правого верхнего углов которого находится как максимумы или минимумы соответствующих координат Пр1 и Пр2.

T3. Назовем маршрут следующей набор:

пункт отправления, последовательность рейсов (пункт отправления каждой из которых совпадает с пунктом прибитыя предыдущего, первоого — с пунктом отправления маршрута), конец маршрута (пункт прибитыя последнего рейса). Начав с «пустого» маршрута (город [1], город [1]), будем продолжать следующую операцию: если из конца маршрута выходит неиспользованный рейс, то вставляем его в маршрут; если такого рейса нет (это возможно только если начало и конец маршрута совпадают), то переносим начало и конец маршрута по первому рейсу, а первый рейс ставим последним. Когда число рейсов в маршруте сравняется с числом всех рейсов, будет найден колъевой маршрут.

T4. При решении задачи надо исходить из того, что ЭВМ работает быстро, а переменка ленты на магнитофоне — медленно, но в память ЭВМ весь файл пар фамилии не помещится. Участиками олимпиды были предложены разные алгоритмы. Возможен такой. Используя два магнитофона и держа в памяти ЭВМ 1000 пар фамилии, по исходному файлу пар фамилий лодей, стоящих на «расстоянии» 1 друг от друга, создается файл пар фамилия лодей, стоящих на «расстоянии» 2 (при наличии пар Ф1, Ф2 и Ф3, Ф3 в новый файл записывается Ф1, Ф3). Из него — файл пар фамилия лодей, стоящих на «расстоянии» 4, потом 8 и т. д. Под конец используется двойное разложение числа 1234567.

M1. a) 111; 6) 259. Основная трудность этой задачи — в точном представлении больших чисел. Оказалось, что если переменная описана как целая, но в процессе вычисления ее значение преосходит допустимые предыденты, то «Роботрон» (и, кстати, большинство других комплюторов) передавают ее в вещественную, теряя при этом знаки, и последовательность искажается. И еще оказалось, что испорченная таким способом последовательность приводит к тому же (верному) ответу: 259, найденномму многоими участниками olимпиды, но не всели «с гарантийей». При решении этой задачи надо было сделать специальную программу работы с большими числами числами и контролировать величины положующихся в процессе вычисления чисел (см. также «Квант», 1988, № 7, с. 59).

M2. Естественная идея — зафиксировать наиболее слабыеаемое в сумме и взять из предыдущих вычислений (для меньших чисел) число представления остальной части суммы. Пусть $P(n, k)$ — число разбиения $n$ на слабыеаемые, не преосходящие $k$ (искомое число — $P(n, n)$). Тогда $P(n, k)=P(n, k-1)+P(n-k, k)$. Строится таблица $P(n, k)$ и из нее находится число представления для построения возрастания $n$. Без специальной арфметики больших чисел удается добрать примерно до $n=37$, с такой арфметкой — до $n=100$.

«Квант» для младших школьников (см. «Квант» № 10)

1. Если обозначить через $x$ стоимость фруктового мороженого, то сливочное будет стоит