Решения задач М340—М342

50

ся атома (это явление называется явлением Доплера). Вследствие этого из-за теплового движения атомов спектральные линии оказываютсяуширенными. Оцените температуру атомов Ne, зная, что вспектре его излучения обнаружена красная линия частоты $f_0 = 4,8 \cdot 10^{14} \text{ e} \mu$, ширина которой $\Delta f = 1,6 \cdot 10^9 \text{ e} \mu$.

С. Козел

Ф394. Устройство рутного медицинского термометра показано на рисунке 3. К баллончику со рутью припаян тонкий капилляр, внизу которого имеется «перегружка» — участок с диаметром примерно 30 микрон. Какую роль играет эта перегружка? Оцените, какое ускорение нужно сообщить термометру для того, чтобы его «стряхнуть» после измерения температуры.

Ф395. Почему измерение температуры медицинским термометром продолжается долго (около 10 минут), а «стряхнуть» термометр можно практическим сразу же после измерения температуры?

Г. Косоуров

Ф396. В направленный водой сосуд погружен вверх домосуд менящего диаметра, неподвижно скрепленный с большим сосудом и частчно заполненный водой (рис. 4). На поверхности воды внутри менящего сосуда плавает кусок льда. Что произойдет с уровнями воды в сосудах, когда лед растает? Как изменится ответ, если меняший сосуд не скреплен с большим и плавает на поверхности воды?

А. Глинский

Ф397. Имеется следующий проект летающего аппарата. Верхняя поверхность большой плоской пластинки поддерживает при постоянной температуре $0 \text{ °C}$, а нижняя — при температуре $100 \text{ °C}$. Избретатель утверждает, что такая пластинка будет высеть в воздухе подобно дирижаблю. Объясните, почему? Оцените по порядку величины подъемную силу такой пластинки с площадью $1 \text{ m}^2$ при температуре воздуха $20 \text{ °C}$.

Решения задач

M340—M342

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

a) Пусть таблица имеет размеры $m \times n$ и $m \geq n$ (строки не длинее стольцов). Выберем в каждом столбце максимальный элемент. Среднее таких элементов минимальный. Возможно, что таким способом мы определим не один элемент, а несколько (равных между собой). Отметим их крестиками. Расстоянием любой из отмещенных крестиком элемент $c_{ij}$, стоящий в $i$-й строке и $j$-м стольце. Если он минимален в своей строке, то клетка $(i, j)$ — искомая. В противном случае

52

> $\frac{\alpha}{\beta}; 2^\circ$ из $\frac{\alpha_1}{\beta_1} < \frac{\alpha}{\beta}, \frac{\alpha_2}{\beta_2} < \frac{\alpha}{\beta}$ следует, что $\frac{\alpha_1 + \alpha_2}{\beta_1 + \beta_2} < \frac{\alpha}{\beta}$ (см. рис. 3). Поэтому

$$\frac{a_{i_1} + b_{j_1}}{p_{i_1} + q_{j_1}} > \frac{a_{i_1} + a_{i_2} + b_{j_1} + b_{j_2}}{p_{i_1} + p_{i_2} + q_{j_1} + q_{j_2}},$$

$$\frac{a_{i_2} + b_{j_2}}{p_{i_2} + q_{j_2}} > \frac{a_{i_1} + a_{i_2} + b_{j_1} + b_{j_2}}{p_{i_1} + p_{i_2} + q_{j_1} + q_{j_2}},$$

и, значит

$$\frac{a_{i_1} + a_{i_2} + b_{j_1} + b_{j_2}}{p_{i_1} + p_{i_2} + q_{j_1} + q_{j_2}} > \frac{a_{i_1} + a_{i_2} + b_{j_1} + b_{j_2}}{p_{i_1} + p_{i_2} + q_{j_1} + q_{j_2}},$$

что невозможно. Получено противоречие. Следовательно, в любой таблице $2 \times 2$ есть седловая клетка, и утверждение задачи 6) следует из пункта a).

Л. Лиманс

Приведем еще одно доказательство пункта 6), независямое от a).

Рассмотрим две функции:

$$f(t) = \max_i (a_i - p_i t),$$

и

$$g(t) = \max_j (q_j t - b_j),$$

определенные для всех $t$. (Такие функции называются кусочной линейными; их графики представляют собой ломаны.) Функция $f$ строго убивает, а функция $g$ — строго возрастает (так как числа $p_i$ и $q_j$ положительные). Поэтому найдется такое число $t_0$, что $f(t_0) = g(t_0)$ — рис. 4.

