Призёры II Всесоюзной олимпиады школьников по информатике

76

Дифференциальная геометрия
вокруг нас

1. $L_\varepsilon = L$.
2. $S_\varepsilon = S + \varepsilon L + \pi \varepsilon^2$.
3. $V_\varepsilon = V + \varepsilon S + \varepsilon^2 I + \frac{4}{3} \pi \varepsilon^3$, где $I$ — интеграл средней кривизны по исходной поверхности.
4. Обозначим угол сектора через $\alpha$, его радиус — образушую конуса — через $l$. Тогда длина параллелы равна $al$. С другой стороны, радиус сечения сферы равен $l$ sin $\varphi$, а длина параллелы равна $2\pi l$ sin $\varphi$. Значит, $\alpha = 2\pi$ sin $\varphi$.
5. Геодезическая кривизна параллели построена. Длина параллелы равна $2\pi R$ cos $\varphi$, а $\varepsilon = R\varphi$. Поэтому $\lim_{|\varepsilon| \to 0} |L_\varepsilon - L|/\varepsilon L = 2\pi R|\cos \varphi|'/2\pi R\cos \varphi = \sin \varphi/\cos \varphi = tg\varphi$.

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

1. Решение этой задачи будет опубликовано позже в «Заданиеке «Кванта» (это задача M1188).

2. Ответ: нельзя. Указание. Если бруски можно было бы уложить в коробку, то каждый слой $11\times 7\times 1$ оказался бы заполненным, но это не возможно, так как число $11\times 7$ не делится на 3.

3. Указание. Пусть $l$ — общая касательная к окружности, вписанным в треугольники BMT и ATC (рис. 1). Доказите, что в четырехугольник AMNP можно вписать окружность, т. е. что $AM+NP=MN+AP$. Для этого достаточно доказать равенство $MN+AP-NP = AB+AC-BC-AM$ и заметить, что $2AM = AB+AC-BC$.

4. Ответ: $N=1989$. Указание. Пусть $d_1, d_2, \dots, d_{12}$ — все делители числа $N$, записанные в порядке возрастания. Тогда $d_1d_13-i=N$ при всех натуральных $i \leq 12$. Пусть $d_4-1=k$. Число $d_1+d_2+d_4$ — делитель $d_k$, и потому $d_1+d_2+d_4$ — делитель $N$, причем $d_1+d_2+d_4 \geq d_5$. Но тогда $d_k-(d_1+d_2+d_4)d_8 \geq d_5d_8=N$, откуда следует, что $d_k=N$, т. е. $k=12$, $d_4=13$ и $d_5=d_1+d_2+d_4=d_2+14$. Поскольку $d_2$ — простое число, причем $d_2 \leq d_4-2=11$, осталось перебрать случай $d_2=2, 3, 7, 11$ и убедиться в том, что $d_2=3$, $d_4=13$, $d_5=17$, причем больше трех простых делителей $N$ имеет не может. Поэтому $d_3=9$ и $N=9\cdot 13\cdot 17=1989$.

5. Решение этой задачи будет опубликовано позже в «Заданиеке «Кванта» (это задача M1186).

6. Проведем прямую $C_1M \parallel AC$ (рис. 2). Из условия и по теореме Фалеса $\frac{CM}{MB} = \frac{AC_1}{C_1B} = \frac{CB_1}{B_1A}$, откуда следует, что $B_1M \parallel AB$ и, таким образом, $AC_1MB_1$ — параллелограмм. Далее, точки $A_1, B_1, C_1$ и $M$ лежат на одной окружности. Если $M$ лежит на отрезке $A_1C$ (рис. 2, а), то $\angle C_1B_1A_1 = \angle C_1MA_1 = \angle ACB$. Если $M$ лежит на отрезке $A_1B$ (рис. 2, б), то $\angle C_1B_1A_1 = 180^\circ - \angle C_1MA_1 = \angle ACB$. В обихах случае треугольники $ABC$ и $A_1C_1B_1$ имеют соответствующее улыбье улы и потому подобны.

7. Решение этой задачи будет опубликовано позже в «Заданиеке «Кванта» (это задача M1187).

8. Указание. Изовем две группы $k$-значных чисел других чисел, если в них содержится порону чисел, причем и суммы, и суммы квадратов входящих в эти группы чисел равны. Достаточно доказать, что все пятизначные числа, составленные из цифр 1, 2, 3, 4, 5, можно разбить на две других группы. Все трехизначные числа, составленные из трех различиных цифр, не равны 0. Тогда группы $(k+1)$-значных чисел $(A^*, \dots, A^*)$ и $(B^*, \dots, B^*)$ (где $A_i^* = A_i + d \cdot 10^k$, $B_i^* = B_i + d \cdot 10^k$, $i = 1, \dots, N$) — также других.

