# Math Help - Two questions

1. ## Two questions

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

2. No one knows?

I think the 7-digit one might be using the nCr rule but I haven't solved satisfactorily yet

3. Hello, Denny!

#2 involves permutations . . .

2. How many different 7-digit numbers can be made by rearranging
the digits in the number: 8028842
We have: . $\{0,2,2,4,8,8,8\}$

If the 7-digit number can have a leading zero,
. . there are: . $\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 $\{2,2,4,8,8,8\}$ can be arranged in: . $\frac{6!}{21\,3!} \:=\:60$ ways.
There are 60 numbers that begin with 0.

Therefore, there are: . $420 - 60 \:=\:\boxed{360}$ numbers that do not begin with 0.

4. Can anyone help with Q1?

5. Originally Posted by Denny Crane
Can anyone help with Q1?

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

6. Originally Posted by Denny Crane
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

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

7. Originally Posted by tonio
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

$\frac{25C_32}{23}$