wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Yet another pigeonhole
        
(Message started by: ecoist on May 16^th, 2008, 9:07pm)

Title: Yet another pigeonhole
Post by ecoist on May 16^th, 2008, 9:07pm

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.

Title: Re: Yet another pigeonhole
Post by Grimbal on May 17^th, 2008, 1:49am

I would use the pigeonhole principle ::).
[hide]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...
[/hide]

Title: Re: Yet another pigeonhole
Post by rmsgrey on May 17^th, 2008, 7:01am

on 05/17/08 at 01:49:39, Grimbal wrote:

I would use the pigeonhole principle ::).

So would I:

[hide]
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.[/hide]

I suspect ecoist may have had another proof in mind since my result is stronger than required

Title: Re: Yet another pigeonhole
Post by ecoist on May 17^th, 2008, 10:08am

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!