Czech-Polish-Slovak Mathematical Match

A finite sequence of integers is called a word and any its contiguous subsequence is called a subword. For a word $u$, by $\sum u$ we denote the sum of numbers in $u$. A prefix of a word is a subword starting at the beginning of the word, and a prefix is proper if it is neither empty nor the whole word. Analogously we define suffixes. For a word $u$, let $R(u)\subseteq \{0,1,\dots ,k-1\}$ be the set of remainders $r$ modulo $k$ for which there exists a proper prefix $v$ of $u$ with $\sum v\equiv r(\mathrm{mod}k)$. In other words, $R(u)$ comprises different remainders modulo $k$ realized by sums of numbers in proper prefixes of $u$. Define the rank of $u$ as $|R(u)|$. We shall prove the following statement: given a word $u$ on the board, Pepa can always play at most 3 rounds so that the rank of the remaining word is strictly smaller than the rank of $u$. Since the rank of the initial word is at most $k$ and the rank of a word is 0 if and only if it consists of one number, in this way Pepa may force the end of the game within at most $3k$ rounds. Assume then that the word $u$ on the board has length larger than 1, and take any $r\in R(u)$. Suppose that the proper prefixes of $u$ giving remainder $r$ modulo $k$ end at positions $1\le i_1<i_2<\cdots <i_p<|u|$, where $p\ge 1$. Consider the following partition of $u$ into subwords: $$u=v_0{v}_1{v}_2\dots v_{p-1}{v}_p,$$ where $v_0$ is the prefix up to position $i_1$, each $v_j$ for $j=1,2,\dots ,p-1$ is the subword between positions $i_j+1$ and $i_{j+1}$, and $v_p$ is the suffix from position $i_p+1$ till the end of the word. We observe that the rank of each of subword $v_j$ is strictly smaller than the rank of $u$. For $j=0$ this is trivial: since $i_1$ is the first position at which a prefix of $u$ has sum congruent to $r$ modulo $k$, we have that $R(v_0)\subseteq R(u)\setminus \{r\}$. For $j>0$, take any proper prefix $w$ of $v_j$, let $w^{\prime }=v_0{v}_1\dots v_{j-1}w$, and let $a$ be the remainder of $\sum v_0{v}_1\dots v_{j-1}$ modulo $k$. Observe that $\sum w^{\prime }\equiv a+\sum w(\mathrm{mod}k)$. Therefore, the remainders realized by proper prefixes $w$ of $v_j$ are exactly the remainders realized by prefixes $w^{\prime }$ as above with $a$ subtracted modulo $k$. Since between $i_j$ and $i_{j+1}$ there is no position at which a prefix of $u$ has sum congruent to $r$ modulo $k$, we infer that none of prefixes $w^{\prime }$ as above has sum congruent to $r$ modulo $k$. This implies that $R(v_j)\subseteq \{q-a:q\in R(u)\setminus \{r\}\}$, so $|R(v_j)|<|R(u)|$. Note that $\sum v_j\equiv 0\mathrm{mod}k$ for each $j=1,2,\dots ,p-1$ by construction. All these observations lead to the following three-turn strategy for Pepa: Partition $u$ into $v_0$ and $v_1{v}_2\dots v_p$. If Geoff chooses $v_0$, then the rank of the word has already decreased. Otherwise Geoff chooses $v_1{v}_2\dots v_p$. Partition $v_1{v}_2\dots v_p$ into $v_1{v}_2\dots v_{p-1}$ and $v_p$. If Geoff chooses $v_p$, then the rank of the word has already decreased. Otherwise Geoff chooses $v_1{v}_2\dots v_{p-1}$. * Partition $v_1{v}_2\dots v_{p-1}$ into $v_1,v_2,\dots ,v_{p-1}$, which are all words with sums of numbers divisible by $k$. Regardless of the move of Geoff, the rank of the word chosen by him is strictly smaller than the rank of $u$. This concludes the proof. $\square$