A finite sequence of integers is called a *word* and any its contiguous subsequence is called a *subword*. For a word u, by ∑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)⊆{0,1,…,k−1} be the set of remainders r modulo k for which there exists a proper prefix v of u with ∑v≡r(modk). 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∈R(u). Suppose that the proper prefixes of u giving remainder r modulo k end at positions 1≤i1<i2<⋯<ip<∣u∣, where p≥1. Consider the following partition of u into subwords:
u=v0v1v2…vp−1vp,
where v0 is the prefix up to position i1, each vj for j=1,2,…,p−1 is the subword between positions ij+1 and ij+1, and vp is the suffix from position ip+1 till the end of the word.
We observe that the rank of each of subword vj is strictly smaller than the rank of u. For j=0 this is trivial: since i1 is the first position at which a prefix of u has sum congruent to r modulo k, we have that R(v0)⊆R(u)∖{r}. For j>0, take any proper prefix w of vj, let w′=v0v1…vj−1w, and let a be the remainder of ∑v0v1…vj−1 modulo k. Observe that ∑w′≡a+∑w(modk). Therefore, the remainders realized by proper prefixes w of vj are exactly the remainders realized by prefixes w′ as above with a subtracted modulo k. Since between ij and ij+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(vj)⊆{q−a:q∈R(u)∖{r}}, so ∣R(vj)∣<∣R(u)∣.
Note that ∑vj≡0modk for each j=1,2,…,p−1 by construction. All these observations lead to the following three-turn strategy for Pepa:
* Partition u into v0 and v1v2…vp. If Geoff chooses v0, then the rank of the word has already decreased. Otherwise Geoff chooses v1v2…vp.
* Partition v1v2…vp into v1v2…vp−1 and vp. If Geoff chooses vp, then the rank of the word has already decreased. Otherwise Geoff chooses v1v2…vp−1.
* Partition v1v2…vp−1 into v1,v2,…,vp−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. □