Results 1 to 7 of 7

Math Help - Two questions

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    16

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2009
    Posts
    16
    No one knows?

    I think the 7-digit one might be using the nCr rule but I haven't solved satisfactorily yet
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539
    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.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2009
    Posts
    16
    Can anyone help with Q1?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Denny Crane View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Denny Crane View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by tonio View Post
    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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. More log questions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 31st 2010, 04:58 PM
  2. Please someone help me with just 2 questions?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 4th 2009, 04:55 AM
  3. Some Questions !
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 3rd 2009, 03:09 AM
  4. Replies: 4
    Last Post: July 19th 2008, 07:18 PM
  5. Replies: 3
    Last Post: August 1st 2005, 01:53 AM

Search Tags


/mathhelpforum @mathhelpforum