AoPS - Problem

Source: Olympic Revenge 2021 #2

Tags: combinatorics, Process

jpedrorvc1

11.11.2021 21:02

Evan is a $n$-dimensional being that lives in a house formed by the points of $\mathbb{Z}_{\geq 0}^n$. His room is the set of points in which coordinates are all less than or equal to $2021$. Evan's room has been infested with bees, so he decides to flush them out through $\textit{captures}$. A $\textit{capture}$ can be performed by eliminating a bee from point $ (a_1, a_2, \ldots, a_n) $ and replacing it with $ n $ bees, one in each of the points: $$ (a_1 + 1, a_2 , \ldots, a_n), (a_1, a_2 + 1, \ldots, a_n), \ldots, (a_1, a_2, \ldots, a_n + 1) $$However, two bees can never occupy the same point in the house. Determine, for every $ n $, the greatest value $ A (n) $ of bees such that, for some initial arrangement of these bees in Evan's room, he is able to accomplish his goal with a finite amount of $\textit{captures}$.

Xrider100

12.11.2021 17:53

Give weight $1/n^S$ to the point $(a_1, a_2, ..., a_n)$, where $\Sigma a_i = S$. It is easy to see that the total weight of the points with bees is invariant under "captures". The total weight of all the points in Evan's room is $(\frac{n^{2022}-1}{(n-1)(n^{2021})})^n$, and the total weight of the points in the whole plane is $(\frac{n}{n-1})^n=(\frac{n^{2022}}{(n-1)(n^{2021})})^n$, thus the total weight of the points outside Evan's room is the difference of the two. Then, just find the largest number of bees you can accommodate in Evan's room, and do this by taking the smallest weights first (near the "vertex" of the n-dimensional house). I'm lazy to do the calculation, do this yourself.

cadaeibf

12.11.2021 19:33

I also thought of that, but this only gives you a upper bound. How do you garantee it to work? For example, consider also the fact that if the bees all lie on $\mathbb{Z}_{>0}^n$ (not $\mathbb{Z}_{\geq 0}^n$) they can never reach a point with a zero coordinate, and so you can't achieve the entire sum of numbers associated to the points outside.

bruckner

13.11.2021 01:42

Firstly, for $n=1$, the answer is clearly $2022$. Now we prove a very powerful lemma: Lemma: For $n \geq 2$, the answer cannot be more than $2$. Proof of Lemma: Let $P$ be the point whose all coordinates are $2021$ (the "corner" of Bob's room), ans $\mathbb{T}$ be the set of points of Bob's house with all coordinates at least $2021$. Whenever the number of bees in his room decreases, it's because he has just operated in $P$ (else, at least one of the new bees would still be inside the room). Now consider the function $f(x_1+2021, \dots, x_n+2021)=n^{-(x_1+ \cdots x_n)}$. There is a simple invariant under the capture operation given by $\sum_{p \text{ has a bee}} f(p)$. Now, let $N$ be the number of times we operated on $P$. Since $N < \sum_{Q \in \mathbb{T}, Q \neq P} Q = (1+n^{-1}+n^{-2}+ \cdots)^n-1=\left( \frac{n}{n-1} \right)^n-1 \leq 3, N \leq 2$, as wanted. $\square$ For $n=2$, the answer is indeed $2$. (I do not have the patience to write the complete steps here, but bees on $(2021,2022),(2022,2022)$ can be fastly removed by a greedy algorithm). $A(3)=1$ can be done by hand: Define $(2022,2021,2021)=Q_1, (2021,2022,2022)=R_1$ (and $Q_2,Q_3,R_2,R_3$ symmetrically). Define $(2022,2022,2022)=S$ too. If we operate in $P$ twice, then we have to operate $Q_i$ at least one time for each $i$ (to give space to the second capture in $P$). But, since operating in $Q_1$ and $Q_2$, for example, generates two new bees for $R_3$, it's easy to see that the $R_i$ must also be operated each one at least once. Finally, since all captures in the $R_i$'s generate bees in $S$, we must operate in $S$ at least two times. But repeating this argument show that all points of the form $(M,M,M)$ for $M>2021$ must be operated, contradicting the finitude of the process. Now, for $n>3$, we prove two bees cannot be removed. For this, suppose they actually could be removed. Then, consider three positions between $1$ and $n$ such that the projection of these bees on such positions gives two distinct three dimensional points. Therefore, being able to remove them in $n$ dimensions implies being able to remove them in $3$ dimensions, which we already proved is impossible.