9 класс

1. Разобем монеты на 4 группы по 500 штук и обозначим через $A_1, A_2, A_3, A_4$ суммарные веса монеты в этих группах. Сравним $A_1$ с $A_2$ и $A_3$ с $A_4$. Достаточно рассмотреть три случая:

1. $A_1 = A_2, A_3 = A_4$. Тогда обе фальшивые монеты лежат в одной группе, и их суммарный вес равен весу двух настоящих монет. В этом случае достаточно двух взвешивания.
2. $A_1 = A_2, A_3 > A_4$. Тогда обе фальшивые монеты находится третий и четвертый группе. Образует две новые группы по 1000 монет, объединив первый группу с второй, а третью — с четвертой. Сравним суммарные веса монеты во новь образованных группах, получим ответ на вопрос задачи. При этом понадобится три взвешивания.
3. $A_1 > A_2, A_3 > A_4$. В этом случае могут представиться две взвешности: либо тяжелая монета находится в первой группе, а легкая —

77

Рис. 3.

в четвертой, либо тяжелая монета находится в третий группе, а легкая — во второй. Сравнив $A_1$ с $A_4$, узнаем, какая из этих возможностей реализуется на самом деле. После этого, сравнив $A_1 + A_4$ с $A_2 + A_3$, получим ответ на вопрос задачи. В этом случае нужно выполнить четые взвешивания.

2. Пусть $S$ — площадь треугольника со стороны $a, b, c$. По формуле Герона

$$S = \sqrt{\frac{1}{2}\left(\frac{1}{2}-a\right)\left(\frac{1}{2}-b\right)\left(\frac{1}{2}-c\right)},$$

откуда

$$16S^2 = -1 + 4(ab + bc + ca) - 8abc.$$

Кроме того, $4(ab + bc + ca) = 2 - 2(a^2 + b^2 + c^2)$, и потому

$$16S^2 = 1 - 2(a^2 + b^2 + c^2) - 8abc > 0.$$

3. а) Утверждение этого пункта — частный случай утверждения пункта 6) при $m=n=1$. 6) Обозначим площадь четырехугольника $ABCD$ через $S$, площади треугольников $ABC, BCD, CDA, DAB$ — через $b, c, d$ и $a$ соответственно (рис. 3); площади треугольников $AMB, DKC$ — через $S_1$ и $S_2$. Пусть также $S_3 = S_{AKMD}$, $S_4 = S_{KBCM}$ и $a = \frac{m}{m+n}$. Тогда $S_1 = aa + (1-a)b$, $S_2 = ac + (1-a)d$, $S_3 = aS_1 + (1-a)d$, $S_4 = aS_2 + (1-a)b$.

Вычисляя $S_{KLM} = a(1-a)\frac{S_1S_2}{S_3}$ и $S_{KMN} = a(1-a)\frac{S_1S_2}{S_3}$, получим $S_{KLMN} = a(1-a)\frac{S_1S_2}{S_3} S$.

Нераевенство $S_{KLMN} < \frac{a(1-a)}{1-a+a^2} S$ равносильно неравенству $(1-a+a^2)S_1S_2 < S_3S_4$. Подставляя вместе $S_1, S_2, S_3, S_4$ их выражения через $a, b, c, d$, приходим к неравенству $a(ab+cd-ac)+(1-a)(b^2+d^2+bd-ad-bc) > 0$, так что достаточно доказать, что $ab+cd-ac > 0$ и $b^2+d^2+bd>ad+bc$, для чего заменим, что $ab+cd>S \min(a, c)$; $ad+bc \leq S \max(b, d) = \max(b, d)(b+d) < b^2+d^2+bd$.

4. Ответ: мог бы использовать один квадратик $1 \times 1$.

Раскрасием квадрат $23 \times 23$, как показано на рисунке 4. Тогда будет заключено нечетное число квадратников $1 \times 1$, но каждый квадрат $2 \times 2$ и $3 \times 3$ содержит нечетное число закрашенных квадратников $1 \times 1$. На рисунке 5 показано, как можно составить квадрат $23 \times 23$, используеврово один квадратик $1 \times 1$.

