Задача из журнала «Квант» (2000 год, 3 выпуск) М1707*

Условие

Квадрат клетчатой бумаги, состоящий из $n\times n$ клеток, разрезан на $2n$ прямоугольников. При этом каждый прямоугольник расположен либо целиком ниже, либо выше ступенчатой ломаной, разделяющей квадрат (рис.1). Докажите, что найдется клетка клетчатой бумаги, являющаяся одним из названных прямоугольников.

Рис. 1

Решение

Ступенчатая ломанная разрезает квадрат на два ступенчатых треугольника $T_1$ и $T_2$, при этом основание $T_1$ состоит из $n$ клеток, а основание $T_2$ – из $n – 1$ клетки. В силу условия задачи, один из них разрезан на $m$, а другой – на $k$ прямоугольников, причем $m + k = 2n$. Пока что фиксируем внимание на отдельно взятом ступенчатом треугольнике $T$, в основании которого $s$ клеток (рис.2). Так как при разрезании $T$ на прямоугольники любые две точки из набора $A_1, A_2, \ldots, A_s$ должны принадлежать разным прямоугольникам, можно заключить, что $T$ нельзя разрезать на менее чем $s$ прямоугольников.

Рис. 2

Разберем далее тот случай, когда $T$ разрезан в точности на s прямоугольников; тогда каждая из точек $A_1, A_2 , \ldots, A_s$ принадлежит только одному из них и, более того, каждая из $s$ закрашенных клеток принадлежит целиком только одному из $s$ прямоугольников. Не закрашенных клеток, примыкающих по сторонам к закрашенным, на единицу меньше, чем закрашенных, поэтому хотя бы один из $s$ прямоугольников не выйдет за пределы своей заштрихованной клетки, т.е. будет с ней совпадать. Возвращаясь к ступенчатым треугольникам $T_1$ и $T_2$, можно сказать, что $m \geq n$, а $k \geq n-1$. Но так как $m + k = 2n$, то либо $m = n$, либо $k = n – 1$. Значит, либо в $T_1$, либо в $T_2$ найдется прямоугольник, совпадающий с клеткой клетчатой бумаги.

В.Произволов

1.3 Ограниченные множества

Пусть $E$ – непустое множество действительных чисел.

Определение. Множество $E$ называется ограниченным сверху, если существует такое $M \in \mathbb{R},$ что для всех $x \in E$ справедливо неравенство $x \leqslant M.$ Число $M$ называется верхней границей множества $E.$
Множество $E$ называется ограниченным снизу, если существует такое $m \in \mathbb{R},$ что для всех $x \in E$ справедливо неравенство $x \geqslant m$. Число $m$ называется нижней границей множества $E.$

У ограниченного сверху множества существует сколь угодно много верхних границ. Действительно, если $M$ – верхняя граница множества $M$, то для любого положительного $\xi$ число $M + \xi $ также является верхней границей $E$. Аналогично, у ограниченного снизу множества существует сколь угодно много нижних границ.
С геометрической точки зрения ограниченность сверху множества $E$ означает наличие на числовой прямой такой точки $M,$ что все точки множества $E$ расположены не правее $M.$ Аналогично, ограниченность снизу множества $E$ означает наличие на числовой прямой такой точки $m,$ что все точки множества $E$ расположены не левее, чем $m.$

Определение. Множество $E$ называется ограниченным, если оно ограничено сверху и снизу, т. е. если существуют такие $m, M \in \mathbb{R} ,$ что для всех $x \in E$ справедливо неравенство $m \leqslant x \leqslant M$.

С геометрической точки зрения ограниченность $E$ означает, что все точки множества $E$ содержатся в некотором отрезке $\left [m, M \right ]$ числовой прямой.

Определение. Элемент $x \in E$ называется наибольшим элементом множества $E,$ если для любого $z \in E$ справедливо неравенство $z \leqslant x.$ Элемент $y \in E$ называется наименьшим элементом множества $E,$ если для любого $z \in E$ справедливо неравенство $z \geqslant y.$

