The set of quadruples $(a,b,c,d)$ where each of $a,b,c,d$ is either $0$ or $1$ is called vertices of the four dimensional unit cube or 4-cube for short. Two vertices are called adjacent, if their respective quadruples differ by one variable only. Each two adjacent vertices are connected by an edge. A robot is moving through the edges of the 4-cube starting from $(0,0,0,0)$ and each turn consists of passing an edge and moving to adjacent vertex. In how many ways can the robot go back to $(0,0,0,0)$ after $4042$ turns? Note that it is NOT forbidden for the robot to pass through $(0,0,0,0)$ before the $4042$-nd turn.
Problem
Source: XI International Festival of Young Mathematicians Sozopol 2022, Theme for 11-12 grade
Tags: combinatorics
Marinchoo
29.09.2022 00:15
The expected (and routine) solution is calculating via recursion. We present a flashy overkill. Associate a change in a digit with one of the letters $A,B,C,D$ for the four positions respectively. We can represent every way to go back to $(0,0,0,0)$ as a string of an even number of each of $A,B,C,D$. Also, every string of an even number of each letter can be interpreted as a different way for the robot to go back to the starting position. Therefore we just have to calculate the number of strings of $4042$ letters where each letter appears an even number of times: \begin{align*} \sum\limits_{\substack{0\leq a,b,c,d\leq 2021\\ a+b+c+d=2021}} \frac{4042!}{(2a)!(2b)!(2c)!(2d)!}&=\sum\limits_{\substack{a=b=0\\ c+d=2021}} \binom{4042}{2c}+\sum\limits_{\substack{c=d=0\\a+b=2021}} \binom{4042}{2a}+\sum\limits_{\substack{0\leq a,b,c,d< 2021 \\ 1\leq a+b\leq 2020}} \binom{4042}{2a,2b,2c,2d}\\ &=2^{4041}+2^{4041}+\sum\limits_{\substack{0\leq a,b,c,d< 2021 \\ 1\leq a+b\leq 2020}} \binom{4042}{2a,2b,2c,2d}\\ &=2^{4042}+\sum\limits_{\substack{0\leq a,b\leq 2020\\1\leq a+b\leq 2020}}\sum\limits_{c=0}^{2021-a-b} \binom{4042}{2a,2b,4042-2a-2b}\binom{4042-2a-2b}{2c}\\ &=2^{4042}+\sum\limits_{\substack{0\leq a,b\leq 2020\\1\leq a+b\leq 2020}}\binom{4042}{2a,2b,4042-2a-2b}\sum\limits_{c=0}^{2021-a-b} \binom{4042-2a-2b}{2c}\\ &=2^{4042}+\sum\limits_{\substack{0\leq a,b\leq 2020\\1\leq a+b\leq 2020}}\binom{4042}{2a,2b,4042-2a-2b}2^{4041-2a-2b}\\ &=2^{4042}+\sum\limits_{s=1}^{2020}\sum\limits_{\substack{0\leq a,b\leq 2020\\a+b=s}}\binom{4042}{2s}\binom{2s}{2a}2^{4041-2s}\\ &=2^{4042}+\sum\limits_{s=1}^{2020}\binom{4042}{2s}2^{4041-2s}\sum\limits_{\substack{0\leq a,b\leq 2020\\a+b=s}}\binom{2s}{2a}\\ &=2^{4042}+\sum\limits_{s=1}^{2020}\binom{4042}{2s}2^{4041-2s}2^{2s-1}\\ &=2^{4042}+\sum\limits_{s=1}^{2020}\binom{4042}{2s}2^{4040}\\ &=2^{4042}-2^{4040}\left(\binom{4042}{0}+\binom{4042}{4042}\right)+\sum\limits_{s=0}^{2021}\binom{4042}{2s}2^{4040}\\ &=2^{4041}+2^{8081} \end{align*}