A collection of combinatorics problems
Problem 1.1 (2020 Balkan Math Olympiad 3)
Let $k$ be a positive integer. Find the smallest integer $n$ such that $n\ge k+1$ and the following process can continue infinitely:
Consider $n$ boxes, where the $i$-th box for $i=1,2,\dots,n$ initially contains $i$ coins. Every second, we do, in order, the following steps:
Select some $k+1$ boxes.
Select one box from the $k+1$ boxes in the previous step. Add $i$ coins to this box, where this box is the $i$-th box. Remove at least half of the coins from the other $k$ selected boxes.
If any box is empty, stop.
Solution
The answer is $2^k+k-1$. We will prove this by first constructing a solution for $2^k+k-1$, and then by proving that no $n\le 2^k+k-2$ will work.
$n=2^k+k-1$ will work. It is obvious that in the second step we halve the number of coins in the other $k$ boxes. Every second, we will always choose boxes $2^k-1$, $2^k$, …, $2^k+k-2$, $2^k+k-1$. We initially choose $2^k-1$ to add coins to, and every second after that we choose the box after the box previously chosen, where $2^k+k-1$ wraps around to $2^k-1$. It follows by induction that after this box has its respective quantity of coins added to it, it will have at least $2^k$ coins, which is enough to last it $k$ halvings until its next addition.
Any $n$ at most $2^k+k-2$ will not work. Suppose that it is possible. Observe that in the long run, there will be some boxes - at least $k+1$ of them - that are selected an infinite amount of times in the first step. It follows that at least $k+1$ boxes must be supplied an infinite amount of times.
Let us define the weight of a box as the number of halvings it can sustain before becoming empty. That is, the weight of a box with $x$ coins is $\lfloor\log_2 x\rfloor$. Consider the cumulative weight of all boxes; let this quantity be $\Phi$.
The $k$ halvings decrease $\Phi$ by $k$. If we add coins to the $i$-th box, which then has $x$ coins, $\Phi$ increases by $\lfloor\log_2(x+i)\rfloor-\lfloor\log_2 x\rfloor$. This increase is maximized when $i$ is maximized, and then when $x$ is minimized; we hence get $\lfloor\log_2(x+i)\rfloor-\lfloor\log_2 x\rfloor\le k$ and $\Delta\Phi\le 0$. However, as at least $k+1$ boxes are supplied an infinite number of times, there must be at least $k+1$ distinct values for $i$. The maximum possible smallest of these $k+1$ values is $(2^k+k-2)-(k+1)+1=2^k-2$, and $\lfloor\log_2(2^k-1)\rfloor<k$. Therefore, there must be an infinite number of seconds where $\Delta\Phi<0$. But $\Phi$ is clearly always a nonnegative integer, a contradiction; therefore this process cannot continue indefinitely.
Problem 1.2 (2020 CGMO 8)
Consider the sequences of positive integers that sum to $n$. Of these sequences, how many have an even number of inversions?
Solution
Clearly for a given $n$ there are $2^{n-1}$ sequences that sum to $n$. This allows us to instead determine the difference between sequences that have an even number of inversions and sequences that have an odd number.
Let $C(n)$ be the aforementioned difference; in particular, $C(0)=1$. Then consider $C(n)$. We will do casework on the first two elements of the sequence.
If there is only one element to this sequence, then the sequence is $a=[n]$, and this has an even number of inversions. If the first two elements are not equal, then we can swap these elements, changing the parity of the number of inversions. This forms a bijection between sequences of sum $n$ with first two elements not equal and an odd number of inversions, and those with an even number of inversions. Otherwise, $a_1=a_2$. Clearly removing these two elements does not change the parity of the inversions. The difference in this case is $C(n-2a_1)$.
Hence, $C(n)=1+C(n-2)+C(n-4)+\dots$.
If $n$ is even, then we have $C(0)=1$, $C(2\times 1)=1+C(0)=2$, and $C(2k)$ is one plus the sum of all terms preceding it. By induction this is $2^k$. If $n$ is odd, $C(1)=1$, and it is clear that $C(2k+1)=C(2k)$. Hence, $C(n)=2^{\lfloor n/2\rfloor}$. We now have $e(n)+o(n)=2^{n-1}$ and $e(n)-o(n)=2^{\lfloor n/2\rfloor}$, where $e(n)$ and $o(n)$ are the number of sequences with an even number and an odd number of inversions, respectively.
By simple arithmetic, it follows that $e(n)=2^{n-2}-2^{\lfloor n/2\rfloor-1}$.
Problem 1.3 (2019 Southeastern Regional 2.4)
Consider a $5\times 5$ matrix $X$ with values from ${0,1}$. Consider the following 24 rows, columns, and diagonals and their reverses:
$$\begin{matrix} (x_{i\ 1},x_{i\ 2},\dots,x_{i\ 5}) & (x_{i\ 5},x_{i\ 4},\dots,x_{i\ 1}) & \text{for }i=1,2,\dots,5 \\ (x_{1\ j},x_{2\ j},\dots,x_{5\ j}) & (x_{5\ j},x_{4\ j},\dots,x_{1\ j}) & \text{for }j=1,2,\dots,5 \\ (x_{1\ 1},x_{2\ 2},\dots,x_{5\ 5}) & (x_{5\ 5},x_{4\ 4},\dots,x_{1\ 1}) \\ (x_{1\ 5},x_{2\ 4},\dots,x_{5\ 1}) & (x_{5\ 1},x_{4\ 2},\dots,x_{1\ 5}) \end{matrix}$$
You are given that these 24 tuples are pairwise distinct. Let the sum of all values of $X$ be $s$. Find all values of $s$.
Solution
Observe that none of these 24 tuples are palindromic, as any tuple and their reverse are both present. However, there are only $2^5-2^3=24$ non-palindromic tuples; therefore, the set of the 24 tuples are exactly the set of the non-palindromic binary tuples of length $5$.
Let this set of 24 tuples be $S$. For any tuple in $S$, its negation, formed by flipping 0’s and 1’s, is also in $S$, and there are 12 such tuple-negation pairs, each of which sum to 5; therefore, $\sum S=12\times 5=60$. Each tuple and its reverse contributes the same to $\sum S$, so $\sum S/2$ is also the sum of the rows, columns, and diagonals. Therefore we have
$$\begin{aligned} \sum x_{i\ 1}+x_{i\ 2}+\dots+x_{i\ 5} +\sum x_{1\ j}+x_{2\ j}+\dots+x_{5\ j} \\ + x_{1\ 1}+x_{2\ 2}+\dots+x_{5\ 5} + x_{1\ 5}+x_{2\ 4}+\dots+x_{5\ 1} & =30 \\ 2s+x_{1\ 1}+x_{2\ 2}+\dots+x_{5\ 5}+x_{1\ 5}+x_{2\ 4}+\dots+x_{5\ 1} & =30\end{aligned}$$
Let us do casework on $s$. This constraint tells us $s\le 15$.
$s=15$ is clearly impossible, as such a constraint would require $x_{1\ 1}+x_{2\ 2}+\dots+x_{5\ 5}+x_{1\ 5}+x_{2\ 4}+\dots+x_{5\ 1}=0$, making $(x_{1\ 1},x_{2\ 2},\dots,x_{5\ 5})$ all zero.
$s=14$ would require that $x_{1\ 1}+x_{2\ 2}+\dots+x_{5\ 5}+x_{1\ 5}+x_{2\ 4}+\dots+x_{5\ 1}=2$. It cannot be the case that $x_{3\ 3}=1$ as then $(x_{1\ 1},x_{2\ 2},\dots,x_{5\ 5})$ is palindromic. Without loss of generality then let $x_{1\ 1}=1$ and $x_{2\ 4}=1$. We now need to somehow fill in
$$\begin{bmatrix} 1 & & & & 0 \\ & 0 & & 1 & \\ & & 0 & & \\ & 0 & & 0 & \\ 0 & & & & 0 \end{bmatrix}$$
Observe that in the fourth and fifth row we cannot fill them with 3 one’s as this makes it a palindrome; likewise we cannot fill the second and fifth columns (from the left) with 3 one’s, either. On the other hand, we need to fill exactly 2 rows or columns with $(1,1,1,1,0)$ and $(1,1,1,0,1)$, and exactly 4 rows or columns with $(1,1,1,0,0)$, $(1,1,0,1,0)$, $(1,0,1,1,0)$ and $(1,1,0,0,1)$. But considering the eliminations above we only have $10-4=6$ rows and columns to fill with these tuples, and there are six tuples.
Then the first, second, and third row, as well as the first, third, and fourth column must have at least 3 one’s. Now, observe that it is impossible to fill any of the fourth and fifth rows or second and fifth columns with $(1,1,0,0,0)$, making a construction impossible.
$s=13$ is possible; there is a construction:
For $s\le 12$, we can use a symmetrical argument, flipping zeroes and ones. Thus $s$ has a construction if and only if $25-s$ has a construction; therefore the only possible $s\le 12$ is $12$.
Thus the set we desire is ${12,13}$.
Problem 1.4 (2019 CGMO 3)
On a sequence of integers, define a movement to be the following operation: Select three adjacent values $a$, $b$, and $c$, and replace these values with $b$, $c$, and $a$. For example, with the sequence $[1,2,3,4]$, the sequence after one movement can be either $[3,1,2,4]$ or $[1,4,2,3]$.
What integers $n\ge 3$ satisfy that the sequence $[1,2,\dots,n]$ can undergo a finite number of movements and become $[n,n-1,\dots,1]$?
Solution
We claim that such a sequence of movements is possible if, and only if, $n\equiv 0\pmod 4$ or $n\equiv 1\pmod 4$.
Necessity. Observe that the parity of inversions is always conserved between movements, as the pairs $(a,b)$ and $(a,c)$ becomes $(b,a)$ and $(c,a)$. Because their contribution to the total inversion count change simultaneously, the total number of inversions change by $-2$, $0$, or $2$. The initial number of inversions is $0$ and the final number of inversions is exactly $n(n-1)/2$, which is even if and only if $n\equiv 0\pmod 4$ or $n\equiv 1\pmod 4$.
Sufficiency. Clearly such a sequence exists for $n=1$. Such a sequence exists for $n=4$, too:
$$[1,2,3,4] \rightarrow [2,3,1,4] \rightarrow [2,1,4,3] \rightarrow [2,4,3,1] \rightarrow [4,3,2,1]$$
On the other hand, for any sequence $[a_1,a_2,\dots,a_{n-4},a_{n-3},a_{n-2},a_{n-1},a_n]$, we can move $[a_1,a_2,\dots,a_{n-4}]$ to the end of the sequence, by "flipping" $a_{n-4}$ over $[a_{n-3},\dots,a_n]$, and then flipping $a_{n-3}$, all the way to $a_1$.
After this finishes, we get $[a_{n-3},a_{n-2},a_{n-1},a_n,a_1,a_2,\dots,a_{n-4}]$, after which we can apply the $n=4$ sequence of movements to $[a_n-3,\dots,a_n]$, getting $[a_n,a_{n-1},a_{n-2},a_{n-3},a_1,a_2,\dots,a_{n-4}]$. It follows by induction that if $n$ is possible, $n+4$ is possible.
Problem 1.5 (2017 Asia-Pacific MO 3)
Let $n$ be a positive integer. Consider the non-increasing sequences of positive integers that sum to $n$. Let $A(n)$ be the subset of those where all values are one less than an integer power of $2$, and $B(n)$ be the subset of those where all values are at least two times the value after it.
Prove that, for any positive integer $n$, $A(n)=B(n)$.
Solution
We demonstrate a bijection between these two quantities.
Let the sequence satisfying the condition for $A(n)$ be $a_1,a_2,\dots,a_m$. Notice that since $a_1=2^x-1$ for some integer $x$, we have $a_1=2^{x-1}+2^{x-2}+\dots+2+1$. Applying this for all values of $a$, we get a diagram that looks like this:
$$\begin{matrix} a_1 & = & 2^{x_1-1} & 2^{x_1-2} & \dots & 2^{x_1-x_2+1} & 2^{x_1-x_2} & \dots & 2 & 1 \\ a_2 & = & 2^{x_2-1} & 2^{x_2-2} & \dots & 2 & 1 \\ \vdots & \vdots & \vdots & \vdots \\ a_{m-3} & = & 8 & 4 & 2 & 1 \\ a_{m-2} & = & 2 & 1 \\ a_{m-1} & = & 1 \\ a_{m} & = & 1 \\ & & b_1 & b_2 & b_3 & \dots \end{matrix}$$
As is standard for problems involving bijections between sequences, we sum vertically. Summing vertically indeed produces a valid sequence satisfying the condition for $B(n)$. Clearly, the sum is conserved. Furthermore, from $b_{m+1}$ to $b_m$, its value at least doubles, with all powers of two contained in $b_{m+1}$ doubling, and the extras manifesting in the form of ones.
This process is uniquely invertible. We can uniquely recover $a$ from the positions of the $1$’s as these $1$’s are the last term in the sum $2^{x-1}+2^{x-2}+\dots+2+1$. To recover the positions of the $1$’s, we look to the difference $b_i-2b_{i+1}$; this quantity tells us the number of $1$’s in the column (column of the above diagram) of $b_m$. These $1$’s must fit precisely above the $1$’s of the last row to ensure that all sums of $a$ terminate with $1$.
This completes the bijection.