5. а) Ответ: существует, например, $a=2+ \sqrt{2}$, $b=-\sqrt{2}$.

6. Ответ: не существует. Предположим про-

78

8. Указание. На рисунке 8 показаны фигуры, которые можно разрезать на прямоугольники 2×1 соответственно одним, двумя, треями и четырьмя способами. На рисунках 9, а и 9, б изображены фигуры $M_n(n \ge 5)$, которые можно разрезать на прямоугольники 2×1 равно $n$ способами. Действительно, если от фигуры $M_n$ отрезать две клеточки, обозначенные буквами $A$ и $C$, то оставшаяся фигура, как легко видеть, может быть разрезана на прямоугольники 2×1 единственным способом. Если же от фигуры $M_n$ отрезать две клеточки, обозначенные буквами $A$ и $B$, то получится фигура $M_{n-1}$.

10 класс

1. Ответ: при $n=7$.
2. Как видно из рисунка 10, $\angle DEF=180^\circ - (180^\circ - 2\angle B) - (180^\circ - 2\angle C)=180^\circ - 2\angle A$, т. е. угол $A$ — острый. Следовательно, центр $O$ описанной около треугольника $ADF$ окружности и вершина $A$ лежат по одному сторону от $FD$, и поэтому $\angle DOF=2\angle A=180^\circ - \angle DEF$. Отсюда следует, что точки $O, D, E$ и $F$ лежат на одной окружности; значит, $\angle DEO=\angle DFO=\angle FDO=\angle FEO$, т. е. $EO$ — биссертиса угла DEF.
3. Решение этой задачи будет опубликовано позже в «Задачике «Кванта» (это задача M1180).
4. Ответ: могут. Указание. Без ограничения общности можно считать, что все ломаная (путь через перевал) лежит в одной вертикальной плоскости, а каждое ее звено (склон) составляет с горизонтального угол $45^\circ$. Определим следующее правило движения: оба туриста идут с постоянной скоростью все время, пока это возможно (при условии их нахождения на одинаковой высоте); если же кто-то из туристов не может идти в пределах направления (по горизонтали), то он поворачивает в противоположную сторону. Докажите, что движясь по этим правилам, оба туриста доберутся до противоположных концов ломаной.
5. Решение этой задачи было опубликовано в «Кванте» (это задача M1158).
6. Указание. Расставим стрелки на ребрах данного многогранника произвольно. Тогда количество вершин, в которых входит нечетное число стрелок (назовем такие вершины нечетными), будет четным. Выберем пару «нечетных» вершин $A_i$ и $A_j$ (если такие найдутся) и проijdем по ребрам многогранника из $A_i$ в $A_j$, меняя на проijdемых ребрах направления стрелок. В результате $A_i$ и $A_j$ перестанут быть «нечетными», тогда как множество остальных «нечетных» вершин не изменится. Повторив указанную операцию необходимое число раз, мы добавемся того, что «нечетных» вершин не останется вовсе.
7. Ответ: не существует. Указание. Если бы такая функция существовала, то среди ее значений при $n>1$ нашлось бы наименьшее значение $f(n_0)>1$, для которого (из условия) имеем бы
   $$f(n_0)>1+f(n_0).$$
8. Указание. Изовем медианой лобой из описанных в условия отрезков. Направление границы многоугольника по часовой стрелке будем называть правым, а против часов стрелки — левым.
   Проведем все медианы многоугольника и затем, что любые две медианы пересекаются внутри него. Будем движения по границе многоугольника влево от конца $A$ медианы $AD$. Если конец $B$ медианы $BC$ оказывается близким с лочеке $A$ (рис. 11), то и конец $C$ оказывается близким с лочеке $D$ (доказатель). Таким образом, соседние медианы $BC$ и $AD$ образуют «бабочки» — фигуру, составленную из треугольников $AOB$ и $COD$. Площади треугольников $AOB$ и $COD$ равны. Площадь «бабочки» равна
   $$\sigma=\frac{1}{2}xy\sin \alpha+\frac{1}{2}(a-x)(b-y)\sin \alpha=\frac{ab\sin \alpha}{4}+\left(\frac{a}{2}-x\right)\left(\frac{b}{2}-y\right)\sin \alpha,$$
   где $AD=a, BC=b, x=OA, y=OB, \angle BOA=\alpha$, причем $\sigma<\frac{a}{4}$, поскольку $a\leq 1, b\leq 1$, а $\left(\frac{a}{2}-x\right)\left(\frac{b}{2}-y\right)\leq 0$.
   Двигаясь дальше по границе многоугольника влево от точки $B$ до точки $D$, мы получим поочередно все «бабочки», образованные соседними медианами. Сумма площадей этих «бабочки», согласно доказанному, будет меньше четырёх суммы соответствующих им углов, т. е. меньше $\pi/4$.
   Осталось доказать, что «бабочки» полностью покрывают многоугольник.