Покажем, что это число $t_0$ есть элемент нашей таблицы. Действительно, для каких-то индексов $i_0, j_0$ имеем:

$$a_{i_0} - p_{i_0} t_0 = q_{j_0} t_0 - b_{j_0},$$

откуда

$$t_0 = \frac{a_{i_0} + b_{j_0}}{p_{i_0} + q_{j_0}}.$$

Докажем, что этот элемент $t_0$ является седловым для нашей таблицы. Из определения функции $f$ следует, что

$$a_i - p_i t_0 \leq a_{i_0} - p_{i_0} t_0 = q_{j_0} t_0 - b_{j_0},$$

и, значит,

$$t_0 \geq \frac{a_i + b_{j_0}}{p_i + q_{j_0}},$$

т. е. элемент $t_0$ не меньше чисел, стоящих с ним в одном столбце (с номером $j_0$). А из определения функции $g$ следует, что

$$q_j t_0 - b_j \leq q_{j_0} t_0 - b_{j_0} = a_{i_0} - p_{i_0} t_0,$$

откуда

$$t_0 \leq \frac{a_{i_0} + b_{j_0}}{p_{i_0} + q_{j_0}},$$

т. е. элемент $t_0$ не больше чисел, стоящих с ним в одной строке (с номером $i_0$). Доказательство законено.

Н. Васильев

54

Рис. 7. Чемппонат по волейболу $n=8$, $k=3$. Команды 6, 7, 8 — европейские; чемппон Евровы — команда 6. Добавленные команды $A$ и $B$.

Рис. 8. a) Европейские команды — 5 и 6. Чемппон Евровы — команда 5. б) Европейские команды — 4 и 5. Чемппон Евровы — команда 4.

При $l \geq 4$ наиболее целое значение $k$, удовлетворяющее (3), равно $2l-5$, в самом деле, при $k=2l-5$ неравенство справедливо, а при $k \geq 2l-4$ его левая часть положительная (убедитесь в этом).

Если же $l=3$, то из (3) получим $k^2-k-2 \leq 0$, т. е. $k \leq 2$.

Если $l=2$, то $k^2+k-2 \leq 0$ и $k \leq 1$.

Так как $2l-5=n-5$ при четном $n$ и $2l-5=n-4$ при нечетном $n$, то получшиеся результаты мы можем записать так:

1. $k \leq n-4$, если $n \geq 7$ и $n$ нечетно;
2. $k \leq n-5$, если $n \geq 8$ и $n$ нечетно;
3. $k \leq 2$, если $n=6$ и $n=5$;
4. $k \leq 1$, если $n=4$ и $n=3$.

Теперь доказем, что во всех полученных неравенствах возможно достижение равенства.

Начнем со случав 1) и 2).

На рисунках 6 и 7 приведены примеры турирных таблиц для случая $n=7$ и $k=3$; $n=8$ и $k=3$; эти таблицы будут служить началом индукции.

Дальнейшие построения проводим по индикции, последовательно добавляя по две европейские команды.

Заметим, прежде всего, что при $k=2l-5$ непреемно $x=y=l-2$.

В самом деле (см. (2’)), $y \geq \frac{(k-1)(k+2)}{2k}$, т. е.

$y \geq \frac{k}{2} + \frac{1}{2} - \frac{1}{2k}$, или $y \geq l-2 - \frac{1}{2(2l-5)}$,

а так как $l \geq 4$ и $y$-целое число, то $y \geq l-2$, откуда $y=x=l-2$.

Значит, наш чемппон Евровы обязательно проигрывает все неевропейским командам.

Пусть в турирне из $n=2l$ команд первыше 5 команд неевропейские, остальные $n-5$ европейские, и чемппон Евровы занял последнее место.

Добавим еще две европейские команды — $(n+1)$ - ю команду $A$ и $(n+2)$-ю команду $B$.

Будем считать, что команда $A$ выигравает у 1-й, 3-й, …, $(n-1)$-й команд, проигрывает остальным и выигрывает у $B$.

Команда $B$ выигравает у 2-й, 4-й,…, $n$-й и проигрывает остальным.

В итоге каждой из $n$ первых команд получает еще по одному очку, так что их взаимное положение в турирной таблице не меняется.

У чемппон Евровы теперь $l-1$ очков, у команда $A-l+1$ очков; у команда $B-l$ очков, так что «старый» чемппон Евровы остается на последнем месте.

В играх с европейскими командами команда $A$ получает $l-2$ очка ($l-3$ очка в играх со «старыми» командами и одно очко — в игре с командой $B$).

