Pasha and Vova play the following game, making moves in turn; Pasha moves first. Initially, they have a large piece of plasticine. By a move, Pasha cuts one of the existing pieces into three(of arbitrary sizes), and Vova merges two existing pieces into one. Pasha wins if at some point there appear to be $100$ pieces of equal weights. Can Vova prevent Pasha's win?
Problem
Source: All-Russian Olympiad 2019 grade 10 problem 2
Tags: Combinatorial games, game strategy, arithmetic, combinatorics
24.04.2019 04:49
Cool problem! The answer is no, Vova cannot prevent Pasha from winning. For convenience, we will refer to the two players as V and Sasha from now on. We will now show that Sasha has a winning strategy. Before doing so, we'll define some terminology. Call two positive real numbers $\mathbf{equivalent}$ if they differ by a factor of a power of $3$. For instance, $1$ and $9$ are equivalent, $\pi$ and $\frac{\pi}{27}$ are equivalent. Call two pieces of plasticine $\mathbf{equivalent}$ if their weights are equivalent to each other. Sasha's winning strategy will proceed in two stages. In the first stage, Sasha will generate $100$ equivalent pieces of plasticine. In the second stage, Sasha will use this to then create $100$ pieces of equal masses. To do so, he will first simply cut the plasticine into three pieces. After V's next move, there will then be two pieces of masses $a$ and $b$. Henceforth, he will set aside the piece of mass $b$, and focus his attention on creating pieces with masses equivalent to $b$ or $2b.$ Indeed, the following observation shows that the first step can be easily completed. $\mathbf{Observation.}$ Using a piece of weight $a$, Sasha can cut it in such a way that after V merges together two of the three parts, some remaining part will be equivalent to a piece of mass $b$ or a piece of mass $2b$. $\mathbf{Proof.}$ Simply cut it into pieces of weight $a-2x, x, x$, where $x$ is a sufficiently small real number of the form $\frac{b}{3^k}$ for $k \in \mathbb{N}$ big. $\blacksquare$ Using this process, it's easy to see that Sasha can eventually generate at least $199$ pieces with masses equivalent to $b$ or $2b$. By Pigeonhole, at least $100$ out of these $199$ are equivalent, call their masses $p_1, p_2, \cdots, p_{100}.$ Now, having obtained these $100$ pieces, Sasha will proceed onto stage two. $\mathbf{Observation.}$ If Sasha has a piece of mass $m$, he can cut it in such a way to replace it with a piece of mass $\frac{m}{3}$ on the next move. $\mathbf{Proof.}$ Just cut it into three equal pieces. $\blacksquare$ With this observation, it's easy to see that for any choice of $a_1, a_2, \cdots, a_{100} \in \mathbb{Z}_{\ge 0}$, Sasha can ensure in finite time that there exist $100$ distinct pieces of plasticine with masses $\frac{p_1}{3^{a_1}}, \frac{p_2}{3^{a_2}}, \cdots, \frac{p_{100}}{3^{a_{100}}},$ and so picking suitable $a_1, a_2, \cdots, a_{100}$ will allow Sasha to generate $100$ pieces of equal masses, as desired. Sasha wins! $\square$
27.04.2019 16:04
Let $a,b$ denote the number of pieces of sizes $1,2$ (the original has size $3^k$ for some $k$ to be determined later). On the first move P splits the big piece into $1,1,\text{big}-2$. From now on, note that in every move V can only do one of the following, assuming besides the largest part, the other parts have sizes $\le 2$: 1. Merge 2 pieces of 1 into a 2. P splits 1,1 from big piece again. 2. Merge 1 and 2 into a 3. P splits 3 into three pieces of 1. 3. Merge 2 pieces of 2 into a 4. P splits 4 into 2,1,1. The net change in $a + b$ is $+1$ in any case, so after $23333333$ moves one of $a,b$ will exceed $100$. Now set $k = \lfloor e^{66666666666} \rfloor$ gives the desired result.
18.08.2019 11:57
Let the weight of original plasticine 500. Pasha's strategy is taking the heaviest plasticine and cut it into 1, 1 and the remaining. Then every pieces are integer-weighted. Pasha can do this until every pieces has weight less than 3. So there must be some 100 pieces with same weight 1 or 2. (I was confused since this seems to easy for ARMO, but according to official solution I didn't misread the question anyway.)
10.03.2020 00:28
Solution with Aatman Supkar, Aditya Khurmi, Alan, Anant Mudgal, Arindam, Derek Liu, Ethan Liu, Jeffrey Kwan, Eric Shen (CAN), Leo Zipeng Lin, Maximus Lu, Misheel Otgonbayar, Paul Hamrick, R Correaa, Robin, Rohan Goyal, Sean Li: The answer is that Pasha can win. Let $M$ be a large integer and assume WLOG (by scaling) that there are $M$ grams of plasticine. Claim: Suppose that any time there is a piece with at least $3$ grams of weight, Pasha splits it into three pieces of integer weight. Then this strategy is winning for Pasha if $M$ is large enough. Proof. This algorithm must eventually terminate because after each of Pasha and Vova's moves, the number of pieces has overall increased by $1$. But it can only terminate if all pieces have weight $1$ or $2$. Thus as long as $M > 500$ then Pasha has won. $\blacksquare$
18.05.2020 18:04
Let us have a $1$ kilogram plasticine initially. We begin with a very intuitive claim. Claim. At some point there are only $1$ and $2$ gram weighted pieces on the table . Proof. Regardless of Vova's play in his turn , Pasha can always make more pieces of plasticine in each turn ,and after every pair of Pasha-Vova plays the number of plasticine pieces strictly increases (at least by $1$), so this eventually happens .$\square$ Now back to the main problem , FTSC assume Pasha cannot win even after this claim ! (i.e. there're less than $100$ pieces of $1 ; 2$ gram weighted pieces). But then the total weight $=1000<1.100+2.100=300$ ,contradiction. $\blacksquare$
10.08.2020 02:00
Different solution. Pasha wins. Suppose the initial piece of plasticine has weight $1$. We claim the following strategy for Pasha is winning: Suppose all pieces are of the form $2^{-n}$ for $n \in \mathbb{N}$, and let $2^{-x}$ be the heaviest piece. Pasha splits this into pieces with weights $2^{-x - 1}, 2^{-x - 1}, 2^{-x - 2}$. Suppose that, in Vova's previous move, he combined the pieces $2^{-a}$ and $2^{-b}$ for $a > b$. Pasha splits the piece of weight $2^{-a} + 2^{-b}$ into pieces with weights $2^{-a}, 2^{-b - 1}, 2^{-b - 1}$. This maintains the invariant that, after each of Pasha's moves, all pieces are of the form $2^{-n}$ for $n \in \mathbb{N}$. Hence, on each of Vova's moves, he combines two pieces of the form $2^{-a}$ and $2^{-b}$ (possibly where $a = b$); thus, at any time, all pieces are of one of the forms $2^{-a} + 2^{-b}$ and $2^{-n}$, meaning that the above algorithm always produces a unique move for Pasha. Claim: Suppose that Pasha has just moved. There exists $m \in \mathbb{N}$ such that the weight of each piece is in the set $\{2^{-m}, 2^{-m - 1}, 2^{-m - 2}\}$. Proof: We prove this by induction. After Pasha's first move, the pieces on the board have weights $2^{-1}, 2^{-2}, 2^{-2}$. Consider a move made by Pasha. Suppose he splits $2^{-x}$, for some minimal $x$, into $2^{-x - 1}, 2^{-x - 1}, 2^{-x - 2}$, each of which is in the set $\{2^{-x}, 2^{-x - 1}, 2^{-x - 2}\}$. By induction, each of the other pieces has weight in the set $\{2^{-x}, 2^{-x - 1}, 2^{-x - 2}\}$; hence, we are done in this case. Otherwise, suppose Pasha splits $2^{-a} + 2^{-b}$ (where $a > b$) into $2^{-a}, 2^{-b - 1}, 2^{-b - 1}$. Prior to this move, suppose the heaviest piece is $2^{-M}$. By induction, $a, b \in \{ M, M + 1, M + 2 \}$. As $a > b$, we have $M \leq b \leq M + 1$, or $M + 1 \leq b + 1 \leq M + 2$, so $a, b + 1 \in \{ M, M + 1, M + 2 \}$, so we are once again done. $\blacksquare$ To finish, note that the number of pieces increases by $1$ with each pair of moves. Hence, after $300$ pairs, there are $301$ pieces. For some $m$, each of the pieces has weight in the set $\{2^{-m}, 2^{-m - 1}, 2^{-m - 2}\}$. Thus, by Pigeonhole, there are $100$ pieces which have the same weight, whence Pasha wins. $\Box$
27.12.2020 09:11
Rename Pasha and Vova to Alice and Bob. Suppose there is initially $1$ kilogram of plasticine. Call a real number quirky if it's of the form $2^{-n}$ for some $n\ge 1$. We claim Alice has a winning strategy. Alice's Strategy: Alice starts by splitting $1$ into $(2^{-2},2^{-2},2^{-1})$, and repeats the following algorithm. Suppose Bob combines $2^{-x}$ and $2^{-y}$. If $x=y$, then Bob's move created $2^{-x}+2^{-x}=2^{-x+1}$, which is quirky. If the largest block is $2^{-m}$, then Alice replaces \[ 2^{-m} \quad \to \quad 2^{-m-2}, \ 2^{-m-2}, 2^{-m-1}. \] If $x>y$, then Alice replaces \[ 2^{-x}+2^{-y} \quad \to \quad 2^{-x-1}, \ 2^{-x-1}, \ 2^{-y}. \] Claim: At any point in time right after Alice's move, each block is one of $\{ 2^{-k-2}, \ 2^{-k-1}, \ 2^{-k} \}$ for some $k\ge 1$. Proof: Induct on the number of moves, base case $(2^{-2},2^{-2},2^{-1})$ clear. Assume all numbers are at most two powers of $2$ apart. In the move when $x=y$, all weights are still within $\{2^{-m-2},2^{-m-1},2^{-m}\}$. In the move when $x>y$, the sizes only get closer together. $\blacksquare$ Note that the number of blocks increases by $1$ from one of Alice's moves to the next. Therefore, after $1000>300$ iterations, there will be at least $100$ equal blocks.
18.11.2021 17:41
A different solution (though, not as elegant as post #5) The answer is NO. Consider a sufficiently small $\epsilon > 0$ (why such $\epsilon$ exists will be mentioned at the end). Suppose the original stone had weight $c$. We keep breaking this into $\epsilon, 2 \epsilon, c - 3\epsilon$. Let $f(x)$ denote numbers of stone with weight $f(x)$. Call a move of Vova bad if the weights he combine are BOTH not in $\{\epsilon,2 \epsilon \}$ and good otherwise. Note that a bad move increases $f(\epsilon) + f(2 \epsilon)$ while a good move increases $f(2 \epsilon) + f(3 \epsilon) + f(4 \epsilon)$. This means if there are $\ge 200$ bad moves, we are done ; on the other hand, is there are $\ge 300$ good moves then we are still done. As every move is either bad or good, so after $500$ moves we must be done. This also shows $1500 \epsilon < c$ is sufficient. $\blacksquare$
16.12.2021 05:38
NO Rename Pasha and Vova to Chen and Zhang, respectively. Define a "round" as two consecutive turns from Chen and Zhang in that order, and an "anti-round" as two consecutive turns from Zhang and Chen in that order. Also, assume WLOG that both players are immortal. Let $N=199^{1104}$ be a very VERY large number. Notice that after every round, the total amount of pieces increases by $1$. For the first $N$ turns, Chen will randomly select a piece and cut it into pieces of arbitrary sizes. Fix an $\epsilon$ that is less than $\frac{1}{69^{420}}$ the size of any existing pieces. In every following turn, Chen will choose a piece of size $3\epsilon$ or $4\epsilon$ if they exist, and otherwise, randomly select a piece with size $>2\epsilon$ then cut away two parts of size $\epsilon$ from it. Let $w$ be the number of pieces with size $\epsilon$ or $2\epsilon$. I claim that $w$ increases by at least $1$ after every anti-round. It increases by at least $2$ after every single one of Chen's turns, and the only way Zhang can decrease it by $2$ is by merging two pieces of size $\epsilon, 2\epsilon$ or $2\epsilon, 2\epsilon$, to which Chen can respond immediately by splitting the newly created piece with size $3\epsilon$ or $4\epsilon$ to increase $w$ by $3$. By pigeonhole, the problem is hereby solved. $\blacksquare$
25.04.2024 07:55
solved with NTguy and 1 other