| Описание и условия задач |
Решения задач части 1 |
Решения задач части 2 |
Решения задач части 3 |
Решения задач части 4 |
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 |
Решения задач части 2 |
Решения задач части 3 |
Решения задач части 4 |
Комментариев нет:
Отправить комментарий