In some squares of a $2012\times 2012$ grid there are some beetles, such that no square contain more than one beetle. At one moment, all the beetles fly off the grid and then land on the grid again, also satisfying the condition that there is at most one beetle standing in each square. The vector from the centre of the square from which a beetle $B$ flies to the centre of the square on which it lands is called the translation vector of beetle $B$. For all possible starting and ending configurations, find the maximum length of the sum of the translation vectors of all beetles.
Problem
Source: 2012 China TST Test 3 p6
Tags: vector, geometry, geometric transformation, analytic geometry, combinatorics proposed, combinatorics
27.03.2012 18:02
If vectors are added as they would in normal vectors, the maximum length of the sum of the translation vectors is 0, since for any beetle, the translation vectors of it, the original beetle on the square it occupies, the original beetle of the square this second beetle occupies, and so on, must form a cycle and hence their sum is 0. Summing over all cycles, the sum of all translation vectors will certainly be 0. Do you mean "the maximum sum of the lengths of the translation vectors" as opposed to "the maximum length of the sum of the translation vectors"?
28.03.2012 14:42
chaotic_iak wrote: If vectors are added as they would in normal vectors, the maximum length of the sum of the translation vectors is 0, since for any beetle, the translation vectors of it, the original beetle on the square it occupies, the original beetle of the square this second beetle occupies, and so on, must form a cycle and hence their sum is 0. Summing over all cycles, the sum of all translation vectors will certainly be 0. Do you mean "the maximum sum of the lengths of the translation vectors" as opposed to "the maximum length of the sum of the translation vectors"? The problem states: "In some squares of a $2012\times 2012$ grid there are some beetles". Since some of the squares may be empty, the translation vectors do not necessarily add up to 0.
28.05.2012 06:14
18.08.2021 16:44
Solved with AwesomeYRY. The maximum length is $\boxed{\frac{1}{4} 2012^3= 2036216432}$. This is achieved when each square in the left half of the square contains a bug at the beginning, and each bug moves $1006$ squares to the right. If there are beetles $A,B,C$ such that $A$ flies to $B$'s square and $B$ flies to $C$'s square, we may achieve the same vector sum by having $A$ fly to $C$'s square. So we may assume no square is both a starting and ending position. Let the center of the grid be $O.$ See that $\overrightarrow{AB} = -\overrightarrow{OA}+\overrightarrow{OB}$ for all vectors $A,B.$ So if $S$ is the set of all vectors between $O$ and a square center, we are negating not more than half of the vectors, leaving the same number of vectors unchanged, and multiplying the rest by $0.$ Let the end vector be in the direction of the unit vector $\vec{v} = \left\langle \cos(\theta), \sin (\theta) \right\rangle.$ Suppose WLOG $\cos(\theta) \ge \sin (\theta) \ge 0.$ For any vector and its negative in $S,$ clearly the magnitude is maximized when we negate the one with nonpositive dot product and leave the nonnegative one unchanged. Thus the desired magnitude has a maximum of $$\sum_{i=0}^{1005}\sum_{j=0}^{1005}\left( (2i+1)\left|\cos\left( \theta \right)+(2j+1)\sin\left(\theta \right)\right|+\left|(2i+1)\cos\left( \theta \right)-(2j+1)\sin\left(\theta \right)\right| \right)$$(through dot product properties) which becomes $$2\sum_{i=0}^{1005}\sum_{j=0}^{1005}\max((2i+1)\cos\left( \theta \right), (2j+1)\sin\left( \theta \right)).$$We prove $\sum_{i=0}^{n}\sum_{j=0}^{n}\max((2i+1)\cos\left( \theta \right), (2j+1)\sin\left( \theta \right) \le (n+1)^3$ through induction finishing the problem. Let $X =\sum_{i=0}^{n-1} \max((2n+1)\cos\left( \theta \right), (2i+1)\sin\left(\theta \right)).$ Let $Y =\sum_{i=0}^{n-1} \max((2i+1)\cos\left( \theta \right), (2n+1)\sin\left(\theta \right)).$ It suffices to show $$X+Y+(2n+1)\max(\cos\left( \theta \right), \sin\left(\theta \right)) \le 3n^2+3n+1.$$ Earlier we've supposed that $\cos(\theta) \ge \sin(\theta) \ge 0,$ so our inequality reduces to $(n+1)(2n+1) \cdot \cos(\theta) +Y\le 3n^2+3n+1.$ Let $m$ be the smallest integer such that $(2m+1) \cos(\theta) \ge (2n+1) \sin(\theta).$ We have that $Y = (n^2-m^2) \cos(\theta) + (2n+1)(m)\sin(\theta).$ It's well known that $a \cos(\theta) + b \sin(\theta)$ is maximized at $\sqrt{a^2+b^2}$ which is in this case $\sqrt{(m(2n+1))^2+(3n^{2}+3n+1-m^{2})^2}.$ From there we verify $(m(2n+1))^2+(3n^{2}+3n+1-m^{2})^2 \le (3n^2+3n+1)^2$ for all valid choices of $m.$ (This requires some expansion but doesn't end up being too bad.) $\square$
24.02.2023 00:08
Fakesolved at first but you just try shapes until something works The answer is $\frac{2012^3}{4}$, which is achieved by moving $\frac{2012^2}{2}$ beetles which start on the left half of the grid each $\frac{2012}{2}$ units to the right. We now prove that this is maximal. Suppose that the beetles start at positions $X_i$ and end at positions $Y_i$, and let $O$ denote the center of the board. Then by the triangle inequality, $$\left|\sum \overrightarrow{X_iY_i}\right|\leq \left|\sum \overrightarrow{OX_i}\right|+\left|\sum \overrightarrow{OY_i}\right|.$$Thus we will prove that $\left| \sum \overrightarrow{OX_i}\right| \leq \frac{2012^3}{8}$. This will be by the triangle inequality again, applied smartly. WLOG suppose that $O=(0,0)$, and scale the board so that the gridlines are of the form $x=2i$ and $y=2i$ for integers $i$, so the closest square centers to $O$ are $(\pm 1, \pm 1)$. For $1 \leq n \leq 1006$, consider the set $S$ of points $(x,y)$ such that $\max\{|x|,|y|\}=2n-1$, which forms a square-shaped "frame". Define $f(A)=\sum_{P \in A} \overrightarrow{OP}$, where $A \subseteq S$. I claim that we have the key bound $$|f(A)| \leq 6n^2-6n+2.$$To prove this, we observe the following "smoothing"-type facts: If $A$ contains two opposite points of the form $(a,b)$ and $(-a,-b)$, we can delete both without changing anything. If $A$ does not contain $(a,b)$ nor $(-a,-b)$, then one of them must form a non-obtuse angle with $f(A)$, so adding that one to $A$ will increase $|f(A)|$. If $A$ contains some $(a,b)$ which forms an obtuse angle with $f(A)$, then removing it from $A$ will increase $|f(A)|$. Hence if $|f(A)|$ is maximal, we must have $|A|=|S|/2=4n-2$, but also that the range of the arguments of the vectors formed by elements of $A$ is at most $180^{\circ}$. On the other hand, it can't be exactly $180^{\circ}$ by the first property, hence we find that $A$ must be formed from a contiguous run of points $4n-2$ points along the frame. The rest of the problem is essentially algebraic. We only have to consider $A$ which satisfy the above requirements, which means that some entire "side" of the frame (i.e. along the one of the lines $x=2n-1$, $x=1-2n$, $y=2n-1$, and $y=1-2n$) must be contained in $A$: WLOG the right side ($x=2n-1$). Then additionally suppose that the rightmost point on the top side has $x$-coordinate $2(n-k)-1>0$, so the rightmost point on the bottom side has $x$-coordinate $2(k-n)+1<0$ (where $k \geq 0$) In this case, the $x$-component of $f(A)$ equals $$2\sum_{i=n-k}^{n-1} (2i-1)+2n(2n-1)=2k(2n-k-2)+2n(2n-1).$$Further, the $y$-component of $f(A)$ is $$-2(2n-1)(n-1-k).$$Therefore, if $m=n-1-k$, we have \begin{align*} |f(A)|^2&=(2m(2n-1))^2+(2(n-1-m)(n-1+m)+2n(2n-1))^2\\ &=4m^2(2n-1)^2+(6n^2-6n+2-2m^2)^2\\ &=36n^4-72n^3+60n^2-24n+4+4m^2(m^2-2n^2+2n-1). \end{align*}Because $k \geq 0$, $m \leq n-1$, so $$m^2-2n^2+2n-1\leq (n-1)^2-2n^2+2n-1=-n^2\leq 0,$$so $$36n^4-72n^3+60n^2-24n+4+4m^2(m^2-2n^2+2n-1)\leq 36n^4-72n^3+60n^2-24n+4=(6n^2-6n+2)^2,$$which is the desired bound. To finish, by summing our bound over $1 \leq n \leq 2012$, we have $$\left|\sum \overrightarrow{OX_i}\right|\leq \sum_{n=1}^{1006} (6n^2-6n+2)=\frac{2012^3}{4}.$$Remembering that we scaled by a factor of $2$, this implies that we actually have $\left| \sum \overrightarrow{OX_i}\right| \leq \frac{2012^3}{8}$, which is the desired result. $\blacksquare$
31.12.2024 17:11
Woozy Construction Have all $\frac{2012^2}{2}$ beetles start on the bottom of the grid and move up $\frac{2012}{2}$ squares, for a total length of $\frac{1}{4} \cdot 2012^3$. Bound Claim: WLOG we can replace the beetles with white and black squares and consider the vector from the sum $B$ of the black square positions to the sum $W$ for white square positions. Proof. If the destination of a beetle $b$ is the same as the starting position of another beetle $b_1$, we can delete $b_1$ and make $b$ travel to the destination of $b_1$. Repeat this until no two beetles has the same starting position as anothers ending position. $\blacksquare$ Note that for any vector $v$ and $w$, one of $v+w, v-w$ has longer length than $w$. We can thus WLOG that every square of the grid is colored white or black by taking a pair of uncolored squares and considering the two ways of coloring one white and the othe rblack. Let $O$ be the center of the grid and the origin, and refer to squres by their center coordinates. We first claim the following: Claim: There exists a line $\ell$ through $O$ such that all squares with center strictly on one side of $\ell$ are white and all squares strictly on the other are black, and no cells lie on $\ell$. Proof. Let the sum vector $S \coloneq W - B$. Note that if $w, b$ are the center of white and black squares, then it must follow that \[ \langle S, w \rangle > \langle S, b \rangle \]else swapping the two squares increases the length of $S$. This implies the existence of such a line $\ell'$ perpendicular to $S$. The line through $O$ perpendicular to $S$ has an equal number of points on both sides, and since shifting $\ell$ by $c \cdot S$ is monotonic in $c$, it follows that either $\ell' = \ell$ or $\ell'$ can be perturbed to the line through $O$ without intersecting any other lines. $\blacksquare$ As such, we get that $S \coloneq 2W$, so we consider the maximal vector length of $W$. WLOG we can suppose $W$ has a larger $y$ coordinate than $x$ coordinate (as equality can't hold by the above and monotonicity). Define $Y, X$ as the $y, x$ coordinates of $W$. Let $\mathcal{W}$ consist of the white cells. WLOG that $\mathcal{W}$ contains the top right corner. Then since a line $\ell$ with angle between $0^\circ$ and $45^\circ$, right side exclusive, it follows that for some Young Tableaux $\mathcal{T}$ strictly bounded between $x = 0, x = y$ and the square centers upper half plane $\mathcal{H}$, that \[ \mathcal{W} = \mathcal{H} \setminus \mathcal{T} \sqcup -\mathcal{T} \]If we define $a, b$ as the sum of the $y$ and $x$ coordinates in $\mathcal{T}$ respectively, it remains to show that \[ (Y - 2a) + (2b)^2 \le Y^2 \iff 2(a^2 + b^2) \le aY \iff a + \frac{b^2}{a} \le \frac{Y}{2}. \]By the constraints, we have that $|a| \ge |b|$ due to where each point is, so it remains to show that \[ a + b \le \frac{Y}{2} \]which holds since $2a + 2b$ is the sum of coordinates of all elements of $\mathcal{T}$ removing the points on $x = y, x = -y$.