Очевидно, что если во множестве $E$ существует наибольший элемент, то это множество ограничено сверху, а если в $E$ существует наименьший элемент, то это множество ограничено снизу. Однако не каждое ограниченное сверху (снизу) множество имеет наибольший (наименьший) элемент. Например, множество $E = \left (0, 1 \right ) \equiv \left \{ x \in \mathbb{R} : 0 < x < 1 \right \}$ ограничено сверху (например, числом $1$), однако в нем нет наибольшего элемента. Действительно, для любого $x \in E$ число $\displaystyle z = \frac{x+1}{2} > x$ также принадлежит $E$. Аналогично можно показать, что $E$ ограничено снизу, но не имеет наименьшего элемента.

Пусть $E$ – ограниченное сверху множество. Через $\overline{E}$ обозначим совокупность всех верхних границ множества $E.$ Множество $\overline{E}$ непусто и, как мы уже видели, неограничено сверху. Очевидно, однако, что $\overline{E}$ ограничено снизу (например, любой элемент множества $E$ является нижней границей множества $\overline{E}).$

Поставим следующий вопрос: существует ли во множестве $\overline{E}$ наименьший элемент?

Определение. Пусть множество $E$ ограничено сверху. Тогда наименьшая из всех его верхних границ называется верхней гранью, или точной верхней границей, и обозначается $\sup E$.

Это определение равносильно следующему.

Определение. Число $M$ называется верхней гранью множества $E,$ если выполнены следующие два условия:

  1. для каждого $x \in E$ справедливо неравенство $x \leqslant M$;
  2. для любого $\xi > 0$ найдется такой $x \in E$, что $x > M − \xi$.

Первое условие этого определения означает, что $M$ является верхней границей множества $E,$ а второе – что $M$ – наименьшая из всех верхних границ, т. е. что никакое число $M − \xi < M$ не является верхней границей множества $E.$
Аналогично формулируется определение нижней грани.

Определение.Пусть множество $E$ ограничено снизу. Тогда наибольшая из всех его нижних границ называется нижней гранью, или точной нижней границей, и обозначается $\inf E$.

Это определение равносильно следующему.

Определение.Число $m$ называется нижней гранью множества $E,$ если выполнены следующие два условия:

  1. для каждого $x \in E$ справедливо неравенство $x \geqslant M$;
  2. для любого $\xi > 0$ найдется такой $x \in E$, что $x < M − \xi$.

Первое условие этого определения означает, что m является нижней границей множества $E,$ а второе – что $m$ – наибольшая из всех нижних границ, т. е. что никакое число $m + \xi > m$ не является нижней границей множества $E.$

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

Теорема (о существовании верхней грани).Каждое непустое ограниченное сверху множество имеет верхнюю грань.

Пусть $E$ – ограниченное сверху множество, а $E –$ множество всех его верхних границ. Оба множества непустые, и для любых $x \in E, y \in E$ справедливо неравенство $x \leqslant y.$ По аксиоме полноты множества действительных чисел, существует такое число $M,$ что для любых $x \in E, y \in E$ справедливо неравенство $x \leqslant M \leqslant y.$ Левое неравенство означает, что число M является верхней границей множества $E,$ т. е. $M \in E,$ а правое неравенство показывает, что $M –$ наименьший элемент во множестве $E.$

Аналогично доказывается следующая.

Теорема (о существовании нижней грани).Каждое непустоеограниченное снизу множество имеет нижнюю грань.

Понятие верхней (нижней) грани мы определили для ограниченного сверху (снизу) множества. Но не каждое множество ограничено сверху (снизу). Так, само множество действительных чисел $\mathbb{R}$ неограничено сверху и снизу. В самом деле, для любого $M \in \mathbb{R}$ найдется $x \in \mathbb{R},$ такой, что $x > M$ (например, $x = M + 1).$ Это означает, что никакое число $M$ не является верхней границей множества $\mathbb{R}.$ В случае если множество $E$ неограничено сверху, иногда пишут $\sup E = +\infty.$ Аналогично, если множество $E$ неограничено снизу, то пишут $\inf E = −\infty.$ Примером неограниченного снизу множества также может быть множество $\mathbb{R}.$

