## Tomas.A 3 years ago How to prove that in group of 6 people there are at least 2 people who has same amount of friends among that group?

1. rld613

LOL

2. Tomas.A

whats so lol

3. rld613

R u sure it cld be proved

4. Tomas.A

of course it is

5. rld613

oh i see didnt read the question correctly

6. Tomas.A

it's classical problem and i have proved it somehow but i don't remember anymore

7. amistre64

do the 6 people even have to be friends? after all, a group of 6 strangers is still a group of 6

8. Tomas.A

no, but if they don't have any friends there will be 6 people who have no friends

9. amistre64

if 2 people in the group are friends; then at least 2 people have 1 friend .... something like that

10. amistre64

if 3 people are friends, then a > bc, b > ac, c>ba

11. amistre64

thats at least 2 with the same amount of friends

12. amistre64

or even a>c , c>b, c>ab

13. Tomas.A

well i translated it from lithuanian but it seems it has same meaning

14. amistre64

can 2 people be not friends? if one of them is a friend?

15. JamesJ

oh wait, I see. Let f(n) be the number of friends in that group that the nth person has. For each n, $0 \leq f(n) \leq 5$ Therefore ...

16. amistre64

a>c, b>c , c>ab is what i meant lol

17. Tomas.A

yes there can be no friends at all or 1 person can have no friends

18. amistre64

I think James has it :)

19. amistre64

even if 4 are friends, that still leaves 2 with 0 friends each which is the same amount

20. JamesJ

there are 6 values for f(1), f(2), f(3), f(4), f(5), f(6). Now it can't be that these six number take on all of 0,1,2,3,4,5. Because if f(n) = 5 for one n, then f(j) > 0 for all other $$j \neq n$$. Hence in fact, there are only 5 possible values for f(n). But as there are six f(n), at least two of the f(n) must be equal.

21. amistre64

ill concede to that answer as well ;)

22. amistre64

my by case proof could get lengthy

23. amistre64

gotta hang it on the left to be a valid q lol

24. amistre64

and I gotta get my ode hw written up so ciao yall :)