Let $A$ be a $8\times 8$ array with entries from the set $\{-1,1\}$ such that any $2\times 2$ sub-square of the array has the absolute value of the sum of its element equal with 2. Prove that the array must have at least two identical lines.
Problem
Source: Romanian Junior JBkMO TST 2004, problem 7
Tags: absolute value
Peter
02.05.2004 19:06
a minor question on the wording: "lines" --> is a row the same as a column enough as a requirement, or do it have to be 2 rows or 2 columns (not that it really matters here but it could be better to explain this)
chavez
16.03.2005 16:50
Please, give me a solution for this problem..
chavez
16.03.2005 21:05
i find good results.. but nothing that conclude the problem
DPopov
16.03.2005 21:11
Can you not begin constructing the square since you must have 3 1's and a -1 or 3 -1's and a 1 in order for the absolute value of the sum of the elements in the 2x2 square to be 2.
chavez
16.03.2005 22:04
DPopov: you have a complete solution?
DPopov
17.03.2005 01:35
I will work on it, that just came to mind after reading the question.
chavez
17.03.2005 15:11
DPopov: You complete your solution ?
DPopov
18.03.2005 06:00
sorry, i haven't been able to write a decent solution yet. I will respond ASAP
probability1.01
19.03.2005 01:45
Ummm... don't there have to be at least 2 pairs of identical rows and 2 pairs of identical columns?
chavez
19.03.2005 07:09
i don´t know
joml88
19.03.2005 14:24
Chavez, could you please not double or triple post? What I mean is don't post one message and then another message without someone responding to your last message. There are certain instances where multi posting is acceptable but not what you've done in this thread. And could you also try to cut down on the extra posts like where you just posted a smiley? Thanks
probability1.01
19.03.2005 18:01
I'm afraid I don't quite understand the problem . But I found some somewhat interesting results looking at this row by row or column by column...
DPopov
21.03.2005 03:20
I have a proof but it is a bit brute forced. I see that once you construct a square which can be done in only two ways, 3 -1's and a 1 or 3 1's and a -1, not counting the permutations of the entries, then you can begin constructing the larger square by just moving each row up two spaces and each column to the right two spaces (assuming you start in the lower left corner). However, this can be broken down into several cases since after shifting the bottom two entries up two rows you can then form the opposite type of square. For example: Consider the 2x2 square in the bottom left corner with top entries {1,1} and bottom entries {1,-1}. After shifting the {1,-1} to the third row from the bottom you can then make the fourth row either {1,1} as I stated in my original construction or {-1,-1}. These cases also follow for shifting the entries in the columns.