wu :: forums - Print Page


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

        riddles >> easy >> 2007x2007 grid of odd numbers
        
(Message started by: Aryabhatta on May 22^nd, 2007, 7:17pm)

Title: 2007x2007 grid of odd numbers
Post by Aryabhatta on May 22^nd, 2007, 7:17pm

A problem from Australian National Olympiad 2007.

There is a 2007x2007 grid of odd integers.

A is the product of row sums and B is the product of column sums.

Show that A+B cannot be zero.

Title: Re: 2007x2007 grid of odd numbers
Post by JP05 on May 23^rd, 2007, 4:35pm

Isn't stating a 2007x2007 grid of anything is like throwing dust in our eyes unless that dimension is really relevant? I surmise that the result is true for KxK much less (can you see it?).

Title: Re: 2007x2007 grid of odd numbers
Post by Aryabhatta on May 23^rd, 2007, 5:53pm

on 05/23/07 at 16:35:44, JP05 wrote:

Isn't stating a 2007x2007 grid of anything is like throwing dust in our eyes unless that dimension is really relevant? I surmise that the result is true for KxK much less (can you see it?).

This was how the problem was stated. (The problem makers usually try to be cute and try to work in the year into the problem statement somehow)

btw, it is not true for K=2. For instance consider

[1 -1]
[-1 777]

For this matrix, A = B = 0.

Title: Re: 2007x2007 grid of odd numbers
Post by JP05 on May 23^rd, 2007, 6:06pm

Why did you pick K=2? Don't you think that an odd dimension is important?

Title: Re: 2007x2007 grid of odd numbers
Post by Icarus on May 23^rd, 2007, 8:46pm

He picked k=2 because it doesn't work for k=2. Since his point was to show that not all dimensions work, one for which it fails is quite important to the counter-example.

It is easy to see that his counter-example extends to all even dimensions, so yes, odd dimensions are quite necessary for this to work. With odd dimensions, it is easy to see that both A and B are odd, so neither can be zero. Unfortunately, this means A+B is even, so it doesn't solve the puzzle yet.

Title: Re: 2007x2007 grid of odd numbers
Post by ecoist on Jun 11^th, 2007, 9:59am

I just found a solution, but I think it is too soon to post it. Unless Aryabhatta disagrees.

Title: Re: 2007x2007 grid of odd numbers
Post by towr on Jun 11^th, 2007, 10:30am

I don't think two weeks after the last post is too soon..
You could also just drop a few (hidden, or not) clues to your solution in the meanwhile.

Title: Re: 2007x2007 grid of odd numbers
Post by ecoist on Jun 11^th, 2007, 10:37am

Ok. Hope this is not too big a hint. If this one doesn't help, I have a bigger hint.

[hideb]Although congruence modulo 2 doesn't work, congruence modulo __ does work.[/hideb]

Title: Re: 2007x2007 grid of odd numbers
Post by Aryabhatta on Jun 11^th, 2007, 12:43pm

on 06/11/07 at 09:59:36, ecoist wrote:

I just found a solution, but I think it is too soon to post it. Unless Aryabhatta disagrees.

No problems :)

Title: Re: 2007x2007 grid of odd numbers
Post by Grimbal on Jun 11^th, 2007, 3:41pm

What I would do if I didn't have to go to sleep:
[hide]Consider all calculations mod 4.

All numbers are +1 or -1 (also known as 3), The sum of a row is also +1 or -1 and it depends on the number of -1's. When you make the product, it also depends on the number of -1 rows. Altogether, I'd say the product of the sums depends on whether the number of -1's is even or odd. A and B are both +1 or -1, and must be equal. They can not sum up to 0 (mod 4).
[/hide]

Title: Re: 2007x2007 grid of odd numbers
Post by ecoist on Jun 11^th, 2007, 4:34pm

I guess my bigger hint is now moot! Someone may post a solution before Grimbal wakes up!

Title: Re: 2007x2007 grid of odd numbers
Post by ecoist on Jun 13^th, 2007, 6:05am

Wow! No solution yet? Here's a disguised hint.

One way to make this problem suitable for 2008 is to consider a 2008x2008 grid of odd integers except with zeros on the main diagonal. Another is to consider a set of 2008 odd integers split two ways into two sets, each containing an odd number of integers(e.g., split into two sets, one with 1003 elements, the other with 1005 elements; or, one with 17 elements, the other with 1931 elements). Let A be the product of the sums of the integers in each set for one partition and let B be the product of the sums of the numbers in each set of the second partition. Show that A+B cannot be zero.

Title: Re: 2007x2007 grid of odd numbers
Post by ecoist on Jun 14^th, 2007, 9:46am

[hideb]As Grimbal suggested, consider the entries in the grid modulo 4. Each is congruent to 1 or -1 modulo 4. If we change the sign of one of the entries in the grid (or add two), that changes the sign of the row sum containing the entry modulo 4 and so changes the sign of the product of the row sums modulo 4. Similarly, the change changes the sign of the product of the column sums modulo 4. Hence A+B becomes -(A+B), which is just A+B modulo 4 because A+B is even (as Grimbal showed). Since such a change has no effect modulo 4 on A+B, we can change the signs of appropriate entries until all entries are 1 modulo 4, whose A+B is congruent to 2 modulo 4 (see Grimbal). Hence, for all grids of odd integers, A+B cannot be zero.[/hideb]

Title: Re: 2007x2007 grid of odd numbers
Post by Aryabhatta on Jun 19^th, 2007, 9:25am

Well done ecoist. I had something similar.

Title: Re: 2007x2007 grid of odd numbers
Post by ecoist on Jun 19^th, 2007, 10:01am

Thanks, Aryabhatta. Thought of another variation for 2008.

~~Arrange 2008 odd integers into an 8x251 array M. Let a be the product of the row sums of M and let b be the sum of the column products of M. Show that a+b is never zero~~.

Once again, I spoke too soon! My argument fails for this variation. Apologies to all. Could it still be true?