Maths Olympiad Prep

Library / /17 of 21

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Czech-Polish-Slovak Mathematical Match

Let kk be a fixed positive integer. A finite sequence of integers x1,x2,,xnx_1, x_2, \dots, x_n is written on a blackboard. Pepa and Geoff are playing a game that proceeds in rounds as follows.
* In each round, Pepa first partitions the sequence that is currently on the blackboard into two or more contiguous subsequences (that is, consisting of numbers appearing consecutively). However, if the number of these subsequences is larger than 2, then the sum of numbers in each of them has to be divisible by kk.
* Then Geoff selects one of the subsequences that Pepa has formed and wipes all the other subsequences from the blackboard.
The game finishes once there is only one number left on the board. Prove that Pepa may choose his moves so that independently of the moves of Geoff, the game finishes after at most 3k3k rounds.

(Poland)

Solution

A finite sequence of integers is called a *word* and any its contiguous subsequence is called a *subword*. For a word uu, by u\sum u we denote the sum of numbers in uu. 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 uu, let R(u){0,1,,k1}R(u) \subseteq \{0, 1, \dots, k-1\} be the set of remainders rr modulo kk for which there exists a proper prefix vv of uu with vr(modk)\sum v \equiv r \pmod k. In other words, R(u)R(u) comprises different remainders modulo kk realized by sums of numbers in proper prefixes of uu. Define the *rank* of uu as R(u)|R(u)|.
We shall prove the following statement: given a word uu 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 uu. Since the rank of the initial word is at most kk 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 3k3k rounds.
Assume then that the word uu on the board has length larger than 1, and take any rR(u)r \in R(u). Suppose that the proper prefixes of uu giving remainder rr modulo kk end at positions 1i1<i2<<ip<u1 \le i_1 < i_2 < \dots < i_p < |u|, where p1p \ge 1. Consider the following partition of uu into subwords:
u=v0v1v2vp1vp, u = v_0v_1v_2\dots v_{p-1}v_p,
where v0v_0 is the prefix up to position i1i_1, each vjv_j for j=1,2,,p1j = 1, 2, \dots, p-1 is the subword between positions ij+1i_j + 1 and ij+1i_{j+1}, and vpv_p is the suffix from position ip+1i_p + 1 till the end of the word.
We observe that the rank of each of subword vjv_j is strictly smaller than the rank of uu. For j=0j = 0 this is trivial: since i1i_1 is the first position at which a prefix of uu has sum congruent to rr modulo kk, we have that R(v0)R(u){r}R(v_0) \subseteq R(u) \setminus \{r\}. For j>0j > 0, take any proper prefix ww of vjv_j, let w=v0v1vj1ww' = v_0v_1\dots v_{j-1}w, and let aa be the remainder of v0v1vj1\sum v_0v_1\dots v_{j-1} modulo kk. Observe that wa+w(modk)\sum w' \equiv a + \sum w \pmod k. Therefore, the remainders realized by proper prefixes ww of vjv_j are exactly the remainders realized by prefixes ww' as above with aa subtracted modulo kk. Since between iji_j and ij+1i_{j+1} there is no position at which a prefix of uu has sum congruent to rr modulo kk, we infer that none of prefixes ww' as above has sum congruent to rr modulo kk. This implies that R(vj){qa:qR(u){r}}R(v_j) \subseteq \{q-a: q \in R(u) \setminus \{r\}\}, so R(vj)<R(u)|R(v_j)| < |R(u)|.
Note that vj0modk\sum v_j \equiv 0 \mod k for each j=1,2,,p1j = 1, 2, \dots, p-1 by construction. All these observations lead to the following three-turn strategy for Pepa:
* Partition uu into v0v_0 and v1v2vpv_1v_2 \dots v_p. If Geoff chooses v0v_0, then the rank of the word has already decreased. Otherwise Geoff chooses v1v2vpv_1v_2 \dots v_p.
* Partition v1v2vpv_1v_2 \dots v_p into v1v2vp1v_1v_2 \dots v_{p-1} and vpv_p. If Geoff chooses vpv_p, then the rank of the word has already decreased. Otherwise Geoff chooses v1v2vp1v_1v_2 \dots v_{p-1}.
* Partition v1v2vp1v_1v_2 \dots v_{p-1} into v1,v2,,vp1v_1, v_2, \dots, v_{p-1}, which are all words with sums of numbers divisible by kk. Regardless of the move of Geoff, the rank of the word chosen by him is strictly smaller than the rank of uu.
This concludes the proof. \Box

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 and solution reproduced as published; topic and difficulty added by this site.