2.1Доказать, что во всякой группе из не менее двух человек найдутся двое с одинаковым количеством знакомых.
Пусть $n$ — количество человек в группе. Рассмотрим два случая.
a) Каждый из членов группы имеет хотя бы одного знакомого из оставшихся $(n-1)$ человек. В этом случае количество знакомых для $n$ человек может принимать одно из $(n-1)$ значений: 1,2...$n-1$.
Таким образом найдутся по крайней мере два человека с одинаковым количеством знакомых.
b) У одного из членов группы $A$ нет знакомых, таким образом $А$ имеет 0 знакомых.
Каждый из остальных не знаком с $A$, поэтому может иметь не более $(n-2)$ знакомых. Снова количество
знакомых для $n$ человек может принимать одно из $(n-1)$ значений: 0,1,...$n-2$, так что и в этом
случае найдутся как минимум два человека с одинаковым количеством знакомых.
2.2Доказать, что в любое время футбольного турнира, проходящего по круговой системе (каждый играет с каждым), найдутся две команды, сыгравшие одинаковое количество игр.
Каждая из $n$ команд встречается с $n-1$ остальными. Поэтому в любое время турнира каждая команда сыграла
не более $n-1$ матчей. Группируя по количеству сыгранных матчей, получаем $(n-1)$ групп, содержащих $n$ команд в совокупности. Дальше все понятно.
2.3Доказать что из $n$ различных чисел можно выбрать либо одно число кратное $n$, либо два числа, разность которых кратна $n$.
Существует $n$ возможных остатков от деления на $n$: $0$, $1$, ... $(n-1)$.
При этом, если среди чисел нет кратных $n$, нулевой остаток невозможен, так что остаются возможными $(n-1)$ остатков: $1$, $2$, ... $(n-1)$. По принципу Дирихле, среди $n$ чисел, дающих $n-1$ возможных остатков, найдутся два числа $a_1$ и $a_2$, дающих одинаковый остаток $r$ при делении на $n$. Таким образом,
$$
a_1 = nq_1 + r \\
a_2 = nq_2 + r
$$
Вычитая второе равенство из первого, получаем: $a_1-a_2=n(q_1-q_2)$, следовательно разность $a_1-a_2$ делится на $n$.
2.4Доказать, что из $n$ различных целых чисел можно выбрать несколько (возможно одно или все), сумма которых делится на $n$.
Запишем числа по порядку: $a_1, a_2 ... a_n$ и обозначим через $s_i$ ($1\leqslant i \leqslant n$) сумму
начальных $i$ элементов последовательности:
$$
s_i = a_1 + a_2 + ... a_i
$$
Согласно задаче 1.4 среди $n$ чисел $\{s_i\}$ можно выбрать либо одно число $s_k$ кратное $n$, либо два числа
$s_j$ и $s_k$ $(j \lt k)$, разность которых кратна $n$. В первом случае начальные $k$ членов последовательности являются искомыми. Во втором случае, ввиду $s_k-s_j =$ $a_{j+1}+a_{j+2}+...+a_k$, члены последовательности с номерами $(j+1)$ по $k$ являются искомыми.
2.5Доказать, что среди $n+1$ натуральных чисел, дающих различные остатки при делении на $2n+1$, либо найдется число кратное $2n+1$, либо найдутся два числа, сумма которых кратна $2n+1$.
Допустим, что среди данных $n+1$ натуральных чисел $а_1, а_2, а_{n+1}$ нет ни одного, кратного $2n+1$. Тогда остаются возможными $2n$ остатков ($1$,$2$...$2n$) при делении на $2n+1$.
Разобьем числа на $n$ групп по следующему правилу: в $i$-ю группу ($1\leqslant i \leqslant n$) попадают числа, дающие при делении на $2n+1$ остаток $i$ или остаток $(2n+1-i)$. Таким образом числа одной группы либо имеют одинаковые остатки при делении на $2n+1$, либо сумма их остатков равна $2n+1$.
Пусть $r$ — остаток от деления числа $a$ на $2n+1$. При этом $1\leqslant r \leqslant 2n$. Если $r \leqslant n$, то число $a$ попадает в $r$-ю группу, однако, поскольку $2n+1-r \geqslant n+1$, группы с номером ($2n+1-r$) не существует. Наоборот, если $r \geqslant n+1$, то группы с номером $r$ не существует, зато $1 \leqslant 2n+1-r \leqslant n$, поэтому $a$ попадает в ($2n+1-r$)-ю группу.
Из сказанного следует, что каждое из данных $n+1$ натуральных чисел попадает в одну и только одну из $n$ групп,
так что как минимум два числа окажутся в одной группе. Так как по условию числа дают разные остатки при делении на $2n+1$, то они могут попасть в одну группу только если сумма их остатков от деления на $2n+1$ равна $2n+1$. Это означает, что сумма чисел кратна $2n+1$.
В общем виде (применительно к четным и нечетным числам) утверждение можно сформулировать следующим образом:
среди $\left\lfloor\frac{n+2}{2}\right\rfloor$ (или $\left\lceil\frac{n+1}{2}\right\rceil$) натуральных чисел, дающих различные остатки при делении на $n$ найдется либо число, кратное $n$, либо два числа, сумма которых кратна $n$.
2.6Доказать, что существует натуральное число, которое делится на 2017 и оканчивается на 2018.
Рассмотрим 2018 чисел $\{a_i\}_{i=1}^{2018}$ вида
$$
a_i = \underbrace{\underbrace{2018}\underbrace{2018}...\underbrace{2018}}_{i\; \text{повторений числа 2018}}
$$
Среди этих чисел найдутся два числа $a_j$ и $a_k$ $(j \lt k)$, дающие одинаковые остатки при делении на 2017.
Таким образом, $a_k - a_j$ делится на 2017. Заметим, что
$$
a_k - a_j = \underbrace{20182018...2018}_{k-j\; \text{повторений}}\underbrace{0...0}_{4j\;\text{нулей}} = a_{k-j} \cdot 10^{4j}
$$
и поскольку числа 2017 и $10^{4j}$ — взаимно простые (2017 не делится ни на 2, ни на 5), число $a_{k-j}$ обязано делиться на 2017. Это число оканчивается на 2018.
2.7Доказать, что для любого натурального $n$ существует число, кратное $n$, состоящее из нулей и пятерок.
Решение очень похоже на предыдущее, поэтому советую подумать, прежде чем читать дальше.
Рассмотрим $n+1$ чисел $\{a_i\}_{i=1}^{n+1}$ вида
$$
a_i = \underbrace{5050...50}_{i\; \text{повторений числа 50}}
$$
среди которых найдутся два числа $a_j$ и $a_k$ $(j \lt k)$, дающие при делении на $n$ одинаковые остатки, следовательно их разность кратна $n$. Эта разность равна
$$
a_k - a_j = \underbrace{5050...50}_{k-j\; \text{повторений}}\underbrace{0...0}_{2j\;\text{нулей}},
$$
так что состоит из нулей и пятерок.
Заметим, что цифру 5 можно заменить любой другой цифрой, отличной от нуля.
2.8Доказать, что для любого простого $p \gt 5$ существует степень $p^n$ ($n$ — натуральное), оканчивающаяся на 0001.
Среди $10^4+1$ различных степеней числа $p$ найдутся две степени $p^i$ и $p^j$ $(i \lt j)$, разность которых $p^j-p^i=p^i(p^{j-i}-1)$ кратна $10^4$. Так как $p \gt 5$, то $p$ и $10$ — взаимно простые, следовательно $p^i$ и $10^4$ — взаимно простые. Отсюда следует, что $p^{j-i}-1$ делится на $10^4$, то есть $p^{j-i} = 10^4k + 1$. Такое число получается приписыванием справа 0001 к числу $k$.
Между прочим доказательство применимо также для $p=3$.
2.9Из 51 различных однозначных или двузначных чисел можно выбрать 6 чисел, никакие два из которых не содержат одинаковых цифр ни в одном разряде.
Будем группировать числа по количеству десятков: 0-я группа — однозначные числа, 1-я группа — числа от 10 по 19 ... 9-я группа — числа от 90 по 99. В полученных 10 группах найдется группа, содержащая не менее $\left\lceil\frac{51}{10}\right\rceil=6$ чисел. Пусть $i_1$ — номер такой группы, а $A_{i_1}$ — множество чисел этой группы. Таким образом $A_{i_1}$ содержит не менее 6, но не более 10 чисел.
Отбросим элементы $A_{i_1}$. Применив принцип Дирихле к оставшимся не менее $41$ числам, придем к выводу о существовании множества $A_{i_2}$ из не менее $\left\lceil\frac{41}{10}\right\rceil=5$ (но не более 10) чисел.
Повторяя данный процесс получаем следующее:
$$
\begin{array}
\;\; 51 & A_{i_1} & \geqslant 6\;\text{чисел} \\
\geqslant 41 & A_{i_2} & \geqslant 5\;\text{чисел}\\
\geqslant 31 & A_{i_3} & \geqslant 4\;\text{чисел}\\
\geqslant 21 & A_{i_4} & \geqslant 3\;\text{числа}\\
\geqslant 11 & A_{i_5} & \geqslant 2\;\text{числа}\\
\geqslant 1 & A_{i_6} & \geqslant 1\;\text{число}
\end{array}
$$
При этом все номера групп $i_k$ различны.
Число из $A_{i_6}$ обозначим через $a_1$.
$A_{i_5}$ содержит как минимум 2 числа, у которых совпадает количество десятков (равное $i_5$), следовательно отличается количество единиц. Поэтому в $A_{i_5}$ найдется число $a_2$, у которого количество единиц отличается от $a_1$. Так как $i_6 \neq i_5$, то $a_1$ и $a_2$ отличаются как количеством единиц, так и количеством десятков.
Так как $A_{i_4}$ содержит как минимум 3 числа, в нем найдется число $a_3$, у которого количество единиц не совпадает ни с $a_1$, ни с $a_2$. При этом количество десятков $a_3$ и предыдущих чисел последовательности также будет отличаться.
Продолжая указанный процесс, получаем 6 чисел $a_1, a_2,\dots a_6$, отличающихся между собой как количеством десятков, так и количеством единиц.
1.1 В учреждении работает 40 человек. Найдется месяц в году
в котором отмечают свой день рождения не менее четырех сотрудников?
Как известно в году всегда 12 месяцев. 12 месяцев и есть те полочки по которым раскладываем
40 сотрудников. Делим 40 на 12, получаем: $3\frac{1}{3}$, таким образом $\left\lceil\frac{40}{12}\right\rceil=4$. Ответ утвердительный. Между прочим, так как $\left\lfloor\frac{40}{12}\right\rfloor=3$, найдется также месяц, где день рождения отмечают не более 3х человек.
1.2 На заводе 45 цехов и 1000 работников.
Какое максимально возможное количество работников может быть в самом маленьком цеху?
Согласно второму утверждению принципа Дирихле, обязательно найдется цех, в котором работает не более чем $\left\lfloor\frac{1000}{45}\right\rfloor=\left\lfloor22\frac{2}{9}\right\rfloor=22$ человека. Цех из 22х человек будет минимальным, если, например, в 44х цехах работает 22 человека, а в оставшемся цеху $1000-22\cdot44=32$ человека. (Другой пример: 40 цехов по 22 человека и 5 цехов по 24 человека.) С другой стороны, если в минимальном цеху работает не менее 23х человек, то общее количество работников не менее $45\cdot23=1035$, что противоречит условию. Таким образом, ответ: 22 человека.
1.3 В ковре размером 4м×4м моль проела 15 дырок. Докажите, что из него можно вырезать коврик размером 1м×1м, не содержащий внутри себя дырок. (Дырки считать точечными.)
Источник: E.Ю.Иванова. «Олимпиадные задачи» МГУ Мехмат М 2008. Задача 19 (без решения)
Еще один пример на округление вниз. Разрезаем на 16 ковриков размером 1м×1м каждый. Дырки, находящиеся на линии разреза можно игнорировать, но даже если таких нет, найдется коврик, содержащий не более $\left\lfloor\frac{15}{16}\right\rfloor = 0$ дырок.
1.4Сколько карт надо вытянуть наугад из преферансной колоды,
чтобы среди них наверняка были:
а) две карты одной масти; б) две карты красной масти;
в) две карты одного достоинства; г) четыре карты одной масти;
д) два туза.
а) 4 карточных масти являются ящиками. Общее количество карт не имеет значения,
так как из 5 карт обязательно найдутся две карты одной масти.
б) Здесь ящиками являются цвета мастей: красный и черный. Имеется два таких ящика, следовательно
достаточно трех карт, чтобы две из них были одной масти.
б) Имеется 8 достоинств: числа: 7,8,9,10 и «картинки»: В,Д,К,Т. Таким образом достаточно 9 карт.
г) Следует найти наименьшее $x$, такое, что $\left\lceil\frac{x}{4}\right\rceil = 4$. Таким
числом является $13=4\cdot3+1$, поскольку $\left\lceil\frac{12}{4}\right\rceil = 3$. В общем случае наименьшее количество предметов, гарантирующих $k$ предметов в одном из $n$ ящиков равно $n(k-1)+1$.
д) В данном случае принцип Дирихле не работает, так как речь идет о конкретном достоинстве. Рассмотрим
наихудший вариант, когда все четыре туза окажутся в конце колоды. Тогда придется перебрать 30 карт,
чтобы получить, наконец, заветные тузы.
1.5На окружности отмечены дуги, сумма длин которых меньше половины длины окружности. Докажите, что существует диаметр окружности, оба конца которого не принадлежат ни одной из дуг.
Присоединим к отмеченным дугам дуги, симметричные им относительно центра окружности. Получим множество дуг, симметричное относительно центра окружности, общая длина которых в два раза больше общей длины исходных дуг, а следовательно меньше длины окружности. Согласно принципу Дирихле в «непрерывной» формулировке, на окружности найдется точка $P_1$, не принадлежащая ни одной из дуг. В силу симметричности множества дуг, точка $P_2$, симметричная точке $P_1$ относительно центра окружности, также не принадлежит ни одной из дуг. Таким образом, $P_1P_2$ — искомый диаметр окружности.
1.6В квадрате $ABCD$, длина стороны которого равна 1, расположены окружности, сумма радиусов которых равна 0,6. Докажите, что существует прямая, параллельная стороне $AB$, содержащая точки как минимум двух окружностей.
Спроецируем окружности на сторону $AD$. Проекция каждой из окружностей является отрезком, длиной равной диаметру окружности. Поскольку сумма радиусов окружностей равна 0,6, сумма их диаметров, а следовательно сумма длин отрезков равна 1,2, что больше длины стороны $AD$, равной 1. Таким образом, согласно принципу Дирихле, на стороне $AD$ найдется точка $P$, принадлежащая как минимум двум отрезкам $s_1$ и $s_2$. Пусть $O_1$ и $O_2$ — окружности, проецирующиеся в отрезки $s_1$ и $s_2$. Каждая из этих окружностей, содержит точки (одну или две), проецирующиеся в точку $P$. Через точку $P$ проведем прямую, параллельную $AB$. Эта прямая перпендикулярна $AD$, следовательно содержит все точки, проецирующиеся в точку $P$. В частности она содержит точки окружностей $O_1$ и $O_2$.
1.7Для всякого ли натурального числа $n$ существуют две различные степени
$n^{k_1}$, $n^{k_2}$ у которых совпадают:
а) последняя цифра;
б) две последние цифры;
в) три последние цифры?
Очевидно, если выполнено в), то выполнено также а) и б), поэтому достаточно доказать совпадение трех последних цифр.
Для этого заметим, что число, составленное последними тремя цифрами есть остаток от деления на 1000. Поскольку при делении на 1000 возможны 1000 различных остатков, среди 1001 различных степеней числа $n$, найдутся два числа, дающие одинаковые остатки при делении на 1000. У этих чисел последние три цифры совпадают.
1.8Какое наименьшее количество из первых 555 натуральных чисел следует выбрать случайным образом, чтобы среди них обязательно нашлись:
а) число оканчивающееся нулем;
б) два четных числа;
в) три с совпадающей последней цифрой;
г) четыре с совпадающим остатком от деления на 7;
д) пять с совпадающей суммой цифр.
а) В каждой из 4х полных сотен есть 10 чисел оканчивающихся нулем (10а+10, 10a+20 ... 10a+100). Остается неполная сотня содержащая 5 чисел с нулем в конце: 510, 520 ... 550. Таким образом имеется 45 чисел, оканчивающихся нулем, и если перемешать все 555 чисел случайным образом, то в худшем случае требуемые 45 чисел окажутся в конце, так что придется выбрать $500-45+1=446$ чисел.
б) Среди первых 555 натуральных чисел есть 277 четных и 278 нечетных. При этом можно перебрать все нечетные числа и лишь потом попадутся 2 четных. Стало быть, чтобы действовать наверняка, надо выбрать 280 чисел и ничуть ни меньше. Еще один пример неоправданного соблазна применения принципа Дирихле.
в) Учитывая опыт предыдущих задач, достаточно лишь сверить ответ: $2\cdot10+1=21$
г) И здесь применим принцип Дирихле. Ответ: $3\cdot7+1=22$
д) Среди натуральных чисел, не бо́льших 555, наименьшую сумму цифр, равную 1 имеет число 1, тогда как наибольшей суммой цифр, равной 22, обладает число 499. Таким образом получаем 22 возможных сумм цифр, что на первый взгляд дает $4\cdot22+1=89$ чисел.
На самом деле, некоторые суммы цифр встречаются менее 5 раз, так что если они попадутся при выборе, это лишь удлинит поиск. Выпишем эти суммы:
Сумма цифр
Соответствующие числа
Количество
1
1 10 100
3
21
399 489 498
3
22
499
1
Таким образом, получаем 3 «лишних» суммы цифр, соответствующих 7 «лишним» числам, выбор которых заведомо идет мимо цели. По закону бутерброда, все эти 7 чисел могут оказаться среди выбранных. Остается $22-3=19$ «порядочных» сумм, так что требуется еще $4\cdot19+1=77$ чисел, что вместе с «лишними» дает $84$ числа.
К возможному сюрпризу некоторых читателей, результат оказался меньше, чем первоначальное значение. В действительности, здесь нет никакого сюрприза: рассматривая некоторые суммы цифр в отдельности, мы уменьшаем количество оставшихся сумм, что с лихвой компенсирует наличие «лишних» чисел.
А если пойти дальше? Тогда, поиск, возможно удастся сделать еще короче. Сумму цифр 2 дают пять чисел: 2, 11, 101, 110, 200. Предположим, что только 4 из них появились вначале, а последнее, как назло, никак не появится. Вместе с предыдущими суммами получаем 7+4=11 «лишних» чисел и 18 оставшихся «порядочных» сумм, что дает $4\cdot18+1+11=84$ пробы, ровно столько же, сколько и раньше.
Следующая попытка: сумму цифр 20 дает 6 чисел: 299, 389, 398, 479, 488, 497. Снова предположим, что только 4 из них появились, так что 11+4=15 «лишних» чисел и 17 оставшихся «порядочных» сумм дает ... $4\cdot17+1+15=84$!
Какой-то заколдованный круг ... хотя ... конечно, увеличивая на 4 количество «лишних» чисел,
мы уменьшаем на единицу количество «порядочных» сумм, а это есть ничто иное, как множитель числа 4. Теперь понятно, что меньше 84 никак не получится.
В этой публикации речь пойдет о так называемом Принципе Дирихле суть которого понятна первокласснику: «Если в книжном шкафу 4 полки, то, разместив в нем 3 книги, мы получим как минимум одну свободную полку (свободных полок будет больше, если несколько книг расположить на одной полке), а если положить туда 5 книг, то как минимум на одной полке окажутся две книги.» А если в шкафу 30 книг? Могу вас заверить, что как минимум на одной полке находится не менее 8 книг, а на какой-нибудь другой полке лежит не более 7 книг. Впрочем, немного поразмыслив, вы сами придете к такому же выводу.
Конечно, это факт был подмечен еше в древности, тогда как название он получил в честь немецкого математика (несмотря на французскую фамилию) Лежёна-Дирихле́ (во французском произношении Диришле́: Johann Peter Gustav Lejeune-Dirichlet), использовавшего этот простой принцип для доказательства такой далеко не простой вещи, как теоремы о приближениях, о которой пойдет речь ниже.
В данной публикации натуральными считаются целые положительные числа, но не ноль!
Между прочим, термин «Принцип Дирихле» в данном контексте распространен пожалуй только в русскоязычной литературе. Правильнее говорить «Принцип яшиков» или «Принцип по́лок» (нем. Schubfachprinzip), как называл его сам Дирихле, или, в качестве компромисса, «Принцип ящиков Дирихле». Практичные англичане используют термин «Принцип голубиных клеток» (Pigeonhole Principle), однако предлагаю не мучать свободолюбивых голубей. Что касается «настоящего» Принципа Дирихле, то это совершенно другой факт, относящийся к уравнениям математической физики, который гораздо менее интуитивен.
Формулировка и доказательство принципа Дирихле
Принцип Дирихле является настолько интуитивным, что многие его считают аксиомой. Между тем, этот факт довольно легко доказывается.
В общем виде принцип Дирихле можно сформулировать следующим образом:
Утверждение 1. Если $n$ предметов разместить в $k$ ящиках ($k \gt 0$), то найдется ящик, содержащий не менее $\dfrac{n}{k}$ предметов, а также ящик содержащий не более $\dfrac{n}{k}$ предметов.
Как видите, здесь фактически содержится два утверждения, однако в каждом конкретном случае используется то, что подходит,
чаще всего первое утверждение.
Доказательство принципа Дирихле. Пусть $a_i$ — количество предметов в $i$-м ящике. Если первое утверждение неверно, то
$$
a_i \lt \frac{n}{k}\qquad i=1,2...k
$$
Суммируя по всем $i$, получаем
$$
a_1 + a_2 + ... + a_k \lt k \cdot \frac{n}{k}.
$$
Заметив, что левая часть неравенства есть не что иное, как общее количество предметов $n$, получаем $n \lt n$,
что конечно неверно. Получили противоречие, которое доказывает первое утверждение. Второе утверждение доказывается совершенно
аналогично, надо только заменить знаки < знаками >.
Учитывая, что $\frac{n}{k}$ — есть средне-арифметическое количества предметов в ящике, принцип Дирихле можно переформулировать так:
Утверждение 2. В непустом множестве ящиков найдется как ящик, содержащий не менее средне-арифметического, так и ящик, содержащий не более средне-арифметического количества предметов в ящике.
Обратимся к примерам в начале. Согласно второму утверждению, в случае трех книг на четырех полках найдется полка, содержащая не
более $\frac{3}{4}$ книги. Поскольку резать книги мы явно не собираемся, на полке должно быть целое количество книг. Так как это количество не более $\frac{3}{4}$ оно обязано быть нулем, то есть полка должна быть свободной. Заметим, что число $0$ получено округлением числа $\frac{3}{4}$ вниз. Если книг 5, согласно первому утверждению, существует полка, содержащая не менее $\frac{5}{4}$ или $1\frac{1}{4}$ книги, так что на этой полке должно быть не менее 2-х книг. Как видим, в случае применения первого утверждения найденное количество следует округлять вверх, а при использовании второго утверждения количество округляется вниз.
Приведенное выше правило округления удобно записывать с помощью функций, введенных в 1960-х годах автором популярных книг по программированию Кеннетом Айверсоном (Kenneth Iverson), которые благополучно проникли в математику, где широко используются. Подробно эти функции (как и многое другое) рассматриваются
в «О целом дроби и о дроби в целом». Здесь я ограничусь их определением:
Функция «пол» (floor) (именуемая также «целая часть») — наибольшее целое число, не превосходящее данное. Обозначается нижними квадратными скобками: $\lfloor x \rfloor$.
Функция «потолок» (ceil или ceiling) — наименьшее целое число, не меньшее данного. Обозначается верхними квадратными скобками: $\lceil x \rceil$.
Легко заметить, что $x-1 \lt \lfloor x \rfloor \leqslant x \leqslant \lceil x \rceil \lt x+1 $, причем
равенства имеют место тогда и только тогда, когда $x$ — целое число.
Теперь понятно, как внедрить в формулировку принципа Дирихле правила округления:
Утверждение 3. Если $n$ предметов разместить в $k$ ящиках ($k \gt 0$), то найдется ящик, содержащий не менее $\left\lceil \dfrac{n}{k} \right \rceil$ предметов, а также ящик содержащий не более $\left\lfloor \dfrac{n}{k} \right\rfloor$ предметов.
Например, в случае 30 книг на 4-х полках получаем: $\frac{30}{4} = 7\frac{1}{2}$, при этом $\left\lceil \frac{30}{4} \right\rceil = 8$, $\left\lfloor \frac{30}{4} \right\rfloor = 7$. В соответствии с принципом Дирихле, найдется полка содержащая не менее 8 книг, а также полка, содержащая не более 7 книг.
Заметим, наконец, что первая часть утверждения 3 справедлива, если предметов больше $n$, так как лишние предметы можно просто проигнорировать. Точно так же, если количество предметов меньше $n$, можно добавить недостающие предметы, затем, воспользовавшись второй частью утверждения 3, удалить из найденного ящика добавленные предметы (если такие найдутся). Таким образом приходим к следующим двум утверждениям:
Утверждение 4а. Если в $k$ ящиках ($k \gt 0$) разместить не менее $n$ предметов, найдется ящик, содержащий не менее $\left\lceil \dfrac{n}{k} \right\rceil$ предметов
Утверждение 4b. Если в $k$ ящиках ($k \gt 0$) разместить не более $n$ предметов, найдется ящик, содержащий не более $\left\lfloor \dfrac{n}{k} \right\rfloor$ предметов
Просто и невероятно!
Вот некоторые результаты, вытекающие непосредственно из принципа Дирихле.
В городе с полумилионным населением найдутся 195 людей, рост которых одинаков с точностью до миллиметра.
Не верите? Проконсультируемся в Интернете. Нормальный рост новорожденного 45-55см, если верить этому сайту, хотя в другом сайте идет речь о новорожденном ребенке ростом 9,8 дюйма или 249мм. Упоминаются другие новорожденные, некоторые меньшего веса, рост которых, к сожалению, не указан. Возьмем 230мм чтобы наверняка не ошибиться. Самый высокий человек в мире Роберт Першинг Уодлоу (22.02.1918-15.07.1940) имел рост 8 футов 11.1 дюймов, что соответствует 2720мм. Возьмем 2800мм, на случай если этот рекорд когда-нибудь будет побит. Таким образом получаем 2800-230+1=2571 групп, в каждой из которых рост одинаков с точностью до миллиметра. Осталось заметить, что 500000:2571 > 194, хотя убежден, что для любого реального города с не менее полумилионным населением эта цифра больше 200.
На XIX-м Всемирном фестивале молодежи и студентов в Сочи день рождения совпал не менее чем у 55 делегатов.
С этим вы справитесь без посторонней помощи, если упомянуть, что в году не более 366 дней, а на фестивале, согласно Википедии, было более 20 тысяч участников.
На любой премьере в Большом театре присутствует не менее трех зрителей, имена и фамилии которых начинаются с одинаковых букв.
Согласно агенству по продаже билетов,
основная сцена Большого театра (а именно там проходят премьеры) вмещает около 2500 зрителей. Неизвестно, что скрывается за этим «около», однако во всяком случае мест должно быть не менее 2200, иначе будет выглядеть слишком большим преувеличением. Представить себе свободные места во время премьеры в Большом театре практически невозможно, максимум 100 зрителей могут не объявиться в результате форс-мажорных обстоятельств, таким образом присутствие 2100 зрителей можно считать гарантированным. Остается подсчитать количество инициалов из имени и фамилии. Начать фамилию или имя с Ь или Ъ невозможно теоретически: обе эти буквы употребляются после согласной. Буква Ѣ, к моему сожалению, давно вышла из употребления в официальной Российской грамматике, причем, будучи выше и стройнее всех, она предпочитала украшать слово в середине, а не в начале, тогда как в иностранных фамилиях вряд ли могла появиться даже в середине. Тем не менее, в качестве утешения, добавлю ее в алфавит, пусть радует глаз хотя бы виртуально! Буква Ё, официально появилась в алфавите лишь чуть более трех четвертей века назад, и многие до сих пор не воспринимают её всерьез, однако в начале фамилий, и не только русских, она появляется, так что игнорировать было бы кощунством. Таким образом в каждой из двух позиций присутствует одна из 32 букв, что дает 322=1024 всевозможных инициалов, так что ожидаемое количество зрителей, несмотря на очень осторожные оценки, все-таки более чем в 2 раза превышает количество инициалов.
А теперь быстро ответьте на следующие вопросы:
Сколько костей домино надо вынуть, чтобы у двух костей одна цифра совпала?
Всего семь возможных цифр, значит следует вынуть 8 костей...
Хотя нет, ведь каждая кость содержит две цифры...
Опять нет! Ведь есть дубли и по закону бутерброда именно они могут выпасть. Итак, в худшем случае достаем
0-0, 1-1, 2-2, 3-3, 4-4, 5-5, 6-6 и лишь только на 8-й попытке получаем желанное повторение.
Ради интереса, поставим вопрос по-другому: требуется вынуть две одинаковые цифры либо на одной кости, либо на разных. В таком случае дубль сразу дает требуемую пару, поэтому будем, наоборот, считать, что дубли не появляются. Таким образом первая кость дает две разные цифры, вторая кость не должна повторять ни одну из них, третья кость не повторяет ни одну из предыдущих. В результате получаем 6 различных цифр, так что четвертая кость обязательно даст повторение
Из 25 шаров трех цветов какое минимальное количество шаров одинакового цвета гарантировано?
Девять? Все правильно. Разложим шары в три ящика то цветам, при этом найдется ящик, содержащий не менее $\left\lceil\dfrac{25}{3}\right\rceil = 9$ шаров.
Верно ли, что среди любых трех чисел можно найти два, сумма которых четна?
Верно! Четность играет роль пресловутых ящиков, и таких ящиков 2. Поэтому из трех
чисел найдутся как минимум два, имеющие одинаковую четность, так что их сумма четна. Интересные факты и задачи
на тему четности читайте в Чет или нечет.
В ящике содержится 5 красных, 5 белых и 5 зеленых шаров. Какое минимальное количество шаров надо вынуть, чтобы среди них было 2 зеленых?
Четыре? Если отвечать быстро, то благодаря инерции мышления можно действительно так ответить. А если
подумать? Ведь согласно все тому же закону бутерброда можно вынуть сначала 5 красных, потом 5 белых и лишь потом, когда других
шаров уже не останется, вынуть долгожданные два зеленых шара, доводя общее количество вынутых шаров до 12. Так почему же принцип Дирихле не применим в этот раз? Потому что речь идет не просто об одинаковом цвете (тогда четырех шаров действительно достаточно), а о конкретном цвете. Итак, будьте осторожны, поскольку возможность применения принципа Дирихле может быть только кажущейся.
В обобщенном виде
В более общем (но не столь изящном) виде принцип Дирихле можно сформулировать следующим образом:
Утверждение 5a. Пусть $q_1$, $q_2$ … $q_n$ — натуральные числа. Если $q_1+q_2+...+q_n−n+1$ (или большее количество) предметов поместить в $n$ ящиков, найдется некоторый $k$-й ящик, содержащий не менее $q_k$ предметов.
Если утверждение неверно, так что, для любого $k$, в $k$-м ящике содержится не более $q_k-1$ предметов, то общее количество предметов не превышает $(q_1-1)+(q_2-1)+$ … $+(q_n-1)$ $=$ $q_1+q_2+$ … $+q_n-n$, что противоречит условию.
Утверждение 5b. Пусть $q_1$, $q_2$ … $q_n$ — натуральные числа. Если $q_1+q_2+...+q_n+n-1$ (или меньшее количество) предметов поместить в $n$ ящиков, найдется некоторый $k$-й ящик, содержащий не более $q_k$ предметов.
Доказывается аналогично предыдущему утверждению.
В непрерывном обличье
Приведенная выше формулировка принципа Дирихле является дискретной, так как она предполагает существование ящиков,то есть определенных групп,содержащих конечное количество элементов. Приведем пример случая, когда ящиков совсем не видно, но тем не менее речь идет именно о принципе Дирихле.
Утверждение 6. Пусть $P$ — множество (открытых) интервалов общей длиной $a$, каждый из которых расположен внутри отрезка $S$ длины $b$. (В частности какие-то концы некоторых интервалов из $P$ могут совпадать с концом отрезка $S$.) Тогда на отрезке $S$ найдется точка, принадлежащая не менее $\left\lceil\dfrac{a}{b}\right\rceil$ интервалам из $P$, а также точка, принадлежащая не более $\left\lfloor\dfrac{a}{b}\right\rfloor$ интервалам из $P$.
Напомним, что концы (открытого) интервала не принадлежат интервалу. Приведенный чертеж показывает пять интервалов, каждый длиной в единицу, расположенные внутри отрезка длиной 5. В этом случае $а=b=5$, следовательно $\left\lceil\dfrac{a}{b}\right\rceil=1$ как можно видеть, нет точек, принадлежащих нескольким интервалам одновременно. Однако стоит увеличить какой-нибудь интервал даже на очень малую величину (но так, чтобы он по-прежнему находился внутри отрезка длиной 5), как этот отрезок пересечется с другим интервалом, так что у этих интервалов найдутся общие точки. При этом $a \gt b$,
так что $\left\lceil\dfrac{a}{b}\right\rceil \geqslant 2$
Для доказательства рассмотрим множество $P$ интервалов $(p_i, q_i)$ с суммой длин $a$, расположенных внутри отрезка $S$ длиной $b$. Каждой точке отрезка можно поставить в соответствие величину, которую назовем кратностью: количество интервалов из $P$, содержащих данную точку.
Рассмотрим подинтервалы между соседними концами интервалов множества $P$. На приведенном рисунке подинтервалами являются промежутки $(0, p_1)$, $(p_1, p_2)$, $(p_2, q_1)$, $(q_1, p_3)$, $(p_3, q_2)$ и т.д. Все точки внутри каждого подинтервала имеют одинаковую кратность, которую назовем кратностью подинтервала. Так, на приведенном рисунке точки подинтервала $(0, p_1)$ не принадлежат ни одному интервалу из $P$, точки подинтервала $(p_1, p_2)$ принадлежат только интервалу $(p_1, q_1)$, точки подинтервала $(p_2, q_1)$ принадлежат как интервалу $(p_1, q_1)$, так и интервалу $(p_2, q_2)$, следовательно кратности подинтервалов $(0, p_1)$, $(p_1, p_2)$ и $(p_2, q_1)$ равны 0, 1 и 2 соответственно.
Понятно, что общая длина всех подинтервалов равна длине отрезка $S$, то есть $b$; в то же время, если длину каждого подинтервала считать столько раз, какова ее кратность, получим общую длину исходных интервалов из $P$, то есть $a$. Другими словами, если $l_i$ и $k_i$ — соответственно длина и кратность $i$-го «подинтервала», а $n$ – количество подинтервалов, то
$$
l_1 + l_2 + ... + l_n = b \\
k_1 l_1 + k_2 l_2 + ... + k_n l_n = a
$$
Предположим первая часть доказываемого утверждения неверна. Это значит, что $k_i \lt \dfrac{a}{b}$ для всех $i=1,2...n$. В таком случае
$$
k_1 l_1 + k_2 l_2 + ... + k_n l_n \lt \frac{a}{b} (l_1 + l_2 + ... + l_n),
$$
откуда, учитывая первое равенство, получаем
$$
k_1 l_1 + k_2 l_2 + ... + k_n l_n \lt a,
$$
что противоречит второму равенству.
Для доказательства второй части утверждения надо заменить всюду знак < знаком >.
Для тех, кого смущает то, что в утверждении фигурируют интервалы, а не отрезки, замечу, что его можно переформулировать «в терминах отрезков», поскольку отрезок — это «всего лишь» замыкание интервала:
Утверждение 7. Пусть $P$ — множество отрезков общей длиной $a$, каждый из которых не выходит за пределы отрезка $S$ длины $b$. (В частности какие-то концы некоторых отрезков из $P$ могут совпасть с концом отрезка $S$.) Тогда на отрезке $S$ найдется точка, лежащая внутри не менее $\left\lceil\dfrac{a}{b}\right\rceil$ отрезков из $P$ а также точка, лежащая внутри не более $\left\lfloor\dfrac{a}{b}\right\rfloor$ отрезков из $P$.
Наконец, аналогично дискретному случаю, точную сумму длин можно заменить ограничениями сверху и снизу:
Утверждение 8а. Пусть $P$ — множество отрезков общей длиной не менее $a$, каждый из которых не выходит за пределы отрезка $S$ длины $b$. Тогда на отрезке $S$ найдется точка, лежащая внутри не менее $\left\lceil\dfrac{a}{b}\right\rceil$ отрезков из $P$.
Утверждение 8b. Пусть $P$ — множество отрезков общей длиной не более $a$, каждый из которых не выходит за пределы отрезка $S$ длины $b$. Тогда на отрезке $S$ найдется точка, лежащая внутри не более $\left\lfloor\dfrac{a}{b}\right\rfloor$ отрезков из $P$.
Наконец, заметим, что приведенную выше одномерную формулировку принципа Дирихле можно перенести на любое количество измерений. В частности для плоскости утверждение формулируется следующим образом:
Утверждение 9. Пусть $P$ — множество геометрических фигур общей площадью $a$, каждая из которых расположена внутри фигуры $S$ площадью $b$. (В частности контуры некоторых фигур из $P$ могут иметь общие точки с контурам фигуры $S$.) Тогда фигура $S$ содержит точку, расположенную внутри не менее $\left\lceil\dfrac{a}{b}\right\rceil$ фигур из $P$, а также точку, расположенную внутри не более $\left\lfloor\dfrac{a}{b}\right\rfloor$ фигур из $P$.
Приложения принципа Дирихле
В этой части обсуждаются несколько важных приложений принципа Дирихле. Если кое-что из этого покажется кому-то слишком скучным, можете это пропустить без ущерба для понимания всего остального.
Приближения вещественных чисел
Для любого вещественного $\alpha$ и натурального $n$ существует целое число $p$ и натуральный множитель $q$, не превосходящий $n$ (т.е. $1 \leqslant q \leqslant n$), такие что
$$
|q\alpha - p| \lt \frac{1}{n} \label{eq:D1}\tag{D1}
$$
Другими словами, сколь бы ни было большим целое число $n$, для всякого действительного числа $\alpha$ (как рационального, так и иррационального) можно подобрать некоторый натуральный множитель, не превосходящий $n$, так что разность между $q\alpha$ и ближайшим целым числом меньше чем $\frac{1}{n}$.
Это и есть та самая Теорема Дирихле о приближениях, для которой принцип Дирихле был впервые сформулирован и применен.
В настоящее время найдены различные способы доказательства этой теоремы, однако метод, изложенный ниже, остается самым простым.
Для каждого целого $k$ от $0$ до $n$ включительно, обозначим через $a_k$ дробную часть от $k\alpha$. Дробная часть образуется вычитанием из числа его целой части (функции «пол», согласно терминологии Айверсона):
$$
a_k = k\alpha - \lfloor k\alpha \rfloor \quad k=0,1,2...n \label{eq:D2}\tag{D2}
$$
Непосредственно из определения целой части следует, что дробная часть положительна и меньше 1, таким образом есть все $a_k$ лежат в полуинтервале $[0,1)$.
Разобьем этот полуинтервал на $n$ одинаковых полуинтервалов $\left[\dfrac{r}{n}, \dfrac{r+1}{n}\right)$,
где $r=0,1...n-1$. Поскольку количество полуинтервалов равно $n$, а количество $a_k$ равно $n+1$, то согласно ... да, именно ему! ...
два числа $a_i$ и $a_j$ ($i \gt j$) окажутся в одном полуинтервале. Таким образом,
$$
|a_i-a_j| \lt \frac{1}{n}
$$
Подставляя сюда выражения для $a_i$ и $a_j$ из $\eqref{eq:D2}$, получаем:
$$
|(i\alpha - \lfloor i\alpha \rfloor) - (j\alpha - \lfloor j\alpha \rfloor)| \lt \frac{1}{n}
$$
или
$$
|(i-j)\alpha-(\lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor)| \lt \frac{1}{n}.
$$
Полагая $q=i-j$, $p=\lfloor i\alpha \rfloor - \lfloor j\alpha \rfloor$, и заметив, что
из $0\leqslant j \lt i \leqslant n$ следует $0 \lt q=i-j \leqslant n$, получаем утверждение теоремы.
Обратимся к одному существенному следствию из доказанной теоремы. Для вещественного $\alpha$, и натурального $q$
обозначим через $p$ — целое число, ближайшее к $\lfloor q\alpha \rfloor$. Тогда $|q\alpha - p| \leqslant \dfrac{1}{2}$, или
$$
\left|\alpha - \dfrac{p}{q}\right| \leqslant \dfrac{1}{2q},
$$
что можно также записать, как
$$
\left|\alpha - \dfrac{p}{q}\right| \leqslant \frac{1}{q^{t}},\quad \text{где}\;t=1+\frac{1}{\log_2{q}} \label{eq:D3}\tag{D3}
$$
.
Как видим, чем больше $q$, тем ближе показатель степени $t$ к единице, Правда, если неравенство $\eqref{eq:D3}$ является строгим, показатель степени можно увеличить. Насколько существенно такое увеличение? Оказывается, для бесконечного множества значений $q$ показатель степени можно сделать равным 2.
Для любого вещественного $\alpha$ и любого натурального $k$ существует бесконечное множество рациональных чисел $\dfrac{p}{q}$, таких что
$$
\left|\alpha - \frac{p}{q}\right| \lt \frac{1}{q^2} \label{eq:D4}\tag{D4}
$$
Докажем от противного. Допустим, что существует конечное множество $M$ дробей $\dfrac{p}{q}$, удовлетворяющих условию $\eqref{eq:D4}$.
Выберем $n$ настолько больши́м, что
$$
\frac{1}{n} \lt |q\alpha - p| \label{eq:D5}\tag{D5}
$$
для всех $\dfrac{p}{q} \in M$. Согласно доказанной теореме, существуют целые числа $u$ и $v$ ($1 \leqslant v \leqslant n$), такие, что
$$
|v\alpha - u| \lt \frac{1}{n} \label{eq:D6}\tag{D6}
$$
Разделив полученное неравенство на $v$ и учитывая, что $n \geqslant v$, получаем:
$$
\left|\alpha - \frac{u}{v}\right| \lt \frac{1}{nv} \leqslant \frac{1}{v^2}
$$
Таким образом, дробь $\dfrac{u}{v}$ удовлетворяет неравенству $\eqref{eq:D4}$. С другой стороны, из $\eqref{eq:D5}$ и $\eqref{eq:D6}$
следует, что $|v\alpha - u| \lt |q\alpha - p|$ для всех $\dfrac{p}{q}\in M$, поэтому $\dfrac{u}{v} \notin M$. Поскольку по предположению множество $M$ содержит все $\dfrac{p}{q}$, удовлетворяющие $\eqref{eq:D4}$, получили противоречие. Утверждение доказано.
Как было доказано французским математиком Эмилем Борелем (Émile Borel), оценку $\eqref{eq:D4}$ можно улучшить:
Теорема Бореля Для любого вещественного $\alpha$ и любого натурального $k$ существует бесконечное множество рациональных чисел $\dfrac{p}{q}$, таких что
$$
\left|\alpha - \frac{p}{q}\right| \lt \frac{1}{\sqrt{5}q^2}, \label{eq:D7}\tag{D7}
$$
причем было доказано, что оценку $\eqref{eq:D7}$ в общем случае нельзя улучшить. Доказательство теоремы Бореля мы опускаем.
Публикация Рациональные зерна иррациональности, посвященная иррациональным числам, содержит
главу, демонстрирующую применение теоремы Дирихле о приближениях к доказательству
иррациональности $\sqrt{n}$ для целого числа, не являющегося полным квадратом.
Числа Рамсея.
Примечательность чисел, названных именем британского математика Ф.Рамсея (Frank Plumpton Ramsey 1903-1930), состоит в том, что, возникнув сравнительно недавно, определение таких чисел тем не менее вполне понятно не только специалистам.
Начало этому положил следующий факт: «в любой группе из 6 человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых».
В самом деле, пусть $A$ один из членов группы. Оставшиеся 5 человек можно разделить на две подгруппы: с которыми $A$ знаком и с которыми $A$ не знаком. Согласно принципу Дирихле, в одной из подгрупп найдется не менее 3х человек. Таким образом, возможны два случая: а) $A$ знаком как минимум с тремя остальными; б) $A$ не знаком как минимум с тремя остальными;
Рассмотрим случай а). При этом $А$ знаком с тремя людьми $B_1$, $B_2$, $B_3$. Если какие-то из них, например $B_1$ и $B_2$ знакомы друг с другом, то $A$, $B_1$ и $B_2$ — тройка попарно знакомых. Если никто из $B_i$ не знаком друг с другом, то $B_1$, $B_2$ и $B_3$ — тройка попарно незнакомых. Случай б) симметричен случаю а): надо в рассуждениях заменить знакомства «незнакомствами» и наоборот.
Поставим вопрос в общем случае: какое наименьшее количество людей следует взять, чтобы среди них нашлось либо $m$ попарно знакомых, либо $n$ попарно незнакомых. Это число обозначается через $R(m,n)$ и называется числом Рамсея, а различные факты, связанные с числами Рамсея объединены в теорию Рамсея.
На самом деле числа Рамсея определяются на языке теории графов (немного о графах
в «Друг моего друга мне не друг» и во множестве других источников online), где знакомства/незнакомства соответствуют раскраске ребер полного графа в разные цвета. Такой подход позволяет определить числа Рамсея также для трех и более аргументов, в соответствии с количеством цветов, используемых для раскраски.
Как следует из определения, доказательство того, что $R(m,n)=A$ состоит из двух частей:
доказать, что $R(m,n) \leqslant A$, то есть для любой группы из $A$ человек найдется либо $m$ попарно знакомых, либо $n$ попарно незнакомых;
доказать, что $A$ является наименьшим из таких чисел, что равносильно $R(m,n) \geqslant A$. Понятно, что для этого достаточно найти группу из $A-1$ человек, не удовлетворяющую вышеуказанным требованиям («по научному» граф Рамсея), однако, как ни парадоксально, именно эта часть оказывается наиболее сложной, неподвластной даже «субсветовому» многоядерному компьютерному процессору. К счастью, при решении задач в доказательстве минимальности зачастую нет необходимости.
Например, доказанный ранее факт о группе из 6 человек равносилен $R(3,3) \leqslant 6$. Для доказательства
минимальности числа 6 надо указать группу из из 5 человек, где нет ни трех попарно знакомых, ни трех попарно незнакомых. Такая группа приведена на чертеже справа, где красными линиями соединены знакомые, а синими линиями соединены незнакомые.
Отметим следующие свойства чисел Рамсея:
a) R(m,n)=R(n,m)
Возьмем группу из $R(n, m)$ человек, в которой превратим всех знакомых в незнакомых и наоборот. При этом $n$ попарно знакомых (если такие существуют) превратятся в $n$ попарно незнакомых, а $m$ попарно незнакомых (которые обязаны быть, если не существуют $n$ попарно знакомых) превратятся в $m$ попарно знакомых. Тем самым доказано $R(m,n) \leqslant R(n, m)$. Для доказательства $R(m, n) \geqslant R(n, m)$ берем группу из $R(n, m)-1$ человек и доказываем от противного,
используя ранее испробованное перевоплощение знакомых в незнакомых и наоборот.
b) R(2, n) = R(n,2) = n
В группе из $n$ человек либо есть двое знакомых, либо все $n$ попарно незнакомы. С другой стороны,
если в группе из $n-1$ человек не окажется знакомых, то в ней не может быть $n$ попарно незнакомых,
поскольку такого количества нет в наличии.
В некоторых публикациях минимальным значением аргумента считается единица, причем $R(1,n)=R(n,1)=1$.
Здесь всюду предполагается, что $m \geqslant 2$ и $n\geqslant 2$.
Кульминацией теории Рамсея является следующее утверждение:
Лемма Рамсея. Если $m \geqslant 3$ и $ n \geqslant 3$, то
$R(m,n) \leqslant R(m-1,n) + R(m,n-1)$
Доказательство напоминает, то что использовалась в случае 6 человек. Рассмотрим группу из $R(m-1,n) + R(m,n-1)$ человек и покажем, что в ней есть либо $m$ попарно знакомых, либо $n$ попарно незнакомых.
Пусть $А$ один из членов группы. Обозначим через $r$ и $s$ количество людей, знакомых и незнакомых с $A$ соответственно. Тогда сумма $r+s$ равна количеству человек, кроме $A$:
$$
r+s = R(m-1,n) + R(m,n-1)-1
$$
Согласно обобщенному принципу Дирихле (утверждение 5а), одно из нижеследующих неравенств должно иметь место:
$$
r \geqslant R(m-1,n) \label{eq:R1}\tag{R1}
$$
$$
s \geqslant R(m,n-1) \label{eq:R2}\tag{R2}
$$
Пусть $\eqref{eq:R1}$ имеет место и $P$ — множество людей знакомых с $A$. Тогда в этом множестве не менее
$R(m-1,n)$ человек, и согласно определению чисел Рамсея, возможно одно из двух:
в $P$ существует $m-1$ попарно знакомых, которые вместе с $A$ образуют $m$ попарно знакомых, что удовлетворяет определению $R(m,n)$;
в $P$ существует $n$ попарно незнакомых, что также удовлетворяет определению $R(m,n)$.
Случай, когда имеет место $\eqref{eq:R2}$, симметричен рассмотренному.
В частности, получаем: $R(3,3) \leqslant R(2,3) + R(3,2)$, то есть $R(3,3) \leqslant 6$ — результат, который нам уже знаком.
Следствие: $R(m.n) \leqslant C_{m+n-2}^{m-1}$, где $C_n^k$ – многим хорошо знакомое количество сочетаний, известное также как биномиальный коэффициент.
Докажем индукцией по $m+n$. Наименьшее возможное значение $m+n$, равное 4 может иметь место только при $m=n=2$. В этом случае неравенство становится равенством и проверяется непосредственно.
Индукционный переход использует тождество Паскаля:
$$
R(m,n) \leqslant R(m-1,n)+R(m,n-1) \leqslant C_{m+n-3}^{m-2}+C_{m+n-3}^{m-1} = C_{m+n-2}^{m-1}.
$$
Приведенные факты важны не только как инструмент для верхней оценки чисел Рамсея, а как доказательство конечности этих чисел. Другими словами
для любого $m\geqslant2$ и $n\geqslant2$ существует $r$, такое что в любой группе из $r$ человек есть либо $m$ попарно знакомых, либо $n$ попарно незнакомых.
В завершение заметим, что
если $R(m-1,n)$ и $R(m,n-1)$ оба четны, неравенство леммы Рамсея можно усилить: $R(m,n) \leqslant R(m-1,n) + R(m,n-1) - 1$. Доказывать не стану, так как мы и так слишком отвлеклись от основной темы, дам только ссылку на Википедию.
Несовершенство алгоритма сжатия данных без потери качества.
Каждый, кому приходилось иметь дело с медиа-файлами (оцифрованные изображения, аудио-файлы, видео-файлы. и т.д) или с различными документами знает,
что для уменьшения памяти на электронных носителях, а также для ускорения передачи данных, файлы необходимо сокращать в размере, или, говоря попросту, сжимать.
Многие популярные форматы медиа-файлов, в частности форматы изображений JPEG (jpg), отсканированных документов Déjà Vu(djvu),
видео MPEG (mpg, mp4), аудио MPEG-AUDIO (mp3, m4a), Dolby AC3, Ogg-Verbis(ogg) а также большинство подформатов Windows Media (wma, wmv) гарантируют уменьшение размера файла ценой незначительного ухудшения качества. Такой метод сжатия называется сжатием с потерей качества (англ "lossy compression").
Однако многие не хотят мириться даже с несущественными потерями и предпочитают сжатие без потери качества (англ "lossless compression").
Кроме того для текстовых документов и других файлов, содержащих точные данные, сжатие без потерь является единственно допустимым.
Большинство современных lossless форматов основано на алгоритмах LZ77, LZ78, опубликованных сотрудниками Техниона Яковом Зивом и Абрахамом Лемпелем в 1977 и 1978 годах. Примерами сжатия без потерь являются форматы ZIP, GZIP(gz), BZIP2(bz2), 7ZIP(7z), RAR, используемые для упаковки данных общего вида, форматы электронных книг и документов: DOC, DOCX (фактически ZIP), EPUB (фактически ZIP), Mobipocket/Kindle(mobi, azw), форматы для изображений: GIF, PNG, а также аудио-форматы: FLAC, Monkey's Audio(ape), АLAC(m4a), отдельные подформаты WMA.
Суть сжатия без потери качества состоит в том, что восстановленный (распакованный) файл должен полностью совпадать с оригиналом. Отсюда следует, что если исходные файлы отличаются, то соответствующие им сжатые файлы также должны отличаться, иначе распаковка будет неоднозначной.
Очевидно, сжатие имет смысл только тогда, когда некоторые файлы уменьшаются в размере. При этом можно мириться с тем,
что размер некоторых файлов сохраняется таким, каким он был до сжатия. Однако, если размер файла в результате сжатия увеличивается, то какое это сжатие?! К сожалению, как сейчас будет доказано, «безпроигрышного» сжатия без потерь не существует.
Если некоторый файл сокращается в размере в результате применения алгоритма сжатия без потери качества, существует файл,
увеличивающийся в размере в результате применения того же алгоритма. (Источник: Википедия)
Обозначим через $A$ — алгоритм сжатия без потерь. Его можно рассматривать, как отображение файла $F$ в файл $A(F)$. Предположим, что, вопреки утверждению, $|A(F)| \leqslant |F|$ для любого файла $F$ (в данном случае вертикальные линии $|...|$ обозначают размер файла).
Заметим, что файлы длиной 1 нельзя сократить, поэтому обязательно найдутся несократимые файлы, для которых $|A(F)| = |F|$. С другой стороны, согласно условию, существуют сократимые файлы, то есть $|A(F)| \lt |F|$ для некоторых $F$.
Пусть $m$ — наименьший размер файла, для которого $|A(F)| \lt |F|$, $F_0$ — один из таких сокрaтимых файлов размера $m$ и $n$ – длина сжатого файла: $n=|A(F_0)|\lt m$. Обозначим через $N$ — множество файлов размера $n$, а $M$ – множество файлов, размер которых после сжатия становится равным $n$:
$$
N = \{F: |F|=n\} \\
M = \{F: |A(F)|=n\}
$$
B силу минимальности числа $m$ а также $n \lt m$, все файлы размера $n$ несократимы, то есть $|A(F)|=n$ для любого $F \in N$. Таким образом, $N$ является подмножеством множества $M$. С другой стороны, файл $F_0$ содержится в $M$, но не содержится в $N$, следовательно множество $M$ содержит больше элементов, чем $N$. Выходит, алгоритм сжатия $A$ отображает множество $M$ во множество $N$ меньшего размера. В этом случае, согласно принципу Дирихле, во множестве $M$ существуют два файла, сжимаемые в один и тот же файл. Как было замечено, это противоречит свойствам алгоритма сжатия без потери качества.
На практике, однако, с этим можно мириться, поскольку расширение в результате хорошего алгоритма сжатия происходит довольно редко, как правило либо для файлов малого размера, либо для файлов, которые уже являются сжатыми (возможно в другом формате). В этом смысле не рекомендуется, например, применять ZIP к папкам, состоящим из файлов GIF, PNG или FLAC, разве что если очень необходимо (например, для шифровки, или объединения в один файл). При этом хорошая программа упаковки обязательно проверит файл на целесообразность сжатия и откажется от сжатия, если оно не оправдано. Все популярные форматы сжатия предусматривают заголовок, где в частности указывается тип и параметры сжатия, или отсутствие такового. Хотя наличие заголовка увеличивает размер файла, такое увеличение обычно не существенно. Так, согласно заверениям Википедии, при использовании алгоритма Deflate, применяемого в файлах формата ZIP, увеличение размера сжатого файла составляет не более 5 байтов на каждые 65535 (т.е. 216-1) байтов исходных данных. В конце концов можно сравнить размеры до и после сжатия и решить, когда следует изменить параметры сжатия, а когда и вовсе отказаться от сжатия.
ЗАДАЧИ
Примечание. Напоминаю, что в данной публикации ноль не считается натуральным числом.
Часть 1.
1.1В учреждении работает 40 человек. Найдется месяц в году
в котором отмечают свой день рождения не менее четырех сотрудников?
1.2На заводе 45 цехов и 1000 работников.
Какое максимально возможное количество работников может быть в самом маленьком цеху?
(Предполагается, что в самом маленьком цеху работает наименьшее количество сотрудников.)
1.3В ковре размером 4м×4м моль проела 15 дырок. Докажите,
что из него можно вырезать коврик размером 1м×1м, не содержащий внутри себя дырок.
(Дырки считать точечными.)
1.4Сколько карт надо вытянуть наугад из преферансной колоды
(32 карты, 4 масти: 2 красные+2 черные, 8 достоинств: 7-Туз), чтобы среди них наверняка были: а) две карты одной масти; б) две карты красной масти; в) две карты одного достоинства; г) четыре карты одной масти; д) два туза.
1.5На окружности отмечены дуги, сумма длин которых меньше половины длины окружности. Докажите, что существует диаметр окружности, оба конца которого не принадлежат ни одной из дуг.
1.6В квадрате $ABCD$, длина стороны которого равна 1, расположены окружности, сумма радиусов которых равна 0,6. Докажите, что существует прямая, параллельная стороне $AB$, содержащая точки как минимум двух окружностей.
1.7Для всякого ли натурального числа $n$ существуют две различные степени
$n^{k_1}$, $n^{k_2}$ у которых совпадают: а) последняя цифра; б) две последние цифры; в) три последние цифры?
1.8Какое наименьшее количество из первых 555 натуральных чисел следует выбрать случайным образом, чтобы среди них обязательно нашлись: а) число оканчивающееся нулем; б) два четных числа; в) три с совпадающей последней цифрой; г) четыре с совпадающим остатком от деления на 7; д) пять с совпадающей суммой цифр.
Как вы заметили, задачи на принцип Дирихле — это, как правило, задачи на доказательство.
Здесь собраны такие из них, которые можно сформулировать одной фразой, причем такая
формулировка будет вполне понятной.
Доказать, что:
2.1Во всякой группе из не менее двух человек найдутся двое с одинаковым количеством знакомых.
2.2В любое время футбольного турнира, проходящего по круговой системе (каждый играет с каждым), найдутся две команды, сыгравшие одинаковое количество игр.
2.3Из $n$ различных чисел можно выбрать либо одно число кратное $n$, либо два числа, разность которых кратна $n$.
2.4Из $n$ различных целых чисел можно выбрать несколько (возможно одно или все), сумма которых делится на $n$.
2.5Среди $n+1$ натуральных чисел, дающих различные остатки
при делении на $2n+1$, либо найдется число кратное $2n+1$, либо найдутся два числа, сумма которых кратна $2n+1$.
2.6Существует натуральное число, которое делится на 2017 и оканчивается на 2018.
2.7Для любого натурального $n$ существует число, кратное $n$,
состоящее из нулей и пятерок.
2.8Для любого простого $p \gt 5$ существует степень $p^n$ ($n$ — натуральное), оканчивающаяся на 0001.
2.9Из 51 различных однозначных или двузначных чисел можно выбрать 6 чисел,
никакие два из которых не содержат одинаковых цифр ни в одном разряде.
Несмотря на простоту (чтобы не сказать «очевидность») принципа Дирихле, связанные с ним задачи как правило довольно
сложны. Даже если возможность его применения указана явно (как в данном случае),
не всегда можно сообразить, где взять те полочки, по которым надо разложить заданные предметы,
а иногда даже выбор предметов не очевиден.
3.1Сколько следует взять различных чисел, чтобы разность квадратов двух из них делилась на $n$?
3.2Десять друзей послали друг другу праздничные открытки. Каждый послал 5 открыток. Докажите, что какие-то двое послали открытки друг другу.
3.3Доказать, что равносторонний треугольник нельзя покрыть
двумя меньшими равносторонними треугольниками.
3.4Доказать, что среди пяти точек внутри равностороннего треугольника с длиной стороны 1 найдутся две точки, расстояние между которыми меньше $\dfrac{1}{2}$
3.5В квадратной клетке со стороной 1м находится анаконда длиной 10м. Барон Мюнхаузен
утверждает, что он в любой момент одним выстрелом может прострелить анаконду сразу в шести местах.
Не преувеличивает ли барон? (Анаконду можно считать ломаной линией.)
3.6В квадрате со стороной 1 проведено несколько окружностей, сумма длин
которых равна 10. Доказать, что можно провести прямую так, что она пересечет не менее четырех окружностей.
3.7В окружности радиуса 1 проведено несколько хорд. Доказать, если каждый диаметр
пересекает не более $k$ хорд, сумма длин хорд меньше $\pi k$.
3.8Доказать, что в любом семизначном числе, не кратном 7, можно вычеркнуть несколько цифр слева и несколько цифр справа, чтобы получившееся после вычеркивания число было кратно 7. Пример: 1234589. 2345=7·335.
3.9К простому числу каждый раз дописывается справа произвольная цифра,
отличная от 9. Доказать, что в некоторый момент число станет составным.
Если не получится решить без подсказки, не смущайтесь. Ведь каждая по-настоящему новая задача,
решение которой полностью понятно (даже если не удалось решить самостоятельно) — это вклад в копилку ваших знаний,
тогда как задача, решенная известным методом, всего лишь использует уже накопленные навыки.
4.1Доказать, что среди $n+1$ различных натуральных чисел, не превышающих $2n$,
найдутся:
a) три числа, одно из которых равно сумме двух других; б) два числа, одно из которых делится на другое.
4.2Каждая клетка прямоугольной доски размера 4×7 окрашена в белый или черный цвет.
Доказать, что найдется прямоугольник, образованный строками и столбцами доски, все угловые клетки которого
окрашены в одинаковый цвет. Привести пример раскраски прямоугольной доски размером 4×6,
где такого прямоугольника не существует.
4.3Дана группа из 15 человек, в которой из любых трех найдутся двое, знакомые друг с другом. Доказать, что из нее можно одновременно выделить три подгруппы из трех, четырех и пяти человек, в каждой из которых все знакомы друг с другом. А верно ли это для группы из 14 человек?
4.4На плоскости отмечено 35 точек, так что две точки из любых трех
находятся на расстоянии менее 1 друг от друга. Доказать, что существует 18 точек, расстояние
между любыми двумя из которых меньше 2.
4.5В стране 2018 городов, и из каждого выходит не менее 93 дорог. Известно, что из любого города можно проехать по дорогам в любой другой. Докажите, что это можно сделать не более, чем с 62 пересадками. (Дорога соединяет между собой два города.)
4.6Множество чисел разбито на 7 подмножеств. Доказать, что хотя бы в одном из этих подмножеств найдутся либо четыре числа $a$,$b$,$c$,$d$, таких что $a+b=c+d$, или три числа $e$,$f$,$g$, для которых $e+f = 2g$.
4.7На прямой расположены $n^2+1$ отрезков. Доказать, что из них можно выбрать либо $n+1$ непересекающихся отрезков, либо $n+1$ отрезков, имеющих общую точку.
4.8Доказать, что в любой последовательности из $mn+1$ различных вещественных чисел можно выбрать либо возрастающую подпоследовательность из $m+1$ чисел, либо убывающую подпоследовательность из $n+1$ чисел. Примечание: подпоследовательность образуется подмножеством элементов, следующих в том же порядке, что и в исходной последовательности.
4.9Дано 2018 множеств по 45 элементов в каждом, при этом каждая пара множеств имеет в точности один общий элемент. Доказать, что существует элемент, принадлежащий всем 2018 множествам.
4.1Решить систему уравнений:
$\qquad\qquad
\left \{ \begin{matrix}
x^2 + \lfloor y \rfloor = 10 \\
y^2 + \lfloor x \rfloor = 13
\end{matrix}
\right .
$
Эта система уравнений мне буквально вскружила голову. Никак не мог получить решения для отрицательных $x$ и $y$,
будучи убежден что в этом случае они могут возрастать до бесконечности. Наверное так бы и застрял в этом неведении,
если бы не подсказка скромного dxiv на форуме Mathematics Stack Exchange.
Прибавляя $x^2$ к обоим частям неравенства $\lfloor y \rfloor \lt y+1$, получаем:
$$
x^2+y \lt x^2 + \lfloor y \rfloor + 1 = 11
$$
аналогично
$$
y^2+y \lt y^2 + \lfloor x \rfloor + 1 = 14
$$
Подумайте над извечным вопросом «Что же дальше?», прежде чем продолжать чтение.Если бы меня этом спросили, я наверняка ответил бы. Но в том то и беда, что спрашивать было некому!😉
Вот продолжение: учитывая тождества $x^2+x=(x+\frac{1}{2})^2-\frac{1}{4}$, $y^2+y=(y+\frac{1}{2})^2-\frac{1}{4}$, полученное неравенство можно записать в следующем виде:
$$
\left (x+\dfrac{1}{2} \right)^2 + \left(y+\dfrac{1}{2}\right)^2 \lt 24\frac{1}{2} \lt 25
$$
Маленький нюанс поставил все на свои места. Теперь понятно, что $\left|x+\frac{1}{2} \right| \lt 5$, или $-5\frac{1}{2} \lt x \lt 4\frac{1}{2}$, откуда $-6 \leqslant \lfloor x \rfloor \leqslant 4$, поэтому из второго уравнения системы получаем:
$$
9 \leqslant y^2 = 13-\lfloor x \rfloor \leqslant 19
$$
или
$$
3 \leqslant |y| \leqslant \sqrt{19}
$$
Рассмотрим отдельно случаи положительного и отрицательного $y$.
a) $y \geqslant 0$, таким образом $3 \leqslant y \leqslant \sqrt{19} $,
следовательно $3\leqslant\lfloor y \rfloor \leqslant 4$.
В таком случае из первого уравнения системы получаем: $x=\pm\sqrt{7}$ для $y=3$
и $x=\pm\sqrt{6}$ для $y=4$ .
Если $x$ — положительно, то есть $x=\sqrt{6}$ или $x=\sqrt{7}$, то
$\lfloor x \rfloor = 2$, следовательно из второго уравнения системы (помятуя $y \geqslant 0$) получаем $y=\sqrt{11}$.
При этом $\lfloor y \rfloor = 3$, так что $x=\sqrt{7}$. Мы получили первое решение: $(\sqrt{7},\;\sqrt{11})$, и,
как вскоре в этом убедимся, далеко не последнее.
Если $x$ — отрицательно, то $x=-\sqrt{6}$ или $x=-\sqrt{7}$,
поэтому $\lfloor x \rfloor = -3$, так что в этот раз второе уравнение дает $y=4$.
Поскольку $\lfloor y\rfloor =4$, то $x=-\sqrt{6}$, так что второе решение $(-\sqrt{6},\;4)$.
б) $y \lt 0$, следовательно $-\sqrt{19} \leqslant y \leqslant -3$,
откуда $-5 \leqslant\lfloor y \rfloor \leqslant -3$.
В таком случае из первого уравнения системы получаем: $x=\pm\sqrt{15}$, $\pm\sqrt{14}$, $\pm\sqrt{13}$
для $y=-5$,$-4$ и $-3$ соответственно.
Если $x$ — положительно, то в любом из трех случаев $\lfloor x \rfloor = 3$, следовательно из второго уравнения системы (помятуя $y \lt 0$) получаем $y=-\sqrt{10}$. При этом $\lfloor y \rfloor = -4$, так что $x=\sqrt{14}$. Получили третье решение: $(\sqrt{14},\;-\sqrt{10})$.
Наконец, если $x$ — отрицательно, то $\lfloor x \rfloor = -4$, что соответствует $y=-\sqrt{17}$. При этом $\lfloor y \rfloor = -5$, так что $x=-\sqrt{15}$. Таким образом. последнее четвертое решение: $(-\sqrt{15},\;-\sqrt{17})$.
Ответ: $(\sqrt{7},\;\sqrt{11})$, $(-\sqrt{6},\;4)$, $(\sqrt{14},\;-\sqrt{10})$, и $(-\sqrt{15},\;-\sqrt{17})$.
Графическое решение системы уравнений показано ниже. Постарался, сделать чертеж настолько понятным, насколько мог. Точки пересечения обозначены красным цветом.
Графическое решение системы уравнений $\left \{ \begin{matrix} x^2 + \lfloor y \rfloor = 10 \\y^2 + \lfloor x \rfloor = 13\end{matrix}\right .$
Олимпиада Англии, 1975 год, однако давно стала математической классикой.
Обозначим через $n$–е слагаемое через $a_n$. Таким образом $a_n=\left\lfloor \sqrt[3]{a} \right\rfloor$
Запишем $n$ и соответствующие $a_n$ в таблицу:
$n$
1
2
...
7
8
9
...
26
27
28
...
(x-1)3-1
(x-1)3
(x-1)3+1
...
x3-1
$a_n=\left\lfloor \sqrt[3]{n} \right\rfloor$
1
1
...
1
2
2
...
2
3
3
...
x-2
x-1
x-1
...
x-1
Mы видим, что каждый полный куб $n=i^3$ увеличивает значение $a_n$, делая его равным $i$.
Таким образом все слагаемые можно разделить на $x-1$ множеств, так что $i$-е множество начинается $(i^3)$-м элементом и
заканчивается $((i+1)^3-1)$-м элементом. В этом множестве будет $(i+1)^3-i^3=3i^2+3i+1$ слагаемое, значение каждого
из которых равно $i$. Таким образом можно вычислить сумму элементов $i$-го множества:
$$
s_i = a_{i^3} + a_{i^3+1} + ... + a_{(i+1)^3-1} = i(3i^2+3i+1) \label{eq:0201}\tag{4.2.1}
$$
Используя формулу суммы квадратов и кубов первых натуральных чисел, можно вычислить общую сумму и приравнять ее к 400,
пытаясь подобрать целый корень полученного уравнения четвертой степени. Стоит ли усложнять жизнь, когда есть
хоть не столь изящный, зато куда более легкий метод? Думаю, вы догадались, о каком методе идет речь.
Действительно, речь идет о методе проб. Введем обозначение $S_x$ для суммы с накоплением:
$$
S_x = s_1 + s_2 +... + s_{x-1}
$$
Будем увеличивать $x$, и накапливать $S_x$, вычисляя дополнительное слагаемое $s_{x-1}$ по формуле $\eqref{eq:0201}$,
пока не получим требуемое число. После этого продолжать процесс не имеет смысла, так как дальнейшие
числа будут больше требуемого.
Вычисления записываем в таблицу:
$x$
$s_{x-1}$
$S_x$
1
-
0
2
7
7
3
38
45
4
111
156
5
244
400
Получилось! Ответ: $x=5$.
4.3 Доказать что для целого положительного $n$ $\quad\{\sqrt{1}\} + \{\sqrt{2}\} + ... + \{\sqrt{n^2}\} \leqslant \dfrac{n^2-1}{2}$,
причем равенство имеет место тогда и только тогда, когда $n=1$.
На первый взгляд может показаться, что последнее слагаемое присутствует из чисто эстетических соображений, поскольку $\{\sqrt{n^2}\} = \{n\}=0$,
так что его можно отбросить. Однако, если $n=1$, то отбросить последнее слагаемое не удается лишь потому, что оно единственное.
Понятно, что в этом случае сумма равна нулю, при этом правая часть неравенства также обращается в нуль.
В дальнейшем будем считать, что $n \geqslant 2$, так что последнее слагаемое действительно можно игнорировать, считая что в сумме ($n^2-1$) слагаемых. Покажем, что в этом случае неравенство является строгим.
Действуем аналогично предыдущему решению, только, разумеется, в этот раз вместо кубов будем использовать квадраты.
Обозначим через $a_m$ целую часть квадратного корня из $m$: $a_m=\left\lfloor \sqrt{a} \right\rfloor$.
Запишем $m$ и соответствующие значения $\left\lfloor \sqrt{m} \right\rfloor$ в таблицу:
$m$
1
2
3
4
5
...
8
9
10
...
(n-1)2-1
(n-1)2
(n-1)2+1
...
n2-1
$\left\lfloor \sqrt{m} \right\rfloor$
1
1
1
2
2
...
2
3
3
...
$n-2$
n-1
$n-1$
...
$n-1$
Замечаем, что каждый полный квадрат $m=i^2$ увеличивает значение $\left\lfloor \sqrt{m} \right\rfloor$, делая его равным $i$.
Разобьем числа $m$ ($1\leqslant m \leqslant n^2-1$) на множества $G_i$ ($1\leqslant i \leqslant n-1$),
каждое из которых содержит числа от $i^2$ до $((i+1)^2-1)$ включительно. Таким образом $G_i$ состоит из $(i+1)^2-i^2=2i+1$ элементов
причем для каждого $m \in G_i$ имеет место $\left\lfloor \sqrt{m} \right\rfloor=i$.
Будем нумеровать элементы внутри $G_i$ с нуля. Тогда $j$-й ($0 \leqslant j \leqslant 2i$) элемент $G_i$ равен $b_{i,j}=i^2+j$,
отсюда, ввиду $\left\lfloor \sqrt{b_{i,j}} \right\rfloor = i$,
$$
\left\{\sqrt{b_{i,j}}\right\} = \sqrt{i^2+j}-i
$$
Поскольку $\left\{\sqrt{b_{i,0}}\right\}= \sqrt{i^2}-i = 0$, нулевой элемент можно игнорировать. Если $j>0$
(а такие элементы обязательно найдутся, так как $2i+1 \gt 1$ при $i \geqslant 1$), то,
используя тождество $a-b=\dfrac{a^2-b^2}{a+b}$, приходим к следующему:
$$
\left\{\sqrt{b_{i,j}}\right\} = \frac{j}{\sqrt{i^2+j}+i} \lt \frac{j}{2i}
$$
Это позволяет оценить сумму $\left\{\sqrt{b_{ij}}\right\}$, для элементов $G_i$:
$$
s_i = \left\{\sqrt{b_{i,1}}\right\} + ... + \left\{\sqrt{b_{i,2i}}\right\} \lt \frac{1}{2i}+...+\frac{2i}{2i}=
\frac{1+...+2i}{2i} = \frac{2i+1}{2}
$$
Осталось оценить общую сумму:
$$
s_1 + s_2 + ... + s_{n-1} \lt \frac{3}{2} + \frac{5}{2}+...+\frac{2n-1}{2} = \frac{(2n+2)(2n-1)}{4} = \frac{n^2-1}{2},
$$
quod erat demonstrandum.
4.4Доказать, что если $p$ и $q$ — взаимно-простые числа, то: $\quad \left\lfloor \dfrac{p}{q} \right\rfloor + \left\lfloor \dfrac{2p}{q} \right\rfloor ... \left\lfloor \dfrac{(q-1)p}{q} \right\rfloor = \dfrac{(p-1)(q-1)}{2}$
Источник: А. Егоров. «Целая и дробная части числа» Квант №5, 2002. Приводится решение из статьи.
В системе координат рассмотрим прямоугольник ограниченный координатными осями, а также прямыми $x=q$ и $y=p$. Количество точек с целочисленными координатами находящихся внутри прямоугольника (но не вдоль его периметра) равно $(p-1)(q-1)$.
Проведем диагональ прямоугольника проходящую через начало координат. Уравнение прямой, на которой лежит диагональ: $y=\frac{p}{q}x$.
Покажем, что диагональ не содержит точек с целочисленными координатами, не совпадающих с ее концами. В самом деле, если точка ($m$,$n$) ($m$ и $n$ — целые числа, причем $0\lt m \lt q$ и $0\lt n \lt p$) принадлежит диагонали, то $n=\frac{p}{q}m$, или $pm=qn$. Отсюда $pm$ делится на $q$ и так как по условию $p$ и $q$ — взаимно простые числа, то $m$ должно делиться на $q$, что невозможно, так как $0 \lt m \lt q$.
Таким образом каждая точка с целочисленными координатами, лежащая внутри прямоугольника лежит также внутри соответствующего треугольника, а не на его границе. Ввиду симметрии относительно центра прямоугольника каждый треугольник содержит одинаковое количество внутренних точек с целочисленными координатами и это количество равно $S = \dfrac{(p-1)(q-1)}{2}$
Подсчитаем количество точек с целочисленными координатами лежащих ниже диагонали прямоугольника другим способом. Для некоторого целого $k$, такого что $0 \lt k \lt q$ рассмотрим точку диагонали $M$ с абсциссой $k$. Так как ордината точки $M$ равна $\dfrac{p}{q}k$, то непосредственно под точкой $M$ находится $\left\lfloor\dfrac{p}{q}k \right\rfloor $ точек с целочисленными координатами. Суммируя по всем $k$ от $1$ до $q-1$ получим общее количество точек с целочисленными координатами, лежащими внутри треугольника под диагональю:
$$
S = \left\lfloor \frac{p}{q} \right\rfloor + \left\lfloor \frac{2p}{q} \right\rfloor + ... \left\lfloor \frac{(q-1)p}{q} \right\rfloor
$$
Приравнивая значения полученные различными способами, приходим к утверждению задачи.
4.5Доказать, что для целого положительного $n$: $\quad\lfloor x \rfloor + \left\lfloor x+\dfrac{1}{n} \right\rfloor ... \left\lfloor x+\dfrac{n-1}{n} \right\rfloor = \lfloor nx \rfloor $
Источник тот же, что и в предыдущей задаче. В этот раз авторское решение отсутствует, так что приходится довольствоваться собственным.
Так как $\left(x+\frac{n-1}{n}\right)-x = \frac{n-1}{n} \lt 1$, значения слагаемых в левой части могут различаться между собой не более, чем на единицу.
Из $x+\frac{i}{n} = \lfloor x \rfloor + \left(\{x\}+\frac{i}{n}\right)$ следует, что $\left\lfloor x +\frac{i}{n} \right\rfloor$ равно $\lfloor x \rfloor$, если $\{x\}+\frac{i}{n} \lt 1$, и $\lfloor x \rfloor+1$ в противном случае.
Пусть $k$ — наименьшее значение $i$, при котором $\{x\}+\frac{i}{n} \geqslant 1$. Это означает следующее:
$$
\{x\}+\frac{k-1}{n} \lt 1 \leqslant \{x\}+\frac{k}{n} \label{eq:0501}\tag{4.5.1}
$$
Поскольку начальные $k$ слагаемых левой части (соответствующие $i=0,\;1,\;...\;k-1$) равны $\lfloor x \rfloor$ , а остальные $n-k$ слагаемых равны $\lfloor x \rfloor+1$, их сумма равна:
$$
k \lfloor x \rfloor + (n-k)(\lfloor x \rfloor+1) = n\lfloor x \rfloor + n-k \label{eq:0502}\tag{4.5.2}
$$
Осталось показать, что правая часть полученного равенства есть не что иное, как $\lfloor nx \rfloor$. Для этого заметим, что равенство $\eqref{eq:0501}$ можно записать в виде:
$$
1-\frac{k}{n}\leqslant \{x\} \lt 1-\frac{k-1}{n}
$$
что после умножения на $n$ дает:
$$
n-k \leqslant n\{x\} \lt n-k+1 \label{eq:0503}\tag{4.5.3}
$$
Прибавляя $n\lfloor x \rfloor$ ко всем частям неравенства $\eqref{eq:0503}$, получаем:
$$
n\lfloor x \rfloor+n-k \leqslant n(\lfloor x \rfloor +\{x\}) \lt n\lfloor x \rfloor+n-k+1
$$
или
$$
n\lfloor x \rfloor+n-k \leqslant nx \lt n\lfloor x \rfloor+n-k+1
$$
откуда $\lfloor nx \rfloor = n\lfloor x \rfloor+n-k$, что совпадает с правой частью равенства $\eqref{eq:0502}$.
Зафиксируем целое положительное $k$ и докажем, что при выбранном $k$ тождество выполняется при любом целом неотрицательном $n$.
Для краткости обозначим левую часть доказываемого тождества через $S_k(n)$ и применим метод математической индукции.
База индукции. При $n=0$ в каждом из слагаемых для $S_k(n)$ числитель меньше знаменателя. Таким образом, все слагаемые — нули,
$S_k(0) = 0$, и тождество действительно имеет место.
Вычтем из второго равенства первое. Тогда все слагаемые правой части, кроме крайних, взаимно уничтожаются. Получаем:
$$
S_k(n+1)-S_k(n) = \left\lfloor \frac{n+k}{k}\right\rfloor - \left\lfloor \frac{n}{k}\right\rfloor = \left\lfloor \frac{n}{k}+1\right\rfloor - \left\lfloor \frac{n}{k}\right\rfloor
$$
Согласно свойству 5 целой части $\left\lfloor \frac{n}{k}+1 \right\rfloor = \left\lfloor \frac{n}{k} \right\rfloor +1$, следовательно $S_k(n+1)-S_k(n)=1$. Так как, согласно индукционному предположению, $S_k(n) = n$, то
$$
S_k(n+1) = S_k(n) + 1 = n + 1
$$
чем завершается доказательство.
Из австрийской олимпиады 1974 года. Приводится авторское решение с незначительными улучшениями.
Согласно неравенству между средне-арифметическим и средне-геометрическим $2\sqrt{n(n+1)} \leqslant 2n+1$ (равенства на самом деле быть не может, так как числа различные, но это не существенно), поэтому
$$
(\sqrt{n}+\sqrt{n+1})^2=2n+1+2\sqrt{n(n+1)}\leqslant 4n+2\,.
$$
Отсюда $\sqrt{n}+\sqrt{n+1} \leqslant \sqrt{4n+2}$, так что
$$
\lfloor \sqrt{n}+\sqrt{n+1} \rfloor \leqslant \lfloor \sqrt{4n+2} \rfloor \label{eq:0701}\tag{4.7.1}
$$
Остается показать, что полученное неравенство является равенством при всех целых неотрицательных $n$.
Допустим, что и неравенство $\eqref{eq:0701}$ является строгим для некоторого целого неотрицательного $n$. Тогда существует целое $m$, такое что
$$
\sqrt{n}+\sqrt{n+1} \lt m \leqslant \sqrt{4n+2}
$$
Возводим в квадрат:$$
2n+1+2\sqrt{n(n+1)} \lt m^2 \leqslant 4n+2
$$
Учитывая что $\sqrt{n(n+1)}\geqslant n$ для целого неотрицательного $n$ (опять неравенство на самом деле строгое!), получаем:
$$
4n+1 \lt m^2 \leqslant 4n+2
$$
и поскольку $m^2$ — целое число, то
$$
m^2=4n+2=2(2n+1)
$$
Есть среди нас такие, у кого последнее равенство вызывает чувство дискомфорта? Обязательно есть!
Квадрат целого числа делится на 2, но не делится на 4, что невозможно себе представить даже в фильмах ужасов!
Полученное противоречие доказывает утверждение.
4.8Доказать, что уравнение: $\quad\lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor + \lfloor 32x \rfloor = 12345\quad$ не имеет решений.
Обозначим сумму слева через $S$:
$$
S = \lfloor x \rfloor + \lfloor 2x \rfloor + \lfloor 4x \rfloor + \lfloor 8x \rfloor + \lfloor 16x \rfloor + \lfloor 32x \rfloor
$$
Из свойства 6b следует:
$$
2\lfloor x \rfloor \leqslant \lfloor 2x \rfloor \leqslant 2\lfloor x\rfloor+1 \\
4\lfloor x \rfloor \leqslant \lfloor 4x \rfloor \leqslant 4\lfloor x\rfloor+3 \\
8\lfloor x \rfloor \leqslant \lfloor 8x \rfloor \leqslant 8\lfloor x\rfloor+7 \\
16\lfloor x \rfloor \leqslant \lfloor 16x \rfloor \leqslant 16\lfloor x\rfloor+15 \\
32\lfloor x \rfloor \leqslant \lfloor 32x \rfloor \leqslant 32\lfloor x \rfloor+31
$$
Складывая эти неравенства и добавляя $\lfloor x \rfloor$ ко всем частям, получаем:
$$
63 \lfloor x \rfloor \leqslant S \leqslant 63 \lfloor x \rfloor + 57
$$
Таким образом, остаток от деления $S$ на $63$ не может быть больше $57$.
Кстати, а какой остаток дает $12345$ при делении на $63$? Давайте проверим: $12345 = 63 \cdot 195 + 60$. Комментарии излишни.
В задаче 2.3 уже встречалось уравнение с двумя целыми частями, но там они были равны, поэтому достаточно
было ввести обозначение для целой части, как ларчик просто открывался. В данном случае такой метод не подходит.
Таким образом, если $\left\{ \frac{2x-1}{3} \right\} \lt \frac{1}{2}$, то
$\left\lfloor \frac{4x+1}{6} \right\rfloor = \left\lfloor \frac{2x-1}{3} \right\rfloor$, тогда как при
$\left\{ \frac{2x-1}{3} \right\} \geqslant \frac{1}{2}$ имеем
$\left\lfloor \frac{4x+1}{6} \right\rfloor = \left\lfloor \frac{2x-1}{3}\right\rfloor + 1$,
поэтому в любом случае можно свести две целые части к одной.
Рассмотрим каждый случай.
а) Дробная часть $\left\{ \frac{2x-1}{3} \right\}$ меньше половины:
$$
\left\{ \dfrac{2x-1}{3} \right\} \lt \dfrac{1}{2} \label{eq:0101}\tag{3.1.1}.
$$
В этом случае целые части равны, так что
$$
2\;\left\lfloor \frac{2x-1}{3} \right\rfloor = \frac{5x-4}{3}
$$
или
$$
\left\lfloor \frac{2x-1}{3} \right\rfloor = \frac{5x-4}{6}
$$
Дальше все отлажено: $y=\frac{5x-4}{6}$, отсюда
$$
x=\frac{6y+4}{5} \label{eq:0102}\tag{3.1.2}
$$ следовательно
$$
\frac{2x-1}{3} = \frac{4y+1}{5} \label{eq:0103}\tag{3.1.3}
$$
Таким образом получаем неравенство $0 \leqslant \frac{4y+1}{5} - y \lt 1$, решая которое находим:
$$
-4 \lt y \leqslant 1 \label{eq:0104}\tag{3.1.4}
$$
Этот интервал можно сузить, если принять во внимание $\eqref{eq:0101}$. Заметим что $\eqref{eq:0103}$ можно записать как $\frac{2x-1}{3} = y + \frac{1-y}{5}$, при этом из $\eqref{eq:0104}$ следует, что $0 \leqslant \frac{1-y}{5} \lt 1$, так что $\left\{ \frac{2x-1}{3} \right\} = \frac{1-y}{5}$, и требование $\eqref{eq:0101}$ записывается в виде: $\frac{1-y}{5} \lt \frac{1}{2}$, откуда $y \geqslant -1$ и, с учетом $\eqref{eq:0103}$, $-1 \leqslant y \leqslant 1$.
Для каждого $y \in [-1, 1]$ находим значения $x$ используя $\eqref{eq:0102}$. Получаем: $x_1=-\frac{2}{5}=-0,4$; $x_2=\frac{4}{5}=0,8$; $x_3=2$.
b) $\left\{ \dfrac{2x-1}{3} \right\} \geqslant \dfrac{1}{2}$.
В этом случае вторая целая часть на единицу больше, чем первая, таким образом
$$
2\;\left\lfloor \frac{2x-1}{3} \right\rfloor + 1 = \frac{5x-4}{3}
$$
или
$$
\left\lfloor \frac{2x-1}{3} \right\rfloor = \frac{5x-7}{6}
$$
В этот раз требуется подстановка $y=\frac{5x-7}{6}$, при этом $x=\frac{6y+7}{5}$, $\frac{2x-1}{3}=\frac{4y+3}{5}=y+\frac{3-y}{5}$.
Решая неравенство $0 \leqslant \frac{4y+3}{5} - y \lt 1$, находим $-2 \lt y \leqslant 3$, что, благодаря $\left\{\frac{2x-1}{3}\right\}=\frac{3-y}{5}\geqslant\frac{1}{2}$ сужается до $-1 \leqslant y \leqslant 0$. Для этих значений $y$ находим:
$x_4=\frac{1}{5}=0,2$; $x_5=\frac{7}{5}=1,4$.
Ответ: $-0,4$; $0,2$; $0,8$; $1,4$; $2$,
3.2 Решить уравнение: $\quad |\sin x + \cos x| = 5 - 4\lfloor x \rfloor$
Пользуясь формулой для $a\;\sin x + b\;\cos x$, преобразуем уравнение к виду:
$$
\sqrt{2}\left|\sin\left(x + \frac{\pi}{4}\right)\right| = 5 - 4\lfloor x \rfloor
$$
откуда следует
$$
0 \leqslant 5 - 4\lfloor x \rfloor \leqslant \sqrt{2}\\
0 \lt \frac{5-\sqrt{2}}{4} \leqslant \lfloor x \rfloor \leqslant \frac{5}{4}
$$
Таким образом, $\lfloor x \rfloor=1$. Подстановка этого значения в исходное уравнение, дает:
$$
\sqrt{2}\left|\sin\left(x + \frac{\pi}{4}\right)\right| = 1\\
\left|\sin\left(x + \frac{\pi}{4}\right)\right| = \frac{\sqrt{2}}{2}
$$
откуда $x + \dfrac{\pi}{4} = \dfrac{\pi}{4} + \dfrac{\pi}{2}k, \quad k=0,\pm 1,\pm 2...$,
следовательно $x = \dfrac{\pi}{2}k$.
Из $\lfloor x \rfloor=1$ следует $1 \leqslant \dfrac{\pi}{2}k \lt 2$, или $0 \lt \dfrac{2}{\pi} \leqslant k \lt \dfrac{4}{\pi} \lt 2$, поэтому $k=1$, следовательно $x=\dfrac{\pi}{2}$.
3.3Решить уравнения: a) $\left\{ x + \dfrac{1}{x} \right\} = \{x\} + \dfrac{1}{\{x\}}$; b) $\left\lfloor x + \dfrac{1}{x} \right\rfloor = \lfloor x \rfloor + \dfrac{1}{\lfloor x \rfloor}$
При решении этих уравнений существенную роль играют следующие тождественные неравенства:
$$
\begin{array}{l}
a + \dfrac{1}{a} \geqslant 2,\quad \text{при}\;a \gt 0\,,\\
a + \dfrac{1}{a} \leqslant -2,\quad \text{при}\;a \lt 0\,.
\end{array} \label{eq:0301}\tag{3.3.1}
$$
причем равенство достигается при $a=\pm 1$.
Первое неравенство получается из неравенства между средне-арифметическим и средне-геометрическим заменой $b$ на $\frac{1}{a}$, при этом для достижения равенства требуется $a=\frac{1}{a}$, откуда $a=1$. Если $a \lt 0$, то с помощью подстановки $a=-b\;(b \gt 0)$ получаем: $a+\frac{1}{a} = -(b+\frac{1}{b}) \leqslant -2\,$, причем равенство достигается при $b=1$ или $a=-1$.
Обратимся теперь к решению уравнений:
a) Согласно свойству 1f дробной части $\{x\} \geqslant 0$, причем значение $\{x\} = 0$ не допустимо для $\{x\} + \frac{1}{\{x\}}$. Поскольку $\{x\} \gt 0$, получаем: $\{x\} + \frac{1}{\{x\}} \geqslant 2$, в то время как $\left\{ x + \frac{1}{x} \right\} \lt 1$. Уравнение не имеет решений.
b) Так как $\left\lfloor x + \frac{1}{x} \right\rfloor$ и $\lfloor x \rfloor$ — целые числа, целым должно быть также число $\frac{1}{\lfloor x \rfloor}$, что возможно лишь при $\lfloor x \rfloor = \pm 1$. Таким образом $\left\lfloor x + \frac{1}{x} \right\rfloor = \pm 2$, что приводит к следующим системам неравенств:
$$
\begin{cases}
2 \leqslant x + \dfrac{1}{x} \lt 3 \\
1 \leqslant x \lt 2
\end{cases}
\qquad
\begin{cases}
-2 \leqslant x + \dfrac{1}{x} \lt -1 \\
-1 \leqslant x \lt 0
\end{cases}
$$
которые, благодаря тождественным неравенствам $\eqref{eq:0301}$, можно упростить:
$$
\begin{cases}
x + \dfrac{1}{x} \lt 3 \\
1 \leqslant x \lt 2
\end{cases} \label{eq:0302}\tag{3.3.2}
$$
$$
\begin{cases}
x + \dfrac{1}{x} = -2 \\
-1 \leqslant x \lt 0
\end{cases} \label{eq:0303}\tag{3.3.3}
$$
Заметим, что если $1 \leqslant x \lt 2$, то $\frac{1}{x} \leqslant 1$, так что $x + \frac{1}{x} \lt 3$ и первое неравенство $\eqref{eq:0302}$ удовлетворяется автоматически. Что касается системы $\eqref{eq:0303}$, то ее решение очевидно: $x=-1$.
Ответ: $x=-1$ или $1 \leqslant x \lt 2$.
3.4Решить уравнение: $\quad \lfloor x \rfloor + \dfrac{1}{\lfloor x \rfloor} = \{x\} + \dfrac{1}{\{x\}}$
Уравнение определено, когда $\lfloor x \rfloor$ и $\{x\}$ отличны от нуля.
Умножая на $\lfloor x \rfloor\{x\}$ и перенося все в левую часть, получаем:
$$
\lfloor x \rfloor^2\{x\} + \{x\} - \lfloor x \rfloor\{x\}^2 - \lfloor x \rfloor = 0\\
$$
то есть
$$
(\lfloor x \rfloor\{x\}-1)(\lfloor x \rfloor -\{x\}) = 0
$$
где один из сомножителей обязан быть нулевым.
Из $\lfloor x \rfloor-\{x\}=0$ следует $\{x\}=\lfloor x \rfloor$, поэтому $\{x\}$ — целое число,
значит $\{x\}=0$, что однако не допустимо.
Остается надеяться лишь на $\lfloor x \rfloor\{x\}-1=0$ то есть $\lfloor x \rfloor\{x\}=1$.
Пусть $k=\lfloor x \rfloor$.
Так как $\{x\}$ — положительно, $k$ также положительно. При этом $\{x\}=\dfrac{1}{k}$, так что $x=k+\dfrac{1}{k}$. Кроме того, из $\dfrac{1}{k} = \{x\} \lt 1$ следует $k \geqslant 2$.
Верно и обратное: если $x=k+\dfrac{1}{k}$, где $k$ — целое число, не меньшее $2$, то $0 \lt x-k = \dfrac{1}{k} \lt 1$, следовательно $\lfloor x \rfloor=k$, и $\{x\}=\dfrac{1}{k}$, так что уравнение выполнено.
Ответ: $x=k+\dfrac{1}{k},\;\;k=2,3,...$
3.5Решить уравнение:$\quad x^2+\{x\}^2=50$
Так как $0 \leqslant \{x\} \lt 1$, то $\{x\}^2 \lt 1$. Поэтому $0 \leqslant 50-x^2 \lt 1$, откуда:
$$
49 \lt x^2 \leqslant 50 \,,
$$
следовательно
$$
7 \lt |x| \leqslant \sqrt{50} \lt 8 \,,
$$
Таким образом, $\lfloor x \rfloor$ равно $7$ или $(-8)$. Обозначим $y = \{ x \}$. Подставляя в исходное уравнение и учитывая $x = \lfloor x \rfloor + \{ x \}$, получаем, что $y$ должен быть корнем одного из следующих уравнений.
$$
\begin{array}{l}
(y+7)^2 + y^2 = 50 \\
(y-8)^2 + y^2 = 50
\end{array}
$$
Корни первого уравнения $\frac{-7 \pm \sqrt{51}}{2}$, корни второго уравнения $1$ и $7$. Так как $0 \leqslant y \lt 1$, подходит только $y=\frac{\sqrt{51}-7}{2}$, соответствующий $\lfloor x \rfloor = 7$. Отсюда $x=7+\frac{\sqrt{51}-7}{2} = \frac{\sqrt{51}+7}{2}$
Ответ: $x=\dfrac{\sqrt{51}+7}{2}$
3.6 Решить уравнение: $\{(x+1)^3\} = x^3$
Всероссийская математическая олимпиада, 1998
Запишем уравнение в виде:
$$
\{(3x^2+3x+1)+x^3\} = x^3 \label{eq:0601}\tag{3.6.1}
$$
Согласно свойству 1f дробной части $0 \leqslant x^3 \lt 1$, откуда
$$
0 \leqslant x \lt 1 \label{eq:0602}\tag{3.6.2}
$$
В этом случае из $\eqref{eq:0601}$ следует, что $(3x^2+3x+1)$ является целой частью числа $(x+1)^3$. Таким образом
число $(3x^2+3x+1)$, а значит и $(3x^2+3x)$ обязано быть целым:
$$
3x^2+3x = n \label{eq:0603}\tag{3.6.3}
$$ где $n$ — целое число.
Решив $\eqref{eq:0603}$, находим $x=\dfrac{-3\pm\sqrt{9+12n}}{6}$, при этом корень $\dfrac{-3-\sqrt{9+12n}}{6}$ - заведомо отрицательный, что
противоречит $\eqref{eq:0602}$.
Найдем значения $n$, при которых $x=\dfrac{-3+\sqrt{9+12n}}{6}$ удовлетворяет $\eqref{eq:0602}$:
$$
0 \leqslant \dfrac{-3+\sqrt{9+12n}}{6} \lt 1
$$
откуда $0 \leqslant n \lt 6$.
Рассуждая в обратную сторону приходим к выводу, что при $0 \leqslant n \leqslant 5$ значение $x=\dfrac{-3+\sqrt{9+12n}}{6}$ удовлетворяет заданному неравенству.
Ответ: $x=\dfrac{-3+\sqrt{9+12n}}{6}$, где $n=0,1,2,3,4,5$.
3.7Решить уравнение: $\quad \lfloor x^3 \rfloor - 3\lfloor x \rfloor^2 + 3\lfloor x \rfloor = \{x\} + 2$
Эта шуточная задача заимствована из Н.Б.Алфутова, Ю.Е.Егоров, А.В.Устинов. «18×18 Вступительные задачи ФМШ при МГУ.» М: МЦНМО, 2017, стр.39 (без решения).
Поскольку все члены, кроме $\{x\}$ обязаны быть целыми числами, $\{x\}$ — также целое число. Поэтому $\{x\}=0$, то есть $x$ — целое число. Убирая все знаки целой части и заодно $\{x\}$, получаем: $x^3 - 3x^2 + 3x = 2$, или $(x-1)^3 = 1$, откуда $x=2$.
3.8Решить систему уравнений:
$\qquad\qquad
\left \{ \begin{matrix}
x + \lfloor y \rfloor + \{z\} = 1,1 \\
y + \lfloor z \rfloor + \{x\} = 2,2 \\
z + \lfloor x \rfloor + \{y\} = 3,3
\end{matrix}
\right .
$
Складывая все три уравнения получаем:
$$
x + \lfloor y \rfloor + \{z\} + y + \lfloor z \rfloor + \{x\} + z + \lfloor x \rfloor + \{y\} = 6,6
$$
Группируем:
$$
x + y + z + (\lfloor x \rfloor+\{x\}) +(\lfloor y \rfloor + \{y\}) + (\lfloor z \rfloor + \{z\}) = 6,6
$$
откуда
$$
x + y + z = 3,3 \label{eq:0801}\tag{3.8.1}
$$
Теперь сложим только первое и второе уравнения. Получим:
$$
x+y+z+\{x\}+\lfloor y \rfloor = 3,3
$$
Учитывая $\eqref{eq:0801}$, получаем
$$
\{x\}+\lfloor y \rfloor = 0
$$
Аналогично, сложив 2-е и 3-е уравнение, а затем 1-е и 3-е уравнения получаем:
$$
\begin{array}{l}
\{y\} + \lfloor z \rfloor = 2,2 \\
\{z\} + \lfloor x \rfloor = 1,1
\end{array}
$$
Учитывая, что $\lfloor y \rfloor$, $\lfloor z \rfloor$ и $\lfloor x \rfloor$ — целые числа,
находим: $\{x\} = \{0\} = 0$, $\{y\} = \{2,2\} = 0,2$, $\{z\} = \{1,1\} = 0,1$.
Осталось найти целые части неизвестных. Прежде всего заметим, что
$$
\lfloor x \rfloor + \lfloor y \rfloor + \lfloor z \rfloor = (x+y+z) - (\{x\}+\{y\}+\{z\})
$$
так что, учитывая $\eqref{eq:0801}$,
$$
\lfloor x \rfloor + \lfloor y \rfloor + \lfloor z \rfloor = 3 \label{eq:0802}\tag{3.8.2}
$$
Далее, заменив в первом из заданных уравнений $x$ на $\lfloor x \rfloor + \{x\}$ и подставив известные значения $\{x\}$ и $\{z\}$,
получим:
$$
\lfloor x \rfloor + \lfloor y \rfloor = 1
$$
откуда, в силу $\eqref{eq:0802}$, $\lfloor z \rfloor=2$. Аналогично получаем $\lfloor x \rfloor=1$, $\lfloor y \rfloor=0$.
Ответ: $x=1;\;y=0,2;\;z=2,1$.
3.9Сколько целых чисел $n$, удовлетворяющих условию
$\displaystyle
\left\lfloor\sqrt{\left\lceil\sqrt{n}\,\right\rceil}\right\rfloor = \left\lceil\sqrt{\left\lfloor\sqrt{n}\right\rfloor}\,\right\rceil
$ существует в диапазоне от 1 до 10000 включительно?
Свежая задача из "The Harvard-MIT Mathematics Tournament", ноябрь 2017. Откровенно говоря, я не люблю задачи,
требующие что-то подсчитать, так как в них действительно легко, цитируя красноречивого В. Сойфера (см комментарий к задаче 2.4), «подловиться на пустячке». Однако в таких задачах есть определенная польза, так как они «ум в порядок приводят», приучая мыслить взвешенно и без суеты.
Ввиду свойства 2аc, $\left\lfloor\sqrt{n}\right\rfloor \leqslant \left\lceil\sqrt{n}\right\rceil$, причем равенство
имеет место тогда и только тогда, когда $\sqrt{n}$ — целое число. Поэтому рассмотрим два случая.
а) Если $t=\sqrt{n}$ — целое число, то $\lfloor\sqrt{n}\rfloor = \lceil\sqrt{n}\rceil = t$, поэтому уравнение задачи записывается в виде:
$$
\left\lfloor\sqrt{t}\right\rfloor = \left\lceil\sqrt{t}\right\rceil
$$
что возможно тогда и только тогда, когда $k=\sqrt{t}$ — целое число. Таким образом $t=k^2$, откуда $n=k^4$ — четвертая степень целого числа.
Так как $10000=10^4$, в интересующем нас промежутке существует 10 чисел вида $k^4$: 1, 16, 81, ... 10000.
b) Пусть $\sqrt{n}$ не является целым числом и $t=\left\lfloor\sqrt{n}\right\rfloor$. Тогда
$$
t \lt \sqrt{n} \lt t+1 \label{eq:0901}\tag{3.9.1}
$$
В этом случае $\left\lfloor\sqrt{n}\right\rfloor=t$, $\left\lceil \sqrt{n} \right\rceil = t+1$, так что условие задачи принимает вид:
$$
\left\lceil\sqrt{t}\right\rceil = \left\lfloor\sqrt{t+1}\right\rfloor \label{eq:0902}\tag{3.9.2}
$$
Если $k$ — общее значение правой и левой частей равенства $\eqref{eq:0902}$, получаем:
$$
\sqrt{t} \leqslant k \leqslant \sqrt{t+1} \label{eq:0903}\tag{3.9.3}
$$
при этом из $\sqrt{t+1} - \sqrt{t} = \frac{1}{\sqrt{t+1} + \sqrt{t}} \lt 1$ следует, что равенство $\eqref{eq:0903}$ является достаточным для выполнения $\eqref{eq:0902}$.
Возведение в квадрат дает: $t \leqslant k^2 \leqslant t+1$, откуда $k^2-1 \leqslant t \leqslant k^2$, , таким образом,
$t=k^2-1$ или $t=k^2$.
Подстановка полученных значений $t$ в $\eqref{eq:0901}$ с последующим возведением в квадрат показывает, что должно быть выполнено одно из следующих неравенств:
$$
\left.
\begin{matrix}
(k^2-1)^2 \lt n \lt k^4 \\
k^4 \lt n \lt (k^2+1)^2
\end{matrix}
\right. \label{eq:0904}\tag{3.9.4}
$$
Добавление к набору неравенств $\eqref{eq:0904}$ чисел вида $k^4$, полученных при рассмотрении случая a), скрепляет неравенства в одно:
$$
(k^2-1)^2 \lt n \lt (k^2+1)^2
$$
Подсчитаем количество чисел, соответствующих $k$. Самое малое из таких равно $(k^2-1)^2+1=k^4-2k^2+2$,
а самое большое — это $(k^2+1)^2-1=k^4+2k^2$, поэтому количество чисел равно $p_k=(k^4+2k^2)-(k^4-2k^2+2)+1=4k^2-1$.
Осталось просуммировать $p_k$ для $k$ от 1 до 10 ... стоп! Здесь не следует суетиться, а проявить ту самую взвешенность,
о которой говорилось ранее. Дело в том, что при $k=10$ чи́сла бо́льшие $k^4$ превышают 10000, так что в этом случае у нас есть
только $k^4-(k^4-2k^2+2)+1 = 2k^2-1=199$ чисел.
Теперь можно суммировать. При этом используется формула суммы квадратов первых $n$ чисел: $1^2+2^2+...+n^2 = \dfrac{n(n+1)(2n+1)}{6}$ (которую можно доказать, например, по индукции).
$$
P_{10} = p_1+p_2+...+p_9+199 = (4 \cdot 1^2-1) + (4 \cdot 2^2-1) + ... + (4 \cdot 9^2-1) + 199 =\\
4(1^2+2^2+...+9^2)-9+199 =
4 \cdot \frac{9 \cdot 10 \cdot 19}{6}+190=1330
$$
Из чистого любопытства подсчитаю количество чисел, удовлетворяющих условию задачи среди первых $n^4$ чисел:
$$
P_{n}=4\frac{(n-1)n[2(n-1)+1]}{6}-(n-1)+2n^2-1=\frac{2(n-1)n(2n-1)}{3}+n(2n-1)=\\
\frac{(2n-2+3)n(2n-1)}{3}=\frac{n(4n^2-1)}{3}
$$
Подставьте сюда $n=10$ и получите точно по ответу. Признаться, формула оказалась гораздо проще, чем я ожидал.
