Let ${k}$ be a fixed positive integer. A finite sequence of integers ${x_1,x_2, ..., 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 ${k}$. - 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 ${3k}$ rounds. (Poland)
Problem
Source: Czech-Polish-Slovak Match 2017 day 1 P3
Tags: winning positions, game strategy, Sequence, divisible, number theory
29.11.2017 21:41
For any sequence, we define its initial segment sum to be the sum $x_1+x_2+....+ x_z$, reduced mod k, for some z. We define the total sum to be $x_1+x_2+....x_n$ (mod k) Define its richness to be the number of different initial segment sum mod k. A sequence is last-distinctive if not other initial segment sum equals the total sum. Given any sequence, we claim that in 3 moves, Geoff can reduces its richness by 1. Note that any continuous sub-block of the sequence has a <= richness of the original sequence Aim of move 1 is to obtain a sequence that has total sum being 0 (mod k) Move 1: Consider the total sum, there may or may not exist another initial segment sum congruent to this. If yes, split the sequence into the first such initial segment and the rest. The first part is last-distinctive. The rest is of total sum 0 ( mod k) If not, then it is last-distinctive, so we can just do move 3. Move 2: For a sequence with total sum divisible by k. Splits the sequences into maximal amount of continuous blocks such that each block is divisible by k. Then easily each block is last-distinctive. Move 3: We can reduce the richness of a last-distinctive sequence by 1: Simply cut off the last digit. The game is finished if Geoff chooses the last one, otherwise, by the definition of last-distinctive, the leftover segment has reduced richness. So in 3k moves, Geoff must have chosen Move 3 accepting the last digit. The proof is complete