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}$.

А. Толпыго

M1237. Точка внутри треугольника

Условие

1

Пусть точка O внутри, треугольника ABC= такова, что \overrightarrow{OK} +\overrightarrow{OM} +\overrightarrow{ON}= \overrightarrow{0}  М,N — основания перпендикуляров, опущенных из  О на стороны  AB, BC, CA треугольника. Докажите неравенство \frac{OK+OM+ON}{AB+BC+CA}\leq \frac{1}{2\sqrt{3}}

1

Решение

В силу условия на точку О отрезки ОК, ОМ, ON можно параллельно передвинуть так, чтобы составился треугольник. После поворота на 90° стороны этого треугольника станут параллельны сторонам треугольника ABC, следовательно, эти треугольники подобны. Коэффициент подобия обозначим через kk=\frac{OK}{AB} = \frac{OM}{BC} = \frac{ON}{CA}. Тогда левая часть доказываемого неравенства равна fe. С другой стороны, представляя площадь S треугольника ABC как сумму площадей треугольников AOB, BOC и COA, получим: 2S=a*OK+b*OM+c*ON = k(a^2+b^2+c^2) ,где a,b,c— длины сторон. Таким образом, задача сводится к доказательству неравенства:

s\leq \frac{a^2+b^2+c^2}{4\sqrt{3}}

Приведем одно из доказательств этого довольно известного неравенства, использующее формулу Герона и неравенство между средним арифметическим и средним геометрическим трех чисел (буквой p, как обычно, обозначен полупериметр):

S=\sqrt{p(p-a)(p-b)(p-c)}\leq \sqrt{p((p-a+p-b+p-c)/3)^3}=\frac{p^2}{3\sqrt{3}}\leq (a^2+b^2+c^2)/4\sqrt{3}

Последнее неравенство следует из соотношений:

4p^2=(a+b+c)^2=a^2+b^2+c^2+2ab+2bc+2ca и  2xy\leq x^2+y^2 .

Отметим, что точка О в этой задаче определена однозначно. Она называется точкой Лемуана треугольника ABC и является точкой пересечения его симедиан, т. е. прямых, симметричных медианам относительно соответствующих биссектрис.

 

Повторный предел

Повторные предельные значения. Для функции  u=f(x_{1},x_{2},...,x_{n}) нескольких переменных можно определить понятие предельного значения по одной из переменных  x=x_{k}   при фиксированных значениях остальных переменных. В связи с этим возникает понятие повторного предельного значения. Уясним это понятие на примере функции  u=f(x,y) двух переменных x и у. Пусть функция   u=f(x,y) задана в некоторой прямоугольной окрестности   \left | x-x_{0} \right |<d_{1}  ,   \left | y-y_{0} \right | <d_{2}  точки  M_{0}(x_{0},y_{0}) , за исключением, быть может, самой точки  M_{0}  . Пусть для каждого фиксированного y, удовлетворяющего условию  0<\left | y-y_{0} \right | <d_{2} существует предельное значение функции  u=f(x,y) одной переменной x в точке  x=x_{0}

\lim\limits_{x\rightarrow x_{0}} f(x,y)=\varphi (y)  

и пусть, кроме того, существует предельное значение b функции   \varphi (y) в точке  y=y_{0} :

\lim\limits_{y\rightarrow y_{0}}\varphi(y) =b

В этом случае говорят, что существует повторное предельное значение b для функции   u=f(x,y) в точке   M_{0} , которое обозначается следующим образом:

 \lim\limits_{y\rightarrow y_{0}} \lim\limits_{x\rightarrow x_{0}} f(x,y) =b

Теорема:

Пусть функция  u=f(x,y) определена в некоторой прямоугольной окрестности   \left | x-x_{0} \right |<d_{1}  ,   \left | y-y_{0} \right | <d_{2}  точки  M_{0}(x_{0},y_{0}) и имеет в этой точке предельное значение b. Пусть, кроме того, для любого фиксированного x,  0<\left | x-x_{0} \right | <d_{1}, существует предельное значение  \psi =\lim\limits_{y\rightarrow y_{0}}f(x,y) и для любого фиксированного y,  0<\left | y-y_{0} \right | <d_{2}, существует предельное значение  \phi (y)=\lim\limits_{x\rightarrow x_{0}} . Тогда повторные предельные значения  \lim\limits_{x\rightarrow x_{0}} \lim\limits_{y\rightarrow y_{0}} и  \lim\limits_{y\rightarrow y_{0}} \lim\limits_{x\rightarrow x_{0}} f(x,y) существуют и равны b.

 

Пример решения:

Вычислить повторный предел функций f(x,y)=\frac{x-y+x^2+y^2}{x+y}

Литература:

Бесконечные пределы

Определение

Пусть задана функция нескольких переменных A\subset \mathbb{R}^n \rightarrow \mathbb{R} и a —предельная точка множества A. Если для любого числа M>0 существует такое число \delta , что при x\in A\cap U(a,\delta ) выполняется неравенство f(x)> M ( \left | f(x) \right | > M), то говорят, что функция f(x) стремится к + \infty при, x\underset{A}{\rightarrow}a и пишут:
\lim\limits_{x\to a}=+\infty (\lim\limits_{x\to a}=-\infty или \lim\limits_{x\to a} =\infty )
Во всех трех случаях функцию f(x) называют бесконечно большой при x\underset{A}{\rightarrow}a.

Пример

Функция f(x, y) = \frac{1}{x^2+y^2} является бесконечно большой при (x, y) \rightarrow (0, 0) Функция g(x, y) = \frac{x}{x^2+y^2} стремится к \infty при (x, y)\underset{A}{\rightarrow} (0, 0), если A — сектор, заключенный между прямыми y = x и y = {-x} и расположенный в правой полуплоскости x > 0. В самом деле, в этом секторе \left | y \right | < \left | x \right | и поэтому:
\frac{x}{x^2+y^2}> \frac{x}{2x^2} = \frac{1}{2x}
Функция g(x, y) стремится к - \infty при (x, y)\underset{A}{\rightarrow} (0, 0), если A — сектор, заключенный между прямыми y = x и y = {-x} и расположенный в левой полуплоскости x < 0, поскольку в этом секторе \left | y \right | < \left | x \right | и поэтому:
\frac{x}{x^2+y^2}< \frac{x}{2x^2} = \frac{1}{2x}
Если A = {(x, y):x = 0, y \in R}— ось ординат, то g(x, y) = 0 на A и функция g(x, y) является бесконечно малой при (x, y)\underset{A}{\rightarrow} (0, 0).

Литература: