Let $M = \{(a,b,c,d)|a,b,c,d \in \{1,2,3,4\} \text{ and } abcd > 1\}$. For each $n\in \{1,2,\dots, 254\}$, the sequence $(a_1, b_1, c_1, d_1)$, $(a_2, b_2, c_2, d_2)$, $\dots$, $(a_{255}, b_{255},c_{255},d_{255})$ contains each element of $M$ exactly once and the equality \[|a_{n+1} - a_n|+|b_{n+1} - b_n|+|c_{n+1} - c_n|+|d_{n+1} - d_n| = 1\] holds. If $c_1 = d_1 = 1$, find all possible values of the pair $(a_1,b_1)$.
Problem
Source: Turkey TST 2003 - P1
Tags: combinatorics proposed, combinatorics
grupyorum
14.04.2018 22:41
There are two ideas in the problem. $\bullet$ The first idea is to look at the sum of all entries in a quadruple; and observe that each step flips the parity. $\bullet$ The second idea is to imagine the process as running on the lattice points at $ab$ and $cd$ planes; which will make it visually more accessible. First, check that there are $127$ quadruples with an even sum; and $128$ with an odd sum.
One way of seeing this is through a visual argument. Start from $(1,1,1,1)$; fix $(c,d)$; and traverse all lattice points in $(a,b)$ plane. Once you hit the last; move to the next lattice point in $(c,d)$ plane, fix it, and then run the process again in $(a,b)$ plane. At the end; we will have a path consisting of all $256$ points; with the desired claim. Hence, we have half of them even; half of them odd. Finally, in our setup $(1,1,1,1)$ is eliminated; thus the claim.
Since we are to make a total of $254$ steps; the parity (of the sum) of the initial quadruple is equal to that of the last quadruple; hence, we must begin from a quadruple with odd sum. Hence, $a+b$ must be odd. Now, let us verify that all $(a,b)$ pairs with an odd sum work. Having $(c,d)$ fixed at $(1,1)$; traverse the remaining 15 lattice points in (punctured, as, $(1,1)$ is taken out) $ab-$plane (as a sanity check, observe that since there are $8$ odd and $7$ evens; we must start at an odd location, which we did). Once you traverse all 15 lattice points; now, make a move in $cd-$plane, to the next location. Having fixed this $(c,d)$ pair; we now traverse, again, all the lattice points in $ab-$plane (however, $(1,1)$ is allowed now). Going in this manner, we cover all the points. Answer: $\{(a,b):1\leq a,b\leq 4, 2\nmid a+b\}$.