Разделы 
Дополнительно
Задача по математике - 3156
2019-05-26 
У Пети всего 28 одноклассников. У каждых двух из 28 различное число друзей в этом классе. Сколько друзей у Пети?
Решение:
У одноклассников Пети может быть $0, 1, 2, \cdots, 28$ друзей - всего 29 вариантов. Но, если кто-то дружит со всеми, то у всех не меньше одного друга. Поэтому либо есть такой, кто дружит со всеми, либо есть такой, кто не дружит ни с кем. В обоих случаях остается 28 вариантов: $1, 2, \cdots, 28$ или $0, 1, \cdots, 27$.
Обозначим того, у кого больше всего друзей через $A$, а того, у кого их меньше всего - через $B$. В первом случае $A$ дружит со всеми, а $B$ - только с одним человеком, т. е. только с $A$. Во втором случае $B$ не дружит ни с кем, а $A$ дружит со всеми, кроме одного, т. е. со всеми, кроме $B$.
Итак, в каждом из случаев $A$ дружит с Петей, а $B$ - нет. Переведем $A$ и $B$ в другой класс. Как мы уже видели, $A$ дружит со всеми из оставшихся, а $B$ - ни с кем из оставшихся. Поэтому после перевода у каждого стало на одного друга меньше (среди одноклассников). Значит, у оставшихся Петиных одноклассников снова будет разное число друзей среди одноклассников.
Теперь снова переведем самого «дружелюбного» и самого «нелюдимого» в другой класс и т. д.
Повторяя эти рассуждения 14 раз, мы переведем в другой класс 14 пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети 14.
Комментарии.
1. В решении «работают» несколько идей: симметрия дружбы, принцип крайнего, индуктивный спуск.
2. Есть очень короткое, но неправильное решение: пусть у Пети $x$ друзей. Поссорим всех друзей, а тех, кто не был друзьями подружим, тогда у Петиных одноклассников снова будет разное число друзей, и значит, у Пети снова $x$ друзей. Получаем уравнение $x = 28 - x$. Где ошибка? Если бы было доказано, что ответ в задаче единственен, то рассуждение было бы верным. Тем не менее, это рассуждение позволяет угадать ответ.
3. Решите задачу, если у Пети 27 одноклассников.
4. Эта задача является продолжением другой известной задачи: докажите, что в любой компании найдутся двое, у которых одинаковое число друзей в этой компании (возможно, ни одного).
Ответ: У Пети 14 друзей.
У Пети всего 28 одноклассников. У каждых двух из 28 различное число друзей в этом классе. Сколько друзей у Пети?
Решение:
У одноклассников Пети может быть $0, 1, 2, \cdots, 28$ друзей - всего 29 вариантов. Но, если кто-то дружит со всеми, то у всех не меньше одного друга. Поэтому либо есть такой, кто дружит со всеми, либо есть такой, кто не дружит ни с кем. В обоих случаях остается 28 вариантов: $1, 2, \cdots, 28$ или $0, 1, \cdots, 27$.
Обозначим того, у кого больше всего друзей через $A$, а того, у кого их меньше всего - через $B$. В первом случае $A$ дружит со всеми, а $B$ - только с одним человеком, т. е. только с $A$. Во втором случае $B$ не дружит ни с кем, а $A$ дружит со всеми, кроме одного, т. е. со всеми, кроме $B$.
Итак, в каждом из случаев $A$ дружит с Петей, а $B$ - нет. Переведем $A$ и $B$ в другой класс. Как мы уже видели, $A$ дружит со всеми из оставшихся, а $B$ - ни с кем из оставшихся. Поэтому после перевода у каждого стало на одного друга меньше (среди одноклассников). Значит, у оставшихся Петиных одноклассников снова будет разное число друзей среди одноклассников.
Теперь снова переведем самого «дружелюбного» и самого «нелюдимого» в другой класс и т. д.
Повторяя эти рассуждения 14 раз, мы переведем в другой класс 14 пар школьников, в каждой из которых ровно один Петин друг. Итак, друзей у Пети 14.
Комментарии.
1. В решении «работают» несколько идей: симметрия дружбы, принцип крайнего, индуктивный спуск.
2. Есть очень короткое, но неправильное решение: пусть у Пети $x$ друзей. Поссорим всех друзей, а тех, кто не был друзьями подружим, тогда у Петиных одноклассников снова будет разное число друзей, и значит, у Пети снова $x$ друзей. Получаем уравнение $x = 28 - x$. Где ошибка? Если бы было доказано, что ответ в задаче единственен, то рассуждение было бы верным. Тем не менее, это рассуждение позволяет угадать ответ.
3. Решите задачу, если у Пети 27 одноклассников.
4. Эта задача является продолжением другой известной задачи: докажите, что в любой компании найдутся двое, у которых одинаковое число друзей в этой компании (возможно, ни одного).
Ответ: У Пети 14 друзей.
