1. Among any group of three students in a class of 25, two of them are friends. Show there is a student with at least 12 friends.
2. How many different 7-digit numbers can be made by rearranging these digits in this number: 8028842
Hello, Denny!
#2 involves permutations . . .
We have: .2. How many different 7-digit numbers can be made by rearranging
the digits in the number: 8028842
If the 7-digit number can have a leading zero,
. . there are: . possible numbers.
If the 7-digit number cannot have a leading zero,
. . count the numbers that do begin with zero.
The number begins with 0: .0 _ _ _ _ _ _
. . Then can be arranged in: . ways.
There are 60 numbers that begin with 0.
Therefore, there are: . numbers that do not begin with 0.
Let's see. I guess we need to proceed in the following way -
if a graph with a vertex = student and an edge if and only if the two students represented by the vertexes are friends is constructed - how many edges would we have under the condition that any three students have 'exactly' two are friends? let this number be 'e'
now let us keep a counter, n = n1+n2...+ni+....+n25
where ni - number of friends of the ith student
it is clear the 2e=n
if no student has 12 or more friends then max(n) = 25*11
we need to show that 2e>25*11 thus by pigeon hole principle atleast one student will have more than 11 friends.
I am not sure if there is any other direct way
1.- You can do it amost playing: We have 25 people: P_1,...,P_25 and supose no one there has at least 12 friends ==> everybody has at most 11 friends.
Assume the friends of P_1 are P_2,P_3,...,P_12 (since the indexes are arbitrary we can attach them to whomever we want), and now let's see who're the friends of P_13 (who is NOT one of P_1's friends!): no matter who the friends of P_13, there is at least one OTHER person, call it P_n (of course, n is not 13 and not 1), who is not friends with neither with P_1 nor with P_13 ==> the set {P_1, P_13, P_n} doesn't fulfill the problem's condition.
Tonio