AoPS - Problem

Problem

Source: 2019 Serbia TST P6

Tags: combinatorics, number

XbenX

19.07.2019 18:15

A figuric is a convex polyhedron with $26^{5^{2019}}$ faces. On every face of a figuric we write down a number. When we throw two figurics (who don't necessarily have the same set of numbers on their sides) into the air, the figuric which falls on a side with the greater number wins; if this number is equal for both figurics, we repeat this process until we obtain a winner. Assume that a figuric has an equal probability of falling on any face. We say that one figuric rules over another if when throwing these figurics into the air, it has a strictly greater probability to win than the other figuric (it can be possible that given two figurics, no figuric rules over the other). Milisav and Milojka both have a blank figuric. Milisav writes some (not necessarily distinct) positive integers on the faces of his figuric so that they sum up to $27^{5^{2019}}$. After this, Milojka also writes positive integers on the faces of her figuric so that they sum up to $27^{5^{2019}}$. Is it always possible for Milojka to create a figuric that rules over Milisav's? Proposed by Bojan Basic

alexiaslexia

26.05.2021 05:56

Basically the jankiest and clunkiest problem I can recall. Gives you a hands-on practice to conjure up obscure Claims, so a plus at that. The answer is $\boxed{\text{Yes}}$; but not in the ways we might first expect. (Another way to see this is $\boxed{\text{No}}$; it's impossible for Milisav to outmanuever Milojka.) Denote a figuric by the (finite) sequence \[ (a_1,a_2,\ldots,a_n,\ldots) \]where $a_i$ is the number of faces with $i$ written on them. To make this finite, only make the sequence last until $27^{5^{2019}}$; as it is impossible to have a number larger than that on the figuric's face. We will sometimes refer the number of faces and the sum of the numbers as $f$ and $s$, respectively. Also, if Milojka can't outmanuever Milisav with his $\textit{insurmountable}$ figuric, we will declare Milisav to win the game.

Getting the obvious out of the bag: observe that a figuric rules over another if and only if after comparing its faces pair by pair (with $f^2$ comparisons), the amount of winning pairs are greater than the amount of losing pairs. $\color{green} \rule{6.3cm}{2pt}$ $\color{green} \clubsuit$ $ \boxed{\textbf{The First Ideas that Matter.}}$ $\color{green} \clubsuit$ $\color{green} \rule{6.3cm}{2pt}$ Assume Milisav can win with the provided $(f,s)$. 1. Let $L$ be the largest $a_i$. Then, $L \geq 2$. (Slang-wise, we will refer the $a_i$s as stacks of coins in the natural-number line.) 2. If $a_x$ and $a_y$ are nonempty stacks and $y \geq 2$, then \[ a_{x}+a_{x+1} \leq a_y+a_{y-1} \]We will call the second assertion as $P(x,y)$. $\color{green} \rule{25cm}{0.2pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$ The first is obvious: if all stacks have one coin, then \[ s \geq 1 +2 +\ldots + f \geq \dfrac{f(f+1)}{2} \]while we know that \[ 27^{5^{2019}} = f^{\log_{26}(27) }\leq f^{1.02} \]The second isn't so hard: we can create $\textbf{a new figuric}$ by moving a coin one step away from $a_x$ (i.e. changing a face's value from $x$ to $x+1$) and moving another coin one step away from $a_y$ (i.e. counteracting the one positive change with one negative change). Comparing this to the initial figuric, we will have changed $a_x$ draw pairs into winning pairs, changed $a_{x+1}$ losing pairs into draw pairs, changed $a_y$ and $a_{y-1}$ draw to losing and winning to draw, respectively. So, since the new figuric have gained $a_x+a_{x+1}$ pairs and lost $a_y+a_{y-1}$ pairs, the conclusion holds (assuming the initial one is insurmountable.) $\blacksquare$ After this, we will establish two more Lemmas of these kind: $\color{cyan} \rule{5.3cm}{2pt}$ $\color{cyan} \clubsuit$ $ \boxed{\textbf{Short-Distance Lemma.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{5.3cm}{2pt}$ Let $a_i = l \geq 2$, and $i \geq 2$. Then, $a_{i-1} \geq a_{i+1}$, and if $a_{i-1},a_{i+1} \geq 1$, then they must be equal. $\color{cyan} \rule{25cm}{0.2pt}$ $\color{cyan} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{cyan} \spadesuit$ Perform $P(i,i)$ to get the first conclusion. Since $i+1 \geq 2$, we can perform $P(i-1,i+1)$ for the second conclusion (i.e. we get $a_{i+1} \geq a_{i-1}$, and we are done by the first conclusion.) $\color{cyan} \rule{5.3cm}{2pt}$ $\color{cyan} \clubsuit$ $ \boxed{\textbf{Long-Distance Lemma.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{5.3cm}{2pt}$ Milisav's figuric cannot cointain $a_m,a_n$ ($m < n$) with $m,n \geq 2$ and $n-m \geq 3$, and $a_{m+1},\ldots,a_{n-1}$ all zero. Furthermore, if $a_{m-1} > 0$, $|n-m|$ must not equal to 2 if there exists another nonzero stack. $\color{cyan} \rule{25cm}{0.2pt}$ $\color{cyan} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{cyan} \spadesuit$ First, perform $P(n,m)$ to get \[ a_n \leq a_{m}+a_{m-1} \]If $a_{m-1} \geq 2$, our job is easy. Indeed, perform $P(m-1,n)$ and $P(m-1,n-1)$ $\textbf{simultaneously}$ (this can be done as there are at least two coins on $a_{m-1}$'s stack) to get \[ a_{n}+2a_{n-1}+a_{n-2} \geq 2 \cdot (a_m+a_{m-1}) \]This is false, since we know that $a_{n-1} = 0$ and $a_{n-2} \leq a_m$ --- with equality iff $n-m = 2$. If $a_{m-1} = 1$, then do that again, but that forces \[ n = m+2, \ \text{and} \ a_{n} = a_m+1 \geq 2 \]Perform $P(m-1,n)$ and $P(n,n-1)$ simultaneously to get a contradiction (as we have successfully generated $2a_m+2$ more wins and $2a_m+1$ more losses.) If $a_{m-1} = 0$, a little extra care is needed; perform $P(m,n)$ and $P(\text{nonzero stack},n-1)$ simultaneously to get a contradiction (if $|n-m| \geq 3$). $\blacksquare$ $\blacksquare$ $\color{magenta} \rule{25cm}{0.2pt}$ The second part is done (where most of the technical work and Lemma lies): now it's time to get to the fun part, where Milojka finally uses this principles to attack whatever figuric Milisav may possess! $\color{yellow} \rule{10cm}{2pt}$ $\color{red} \diamondsuit$ $\color{red} \boxed{\textbf{Finishing: Decoding Every Weak Spot Milisav has.}}$ $\color{red} \diamondsuit$ $\color{yellow} \rule{10cm}{2pt}$ First, Milojka will select a biggest-sized-stack. Call that $a_k = L$. For neighboring-stack reasons, pick the one with $k \geq 2$. (Verify that unless all numbers of the figuric are less than three, $k$ must exist!) By $\color{cyan} \clubsuit$ $ \boxed{\textbf{Short-Distance Lemma}}$ $\color{cyan} \clubsuit$, \[ (a_{k-1},a_{k+1}) = (a,a) \ \text{or} \ (b,0) \ \text{or} \ (1,0) \ \text{or} \ (0,0) \]with $a \geq 1$, $b \geq 2$. If $a \geq 2$, we can chain down the sequence up to $a_1$; yielding the sequence up to $a_{k+1}$ to alternate. Similarly, all terms above $a_{k+1}$ can be chained up, since there will be 2 or more coins in the rightmost stack. Here, if the chain stops at $a_m$ but there exists a coin beyond $a_{m+1}$ (say it is located at $a_n$), we can apply the $\color{cyan} \clubsuit$ $ \boxed{\textbf{Long-Distance Lemma}}$ $\color{cyan} \clubsuit$ to instantly derive a contradiction. (The case $b \geq 2$ is very similar to this case.) If $a = 1$, we do not have the luxury to chain down by using leftmost coins only (since the Short-Distance Lemma doesn't necessarily hold) but we can ensure the conclusion by $P(k,\text{leftmost stack})$ when chaining down from $a_i = 1$ to $a_{i-1} = L$, or just by the Short-Distance Lemma when $a_i = L$ to $a_{i-1} = 1$. For chaining up, if exists $a_m$ and $a_n$ as in the prior case, as $a_{m-1},a_m > 0$, we are done analogously. $\color{yellow} \rule{25cm}{0.2pt}$ If $(a_{k-1},a_{k+1}) = (1,0)$, we can directly apply the Long-Distance Lemma to nullify all stacks beyond $a_{k+2}$ (as $a_{k-1} = 1 > 0$). By $P(k,k-1)$ (if $k \geq 3$) we get \[ a_{k-2} + 1 \geq a_k = L \]Since $a_{k-2} \leq L$, $a_{k-2} \in \{L-1,L\}$. If $a_{k-2} = L$ we can apply the case $a=1$ here. Otherwise, let $a_{k-2} = L-1$. We will prove that $k = 3$ (which will give us the $(n-1,1,n)$ config). If not, $P(k-1,k-2)$ yields $a_{k-3} \geq 2$. Finally, $P(k-3,k-1)$ yields a contradiction. If $(a_{k-1},a_{k+1}) = (0,0)$, observe that \[ a_i = L \ \text{implies} \ a_{i-1} = a_{i+1} = 0\]by $P(i,k), P(i-1,k)$. Following from that, we can $\textit{chain down in periods of two}$ from $a_k$ by using a variance of the Long-Distance Lemma. Similar to above, we chain up first. If there exists a stack above $a_k$, the adjacent stack must be $a_{k+2}$ by (the second part of) Long-Distance Lemma, and it must have $L$ coins. Do this until there is no coins above a certain stack. Chaining down, if we have $a_{k'} = L$ for some $k' \geq 4$, we can prove that $a_{k'-2} = L$ as long as $f \ne 3$. Since we know that $a_{k'-1} = 0$, if $a_{k'-2}$ is also $0$, we simultaneously perform $P(k',k')$ and $P(\text{other nonzero stack},k'-1)$ for a contradiction. As there is a coin in $a_{k'-2}$, applying $P(k',k'-2)$ gives us $a_{k'-2} = L$ (as long as $k' \geq 4$). Now, if $k' = 3$ and $L \geq 3$, we can get away with simultaneously performing $P(3,3)$ and $P(3,2)$ to yield $a_1 = L$. If $L = 2$, again, $f \ne 3$ and the above procedure yields our result. Aside from the outliers $(1,0,2)$ and $(1,0,1,1)$, we have categorized all Milisav's win position. $\color{blue} \rule{3.7cm}{2pt}$ $\color{blue} \diamondsuit$ $\color{blue} \boxed{\textbf{Just Counting.}}$ $\color{blue} \diamondsuit$ $\color{blue} \rule{3.7cm}{2pt}$ We can eliminate the case $(n-1,1,n)$ easily. For the case $(p,q,\ldots,p,q)$ and $(p,q,\ldots,q,p)$, notice that Milisav can construct those figurics iff they satisfy the equations \begin{align*} n(p+q) &= 26^{5^{2019}} \\ n^2p+n(n+1)q &= 27^{5^{2019}} \\ \end{align*}or \begin{align*} (n+1)p+nq &= 26^{5^{2019}} \\ (n+1)^2p+n(n+1)q &= 27^{5^{2019}} \\ \end{align*}have a solution with $n > 1$ (the case $n = 1$ is easily eliminated, too, as $s > f$). But that would imply that $\gcd{(26^{5^{2019}},27^{5^{2019}})} > 1$, a contradiction. Four janky Claims and we are finally done. $\blacksquare$ $\blacksquare$ $\blacksquare$

$\color{red} \text{The irrelevant cases.}$ First: $f = 3$. A stack of size $3$ will either place it in the $(0,p,0)$ or $(p,0)$ category; or it will succumb after two applications of $P(x,y)$. A stack of size 2 can only be accompanied by a coin in $a_1$ (otherwise we can move one coin 1 unit backwards and one other coin 1 unit forwards; there are two cases here.) Also check that the sized-two-stack must be from $a_2$ by two-unit-apart rule (i.e. Long-Distance Lemma.) The rest is the case $L = 1$, or all numbers in the figuric are different. Easily, we can infer that no two stacks are 3 units apart or more, or we can move one coin two steps backwards (and only lose one pair) and two coins one step forward. So, assuming that all stacks are 2 units apart, we get the config $(0,1,0,\ldots,1)$ or $(1,0,1,\ldots,1)$. However, if there are two stacks that are one unit apart (say $a_k$ and $a_{k+1}$) we can apply $P(k,l)$ to whatever stack $a_l$ with $a_l \geq 0$ and $l \geq 2$ to get a contradiction. So, the only way Milisav can protect his win is to have \[ a_l + a_{l-1} = 2 \]for every $l \geq 2$ (i.e. building the config $(1,1,\ldots,1)$) or having the only $l$ with $a_l \geq 0$ to be when $l = 1$ --- hence the config $(1,0,1,1)$. Note that the config \[ (1,0,\ldots,0,1,1) \]cannot be an insurmountable figuric by the two-unit-apart rule. $\color{red} \text{Verifying the win configs.}$ The ones except $(p,q,p,\ldots,q)$ and $(p,q,p,\ldots,q,p)$ are easy to verify, so we only verify these. Say Milisav wishes to prove to Milojka that these configs are indeed insurmountable. Now, take any figuric Milojka may create, and subject it to the procedure as follows: Assign each of Milojka's $f$ coins to Milisav's $f$ coins, and every turn, a third observer will choose a pair of Milojka's coins $c_1,c_2$ so that $c_1,c_2$ is located to the left and right of its pair, respectively. Note that this process will end, since the sum of the initial differences is finite. By doing this, we can tell that this process will strengthen Milojka's position towards Milisav's figuric every turn, since $c_1$ will bring an increase of exactly $p+q$ win-pairs, and $c_2$ will bring at most $p+q$ more lose-pairs. At the end of this process, Milojka will have a figuric which is exactly Milisav's, and even then, her figuric only draws with his. So, she cannot have a figuric which rules over Milisav's figuric before it undergoes this process. (This method can also be used to more easily verify the figuric $(n-1,1,n)$. Notably, each increase will bring the value up by $n$ or $n+1$, and assuming that there are less than $n$ coins which lie beyond $a_4$, all of those can be paired with coins on $a_3$ for a value decrease of at most $n$ per move.)

From reading this Solution alone, the jank can be seen at every corner of it. If some problems can be cheesed with one singular observation, this problem keeps dispelling possible re-wordings until all the cases have been exhausted. $\color{green} \rule{25cm}{2pt}$ $\color{red} \text{Sec 1: Motivating Stack Sizes.}$ Since the consideration of $f = 2$ is worse than useless, I started to consider $f = 3$ first. Here I made the problem change its skin by shifting $(a_1,a_2,\ldots)$ to $(a_0,a_1,\ldots)$ --- and while it made the visualisation of $s = 1,2,3$ much easier, the larger numbers prove to be very difficult. While $s' = 3$ (or $s = 6$, in the standard sense) has only three configs $[1,1,1]; [0,1,2]; [0,0,3]$ ($[a,b,c]$ denoting the figuric with faces $a,b,c$; this is to differentiate this notation with the $(a_1,a_2,\ldots)$ notation), $s' = 4$ starts to present figurics with lots of $\textit{personalities}$. You can try this for yourself (I first did this by drawing graphs with $[a,b,c]$ as edges; and drawing tables with the upper row/leftmost column denoting the figurics' numbers, and the $3 \times 3$ entries denoting which side wins) and see that $[2,2,0]$ and $[3,2,0]$ is insurmountable --- and this made me think whether two insurmountable figurics can exist with one $(f,s)$. Granted, with the configs $(p,q,\ldots,p)$ later that they can indeed be equal (though whether or not they can will require lots of computation); but this observation is still so far removed from the correct way to think things through. The realization that made it apparent to use the number line notation was the relations \[ [2,2,2] \leq [3,3,0] \leq [4,1,1] \leq [2,2,2] \]with there doesn't seemingly exist other figurics combatting each of the listed three. Closer inspection yields those to be somewhat attached with each other: especially they all entail one backwards step of two units and two forwards step of one unit! I also asked the question: what happens if Milisav is allowed to use real numbers? What if only Milojka? What if both? Here, the obvious answer can be found for the second question: Milojka can move one counter left by $\dfrac{1}{n}$, and move the rest of them to the right by $\dfrac{1}{n(f-1)}$, adding lots of value to her figuric when compared to Milisav's. Adding $\textit{values}$ to each counter's movement yields equation mostly consisting of $a_y+a_{y-1}$; but I didn't realize the possibility of having $\textbf{both}$ \[ a_y,a_{y-1} > 0\]until later. Instead, I aimed to make the gaps as large as possible to warrant a movement of one coin to the left (say $t$ times), and adding value to $t$ coins by moving it right one unit. Specifically, I tried this with $f = 4$, and found this more effective than anticipated, especially with gaps 3 units and above. I conjectured that when $s$ is sufficiently large compared to $f$, Milojka can launch an effective counter; but this is still in the shadows. For now, instead of setting the movements to be in the form $a_x+a_{x-1}$, I opted for adding weights in $\textbf{coin stacks}$. Namely, if $a_7$ has four counters, I assigned each of them to have four value; and I put arrows to each of the coins on where they can go. This is redundant since any coin from $a_i$ could go left at most $i$ times (assuming we still use the $s'$ notation), and the 0-coins can only traverse right-wards. $\color{green} \rule{25cm}{2pt}$ $\color{red} \text{Sec 2: Distances and Linearity; when the Largest-Sized Stack will tackle both.}$ Aside from individual stack values (which are obvious but beautiful in their own way), I also assigned a distance marker for each point: say I have the config \[ (2,0,5,1) \]the coins' distance marker would be $D(c_1,c_2) = \{+2\}$; $D(c_3,\ldots,c_7) = \{-2,+1\}$ and $D(c_8) = \{-1\}$. I noted that the smaller the positive marker is, the better they are to ge moved rightwards, and so the mission is actually finding two stacks which are near, and two stacks so far apart that they can provide a somewhat enough space for the right-side of the stack to move left. While the first pair is relatively easy to find, I realized that $27^{5^{2019}}$ is a lot closer to $26^{5^{2019}}$ than I thought. After that, challenging my initial notion that the coins need to distance themselves from each other, I noted that the config \[ (1,1,\ldots,1) \]is actually unbeatable; and we might as well create something like that with $(f,s) = (n,O(n^2))$. If size is the sole reason for Milojka to ensure her win, couldn't Milisav just create a dense enough figuric to render her (rudimentary) distance-manipulation tech useless? Bonus.Here I conjured the Claim that if a size has $c$ coins, their left-marker must $\in \{-c,-(c-1),\ldots,-1\}$. This is just a glorified version of the 3-unit rule of $f = 4$, and it's very easy for Milisav to construct a figuric where no coin has a large-enough left-marker. The proof for this is bland, though --- move the coin $c$ times to the left for a value loss of $c$, and move $c$ coin one times to the right, with one of them having value $2$ or more. Note the layered approach to prove $\textbf{even the most basic claim.}$ Seeing that it is inevitable for Milisav to create a large stack of coins (assuming the sequence $(a_1,a_2,\ldots)$ is dense), I wanted to gauge out its relative size to both $f$ and $s$. Seeing that \[ s \sim f^{1.02} \]I successfully proved that there must exist a stack of $L \geq f^{0.51}$ coins (by casework on whether the number of stacks is greater or less than $\sqrt{f}$.) Here I could've bet that I can improve this somewhere closer to $f^{0.6}$, but I didn't see a clear way out even if it is so. Namely, I wondered what would happen if I moved all $L$ coins rightwards, and move some other $L$ coins exactly one unit leftward. For this to be a strictly positive gain, the $L$ coins must lose at most $L$ value, and there came the janky formulation of \[\begin{tabular}{p{12cm}} If there exists $\leq \frac{n-L}{2}$ coins in stacks of size between $\frac{L}{2}$ and $L$, we are done. \end{tabular}\]as we can transfer the ones which are not on big stacks, nor to the right of some big stack leftwards. Not only is this inefficient (we can just choose one coin which has the greatest $a_x+a_{x+1}$) but also ineffective (what if $L = O(f)$?) Here I finally considered a stack of $L$ coins on its own, and paid more attention to its surroundings. I boldly conjectured that almost all configs have the same $a_i+a_{i+1}$, for $i$ less than some $N$ (meaning that it will be strictly regular, with no indents or protrusions.) $\color{green} \rule{25cm}{2pt}$ $\color{red} \text{Sec 3: Handling Big Gaps.}$ A final obstacle to overcome is the blatantly long casework surrounding one particular $L$. Sure, chaining up and down is easy enough when $a_{k-1}$ and $a_{k+1}$ are supportive --- but that isn't always the case! (Especially with $(n-1,1,n)$.) In short, the case $(1,L,0)$ points back up to $(1,L,1)$ once $a_{k-2} = L$ --- but even in the case of $(1,L,1)$, chaining up isn't always easy. While the finiteness must guarantee it to stop, we can't necessarily control what happens $\textbf{after}$ the chain is over. This kind of brought back the 3-unit rule earlier, with a twist: there must be a nonzero stack ready to be moved to the right somewhere. Hence, the unnecessarily (or necessarily, if you're working on the same page as myself) division where $L \geq 3$, and $k \geq 3$. Finally, to eliminate the case of $(1,0,2)$ and the case of \[ (a_{k-1},a_k,a_{k+1}) = (0,L,0) \]in general, I had to consider the case of moving the coin in $a_3$ and $a_4$ to the left two times (akin to the Long-Distance Lemma, worded another way.) \[\begin{tabular}{p{12cm}} $\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\ \end{tabular} \\ \]