Czech-Polish-Slovak Mathematical Match competition problems

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 \pmod 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 < \dots < i_p < |u|$, where $p \ge 1$. Consider the following partition of $u$ into subwords:
$$u = v_0v_1v_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' = v_0v_1\dots v_{j-1}w$, and let $a$ be the remainder of $\sum v_0v_1\dots v_{j-1}$ modulo $k$. Observe that $\sum w' \equiv a + \sum w \pmod k$. Therefore, the remainders realized by proper prefixes $w$ of $v_j$ are exactly the remainders realized by prefixes $w'$ 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'$ 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 \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_1v_2 \dots v_p$. If Geoff chooses $v_0$, then the rank of the word has already decreased. Otherwise Geoff chooses $v_1v_2 \dots v_p$.
* Partition $v_1v_2 \dots v_p$ into $v_1v_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_1v_2 \dots v_{p-1}$.
* Partition $v_1v_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. $\Box$