Решения задач М504, М506, М507; Ф513, Ф516, Ф517

34

Решения задач
M504, M506, M507; Ф513, Ф516, Ф517

М504. На шахматную доску $n \times n$ клеток уложено $k$ плимок размером $2 \times 1$, причем мак, что положить $(k+1)$-ю плимку, не перемещая уже имеющих плимок, нельзя. Доказите, что свободных клеток осталось не более чем $a) (n^2+n+1)/3$;
$b) (n^2+2)/3$;
$c) n^2/3$.

Можно ли получить для некоторых $n$ еще более мощную оценку?

Рис. 1.

Рис. 2.

Эта клетка обязаетно свободная

Рис. 3.

Рис. 4.

Пусть свободных клеток $x$.

a) Сопоставим каждой свободной клетке, не лежащей на верхней горизонтали доски, плитку, «накрывающий» ее сверху (рис. 1). Ясно, что каждая плитка сопоставлена не более чем одной клетке (так что количество свободных клеток, не лежащих на верхней горизонтали доски, не больше одного количества $\frac{n^2-x}{2}$ плиток, уложенных так, как сказано в задаче). Пусть на верхней горизонтали доски $x_1$ свободных клеток; тогда $x_1 \leq \frac{n+1}{2}$. Имеем $x-x_1 \leq \frac{n^2-x}{2}$, то есть

$$3x \leq n^2+2x_1 \leq n^2+n+1,$$

откуда

$$x \leq (n^2+n+1)/3.$$

6. Обозначим через $x_1$ количество свободных клеток внутри доски, через $x_2$— количество свободных клеток на границе доски, не считая угловых клеток; наконец, через $x_3$ обозначим количество свободных угловых клеток доски. Тогда $x=x_1+x_2+x_3$. Через $y_1$ обозначим количество расположенных строгого внутри доски л и то к; через $y_2$— количество плиток, выходящих на края доски хотя одной клеткой; тогда $y_1+y_2 = \frac{n^2-x}{2}$.

Подсчитаем, сколько имеет пр. с свободная клетка — граница с ней плимка. С одной стороны, их $4x_1+3x_2+2x_3$. С другой стороны, поскольку плитки уложены так, что добавить ни одной уже нельзя, этих пар не более чем $4y_1+3y_2$ (каждая плитка, выходящая на края доски, граничит не более чем с третья клетками, а каждая плитка строгого внутри доски — не более чем с четырьмя). Позному

$$4x_1+3x_2+2x_3 \leq 4y_1+3y_2.$$

Поскольку две свободные клетки на границе доски разделяются плиткой, имеем

$$x_2+x_3 \leq y_2.$$

Складывая неравенства (1) и (2), получаем

$$4x_1+4x_2+3x_3 \leq 4(y_1+y_2),$$

или

$$x-\frac{1}{4}x_3 \leq \frac{n^2-x}{2}.$$

Но $x_3 \leq 4$; значит, $x \leq \frac{n^2-x}{2} + 1$ или $3x \leq n^2+2$, откуда $x \leq (n^2+2)/3$.

в) Заметим, что если неравенство (1) — строгое, то мы получим то, что надо в пункте в): строгое неравенство $x < \frac{n^2-x}{2} + 1$ равносильно таким путем:

$$x \leq \frac{n^2-x}{2}, \text{откуда } x \leq \frac{n^2}{3}.$$

Позному, если допустить, что $x > \frac{n^2}{3}$, то во всяком случае нужно, чтобы к каждой плитке обязаτεльно прилегало максимальное число свободных клеток. В частности, к любой стороне плитки длины 1, не управающейся в край доски, должна прилегать

35

Свободная клетка. Поэтому плитки должны располагаться «рядами» (рис. 2), причем «ряды» не могут ни упраться друг в другу, ни пересекаться друг с другом, поскольку и в том и другом случае возникнет картина, изобразенная на рисунке 3,— до тех пор, пока не достигнет края. Значит, все «ряды» должны быть параллельны, что возможно лишь тогда, когда $n$ делится на 3. В этом случае число плиток равно $n^2/3$ (соответствующий пример изображен на рисунке 4). Итак, для досок $n \times n$, где $n=3k$, оценка $\frac{n^2}{3}$ — точная.

C. Фомин

