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: .$\displaystyle \{0,2,2,4,8,8,8\}$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: .$\displaystyle \frac{7!}{2!\,3!} \:=\:\boxed{420}$ 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 $\displaystyle \{2,2,4,8,8,8\}$ can be arranged in: .$\displaystyle \frac{6!}{21\,3!} \:=\:60$ ways.
There are 60 numbers that begin with 0.
Therefore, there are: .$\displaystyle 420 - 60 \:=\:\boxed{360}$ 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
Thanks Tonio.
Am I correct in saying this too for this problem -
there is atleast one student with 16 or more friends. I am getting this based on logic I wrote but not too sure of my calcultion.
Essentially e=number of edges, I am getting as
$\displaystyle \frac{25C_32}{23}$