Решение задач олимпиады

Квант 1977, №11 с. 63-64 Тег YRV0

теоремы. В этом большею помощь может оказать вам «Квант».

Торжественное закрытие олимпиды состоялось 19 апреля. Заместитель представления жорри М. И. Башмаков зачитал решение жорри XI Всесоюзной математической олимпиды. Итак, по итогам двух дней состояний было решено присуditь 13 первых, 24 вторых, 24 третьих премии и отметить пожавляемыми отзывами I степени 32 участника олимпиды и пожавляемыми отзывами II степени — 36 участников. Имена победителей XI Всесоюзной олимпиды мы публикуем на с. 72.

Кроме того, различные организации и предприятия Эстонии учредили специальные призы (за лучший результат, за самое оригинальное решение, лучший по ресурсике, представитель самого отделенного уголка Советского Союза и т. д.), которые были направлены многое школьники. Специальный приз жоррала «Квант» — подшивку жоррала за 1976 год с авторфом главного редактора академика И. К. Кикона — получил школьник 8-го класса из г. Таллина Марк Левин (он участвовал в соревнованиях вне конкурса, и поэтому ему не было присужденоникакого официального места). Подпиской на жоррала «Квант» на 1978 год были направлены также восьми классики: Ляховец Андрей (Краснодар), Хлебутин Сергей (Пермь), Бернотас Андрюс (Вильнюс), Власов Вячеслав (Киев), Ирматов Андар (Наманган УзССР).

По итогам олимпиды была составлена команда для участия в XIX Международной олимпиде школьников по математике. В состав команды вошли: А. Амброладзе (Тбилиси), А. Аузинш (Рига), Я. Виннишин (Киев), В. Гальперин (Москва), А. Кодрян (Рыбница), Г. Рыбников (Москва), Д. Флаасс (Новосибирск) и А. Чурбанов (Москва). XIX Международная олимпида проходила в Белграде (Югославия). Мы рассекем об этой олимпиде в одном из следующего номеров жоррала.

Л. Лиманов

Решение
задач
олимпиды

В этой статье разбираются три задачи заключительного типа XI Всесоюзной математической олимпиды, которые не вошли в «Задачник« Жванта». Решения задач, опубликованных в «Задачнике« Жванта», появятся в соответствии with номера жоррала в следующем году. (Условия задач см. на с. 58—61.)

8 класс. Задачка 4.

Вместо того чтобы убрать фишки, будем ставить их, начав с одной черной фишки. Добавим к ней белые фишки так, чтобы у каждой из них был черный сосед (одну или две). Затем поставим несколько черных фишек так, чтобы у каждой из них был белый сосед и чтобы у «старой» черной фишки белых сосед не было. Следующим ходом снова ставятся белые фишки с соблюдением этих двух условий и т. д.

Обозначим через $b_i$ число черных фишек, выставленных после $i$ ходов, а через $w_i$ число белых. Если на $i+1$ -м ходу приставляются черные фишки ( $i$ четно), то $b_{i+1} = b_i + 2w_i$ , $w_{i+1} = w_i$ . Если же — белые фишки ( $i$ четно), то $b_{i+1} = b_i$ , $w_{i+1} = w_i + 2b_i$ ; мы каждойх ходом все фишки какого-нибудь одного цвета okружаем двумя фишками другого цвета. Ясно, что большего числа приставить невозможно.

Условия записываются положение фишек на okружности после $i$ -го хода в виде вектора $\langle b_i; w_i \rangle$ и вычислить несколько векторов:

$\langle 1;0 \rangle \rightarrow \langle 1;2 \rangle \rightarrow \langle 5;2 \rangle \rightarrow \langle 5;12 \rangle \rightarrow \langle 29;12 \rangle \rightarrow \langle 29;70 \rangle \rightarrow \langle 169;70 \rangle \rightarrow \langle 169;408 \rangle \rightarrow \langle 985;408 \rangle.$

Убедимся теперь, что в задаче a) ответ положительный, а в задаче b) наименование числа ходов — восемь.

Действительно, послечетвертохода будет выставлено $29+12=41$ фишек. При перехождение от $\langle 5;12 \rangle$ к $\langle 29;12 \rangle$ добавляются 24 фишки. Из них не больше $2 \times 5=10$ ответа за выполнение второго условия — отдельют старые черные фишки от белых. Изозвем эти фишки обязательными. Пометим их

Докажем индукцией по $i$ такое неравенство:

$\frac{1}{2^i} a_n - 2\varepsilon < a_{n+i} < \frac{1}{2^i} a_n + 2\varepsilon,$

где $n$ — любое число, большее $m$ . Действительно,

$\frac{1}{2^{i+1}} a_n - 2\varepsilon = \frac{1}{2} \left( \frac{1}{2^i} a_n - 2\varepsilon \right) -$

$-\varepsilon < \frac{1}{2} a_{n+i} - \varepsilon < a_{n+i+1} <$

$< \frac{1}{2} a_{n+i} + \varepsilon < \frac{1}{2} \left( \frac{1}{2^i} a_n + 2\varepsilon \right) + \varepsilon =$

$= \frac{1}{2^{i+1}} a_n + 2\varepsilon.$

Но для любого $\varepsilon > 0$ можно указать такое $i$ , что $\left| \frac{a_n}{2^i} \right| < \varepsilon$ . Из этого следует, что для произвольного $\varepsilon > 0$ можно указать такое $k$ , что для всех $l > k$ выполняется неравенство $-3\varepsilon < a_l < 3\varepsilon$ . По определению предела это и означает, что $\lim_{n \to \infty} a_n = 0$ .

9 класс. Задча 5.

Будем считать, что на границе квадрата свободных узлов нет. Докажем, что любая система ломаных, удовлетворяющих условиям задачи и этому условию, проходит через четверное число узлов.

Занутерум узлы на границе квадрата так, как это показано на рисунке 2. Легко сообщить, что ломаная, соединяющая точки с номерами $i$ и $j$ , проходит через $1+i-j+2l$ узлов, где значение $l$ зависит от ломаной. Подсчитаем теперь увоенное число узлов, через которого проходят наши ломаные. Поскольку из каждой точки квадрата, кроме вершин, выходит ломаная, это число равно $4.99 + \sum i - \sum j + 2\sum l (i,j)$ , где $l(i,j)$ — значение $l$ для ломаной с началом в точке $i$ и концом в точке $j$ . Легко заметить, что $\sum l(i,j)$ четна, поскольку каждое слагаемое встречается в ней дважды: $l(i,j) = l(j,i)$ . Следовательно, наша система ломаных проходит через число узлов, а всего узлов, не лежащих на границе нашего листа, $99^2$ — нечетное число. Таким образом, действительное непройдетным хотя бы один узел.