Не ограничивающая общности, можно считать, что $0 < a \leq b \leq c \leq d$. Сложив три очередных неравенства
$$a(a-b)(a-c)(a+2d) \geq 0,$$
$$a(a-b)(a+2c)(a-d) \geq 0,$$
$$a(a+2b)(a-c)(a-d) \geq 0,$$
получим
$$3a^4 - 3a^2(bc + bd + cd) + 6abcd \geq 0,$$
или
$$a^4 - a^2(bc + bd + cd) + 2abcd \geq 0.$$

С другой стороны, неравенство
$$b^4 + c^4 + d^4 - a^2(b^2 + c^2 + d^2 - bc - bd - cd) - b^2c^2 - b^2d^2 - c^2d^2 \geq 0$$
эквивалентно очередному
$$[(b+c)^2 - a^2](b-c)^2 + [(b+d)^2 - a^2](b-d)^2 + [(c+d)^2 - a^2](c-d)^2 \geq 0.$$

Сложив неравенства (1) и (2), получим утверждение задачи.
Приведем решение этой задачи, используем математический анализ. Нам понадобится следующая геометрическая оценная
Лемма. Если функция $f$ имеет неотрицательную произвольную в каждой точке луца $[x_0; +\infty[$, то она— неубывающая на этом луце.
Заметим, что если какое-то два из чисел $a, b, c, d$ совпадают, то доказывающее неравенство справедливо. В самом деле, пусть направим, $a = d$. тогда наше неравенство можно переписать так:
$$a^4 + 2(bc - b^2 - c^2)a^2 + b^4 + c^4 - b^2c^2 \geq 0.$$

Левая часть неравенства (3) — квадратный трехчлен относительно $a^2$ с неположительным дискрипиментом $-2bc(b-c)^2$, поэтому (3) справедливо.

Перепишем теперь требуемое неравенство в таком виде:
$$d^4 - (a^2 + b^2 + c^2)d^2 + 2abcd + a^4 + b^4 + c^4 - a^2b^2 - a^2c^2 - b^2c^2 \geq 0$$

и рассмотрим левую часть (4) как функцию от $d$; обозначим эту функцию через $f$. Нам нужно доказать, что $f(d) \geq 0$ при $d \geq c$ (и $0 < a \leq b \leq c$). Имеем:
$$f'(d) = 4d^3 - 2(a^2 + b^2 + c^2)d + 2abc,$$
так что $f'(c) = 2c^3 - 2(a^2 + b^2)c + 2abc \geq 0 (0 < a \leq b \leq c)$.
Далее,
$$f''(d) = 12d^2 - 2(a^2 + b^2 + c^2) \geq 0$$

при $0 < a \leq b \leq c$. Поэтому по лемме $f'(d) \geq f'(c) \geq 0$ при $d \geq c$. Используя то, что $f(c) \geq 0$ (см. замечание выше) и $f'(d) \geq 0$ при $d \geq c$, и снова применяя лемму, получим неравенство $f(d) \geq 0$ при $d \geq c$, которое и требовалось.

Интересное обобщение этого неравенства придумал Ф. Шлеёфер (Рязань): для любых $a_1, \dots, a_n$
$(n-1)(a_1^2 + a_2^2 + \dots + a_n^2) + n\sqrt{a_1^2 \cdot a_2^2 \cdot \dots \cdot a_n^2} \geq (a_1 + a_2 + \dots + a_n)^2$.

При $n=4$, $a_1=a^2$, $a_2=b^2$, $a_3=c^2$, $a_4=d^2$ получим утверждение нашей задачи.

В. Сендеров, Э. Туркевич

36

М507. Пусть $a_1 < a_2 < \dots < a_n < 2n$ — конечная последовательность натуральных чисел ($n \ge 6$).
a) Доказим, что
$$\min [a_i, a_j] \leq 6 \left( \left[ \frac{n}{2} \right] + 1 \right),$$
еще $[a_j, a_j]$ означает наименьшее общее кратное чисел $a_i$ и $a_j$, а минимум берется по всем параметры чисел $a_i, a_j$.
b) Доказим, что
$$\max (a_i, a_j) > \frac{38n}{147} - c,$$
еще $c$ не зависит от $n$, а $(a_i, a_j)$ означает наименьший общий делитель $a_i$ и $a_j$.
Оценки в задачах a) и b) нельзя улуцишь (мо есть коэффициент 6 заменить меньшим, а $\frac{38}{147} - \text{большим}$).