79

II Всесоизная олимпида
школьников по информации

T1. Сложив все премии (для $i$ от 1 до $N$), мы найдем, что члены $2i+3j$ в сумме даут $5N(N+1)/2$, а остальная часть — запись в системе счисления с основанием $N+1$ номеров сотрудников в списке коллектива в порядке, обратном списку начальника. За алгоритм, использующий эту идею (например, деление на $N+1$ и выделение дробной части и т. д.; см. «Квант» № 5 за 1989 г., с. 66, 70), давалось 10 баллов, за переборный ($N!$ перестановок) — от 3 до 7 баллов.

T2. За формулировку правил давалось 4 балла, за алгоритм — еще 6.

T3. Надо спроектировать вертикальные стороны прямогоугольников на ось $x$ (это дакт $2n$ точек: $x_1, x_2, ..., x_{2n}$), а горизонтальные — на ось $y$ (тоже $2n$ точек: $y_1, y_2, ..., y_{2n}$), и для каждой «узла» $(x_i; y_j)$ определять, скольким прямогоугольником он принадлежит ($n$ провекок); это и дает порядка $n^3$ действий. Перебор разных наборов прямогоугольников дает $2^n$ действий. За решение с проведением «части сетки» (были и такие) давался 1 балл, с перебором — 2 балла, с рассмотрением узлов — 10 баллов. Два школьника уложились в $n^2$ действий, использую такую идею: спроектировать стороны на ось $x$, они их занумеровали подряд, заведя при этом массивы указаний, какой прямогоугольник начинается или кончает (при совпадении проекций сначала бралисьлевые стороны), а тогда каждый просмотр по горизонтали (для точек $y_j$; $2n$ просмотров) требует лишь порядка $2n$ действий. За такое решение жорни давало 15 баллов.

M1. Пусть $P_{2n}$ — число искомых «счастливых» $2n$-значных чисел; $S_i(k)$ — число $i$-значных чисел с суммой цифр $k$. Тогда

$$P_{2n} = \sum_{k=0}^{9n} (S_n(k))^2,$$
$$S_{n+1}(k) = \sum_{j=0}^{min(k,9)} S_n(k-j).$$

Первая формула отражает разбиение $2n$-значных чисел на группы с требуемыми суммами цифр, равными 0, 1, …, $9n$; вторая — разбиение $n+1$-значных чисел с суммой цифр $k$ на группы чисел с первой цифрой 0, 1, …, $9$ (или $k$, если $k<9$). Вторая формула позволяет построить таблицу $S_n(k)$. Эти числа быстро растут и на Бейсике при $n>7$, а на Паскале при $n>6$ выходит за пределы диапазона целых чисел, допускаемых компьютером, поэтому надо использовать специальные программы для работы с большими числами.

Калейдоскоп «Кванта»
(cm. «Квант» № 10)

Вопросы и задачи

1. Необходимо, чтобы процессы протекали без теплопотенения с окружающей средой и без совершения вперед-назад) быстро давали бы ответ (если требуемое положение достижимо), но как раз здесь ничего изучтиков олимпиды составить переборную программу не отважился.

2. Нет, так как удаленные теплопотености воды и алюминия различны.

3. Теплоемкость пилы меньше, чем дерева.

4. Изменения температур кофе и молока обратно пропорциональны их массам. Поэтому при добавлении, скажем, 10 г молока при $5^{\circ}\text{C}$ в чашку кофе — 200 г при $95^{\circ}\text{C}$ — температура кофе понизится меньше чем на $5^{\circ}\text{C}$.

5. У воздуха меньше, чем у воды, удельная температура, поэтому воздуха грела быстро охлаждается.

6. Изменения температуры меди и железа обратно пропорциональны их удельным теплопотеном.

80

емкость. Поэтому сильнее нагреется медное тело.

7. Нет, поскольку помещо одинакового изменения внутренней энергии потребуется совершить различную работу при подъеме центра тяжесте первого ($A_1 > 0$) и опускании второго ($A_2 < 0$) шара.

