[Archive!] Pure mathematics, physics, chemistry, etc.: brain-training problems not related to trade in any way

Sceptic Philozoff  

The problem is from the Mechmatov forum, here.

Петя заметил, что у всех его 25 одноклассников различное число друзей в этом классе. Сколько друзей может быть у Пети?


1. Petya is also in this class, i.e. there are 26 people in total in the class.
2. If A is friends with B, then B is friends with A.

Find all solutions.

In the same branch the solution is given - 12 or 13.

Such a categorical answer is astonishing. I began to ponder at my leisure and came to some conclusions. But it's a long way to solving the problem. Whoever is interested, join me.

But please don't google and rable, or it will become uninteresting. Surely the problem is solved elementary.

RomanS >>:
от 0 до 25

oh yeah.....

12 or 13 is the golden mean....

Sergey Pavlov  
Mathemat писал(а) >>
I don't think more than 5, more likely 4.
Sceptic Philozoff  

OK, let's start to get a grip on something. Let's divide the class into two sets, {Petya} and {Other} (there are 25 of them). A person who has N friends, for convenience we will call "N".

Suppose Petya has 0 friends. Then {Other} can have from 0 to 24 without repetition (a person "25" cannot exist, since he must be friends with everyone, and we already have Petya, who is "0").

But there can't be a person "24" either, as we have two "0's" who are not friends with anyone, and therefore he is not friends with both of them either.

Consequently, for 25 {Others}, only options from 0 to 23 remain. Contradiction.

Similarly, it is proved that Petya cannot have 25 friends (if it were, then {Other} is from "1" to "25". But two people "25" and the existing "1" is a contradiction, since "1" would have to be friends with both "25").

More subtle reasoning shows that Petya cannot have and only 1 friend. And then I'm stalled.

Is Petya an adult? What category do mistresses fall into? :)
Sceptic Philozoff  

Svetik, mistresses meet the same requirements as friends: if A is B's lover, then B is A's lover, so let's consider Petya an adult.

Mathemat >>:

Продолжаем пьянку. Очевидно, что во множестве {Остальных} не может быть одновременно людей "0" и "25". Следовательно, {Остальные} могут иметь только две возможные конфигурации - либо от "0" до "24", либо от "1" до "25".

If binge drinking, 25-(I can't think of exactly 1 to 3). It seems to me that the condition "that all his 25 classmates have a different number of friends in that class" would be met in this case. But that's without taking into account the sexual relationships.

Or maybe not :o)