Ниже будет доказано более общее утверждение. Пусть $a_1 < a_2 < \dots < a_n \leq 2n$.
a) Докажем, что требуем неравенство выполняется при $n \ge 5$. Пусть среди элементов последовательности $a_1, a_2, \dots, a_n$ найдется число $a \leq n$. Если число 2a также принадлежит данной последовательности, то
$$\min [a_i, a_j] \leq [a, 2a] = 2a \leq 2n \leq 6 \left( \left[ \frac{n}{2} \right] + 1 \right),$$
что дает решение задачи. Если же 2a не принадлежит последовательности, то выбросим из нее число $a$ и заменим его на 2a. Ясно, что $\min [a_i, a_j]$ для новой последовательности не меньше, чем для исходной. Применив это же рассужение к каждому элементу $a \leq n$, мы приdem в конце концов к последовательности $n + 1, n + 2, \dots, 2n$, причем
$$\min [a_i, a_j]$$ для этой последовательности не меньше соответствующего минимума для любой другой последовательности, из которой она была получена, в частности — для исходной.
Докажем теперь, что для последовательности $n + 1, n + 2, \dots, 2n$ при $n \ge 5$ выполняется равенство
$$n + 1 \leq a < b \leq 2n$$
и
$$[a, b] = 6k + 6 = 6 \left( \left[ \frac{n}{2} \right] + 1 \right).$$

А теперь проверим, что для любой пары чисел $c, d$, удовлетворяющей условию $n + 1 \leq c < d \leq 2n$, выполняется неравенство $[c, d] \geq 6 \left( \left[ \frac{n}{2} \right] + 1 \right)$. Действительно, $[c, d] = pd = qc$, где $q > p > 1$. При этом либо $p = 2$ и $q \ge 3$, либо $q \ge 4$. В первом случае $c$ — число четное, тем самым $c \ge 2 \left( \left[ \frac{n}{2} \right] + 1 \right)$ и $[c, d] = qc \ge 3c \ge 6 \left( \left[ \frac{n}{2} \right] + 1 \right)$. Во втором случае $[c, d] = qc \ge 4 (n + 1) \ge 6 \left( \left[ \frac{n}{2} \right] + 1 \right)$. Этим завершается доказательство утверждения a).

6. Рассмотрим более общую задачу: пусть $a_1 < a_2 < \dots < a_k \leq B$ — последовательность натуральных чисел; пребуем оценить силу $max (a_i, a_j)$. Для этого полезно обратную задачу: пусть $A, B$ — положительные (не обязательное целое) числа; определить максимальное $k$, для которого найдется последовательность из $k$ различных натуральных чисел $a_1, a_2, \dots, a_k$ максим, что
   (1) какный элемент последовательности не превышает $B$;
   (2) $(a_i, a_j) \leq A$ для любых различных элементов $a_i, a_j$.
   Будем обозначать это максимальное количество через $k (A, B)$. Для решения исходной задачи нужно подобрать $A$ так, чтобы $k (A, 2n)$ примерно равнялось $n$. Действительно, если для каждого $A$
   $$k (A, 2n) < n,$$
   то для любой последовательности $a_1 < a_2 < \dots < a_n \leq 2n$ будет
   $$max (a_i, a_j) > A;$$
   если же $k (A, 2n) \ge n$, то найдется последовательность $a_1 < a_2 < \dots < a_n \leq 2n$ также, что
   $$max (a_i, a_j) \leq A.$$
   Пусть $a_1, \dots, a_k$ — последовательность, удовлетворяющей условиям (1) и (2). Если у какого-то элемента $a_i$ этой последовательности найдется с обстенены (то есть не совпадающий с $a_i$) делитель $d > A$, то в силу условия (2) $d$ не является элементом последовательности. Тогда, заменяя

37

$a_i$ на $d$, мы получим новую последовательность той же длины, также удовлетворяющий условиям (1) и (2). Поступая таким же образом, мы получим в конце концов последовательность, в которой никакой элемент не имеет собственных делительей, больших $A$. Такую последовательность называем неократимой.

Рассмотрим теперь множество $M$ всех натуральных чисел, которые не превосходят $B$ и не имеют собственных делителей, больших $A$. М является неократимой последовательностью, удовлетворяющей условиям (1) и (2), и любая другая неократимая последовательность содержится в $M$. Поэтому ясно, что $k(A, B)$ просто равно числу элементов $M$.