8. Нет; надо учитывать совершенную газом работу.

9. Да, если тело будет совершать работу (или переходить в иное агрегатное состояние).

10. Процессы 1—2 и 4—1 протекают с поглощением теплоты, 2—3 и 3—4 с теплотадчей.

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

12. Из-за превращения части внутренней энергии в механическую работу, совершаемую при расширении газа, его температура будет понжаться.

13. Тепляй воздух, поднимая по склонам гор, попадает в область более низкого атмосферного давления, расширяется и охлаждается.

Микроопыт
Сжатый в бутылке газ быстро расширяется, совершая работу против сил атмосферного давления, его температура падает, и часть содержащого в газе водяного пара конденсируется в виде тумана. Подбная картина наблюдается при выпуске скатого газа из баллона, когда вентиль покрывается россий или даже инеем.

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

1. 6 дней.
2. Если Людмилle 10x+y лет, то ее пределу 100x+y лет, и 60x+6y=100x+y. Отсюда 8x=y. Людмилle 18 лет.

Рис. 13.

3. Раз число делится на 5, то оно окачивается на 0 или на 5, но 0 быть не может. Заметим, что число делко при этом делится на 25, при этом вторая цифра — либо 2, либо 7. Но 2 быть не может, так как в этом случае число делко было бы окачивается на 0. Осталось найти первую цифру. Обозначим ее через x; тогда 100x+70+5=5·x·7·5. Отсюда x=1. Искомое число равно 175.
4. 540498+60898+142058=743454.
5. Шеступольник разрежет на три параллерогамма (см. рис. 13). В каждом из них половину площади занимает красный треугольник и половину — синей.

Главный редактор — академик Ю. А. Осипьян

Заместители главного редактора:
В. Н. Боровишки, А. А. Варламов,
В. А. Лешковцев, Ю. П. Соловьев

Редакционная коллекция:
А. А. Абриковов, М. И. Башмаков,
В. Е. Белонучкин, В. Г. Болтянский,
А. А. Боровой, Ю. М. Брук, В. В. Вавилов,
Н. В. Васильев, С. М. Воронин, В. В. Гнеденko,
Н. И. Долбилин, В. Н. Дубровский,
А. Н. Земляков, А. Р. Зильберман, С. М. Козел, С. С. Кротов, Л. Д. Кудрявцев, А. А. Леонович, С. П. Новиков, Т. С. Петрова, М. К. Потапов, В. Г. Разумовский, Н. А. Родина, Н. Х. Розов, А. П. Савин, Я. А. Смородинский, А. В. Сосинский, В. М. Уроев, В. А. Фабрикант

Редакционный совет:
А. М. Балдин, С. Т. Беляев, Е. П. Велихов, И. Я. Верченko, В. В. Воздвиженский, Г. В. Дорофеев, Н. А. Erpmолаева, Ю. В. Иванов, В. А. Кириллин, Г. Л. Коткин, Р. Н. Кузьмин, А. А. Логунов, В. В. Можаев, В. А. Орлов, Н. А. Патрикеева, Р. З. Сагдеев, А. Л. Стасенko, И. К. Сурин, Е. Л. Сурков, Л. Д. Фаддеев, В. В. Фирсов, Г. Н. Яковлев

Номер подготовки:
А. И. Вуздин, А. Н. Виленкин,
А. А. Егоров, Л. В. Кардасвенич,
И. Н. Климова, Т. С. Петрова,
С. Л. Табачников, В. А. Тихомирова

Номер оформления:
М. В. Дубах, С. Ф. Лухин, Э. В. Назаров,
И. Е. Смирнова, Л. А. Тишков, П. И. Чернуский, В. В. Юдин

Редактор отдела худоместственного оформления
С. В. Иванов
Худоместственный редактор Т. М. Макарова
Заведующая редакцией Л. В. Чернова

Корректор Н. Д. Дорохова

103006, Москва К-6, ул. Горького, 32/1, «Квант», тел. 250-33-54

Сдано в набор 24.08.89. Подписано к печати 17.10.89. Т-16644. Формат 70×100/16. Бумага офс. № 1
Гарнитура школьная. Печать оформная.
Усл. печ. л. 6,45. Усл. кр.-отт. 27,09. Уч.-изд. л. 7,87.
Тираж 127 829 экз. Заказ 1938. Цена 45 коп.

Ордена Трудового Красного Заменини
Чеховский полигraphический комбинат
Государственное комитета СССР по печати
142300, г. Чехов Московской области