Library / /1308 of 1394

, 2019

Combinatorics Difficulty 6.0 National Olympiad Prove it United States

Problem:

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?

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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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