Thread: 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?

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.

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.