Чтобы подсчитать число элементов множества $M$, осуществляем отдельно число четырех элементов, число нечетных элементов, делящихся на 3, и т. д. Более точно, пусть $M_2$ состоит из всех четырех элементов множества $M$, $M_3$ состоит из всех четырех элементов из $M$, делящихся на 3, $M_5$ состоит из всех четырех элементов $M$, делящихся на 5, но не делящихся ни на 2, ни на 3. И вообще, для любого простого числа $p$ множество $M_p$ состоит из тех элементов множества $M$, которые делятся на $p$ и не имеют простых делителей, меньших $p$.

Подсчитаем число элементов множества $M_p$. Любой элемент из $M_p$ имеет вид $pc$, где $c \leqslant A$ (так как $M$ — неократимое множество), $pc \leqslant B$ и $c$ не имеет простых делителей, меньших $p$. Если $pA \leqslant B$, то условие $pc \leqslant B$ можно не применять во внимание, и число элементов $M_p$ равно количеству натуральных $c \leqslant A$, не имеющих простых делителей, меньших $p$ (такое число будем обозначать через $m_p(A)$). Если же $pA > B$, то число элементов $M_p$ равно $m_p\left(\frac{B}{p}\right)$ и не превосходит $m_p(A)$.

Зафиксируем простое число $p$. Множества $M_2, M_3, M_5, \dots, M_p$, вообще говоря, не исчерпывают множества $M$. Обозначим через $N$ множество всех оставшихся элементов $M$. Они не имеют делителей среди чисел 2, 3, 5, …, $p$, поэтому их количество не превосходит числа $m_q(B)$, где $q$ — следующее за $p$ простое число. Таким образом,

$$k(A, B) \leqslant m_2(A) + m_3(A) + \dots + m_p(A) + m_q(B).$$

Если $pA \leqslant B < qA$, то это неравенство превращается в равенство. Действительно, ясно, что каждое $M_r$ содержитровно $m_r(A)$ элементов. С другой стороны, каждое число $c \leqslant B$, которое не имеет делителей, меньших $q$, не имеет тем самым делителей, больших $A$ (если $c = df$, где $d > A$ и $c \leqslant B < qA$, то $f < q$), и поэтому входит в $N$; следовательно, $N$ содержит $m_q(B)$ элементов.

Теперь займемся оценкой чисел вида $m_r(C)$. Во-первых, $m_2(C)$ равно количеству всех натуральных $l \leqslant C$, то есть равно $[C]$, и отличается от $C$ меньше, чем на 1. Далее, $m_3(C) = m_2(C) - m_2\left(\frac{C}{2}\right)$ (количество всех $l \leqslant C$ меньше, чем на 1, то $m_3(C)$ отличается от $C$ $\left(1 - \frac{1}{2}\right)$ меньше чем на 2).

Рассудядя таким же образом, мы получим, что если $p$ и $q(p < q)$ — два соседних простых числа, то $m_q(C) = m_p(C) - m_p\left(\frac{C}{p}\right)$, откуда индикцией получается, что $m_q(C)$ отличается от числа $C\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) \dots \dots \left(1 - \frac{1}{p}\right)$ меньше, чем на $2^{i-1}$, где $i$ — номер простого числа $q$. Иначе говоря, обозначив через $Z_q$ произведение всех чисел вида

38

$$\left(1 - \frac{1}{r}\right),$$
где $r$ — простое число, меньше $q$ (и положив $Z_2 = 1$), получим

$$|m_q(C) - C \cdot Z_q| < 2^{i-1}$$

($i$ — номер простого числа $q$). Таким образом, для числа $k(A, B)$ верны следующие оценки:

$$k(A, B) \leq m_2(A) + \ldots + m_p(A) + m_q(B) < A(Z_2 + Z_3 + \ldots + Z_p) + B \cdot Z_q + 1 + 2 + \ldots + 2^{i-1} = A(Z_2 + \ldots + Z_p) + B \cdot Z_q + (2^i - 1);$$

если же $pA \leq B \leq qA$, то

$$k(A, B) = m_2(A) + \ldots + m_p(A) + m_q(B) > A(Z_2 + \ldots + Z_p) + B \cdot Z_q - (2^i - 1).$$

(3)

Вернемся теперь к исходной задаче и выясним, при каких $A$ $k(A, 2n) < n$. Для этого достаточно решить относительно $A$ неравенство

$$A(1 + Z_3 + \ldots + Z_p) + 2n \cdot Z_q + (2^i - 1) \leq n.$$

