3
$\begingroup$

We begin with a table as shown below. The rules of the game are that in one step you can either add $1$ to all the numbers in any row or column or subtract $1$ from all the numbers in any row or column. You may repeat this step as many times as you want. Prove that you can't reach a table with all $1$. $$\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{array}$$

I want to consider the sum of the squares $\mod3$ will always be of the form $3k+1$ for some $k \in \mathbb{Z}$. I'm having trouble formulating my thought. I claim that since it is now of the form $3k+1$ it will always maintain this form yet not quite sure how to word that. I also considered another approach using a system of linear equations to show that it will have no solution. With $9$ equations for the values of the squares but not sure what would be the variables so went with the first approach.

$\endgroup$
1
$\begingroup$

Well done on your thinking so far. You have identified what might be called an "invariant" - something which stays the same whichever permitted operation you carry out. What you seem to be lacking is clear language to describe the situation.

So the invariant is that the sum of the entries in all the boxes is $\equiv 1 \bmod 3$ - you have clearly stated that.

You now need to do two things.

First you need to show that this really is invariant - so for each of the permitted operations show it doesn't change. You don't need to worry about the substructure of the problem - for each operation, what does it do to the sum of all the entries, and does that leave the sum $\equiv 1 \bmod 3$.

Second you need to show that the target position does not have the same invariant - that the residue class modulo $3$ is different from $1$.

If the residue class of the target position was $\equiv 1 \bmod 3$ you might instead be looking for a sequence of moves which would arrive at that position (we have not said anything yet about whether all such positions are attainable).

I hope this helps you to structure your thoughts. Invariants are incredibly important, and the amount of effort which goes into pinning down and defining invariants is matched by their utility - both in simple terms (even as simple as odd and even) and influencing whole wider fields of mathematics (e.g. homology and cohomology, various things called the "genus" of a mathematical object, the Euler characteristic)

$\endgroup$
0
$\begingroup$

Color the table like that:
$$RRB\\ RRB\\ BBB$$

Let $S$ be the number of $1$ in $R$ sector. Then what ever you do $S$ will stay the same modulo $2$ and thus impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.