Let $r$ and $b$ be positive integers. The game of Monis, a variant of Tetris, consists of a single column of red and blue blocks. If two blocks of the same color ever touch each other, they both vanish immediately. A red block falls onto the top of the column exactly once every $r$ years, while a blue block falls exactly once every $b$ years. (a) Suppose that $r$ and $b$ are odd, and moreover the cycles are offset in such a way that no two blocks ever fall at exactly the same time. Consider a period of $rb$ years in which the column is initially empty. Determine, in terms of $r$ and $b$, the number of blocks in the column at the end. (b) Now suppose $r$ and $b$ are relatively prime and $r+b$ is odd. At time $t=0$, the column is initially empty. Suppose a red block falls at times $t = r, 2r, \dots, (b-1)r$ years, while a blue block falls at times $t = b, 2b, \dots, (r-1)b$ years. Prove that at time $t=rb$, the number of blocks in the column is $\left\lvert 1+2(r-1)(b+r)-8S \right\rvert$, where \[ S = \left\lfloor \frac{2r}{r+b} \right\rfloor + \left\lfloor \frac{4r}{r+b} \right\rfloor + ... + \left\lfloor \frac{(r+b-1)r}{r+b} \right\rfloor . \] Proposed by Sammy Luo
Problem
Source: ELMO 2014 Shortlist C4, by Sammy Luo
Tags: floor function, number theory, relatively prime, combinatorics proposed, combinatorics
08.02.2020 01:29
Bump.
02.06.2022 11:09
Step 1: Change the order of operations, and noting the order of operations don't matter if I only add stones before or after the whole pile. For both parts of the problem, consider an alternate process where $rb$ years pass and blocks don't vanish on top of each other and call this the rough $(r,b)$ sequence. After that, time freezes and two consecutive blocks of the same color vanish, forming the final $(r,b)$-sequence. We can induct on the number of blocks to see why the end results of the two processes are equivalent. Part a) The answer is $2\gcd(r,b)$. Let $f(r,b)$ denote the answer for $(r,b)$. We will induct on $r+b$ to show that the number of stones in the final $(r,b)$-sequence is $2\gcd(r,b)$. The base case is $r=b$, where the answer is clearly $2r$ because the sequence is $RBRBRB\cdots RB$ where there are $r$ R's and $r$ B's. WLOG, $r<b$ and we start with a blue block, call the 0th. The first red block comes later in the same year. Notice between the $j$th and the $(j-1)$-th blue blocks of the rough $(r,b)$ sequence, there exists $\lfloor \frac{jb}{r} \rfloor - \lfloor \frac{(j-1)b}{r} \rfloor$ red blocks. If $b>2r$ then the rough sequence formed by $(r,b-2r)$ has 2 less red blocks between the $(j-1)$th and $j$th blue block for every $j$. The two additional stones from the rough $(r,b)$ sequence in each of these two adjacent blue blocks will vanish, and therefore, $f(r,b)=f(r,b-2r)=2\gcd(r,b-2r)=2\gcd(r,b)$, where we've used our inductive hypothesis. Otherwise, $r<b<2r$. I claim $f(r,b)=f(r,2r-b)$ because in the $(r,b)$ sequence, if I remove adjacent red blocks, I will get the $(r,2r-b)$ sequence. Let $a_j$ be the number of reds between the $(j-1)$th and $j$th blue in the rough $(r,b)$ sequence and $b_j$ be the number of reds between the $j-1$th and $j$th blue in the rough $(r,2r-b)$ sequence. Observe $a_j+b_j=\lfloor \frac{jb}{r} \rfloor - \lfloor \frac{(j-1)b}{r} \rfloor + \lfloor \frac{j(2r-b)}{r} \rfloor - \lfloor \frac{(j-1)(2r-b)}{r} \rfloor = 2$ because for all $t$, $\lfloor \frac{tb}{r} \rfloor + \lfloor \frac{t(2r-b)}{r} \rfloor = \frac{2tr}{r} - \{ \frac{tb}{r} \} - \{ \frac{t(2r-b)}{r} \} = 2t-1$. Notice if I remove 2 consecutive reds between two blues, the number of reds between two adjacent blues in the original sequence (no removals) plus the number of reds between two adjacent blues in the new sequence is 2. Therefore, taking the rough sequence and removing two consecutive reds between the $j$th blue and $(j-1)$th blue yields the rough $(r,2r-b)$ sequence, which by inductive hypothesis, yields $2\gcd(r,2r-b)$ stones in the end. Therefore, the final $(r,b)$ sequence has $2\gcd(r,2r-b)=2\gcd(r,b)$ stones in the end as well. b) Let $g(r,b)=1+2(r-1)(b+r)-8s(r,r+b)$ where $s(r,k)=\sum\limits_{j=1}^{\frac{k-1}{2}} \lfloor \frac{2jr}{k}\rfloor$ and let $h(r,b)$ denote the number of stones in the end. Lemma: $s(r,k)=\frac{(r-1)(k-1)}{2}-\sum\limits_{t=1}^{r-1} \lfloor \frac{kt}{2r} \rfloor$ Proof: we swap the order of sums: $s(r,k)=\sum_{1\le j\le \frac{k-1}{2}} \sum_{t\le \frac{2jr}{k}} 1 = \sum_{t=1}^{r-1} \# ( \frac{kt}{2r}\le j\le \frac{k-1}{2}) =\sum_{t=1}^{r-1} (\frac{k-1}{2}- \lfloor \frac{kt}{2r} \rfloor)$ as needed. Claim: $g(r,b)=g(r,b+2r)$ Proof: $g(b+2r)-g(b,r)$ $=2(r-1)(r+b+2r)-2(r-1)(b+r)-8(s(r,b+3r)+s(r,b+r))= 4(r-1)r -8\sum\limits_{t=1}^{r-1} \left( \lfloor \frac{t(b+3r)}{2r} \rfloor - \lfloor \frac{t(b+r)}{2r} \rfloor \right) = 4(r-1)r - 8\sum\limits_{t=1}^{r-1} t=0$ Claim: $g(r,b)+g(b,r)=0$ Proof: $2+2(r-1)(b+r)+2(b-1)(b+r)-8\sum\limits_{j=1}^{\frac{r+b-1}{2}} ( \lfloor \frac{2jr}{r+b} \rfloor + \lfloor \frac{2jb}{r+b} \rfloor)=2+2(r+b-2)(r+b) -8\sum\limits_{j=1}^{\frac{r+b-1}{2}} (2j-1)=2+2(r+b-2)(r+b) - 8 (\frac{r+b-1}{2})^2=0$ Claim: if $b<2r$, $g(r,b)+g(r,2r-b)=2$ Proof: $g(r,b)+g(r,2r-b)=2+2(r-1)(r+b+r+2r-b) - 8s(r,b+r) -8s(r,3r-b)=2+8(r-1)r -8 \frac{(r-1)(b+r+3r-b-2)}{2} + 8\sum\limits_{t=1}^{r-1} (\lfloor \frac{t(b+r)}{2r} \rfloor + \lfloor \frac{t(3r-b)}{2r} \rfloor) = 2-8(r-1)^2 +8\sum\limits_{t=1}^{r-1} (2t-1)=2$ We now induct on $b+r$ to show $h(r,b)=|g(r,b)|$, and call this assertion $P(r,b)$. We will use an auxiliary assertion, which is $g(r,b)>0$ if and only if the $(r,b)$ sequence, after repeatedly taking out adjacent pairs of the same color, has red starting and ending blocks, and call this assertion $Q(r,b)$. Our base case is $(1,2)$. We can check $P(1,2), Q(1,2)$ holds. First, it suffices to $P(r,b), Q(r,b)$ for $r<b$, because if $r>b$, we have proven $g(r,b)=g(b,r)=0$ so $h(r,b)=|g(r,b)|=|g(b,r)|=h(b,r)$ so $P(b,r)$ follows from $P(r,b)$. $Q(b,r)$ also follows from $Q(r,b)$ because $g(r,b)=-g(b,r)$, and the final $(r,b)$ sequence is just the final $(b,r)$ sequence with red and blue interchanged. Case 1: $b>2r$. In this case, note $h(r,b)=h(r,b-2r)$. Note our rough $(r,b)$ sequence is $\lfloor\frac{b}{r} \rfloor$ R's, B, $\lfloor \frac{2b}{r}\rfloor - \lfloor \frac{b}{r} \rfloor$R's, B, $\cdots$, B, $\lfloor \frac{rb}{r} \rfloor - \lfloor \frac{(r-1)b}{r} \rfloor -1$ R's. Where R,B denotes a red, blue block respectively. If I turn $b \to b-2r$ then each of the floor differences reduce by 2, and therefore removing two stones before the first blue, between the $(j-1)$th and $j$th blue, and after the last blue yields the rough $(r,b-2r)$ sequence. Therefore $h(r,b)=h(r,b-2r)$. Since $g(r,b)=g(r,b-2r)$, $Q(r,b)$ holds. Also, it follows that $h(r,b)=|g(r,b)|$, so $P(r,b)$ holds. Case 2: $r<b<2r$. Observe if we apply the following operations to the rough $(r,b)$ sequence Remove one R in the beginning, one R in the end. If between the $j-1$th and $j$th blues, there are two consecutive reds, remove them. We get the rough $(r,2r-b)$ sequence. We have two cases on the sign of $g(r,2r-b)$: Subcase 2.1: $g(r,2r-b)>2$. This means by $Q(r,2r-b)$, the starting and ending are red, and by $P(r,2r-b)$ the final $(r,2r-b)$ sequence has $g(r,2r-b)=h(r,2r-b)$ stones with pattern RBRBRB $\cdots$ R (B's exist because $g(r,2r-b)>2$). If I don't touch both the starting and ending red of the $(r,b)$ sequence then I go from R [(r,2r-b)-sequence] R to RRBRBRB $\cdots$ BRR. Removing the first and last pair grants $h(r,2r-b)-2$ stones. Since $g(r,b)=2-g(r,2r-b)$, it follows that $|g(r,b)|=|h(r,b)|$, so $P(r,b)$ holds. Also, it guarantees that the starting stone is blue, which holds if $g(r,2r-b)>2$. Therefore, $g(r,b)=2-g(r,2r-b)<0$ and the starting stone is blue, so $Q(r,b)$ holds. Subcase 2.2: $g(r,2r-b)=1$. Same argument, but it ends with RRR. Subcase 2.3: $g(r,2r-b)<0$. Analogous argument. This completes our induction.