M683. О расположении кружков разных цветов так, чтобы любые два касающиеся были разными

Задачa из журнала «Квант» (1981 год, 5 выпуск)

Условие

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

Доказательство

Доказательство возможности требуемой раскраски проведем индукцией по числу кружков n.
При n\leq 4 утверждение очевидно. Предположим, что оно справедливо для любого расположения k кружков. Пусть на столе лежит k+1 кружков. Зафиксируем на плоскости произвольную точку M и рассмотрим кружок, центр O которого находится на наибольшем расстоянии от M (если таких кружков несколько, возьмем любой из них). Нетрудно убедиться, что выбранного кружка касается не более двух других (центры всех кружков лежат в круге \left ( M, \left | OM \right | \right ) — рис. 1).
Отбросим кружок с центром O и раскрасим нужным образом в четыре цвета оставшиеся k кружков (по предположению индукции это можно сделать). Вернем теперь кружок с центром O на место. Поскольку он касается не более трех из уже покрашенных кружков, его можно раскрасить в тот цвет, который не был использован при раскраске касающихся его соседей.

Утверждение доказано.

Рисунок 1.

На рисунке 2 изображены 11 кружков, для нужной раскраски которых трех цветов недостаточно. Действительно, предположив, что эти кружки можно раскрасить тремя цветами, получим, что кружки A, B, C, D, E должны быть окрашены одинаково. Но это невозможно, поскольку кружки A и E касаются.

Рисунок 2.

M610. Об «интересных» наборах чисел

Задачa из журнала «Квант» (1980 год, 2 выпуск)

Условие

Фиксируем $k \in \mathbb N$.
$а)$ Рассмотрим множество всех наборов целых чисел $a_1, \ldots , a_k$ таких, что $0 \le a_1 \le a_2 \le \ldots \le a_k \le k$; обозначим число таких наборов через $N.$ Рассмотрим среди них те, для которых $a_k = k$; пусть их число равно $M$. Докажите, что $N=2M$.
$б)$ Наложим на рассматриваемые наборы дополнительное ограничение: сумма $a_1 + \ldots + a_k$ делится на $k$. Пусть соответствующие числа равны $N’$ и $M’$. Докажите, что $N’ = 2M’$ (Из рисунка 1 видно, что при $k=3$ эти числа равны $M=10$, $N=20$; $M’=4$, $N’=8$.)

Рис. 1.

Решение

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

Нам нужно доказать, что наборов, в которых $a_k = k$ ровно половина. Поэтому попробуем установить взаимно однозначное соответствие между этими наборами и оставшимися, теми, у которых $a_k < k$.

Сопоставить набору $(a_1, a_2, \ldots, a_k)$ набор $(a_k, a_{k-1}, \ldots, a_1)$ нельзя, так как новый набор — невозрастающий. Можно попробовать сопоставить набору $(a_1, \ldots, a_k)$ набор $k-a_k, k-a_{k-1}, \ldots, k-a_1)$: он уже — неубывающий, но… $k-a_1$ не обязательно быть меньше $k$. Поэтому это соответствие не решает задачу.

Значит, необходимо более сложное соответствие. Для его построения нам понадобится понятие диаграммы Юнга данного набора.

Рис. 2

Что это такое, проще всего объяснить на примере: набору $(0, 0, 2, 3, 5)$ соответствует диаграмма, изображенная на рисунке 2 — в каждой строке столько соответствующее число.

Дополним диаграмму Юнга до квадрата (рис. 3). Тогда становится ясно, что наша первоначальная идея заключалась в том, что отсчитывать диаграмму не из красных, а из белых квадратиков (и, соответственно, не слева-снизу, а справа-сверху).

Рис. 3

Попытаемся теперь дополнить рисунок 3 вертикальной диаграммой — как на рисунке 4. Отсчитывая эту диаграмму снизу-слева, получим набор $(2, 2, 3, 4, 4)$. Назовем этот набор дополнительным к набору $(0, 0 , 2, 3, 5)$. Еще один пример изображен на рисунке 5.

Ясно, что если исходный набор $(a_1, \ldots, a_k)$, а дополнительный — $(b_1, \ldots, b_k)$, то $(a_k = k)$ тогда и только тогда, когда $b_k < k$. В самом деле, $a_k = k$, если верхняя правая клетка входит в основную диаграмму Юнга, и $a_k < k$, если она входит в дополнительную.

Рис. 4

Установленное нами соответствие между наборами, у которых $a_k = k$, и наборами, у которых $a_k < k$, очевидно, взаимно однозначно. Тем самым мы решили $a)$. Кроме того, сумма чисел исходного и дополнительного наборов равна $k^2$ (в наших примерах — 25). Поэтому сумма чисел дополнительного набора делится на $k$ тогда и только тогда, когда делится на $k$ сумма чисел исходного набора. Это решает $б)$.

