2019-04-29
На заседании присутствуют несколько человек (разумеется, больше одного человека - иначе какое же это было бы «заседание»?).
а) Может ли быть, что никакие двое из присутствующих не имеют одинакового числа знакомых?
б) Доказать, что при любом числе участников заседания может случиться так, что никакие трое из присутствующих не имеют одинакового числа знакомых.
Решение:
а) Каждое из $N$ присутствующих лиц может иметь $0, 1, 2,\cdots, N-1$ знакомых. Здесь мы имеем $N$ возможных значений числа знакомых; однако если некто имеет 0 знакомых, то никто не имеет $N - 1$ знакомых (и наоборот - если некто имеет $N-1$ знакомого, то никто не имеет 0 знакомых). Отсюда уже следует, что двое лиц с одним и тем же числом знакомых обязательно существуют.
б) Занумеруем присутствующих на заседании $N$ лиц номерами $1, 2,\cdots, N$ и рассмотрим такое «распределение знакомств»: пусть для всех значений $i = 0, 1, 2, \cdots$, где $i< \frac{N}{2}$, лицо с номером $N - i$ знакомо со всеми лицами, кроме первых $i$ лиц (т. е. $N$-e лицо знакомо со всеми без исключения; ($N - 1$)-е - со всеми, кроме 1-го лица; ($N - 2$)-е - со всеми, кроме 1-го и 2-го; ...); все же лица с номерами $i$, где $i \leq i \leq \frac{N + 1}{2}$ между собой незнакомы, В таком случае, при $N = 3$, очевидно, 1-е и 2-е лица знакомы лишь с 3-м, а 3-е лицо имеет двух знакомых; аналогично, при $N = 4$ 1-е лицо знакомо лишь с 4-м; 2-е - с 4-м и с 3-м; 3-е - с 4-м и со 2-м; 4-е имеет трех знакомых. Точно так же можно убедиться, что при $N = 2k+l$ нечетном числа $n_i$ знакомых у $i$-ro лица имеют значения: $n_1 = 1, n_2 = 2, \cdots, n_k = k, n_{к+1} = k + 1, n_{k+ 2} = k + 1, \cdots, n_N = N - 1$, а при $N = 2k + 2$ четном $n_1 = 1, n_2 = 2, \cdots, \cdots, n_{k+l} = k + 1, n_{k+2} = k + 1, n_{k+3} = k + 2, \cdots, n_N = N - 1$. Таким образом, здесь во всех случаях никакие трое лиц не имеют одинакового числа знакомых.
Ответ: а) Не может, б) Постройте пример удовлетворяющего условиям задачи «распределения знакомств».