Problem Statement
There is an integer in each square of an 8 x 8 chessboard. In one move, you may
choose any 4 x 4 or 3 x 3 square and add 1 to each integer of the chosen square.
Can you always get a table with each entry divisible by (a) 2, (b) 3?
Solution:
a) Let S be the sum of all numbers except the 3rd and 6th row. S mod 2 is invariant. If S != 0 (mod 2) intially, then odd numbers will remain on the chessboard.
(b) Let S be the sum of all the numbers except the 4th and the 8th row. Then I = S mod 3 is an invariant. If intially, I != 0 (mod 3) there will always be numbers on the chessboard which are not divisible by 3.
My Questions:
What I don't understand is why were 3rd, 6th, 4thand8th rows were disregarded? Could taking the sum of all the integers on the chessboard without disregarding any rows produce equivalent results?
Also, I don't really see why S != 0 (mod 2) would be enough to make any arguement. Should we not consider the case when S = 0 (mod 2)? Sum(S) can be divisible by 2 when there exist even number of odd numbers, too? So I dont understand how S not divisble by 2 is a determental statement in its own? Similar, points could be made about the divisiblity by 3 as well.
Any help/suggestion on this would be much appreciated.
Suppose all the numbers in some group of squares from the chessboard are even, then their sum must be even. So if you find any group of squares where the sum is never even, no matter how you adjust it according to the rules, then there must be a square in the group which doesn't have an even number in it - it may be a different square at each stage.
So the rows are chosen so that you find a group of cells where the sum is never even (note columns would work as well). The difficult thing is finding some group of cells where this works.