Results 1 to 3 of 3

Math Help - Problem/Question

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Brussels
    Posts
    4

    Problem/Question

    John opens a store, he has 20 clients, all of the clients are younger than 70 and they all have a different age.
    John sees that there's a same age difference 4 times.
    Prove that this always will happen.

    I really don't know how I could prove this, does someone have any ideas?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Problem/Question

    Try to build the most efficient "packing of ages", and show that it can't be done if the same age difference only shows up at most 3 times.
    Let's assume age 0 is included, as that represents a person (a baby) prior to his or her first birthday.
    Begin
    For Difference = 1: 0, 1, 2, 3.
    Age difference 1 occurs 3 times (0~1, 1~2, 2~3). Note that age difference 2 occurs twice (0~2, 1~3) and that age difference 3 occurs once (0~3). Thus can have at most 1 more age difference 2, and 2 more age difference 3.
    Having put in age difference 1, try to efficiently (meaning keeping the ages used as small as possible, so as to pack as many in as possible) put in age difference 2. We couldn't use 4, because then 3~4 would be a 4th instance of age difference 1. Thus
    For Difference = 2: 5.
    We now have 3 instances of age difference 2: (0~2, 1~3, 3~5). Note that we now also have 2 instances of age difference 3: (0~3, 2~5) and one of age difference 4 (1~5) and one of age difference 5 (0~5).
    To try difference = 3 case, we can't have any new difference = 1 or 2, so only thing to try is 8:
    Difference = 3: 8.
    We now have 3 instances of age difference 3: (0~3, 2~5, 5~8). Also: one of age difference 8 (0~8), one of age difference 7 (1~8), one of age difference 6 (2~8), two of age difference 5 (0~5, 3~8) and one of age difference 4 (1~5).
    Difference = 4: 12, 16.
    We now have 3 instances of age difference 4: (1~5, 8~12, 12~16).

    Summary so far: Maximal packing has ages {0, 1, 2, 3, 5, 8, 12, 16}
    age difference 16 (0~16)
    age difference 15 (1~16)
    age difference 14 (2~16)
    age difference 13 (3~16)
    age difference 12 (0~12)
    age difference 11 (1~12, 5~16)
    age difference 10 (2~12)
    age difference 9 (3~12)
    age difference 8 (0~8, 8~16)
    age difference 7 (1~8, 5~12)
    age difference 6 (2~8)
    age difference 5 (0~5, 3~8)
    age difference 4 (1~5, 8~12, 12~16)
    age difference 3 (0~3, 2~5, 5~8)
    age difference 2 (0~2, 1~3, 3~5)
    age difference 1 (0~1, 1~2, 2~3)

    OK, that's more than enough. Now, the next step, rather than continuing (which we could), is to realize that, AT BEST (meaning packing as many in as possible), for difference 5 we'll have 3 instances of +5 on the previous highest. Then for difference 6 we'll have 3 instances of +5 on the previous highest, etc.. This is obviously way underestmmates the actual minimal ages, (for insatnce, we're only going to have one more number to create an age difference of 5, not 3 more numbers. OK - that means that things I was calling 5's are really 6's, or higher, which means we've underestimated - which is fine).

    Maximal packing, 1st 8 people ages = {0, 1, 2, 3, 5, 8, 12, 16}
    At BEST, next three (for diff = 5) are 16+5, 16+10, 16+15 = 21, 26, 31
    At BEST, next three (for diff = 6) are 31+ 6, 31+12, 31+18 = 37, 43, 47
    At BEST, next three (for diff = 7) are 47+7, 47+14, 47+21 = 54, 61, 68
    At BEST, next ONE (for diff = 8) are 68+8 = 76.

    Thus the absolute lowest age for the 18th person is at least 76. In fact, it's going to be much more than 76, but that's good enough to solve the problem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2012
    From
    Brussels
    Posts
    4

    Re: Problem/Question

    So this is a prove that its imposible that there isnt a difference occurring 4 times? So the answer should be: There will always be a difference uccurring 4 times unless the 2 last people are older than 75? Thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question/ Problem
    Posted in the Statistics Forum
    Replies: 0
    Last Post: July 21st 2010, 01:04 PM
  2. Problem with this question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 29th 2009, 06:47 AM
  3. Replies: 3
    Last Post: April 13th 2009, 05:42 PM
  4. i have got a problem with this question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 24th 2005, 07:53 AM

Search Tags


/mathhelpforum @mathhelpforum