A sequence of $2n + 1$ non-negative integers $a_1, a_2, ..., a_{2n + 1}$ is given. There's also a sequence of $2n + 1$ consecutive cells enumerated from $1$ to $2n + 1$ from left to right, such that initially the number $a_i$ is written on the $i$-th cell, for $i = 1, 2, ..., 2n + 1$. Starting from this initial position, we repeat the following sequence of steps, as long as it's possible: Step 1: Add up the numbers written on all the cells, denote the sum as $s$. Step 2: If $s$ is equal to $0$ or if it is larger than the current number of cells, the process terminates. Otherwise, remove the $s$-th cell, and shift shift all cells that are to the right of it one position to the left. Then go to Step 1. Example: $(1, 0, 1, \underline{2}, 0) \rightarrow (1, \underline{0}, 1, 0) \rightarrow (1, \underline{1}, 0) \rightarrow (\underline{1}, 0) \rightarrow (0)$. A sequence $a_1, a_2,. . . , a_{2n+1}$ of non-negative integers is called balanced, if at the end of this process there’s exactly one cell left, and it’s the cell that was initially enumerated by $(n + 1)$, i.e. the cell that was initially in the middle. Find the total number of balanced sequences as a function of $n$. Proposed by Viktor Simjanoski, North Macedonia
Problem
Source: BMO Shortlist 2021
Tags: Balkan, shortlist, 2021, combinatorics, Sequence, Process
guptaamitu1
16.06.2022 01:47
I got the answer as $$ 2 \cdot \left( \binom{2n-2}{n-1} - \binom{2n-2}{n-3} \right)^2 $$Can someone please verify if it is correct or not.
Infinityfun
07.12.2022 14:49
The answer is $C_n^2$ where $C_n$ is the nth Catalan number.
Number1048576
12.01.2024 13:43
We claim that the answer is $\left (\frac{1}{n+1} \times {2n \choose n} \right )^2$.
First, note that if after the $i$th move the cell to be removed is cell $j$ (write $j = c_i$), then $c_{i+1} \le c_i + 1$.
Hence, if cell $u$ is the final cell, if there is $i$ such that $c_i < u$ and there is a cell above $u$ not yet removed, then we cannot remove that cell without first removing cell $u$, a contradiction, so we have to remove all cells above $u$ and then all cells below $u$.
Note that after the set of cells above $u$ have been removed, if cell $u$ contains a $0$, then the set of cells below $u$ must be a configuration ending in $1$, and if cell $u$ contains a $1$ then the set of cells below $u$ must be a configuration ending in $0$.
Also, the final cell removed above $u$ must have value $u+1$ minus the sum of cells less than or equal to $u$.
Note that if we remove all cells below $u+1$ and replace the value in cell $u+1$ with $1$ then we still have a valid configuration, and vice versa.
Let $f_0(k)$ be the number of configurations with $k$ starting cells which have last cell (time-wise) $0$; define $f_1(k)$ similarly.
Then $f_0(k) = \sum_x [f_1(x)f_1(k-x-1)]$, where $f_0(0) = f_1(0) = 1$. Hence, by an induction $f_0(k) = f_1(k)$.
However, this is a well-known recurrence for the Catalan numbers.
The final answer is however $(f_1(n))^2 = (C_n)^2 = \left (\frac{1}{n+1} \times {2n \choose n} \right)^2$