Команда $B$ в играх с европейскими командами наберет $l-2$ очка, так что «старый» чемппон Евровы сохранит свое значение.

При нечетном $n=2l-1$ рассудения волне аналогичны, только нужно считать, что команда $B$ выигравает у $A$ (проведите доказательство самостояльно).

При $n=6$ и $n=5$ легко построить примеры с $k=2$ (рис. 8, а и б). Случан $n=4$ и $n=3$ тривиальны.

A. Егоров

55

М342. а) Докажите, что из цифра 1 и 2 можно составить $2^{n+1}$ чисел, каждое из которых $2^n$-значно и каждое два из которых различаются не менее, чем в $2^{n-1}$ разрядах.

6. Докажите, что больше чем $2^{n+1}$ максимум $2^n$-значных чисел составить нельзя.

Рис. 9.

Будем решать эту задачу методом математической индукции. База и индекции. При $n = 1$ каждые два из четырех двухзначных чисел 11, 12, 21, 22 различются, по крайней мере, в одном разряде.

Шаг идукции Допустим, что из единиц и двоечек составлены $2^{n+1}$ чисел, каждое из которых $2^n$-значно и каждое два из которых различается не менее чем в $2^{n-1} \times$ разрядах. Составим из этих чисел таблицу $A$ размерми $2^{n+1} \times 2^n$ (по строкам таблицы — сами числа, по столбцам — разряды чисел). Припишем каждому числу $a$ таблицы $A$ справа то же самое число $a$; получившиеся $2^{n+1}$ чисел, каждое из которых уже $2^{n+1}$-значно, образуют таблицу $AA$. Затем к каждому числу $a$ таблицы $A$ припишем справа противоположное число $a$ (единиц заменим двойками, а двойки — единицами).

Рассмотрим таблицу размерми $2^{n+2} \times 2^{n+1}$ (см. рис. 9), по строкам которой вписаны $2^{n+2}$ чисел, каждое из которых $2^{n+1}$-значно. Докажем, что каждые два из этих чисел различается по крайней мере в $2^n$ разрядах.

В самом деле, по предположению индукции, любые два числа, взятых из верхней «половины» нашей таблицы (части $AA$), различаются не менее чем в $2 \cdot 2^{n-1} = 2^n$ разрядах. Тоно так же различаются и любые два числа, взятые из «низней» половины таблицы (из части $A\bar{A}$, так как числа из таблицы $\bar{A}$ различаютсяровно в тех же разрядах, что и соответствующие им числа из таблицы $A$). Если же мы возьмем два числа из разных «половин» таблицы — $aa$ из верхней и $b\bar{b}$ — из нижней, то они будут различатьсяровно в $2^n$ разрядах: если числа $a$ и $b$ отличаются в $k$ разрядах, то числа $a$ и $b$ отличаются в остальных $2^n - k$ разрядах.

6. Предположим противное: пусть удалось составить $2^{n+1} + 1$ число так, как требуется в задаче. Тогда среди них найдется $2^n + 1$ чисел с одной и той же первой цифрой. Расмотрим эти числа.

В каждом из оставшихся $2^n - 1$ разрядов совпадает по крайней мере $2^{n-2}$ пар этих чисел. Действительно, если в каком-то разряде (по всем этим числам) $2^{n-1} - k$ единиц ($k \ge 0$) и $2^{n-1} + k + 1$ двоеок (всего чисел $2^n + 1$), то число совпадений равно

$$C_{2n-1}^{2} + C_{2n-1}^{2} + k + 1 = 2^{2n-2} + k^2 + k \ge 2^{2n-2}.$$

Таким образом, количество $N$ совпадений во всех разрядах не меньше

$$C_{2n+1}^{2} + (2^n - 1)2^{2n-2} = 2^{3n-2} + 2^{n-2} + 2^{n-1}.$$

С другой стороны, если каждое из рассматриваемых $2^n + 1$ чисел отличяется не менее чем в $2^{n-1}$ разрядах, то совпадений не больше

$$C_{2n+1}^{2} \cdot 2^{n-1} = 2^{3n-2} + 2^{2n-2}.$$

Поскольку (1) больше (2), мы пришли к противению, что и требовалось.

Для тех, кто знаком с понятным многомерного включения пространства, приведем план другого доказательства. Заменим в условии «двойки» на «минус единиц». Телер утверждение задачи следует из общего факта, который легко доказать индукцией по $k$: среди $(2k + 1)$ $k$-мерных векторов найдется два с неотрицательным скалярным произведением.

И. Клумова,
С. Фомин