Track / Stage 6 / 56 of 400 #1536 of 2444

Problem 1536

National Olympiad, first round

Combinatorics Difficulty 6.0 Prove it HMMT February · United States · 2019

Fred the Four-Dimensional Fluffy Sheep is walking in 4-dimensional space. He starts at the origin. Each minute, he walks from his current position $(a_{1}, a_{2}, a_{3}, a_{4})$ to some position $(x_{1}, x_{2}, x_{3}, x_{4})$ with integer coordinates satisfying
$(x_{1}-a_{1})^{2}+(x_{2}-a_{2})^{2}+(x_{3}-a_{3})^{2}+(x_{4}-a_{4})^{2}=4$
and
$\left| (x_{1}+x_{2}+x_{3}+x_{4})-(a_{1}+a_{2}+a_{3}+a_{4}) \right|=2.$
In how many ways can Fred reach $(10,10,10,10)$ after exactly 40 minutes, if he is allowed to pass through this point during his walk?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

The possible moves correspond to the vectors $\pm\langle 2,0,0,0\rangle$ , $\pm\langle 1,1,1,-1\rangle$ , and their permutations. It's not hard to see that these vectors form the vertices of a 4-dimensional hypercube, which motivates the change of coordinates
$(x_{1}, x_{2}, x_{3}, x_{4}) \Rightarrow \left(\frac{x_{1}+x_{2}+x_{3}+x_{4}}{2}, \frac{x_{1}+x_{2}-x_{3}-x_{4}}{2}, \frac{x_{1}-x_{2}+x_{3}-x_{4}}{2}, \frac{x_{1}-x_{2}-x_{3}+x_{4}}{2}\right)$
Under this change of coordinates, Fred must travel from $(0,0,0,0)$ to $(20,0,0,0)$ , and the possible moves correspond to the sixteen vectors $\langle \pm 1, \pm 1, \pm 1, \pm 1\rangle$ . The new $x_{1}$ -coordinate must increase 30 times and decrease 10 times during Fred's walk, while the other coordinates must increase 20 times and decrease 20 times. Therefore, there are $\binom{40}{10}\binom{40}{20}^{3}$ possible walks.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.