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

1. rld613 Group Title

LOL

2. Tomas.A Group Title

whats so lol

3. rld613 Group Title

R u sure it cld be proved

4. Tomas.A Group Title

of course it is

5. rld613 Group Title

oh i see didnt read the question correctly

6. Tomas.A Group Title

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

7. amistre64 Group Title

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 Group Title

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

9. amistre64 Group Title

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

10. amistre64 Group Title

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

11. amistre64 Group Title

thats at least 2 with the same amount of friends

12. amistre64 Group Title

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

13. Tomas.A Group Title

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

14. amistre64 Group Title

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

15. JamesJ Group Title

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 Group Title

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

17. Tomas.A Group Title

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

18. amistre64 Group Title

I think James has it :)

19. amistre64 Group Title

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

20. JamesJ Group Title

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 Group Title

ill concede to that answer as well ;)

22. amistre64 Group Title

my by case proof could get lengthy

23. amistre64 Group Title

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

24. amistre64 Group Title

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