Разделы 
Дополнительно
Задача по математике - 1462
2019-01-03 
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более, чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
Решение:
Докажем утверждение задачи индукцией по $n$ — числу жителей города. При $n \leq 2$ утверждение очевидно. Пусть $n \geq 3$, а $m$ - общее количество звонков в этот день. По условию $m \ \leq n$, поэтому найдется житель $N$ города, разговаривавший не более, чем с двумя жителями (в противном случае $m \geq \frac{3n}{2} > n$. По предположению индукции, всех жителей города, кроме N, можно разбить на три группы так, чтобы выполнялось условие задачи. Житель $N$ не разговаривал с жителями, входящими в одну из групп, поэтому его можно добавить к этой группе, сохранив в силе требуемое утверждение.
В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более, чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону.
Решение:
Докажем утверждение задачи индукцией по $n$ — числу жителей города. При $n \leq 2$ утверждение очевидно. Пусть $n \geq 3$, а $m$ - общее количество звонков в этот день. По условию $m \ \leq n$, поэтому найдется житель $N$ города, разговаривавший не более, чем с двумя жителями (в противном случае $m \geq \frac{3n}{2} > n$. По предположению индукции, всех жителей города, кроме N, можно разбить на три группы так, чтобы выполнялось условие задачи. Житель $N$ не разговаривал с жителями, входящими в одну из групп, поэтому его можно добавить к этой группе, сохранив в силе требуемое утверждение.