Беря $p$ равным 3,5 или 7, мы получим, соответственно,

$$A \leq \frac{2}{9}n - \frac{14}{3}, \quad A \leq \frac{14}{55}n - \frac{90}{11},$$

$$A \leq \frac{38}{147}n - \frac{310}{21}.$$

При $p = 7$ появляется тиннстевенный множитель $\frac{38}{147}$, самый большой из трех. Брать $p \geq 11$ бессмысленно, так как $11 \cdot \frac{38}{147}n \geq 2n$, и неравенства для $k(A, 2n)$ будут менее точными. Итак, мы доказали, что при $n \geq 2$ для любой последовательности $a_1 < a_2 < \ldots < a_n \leq 2n$

$$\max(a_i, a_j) > \frac{38}{147}n - \frac{310}{21}.$$

Чтобы доказать, что коэффициент $\frac{38}{147}$ нельзя увечит, возьмем $A = \frac{38}{147}n + \frac{310}{21}$. Тогда при $n \geq 543$ будет $7A \leq 2n < 11A$, и, используя неравенство (3), получаем $k(A, 2n) \geq n$. Следовательно, при $n \geq 543$ всегда найдется последовательность $a_1 < a_2 < \ldots < a_n \leq 2n$, для которого

$$\max(a_i, a_j) \leq \frac{38}{147}n + \frac{310}{21}.$$

Если оценить $m_r(C)$ следует аккуратной, то можно получить более точные неравенства: при $n \geq 2$ для любой последовательности $a_1 < a_2 < \ldots < a_n \leq 2n$

$$\max(a_i, a_j) \geq \frac{38}{147}n - \frac{73}{49};$$

и, кроме того, существует последовательность $a_1 < a_2 < \ldots < a_n \leq 2n$, для которого

$$\max(a_i, a_j) \leq \frac{38}{147}n + \frac{73}{49}.$$

(замечательно то, что константу $\frac{73}{49}$ в этих неравенствах уменьшить уже нельзя).

Д. Берништейн

39

Ф513. В ясный солнечный день, когда Солнце находится в горизонтом, получите на эладком экране, направер, на белой стене, меня отровно края куска картона. Если meterр поднести к листу картона пальце mak, как это показано на рисунке 5, то на экране насстрему меня пальца из меня, отбрасываемой листом картона, высушет меня второго пальца. Проведите макой опыт и обясните его результат.

Привлечь для описания явления понятие диффракции невозможно, так как размеры диффрационной картины при таких расстояниях малы.

Решение задачи взрослого только тогда, когда мы учтем, что Солнце — не точный источник света, а обладает конечными угловыми размерами.

Чтобы понять, как появляется встречная тень, обратится к рисунку 6.

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

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

Г. Соловьянок

Рис. 5.

Ф516. Тяжелый диск радиуса R скатывается на двух нерастяжимых нитях, наоматных на него. Свободные концы нитей закреплены (рис. 7). Нити при движении диска постоянно наятыми. В некоторых моменту человека скорость диска равна $\omega$, а угод между нитями $\alpha$. Какова в этом моменте скорость центра диска?

Рассмотрим движение точки $c$ и $d$, в которыхнится касаются диска, в системе координат, начало которой совпадает с точкой $O$, в которой находится центра диска, когда угол между нитями равен $\alpha$, а оси $OX$ и $OY$ составляют угол $\alpha$ друг с другом и параллельны нитям (рис. 7). В этой системе координат (как и в любой неподвижной системе) скорости точки $c$ и $d$ равны соответственно

$$v_c = v_0 + v_{c0}, \quad v_d = v_0 + v_{d0}.$$

где $v_0$ — скорость центра диска, $v_{c0}$ и $v_{d0}$ — скорости точки $c$ и $d$ относительно центра диска. Очевидно, $|v_{c0}| = |v_{d0}|$, и при угловой скорости врашения диска $\omega$

$$|v_{c0}| = |v_{d0}| = \omega R = u.$$

Из условия нерастяжимости нитей следует, что, когданится образуют угол $\alpha$, проекции $v_{dx}$ и $v_{cy}$ скоростей $v_d$ и $v_c$ на оси $OX$ и $OY$ равны нулю:

$$v_{dx} = v_{0x} - u = 0, \quad v_{cy} = v_{0y} - u = 0.$$

Отсюда

$$v_{0x} = v_{0y} = u.$$

Это означает, что вектор $v_0$ скорости центра диска направ-