Примеры решения задач

  1. Пусть $\displaystyle X = \left \{ 1, \frac{1}{2}, \frac{1}{3}, \ldots \frac{1}{n}, \ldots \right \}.$
    1. Указать наименьший и наибольший элементы этого множества, если они существуют.
    2. Каковы множества верхних и нижних границ для множества $X.$ Найти $\sup X$ и $\inf X.$
    Решение
    1. Данное множество имеет наибольший элемент $M=1$ поскольку для всех элементов множества $x \in X$ выполняется неравенство $x \leqslant 1$ и при этом $1 \in X.$ Наименьшего элемента заданное множество не имеет, так как для любого элемента $\displaystyle x_n= \frac{1}{n}\in X$ всегда найдется элемент $\displaystyle x_{n+1}=\frac{1}{n+1} \in X$ для которого выполняется неравенство $x_{n+1} \leqslant x_n.$

      Наименьшего элемента множества $X$ не существует. Очевидно, что для всех элементов $x$ множества $X$ выполняется $x \geqslant 0,$ то есть множество $X$ ограничено снизу. Покажем, что $0$ является предельным значением множества $X.$ Действительно, для любого $\xi >0$ можно найти натуральное число:
      $$\displaystyle n > \frac{1}{\xi} \Rightarrow \frac{1}{n} < \xi, \frac{1}{n} \in X. $$

    2. Поскольку для всех элементов $x$ множества $X$ выполняется неравенство $x \leqslant 1,$ причем $1 \in X,$ то множество верхних границ для множества $X$ это множество $[1,+\infty)$ c наименьшим элементом равным $1.$ Таким образом, $\sup X=1.$ Множество нижних границ для $X$ это множество $(−\infty,0]$ c наибольшим элементом равным $0.$ Отсюда находим $\inf X=0.$

    Ответ: $M=1,$ наименьшего элемента не существует, $[1,+\infty), (−\infty,0], \sup X=1, \inf X=0.$

  2. Доказать, что для любого непустого ограниченного множества $A \subset \mathbb{R}$ и для любого числа $\lambda \geqslant 0$ справедливо равенство $\sup \lambda A = \lambda \sup A.$ (здесь $\lambda A = {\lambda x : x \in A}$).
    Решение

    Если $\lambda = 0,$ утверждение очевидно. Будем считать, что $\lambda \neq 0$. Обозначим $a = \sup A.$ Требуется доказать, что $\lambda a$ — точная верхняя граница множества $\lambda A.$ Как указано выше, для этого надо проверить, что $\lambda a$ — верхняя граница и что сдвиг вниз на произвольное $\xi > 0$ уже не будет верхней границей. Проверка. Так как $a = \sup A,$ число $a$ — верхняя граница множества $A,$ стало быть, $(\forall x \in A) x \leqslant a.$ Умножив неравенство на положительное число, получаем, что $(\forall x \in A) \lambda x \leqslant\lambda a,$ так что $\lambda a —$ верхняя граница.

    Проверим второе свойство. Пусть дано произвольное $\xi > 0.$ Надо подобрать такое $x \in A,$ что $\lambda x > \lambda a − \xi.$ Запишем последнее неравенство,изолировав в нем $\displaystyle x: x > a − \frac{\xi}{\lambda},$ и вновь воспользуемся условием, согласно которому для любого $\xi_1 > 0$ найдется такое $x \in A,$ что $x > a − \xi_1.$ Взяв в качестве $\xi_1$ число $\displaystyle \frac{\xi}{\lambda},$ получаем, что для любого $\xi > 0$ есть такое $x in A,$что $\displaystyle x > a − \frac{\xi}{\lambda},$ это и требовалось.

Смотрите также

  1. Тер-Крикоров А. М., Шабунин М.И. Курс математического анализа: Учеб. пособие для вузов. – 3-е изд., исправл. / А. М. Тер-Крикоров, М.И. Шабунин. – Москва: ФИЗМАТЛИТ, 2001. – 672 с. — с. 15-23.
  2. Кудрявцев Л. Д. Курс математического анализа : учебник для вузов: В 3 т. Т. 1. Дифференциальное и интегральное исчисления функций одной переменной / Л. Д. Кудрявцев. — 5-е изд., перераб. и доп. — Москва: Дрофа, 2003. — 703 с. — с.22-28.

Ограниченные множества

Пройдите этот тест, чтобы проверить свои знания по только что прочитанной теме «Ограниченные множества».

Задачи из журнала «Квант» № M2141

Условие

В треугольнике ABC проведена биссектриса BD ( точка D лежит на отрезке AC ). Прямая BD пересекает окружность \Omega , описанную около треугольника ABC, в точках B и E. Окружность \omega, построенная на отрезке DE как на диаметре, пересекает окружность \Omega в точках E и F. Докажите, что прямая, симметричная прямой BF относительно прямой BD, содержит медиану треугольника ABC.

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