Рис. 5

Замечание. Задача $a)$ имеет и другое решение: можно непосредственно посчитать числа $N$ и $M$. Именно:

Лемма. Число наборов целых чисел $a_1, \ldots, a_m$ таких, что $0 \le a_1 \le \ldots \le a_m \le k$ равно $C^m_{k+m}$.

Доказательство. Рассмотрим набор $(b_1, \ldots, b_m)$ где $b_i = a_i + i : b_1 = a_1 +1, b_2 = a_2 +2 $ и т. д. Тогда, очевидно, $1 < b_1 < b_2 < \ldots < b_m \le k+m$, то есть $(b_1, \ldots, b_m)$ — произвольный возрастающий набор $m$ целых чисел их первых $k+m$ чисел. Число таких наборов равно $C^m_{k-m}$.

Поэтому число наборов, в которых $a_k \le k$, по лемме равно $C^k_{2k}$. Если же $a_k = k$, то нам остается выбрать числа $a_1, \ldots, a_{k-1}$ так, что $0 \le a_1 \le \ldots \le a_{k-1} \le k$; их число равно $C^{k-1}_{2k-1}$. Остается посчитать, что $2C^{k-1}_{2k-1}$ равно $C^k_{2k}$.

А. Толпыго

M1677. Диагонали параллелограмма

Задача из журнала «Квант» (выпуск №5, 1999)

Условие

Диагонали параллелограмма $ABCD$ пересекаются в точке $O$. Окружность, проходящая через точки $A$, $O$ и $B$, касается прямой $BC$. Докажите, что окружность, проходящая через точки $B$, $O$ и $C$, касается прямой $CD$.

Решение

Углы $OAB$ и $OBC$ равны, так как первый вписан в окружность $AOB$, а второй образован касательной $BC$ и хордой $BO$ этой окружности (см. рисунок). Следовательно, углы $OBC$ и $OCD$ также равны, что эквивалентно утверждению задачи. Отметим, что параллелограмм, вершинами которого являются середины сторон данного, подобен исходному, поэтому задача допускает другую формулировку: в параллелограмме $ABCD$ углы $CAB$ и $DBC$ равны, $AD=1$, найти $AC$.

А.Заславский

М1874. Все решения уравнения

Задача из журнала «Квант» (2004 год, 1 выпуск)

Условие задачи

Найдите все решения уравнения $x^{y} — y^{x} = 1$ в натуральных числах $x$ и $y$.

Ответ: $x = 2$, $y = 1$ и $x = 3$, $y = 2$.

Решение

Пусть $x = 2$. Тогда $2^{y} = y^{2} + 1$. Поскольку $y^{2} + 1$ не делится на $4$, то решений, кроме $(2, 1)$, нет.
При $y = 1$ имеем $x = 2$.
Пусть $y = 2.$ Тогда Пусть $\left(x + 1 \right) \cdot \left(x — 1 \right) = 2^{x},$ откуда $\left(x — 1 \right) = 2,$ $x = 3,$
Пусть $x \geqslant 3$, $y \geqslant 3.$ Рассмотрим функцию
$$f(t) = a^{t} — t^{a} = \left(a^{\frac{t}{a}} — t \right) \cdot \left(\left(a^{\frac{t}{a}} \right)^{a — 1} + … + t^{a — t} \right),$$
где $a \geqslant 3$ — целое число, $t \geqslant a$. Имеем $f(a) = 0;$ поскольку $\varphi(t) = a^{\frac{t}{a}} — t$ — возрастающая неотрицательная функция, то и f(t) возрастает.
Получили: при $t \geqslant a + 1$
$$f(t) \geqslant f(a + 1) = a^{a + 1} — (a + 1)^{a} \geqslant 1.$$
Последнее неравенство строгое: при $a^{a + 1} — (a + 1)^{a} = 1$ было бы $m \cdot a = 2,$ где $m$ $\epsilon$ $\mathbb{Z}.$
Окончательно: $x^{y} — y^{x} \neq 1.$
Рассуждая несколько по-иному, нежели выше, можно сразу получить числовую оценку выражения $a^{t} — t^{a}.$ Именно, пусть $a \geqslant 3,$ $z$ $\epsilon$ $\mathbb{N},$ Тогда, используя легко доказываемые неравенства $(1 + t)^{\frac{1}{t}} < e < 2,8,$ получаем
$$a^{a+z} — \left(a+z \right)^{a} = a^{a} \cdot \left(a^{z} — \left(\left(1 + \frac{z}{a} \right)^{\frac{a}{z}} \right)^{z} \right) >$$ $$>a^{a} \cdot \left(a^{z} — e^{z} \right) \geqslant a^{a} \cdot \left(a — e \right) > 3^{3} \cdot 0,2 > 1.$$
Вот и все.

В. Произволов, В. Сендеров

М1762. Две тысячи делителей

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров