Author |
Topic: Yet another pigeonhole (Read 541 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Yet another pigeonhole
« on: May 16th, 2008, 9:07pm » |
 Quote  Modify
|
Show that every set of 90 numbers selected from {1,...,2008} contains four different numbers such that the sum of two of the four equals the sum of the remaining two.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Yet another pigeonhole
« Reply #1 on: May 17th, 2008, 1:49am » |
Quote Modify
|
I would use the pigeonhole principle  .
Create the set of all ordered pairs of 2 numbers chosen among the 90.
That set has 90*89/2 = 4005 elements.
Now compute the sum of each pair.
The minimum total is 3, the maximum is 2008+2007 = 4015, that is 4013 possible values.
Then uh.....
Well, the idea was to find 4013<4005 so that there would have been an a+b and c+d such that a+b=c+d.
But there are still too many holes and too little pigeons.
Back to the drawing board...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Yet another pigeonhole
« Reply #2 on: May 17th, 2008, 7:01am » |
Quote Modify
|
on May 17th, 2008, 1:49am, Grimbal wrote:| I would use the pigeonhole principle . |
|
So would I:
Again, start with the set of 4005 distinct pairs, but, rather than computing their sums, compute their differences.
Take any pair, (a,b) with a-b=x. For any pair, (c,d) with c-d=x, a+d=a+(c-x)=(a-x)+c=b+c, so when (a,b,c,d) are all distinct, any repeated pairwise difference gives you the set of four numbers.
There are three ways (a,b,c,d) can have repeated values:
a=c,b=d - which means that (a,b) and (c,d) are the same pair
a=d, b=c-2x
b=c, a=d+2x
The latter two each allow a different pair from (a,b) to share the same difference without giving a set of four by having one element in common - forming an arithmetic progression of three elements, (i,j,k). Extending the progression to a fourth element, (i,j,k,l), gives two non-overlapping pairs with the same difference, so gives a set of four.
So, to avoid having a set of four with the required property, each difference can occur at most twice. There are 2007 possible differences (from 1 to 2008-1), but, a repeated difference must be less than or equal to half the maximum possible difference, so only 1003 differences can repeat, accounting for at most 2007+1003=3010 pairs, so any subset of 79 or more numbers (79*78/2=3081 pairs) must contain a set of four with a shared pairwise sum.
I suspect ecoist may have had another proof in mind since my result is stronger than required
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Yet another pigeonhole
« Reply #3 on: May 17th, 2008, 10:08am » |
Quote Modify
|
Right, rmsgrey! My proof was lazily based on the earlier pigeonhole concerning parallelograms on a checkerboard. I knew my proof was weak because it required 11 numbers from {1,...,30}; yet it seems that 9 is sufficient. Even smaller than the 10 your argument requires!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print