Пусть M - середина стороны AC (см. рисунок ). Так как дуги AE и CE равны, то ME - серединный перпендикуляр к отрезку AC. Поскольку \angle DME = 90^{\circ}, то M лежит на окружности \omega. Пусть прямая DF пересекает вторично окружность \Omega в точке G. Так как \angle DFE = 90^{\circ}, то G - точка, диаметрально противоположная точке E, в частности EG проходит через M.
Имеем \angle FBE =\angle FGE .
Далее, поскольку EG - диаметр, \angle GBE = 90^{\circ}. Из равенств \angle GBD = \angle GMD = 90^{\circ} вытекает, что GBDM - вписанный четырехугольник ( в отружность с диаметром DG ), откуда \angle MBE = \angle MBD = \angle MGD = \angle EGF. Окончательно, \angle FBE = \angle FGE = \angle MBE , что и требовалось установить.

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

Условие

Натуральные числа $а,$ $b$ и $с$ таковы, что

$$a^2+b^2+c^2=(a-b)^2+(b-c)^2+(c-a)^2.$$

Докажите, что каждое из четырех чисел $ab,bc,ca$ и $ab+bc+ca$ является квадратом.

Решение

Можно записать:
$$a^2+b^2+c^2=2ab+2bc+2ca,\,\,\,\,\,\,\,\,\,\,(*)$$
или иначе:
$$(a+b+c)^2=4(ab+bc+ca).$$
Значит, число $ab + bc + ca$ является квадратом. Равенство $(*)$ можно истолковать как квадратное уравнение относительно $с.$
Поэтому
$$c=(a+b)\pm \sqrt{ab}.$$
Значит, число $ab$ является квадратом. Точно так же убеждаемся, что числа $bc$ и $ca$ – тоже квадраты.

В.Произволов

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

Условие

Пусть $A$ – произвольная четная цифра, $B$ –произвольная нечетная цифра. Докажите, что существует натуральное число, делящееся на $2^{2000},$ каждая цифра которого – либо $A,$ либо $B.$

Решение

Укажем способ составления из цифр $A$ и $B$ числа, делящегося на $2^n$ для любого натурального $n.$ Обозначим такое число $G_n.$ При $n = 1$ полагаем $G_n=G_1= A.$ Пусть построено число $G_k$ при $n=k \geqslant 1.$ Воспользуемся им при построении следующего числа $G_{k+1},$ делящегося на $2^{k+1}$.

Если $G_k$ делится на $2^{k+1},$ то полагаем $G_{k+1}=G_k,$ в противном случае построим вспомогательное число $F_k$ , обладающее следующими свойствами: число $F_k$ составлено из цифр $A$ и $B$, делится на $2^k$ и имеет в своей десятичной записи ровно $k$ цифр.

Если $G_k$ имеет в своей записи ровно $k$ цифр, то полагаем $F_k=G_k$.

Если в записи $G_k$ более $k$ цифр, положим $F_k$ равным числу, получающемуся из $G_k$ отбрасыванием старших цифр, начиная с $(k + 1)$-й. По признаку делимости на $2^k,$ полученное из $G_k$ после такой операции число $F_k$ будет также делиться на $2^k$.

Если в записи $G_k$ менее $k$ цифр, припишем к числу $G_k$ слева его же несколько раз таким образом, чтобы в результате получилось число, в записи которого не менее $k$ цифр. Это число делится на $G_k$ и, следовательно, на $2^k.$ Если из него отбросить все старшие цифры, начиная с $(k + 1)$-й, то в результате получим число $F_k,$ которое, по признаку делимости на $2^k,$ также делится на $2^k.$

Если число $F_k$ делится на $2^{k+1},$ то полагаем $G_{k+1}=F_k,$ в противном случае полагаем $G_{k+1}=\overline{B F_k},$ приписав к числу $F_k$ число $B$ слева. Положив $F_k=2^k p,$ где $p$ – некоторое нечетное число, получаем $G_{k+1}=10^k B+2^k p=2^k (5^k B + p).$ В скобках стоит четное число, поэтому $G_{k+1}$ делится на $2^{k+1}.$

И.Акулич, А.Жуков