Author |
Topic: 2007x2007 grid of odd numbers (Read 1997 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
2007x2007 grid of odd numbers
« on: May 22nd, 2007, 7:17pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
JP05
Guest
|
|
Re: 2007x2007 grid of odd numbers
« Reply #1 on: May 23rd, 2007, 4:35pm » |
Quote Modify
 Remove
|
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?).
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 2007x2007 grid of odd numbers
« Reply #2 on: May 23rd, 2007, 5:53pm » |
Quote Modify
|
on May 23rd, 2007, 4:35pm, 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.
|
| « Last Edit: May 23rd, 2007, 5:53pm by Aryabhatta » |
IP Logged |
|
|
|
JP05
Guest
|
|
Re: 2007x2007 grid of odd numbers
« Reply #3 on: May 23rd, 2007, 6:06pm » |
Quote Modify
Remove
|
Why did you pick K=2? Don't you think that an odd dimension is important?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 2007x2007 grid of odd numbers
« Reply #4 on: May 23rd, 2007, 8:46pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2007x2007 grid of odd numbers
« Reply #5 on: Jun 11th, 2007, 9:59am » |
Quote Modify
|
I just found a solution, but I think it is too soon to post it. Unless Aryabhatta disagrees.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 2007x2007 grid of odd numbers
« Reply #6 on: Jun 11th, 2007, 10:30am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2007x2007 grid of odd numbers
« Reply #7 on: Jun 11th, 2007, 10:37am » |
Quote Modify
|
Ok. Hope this is not too big a hint. If this one doesn't help, I have a bigger hint.
| hidden: | | Although congruence modulo 2 doesn't work, congruence modulo __ does work. |
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 2007x2007 grid of odd numbers
« Reply #8 on: Jun 11th, 2007, 12:43pm » |
Quote Modify
|
on Jun 11th, 2007, 9:59am, ecoist wrote:| I just found a solution, but I think it is too soon to post it. Unless Aryabhatta disagrees. |
|
No problems 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: 2007x2007 grid of odd numbers
« Reply #9 on: Jun 11th, 2007, 3:41pm » |
Quote Modify
|
What I would do if I didn't have to go to sleep:
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).
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2007x2007 grid of odd numbers
« Reply #10 on: Jun 11th, 2007, 4:34pm » |
Quote Modify
|
I guess my bigger hint is now moot! Someone may post a solution before Grimbal wakes up!
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2007x2007 grid of odd numbers
« Reply #11 on: Jun 13th, 2007, 6:05am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 13th, 2007, 9:27am by ecoist » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2007x2007 grid of odd numbers
« Reply #12 on: Jun 14th, 2007, 9:46am » |
Quote Modify
|
| hidden: | | 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. |
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 2007x2007 grid of odd numbers
« Reply #13 on: Jun 19th, 2007, 9:25am » |
Quote Modify
|
Well done ecoist. I had something similar.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: 2007x2007 grid of odd numbers
« Reply #14 on: Jun 19th, 2007, 10:01am » |
Quote Modify
|
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?
|
| « Last Edit: Jun 19th, 2007, 4:46pm by ecoist » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print