Greedy goblin Griphook has a regular $2000$-gon, whose every vertex has a single coin. In a move, he chooses a vertex, removes one coin each from the two adjacent vertices, and adds one coin to the chosen vertex, keeping the remaining coin for himself. He can only make such a move if both adjacent vertices have at least one coin. Griphook stops only when he cannot make any more moves. What is the maximum and minimum number of coins he could have collected? Proposed by Pranjal Srivastava and Rohan Goyal
Problem
Source: INMO 2025/5
Tags: combinatorics, game, INMO 2025
19.01.2025 15:50
I guess maximum value is $1998$ and minimum is $665$ Sillied , $668$ will be the answer for min.
19.01.2025 16:33
@above What was your construction? I also suspected the same lower bound but my construction was going to be the coins placed as so: 020 (665 times) 11 (ith entry in this seq is number of coins in ith vertice) but then I realized you could play on 0 coin vertice as well and then it all came down.......
19.01.2025 17:18
I was getting 1998 as maximum and 668 as minimum.
19.01.2025 23:21
This problem was proposed by Pranjal and I had simply found the solution. The minimum is $668$ and the maximum is $1998$. The original phrasing we had was not Griphook the Goblin but Alice the greedy tax collector Here are the proofs for the $4$!!!! parts of this problem. 1. Griphook can pick 1998 coins: Lemma. $1^n01s\mapsto 010^{n}s$ for any $n\ge 1$ and any string $s$. Proof. Observe that $1^n01\mapsto 1^{n-1}010$. Repeating this move $n$ times gives the desired result. Now, \[1^{2000}\mapsto 1^{1996}0201\mapsto 1^{1995}01010\stackrel{\text{Lemma.}}{\mapsto}010^{1996}10\] 2. Griphook can collect exactly $668$ coins: \[1^{2000}\mapsto 1(020)^{666}1=1020(020)^{664}0201\mapsto 0110(020)^{664}0110\] 3. Griphook cannot collect more than $1998$ coins: Observe that if $o$ is the number of coins on odd positions and $e$ on even positions then $o-e$ is invariant $\pmod{3}$. Thus, $o\equiv e\pmod{3}$ always! Now, we must end with atleast one coin so atleast $2$ must be remaining since $o\equiv e\pmod{3}$. The below proof is not mine and much better than mine which was extremely convoluted. It was shared by an anonymous (to me) reviewer. 4. Griphook could not have collected less than $668$ coins when the game stops: We show that Griphook makes atleast $668$ moves even in the weaker game where no coin is placed back and both are pocketed. This cannot increase the length of the game and thus we just bound the minimum number of moves Griphook has to make. Observe that this game is now simply on two distinct circles of length $1000$ where you can pick up two adjacent coins and pocket them. Clearly each circle requires atleast $334$ moves to ensure that there are no adjacent coins! Thus, atleast $668$ moves are required.
20.01.2025 00:50
For minimizing proof we have a nice solution:- Paint all odd places as Maroon, Paint all even as Green connect all maroon (1000) to form a circle and all green (1000) to for another circle, then notice that one process on either green or maroon removes 3 edges and so the colored edges are mutually exclusive that is 334 steps to remove greens, 334 steps to remove red and we are done. Credits:- Elliot (dc) For maximizing proof:- 1998 is the answer which has construction as shown above and for proof just note that at least 2 coins must be left because 2000 is 2 mod 3 and note that's the alternating difference is invariant so we are done Credits:- me
20.01.2025 04:35
Hello Rohan sir! So i guess my idea for the construction was half way there I guess but is there any backstory to this one?(other than the tax collector part)
20.01.2025 13:57
Rg230403 wrote: The below proof is not mine and much better than mine which was extremely convoluted. It was shared by an anonymous (to me) reviewer. 4. Griphook could not have collected less than $668$ coins when the game stops: We show that Griphook makes atleast $668$ moves even in the weaker game where no coin is placed back and both are pocketed. This cannot increase the length of the game and thus we just bound the minimum number of moves Griphook has to make. Observe that this game is now simply on two distinct circles of length $1000$ where you can pick up two adjacent coins and pocket them. Clearly each circle requires atleast $334$ moves to ensure that there are no adjacent coins! Thus, atleast $668$ moves are required. One more way to finish the weaker game is: Consider the mono variant: $$I = \sum \min(a_{k-1}, a_{k+1}).$$(where $a_k$ denotes the coins at vertex $k$). It decreases by atleast $1$ and at-most $3$ at every step (and we are basically done).
20.01.2025 15:42
S.Ragnork1729 wrote: I guess maximum value is $1998$ and minimum is $665$ Bros actually dotted
20.01.2025 19:59
guys i solved for general n(n>=3), and wrote max is (n-2) but this faults at n=5, how much you think will be deducted for this?
20.01.2025 20:27
I have a doubt the question clearly states that Griphhook chooses a vertex and picks up two coins from two adjacent vertices to the chosen vertex , And keeps one coin for itself and places the other on the "chosen" vertex . If this is true then it is not possible to use the vertices adjacent to the chosen one. Which leaves in group of (020) tuple (no of coins) Then this arrangement of tuple is arranged around the 2000-gon. Which does not give 1998 as maximum answer. Say, (1-2-3) are 3 vertices with 1 coin each now if choose the 2-vertex we take coins from 1 and 3 and keep one and put back the other on 2. Please correct if i am wrong..
21.01.2025 15:28
Call a vertex viable if the given operation can be performed on a vertex.Observe that when we perform a move,it is trivial that the no. of viable vertices decrease by atmost 3:the vertex on which the operation is performed,and the other neighbouring vertices of the adjacent vertices of the vertex on which it is performed(Viability of other vertices are not decreased).Moreover if we had numbered the vertices consecutively,observe that all these three are either on even numbered vertices or odd numbered vertices(Extending the argument used in maximising case). Initially there are 1000 even viable vertices and 1000 odd viable vertices.Griphook can continue performing until there are 0 viable verices.So there must be atleast 334 moves on odd vertices and 334 on even,completing our argument [In exam,I didn't use the extension of the parity argument thus had proved that atleast 667 moves are needed.After returning home,I am depressed as I think that I should have used the parity idea coz i had used it in the maximising argument earlier.Don't know what I will get on this] Please correct if I am wrong
22.01.2025 08:09
Since no-one posted more about mono-variants, here we go (a complete mono variants solution): As in #9, define $a_k$. Note that: $a_k \le 2$ along with the fact that: we can never have something like $\cdots, 2, 0, 2, \cdots$ config.
Thus, $\min(a_{k-1}, a_{k+1}) \le 1$. Thus, note that: $$I = \sum \min(a_{k-1}, a_{k+1})$$is mono variant (for the original game itself). Each step, we decreases $I$ by at-least $1$ and at-most $3$ and we are done.
22.01.2025 18:31
#12 If you have a 020 string repeating then note since 2000 leaves a remainder 3, you will get in the end two 1s so the last four are 2011 now note you can play on the 0 coin vertice to get 1101 then 1020 now note this game is done. Since very number has 0 as a neighbour(s). You're idea is actually great! It is actually the same construction I got during test(I thought it was wrong and cut it out). However you are just assuming that you will ONLY play on the (i+3)th vertice (assuming you just played on ith vertice) BUT it can be played on any vertice that is not i-1 or i+1.
22.01.2025 18:38
am I the only one who noticed the Harry Potter and the Deathly Hallows reference?
22.01.2025 18:39
a) no; and b) it's not just deathly hallows, iirc he appeared first in philosopher's stone
25.01.2025 15:23
I do also have a good solution for the minimization part : We would start with the introducing a function $Q_i(N)$ to be the "Number of vertices which could be chosen in a $N$ sided polygon,at $(I-1)$ steps" .So our goal is to find the :$min(Q_i(N))$,at any step "$I-1$". Now observe that our first step would give us : $1-0-2-0-1-1-1-1-1-1..$,now if chose $1-0-2$ chain the number of vertices we could choose ,i.e $Q_2(N)=N-4$: but if we chose the $1-1-1$ chain we would get $Q_2(N)=N-6$. $\implies$ That choosing the $1-1-1$ chain is more beneficial that choosing the $1-0-2$ chain because it reduces the possibility of choosing the vertices. Hence ,reducing the number of moves which reduces the number of coins. CLAIM: Min number of coins could be chosen for any $n$ : $\boxed{\lfloor \frac{n}{3} \rfloor +i}$ where $n \equiv i(mod3)$ PROOF: As show above we have to choose $1-1-1$ chain which is $ \lfloor \frac{n}{3} \rfloor $ in number. Now when $n \equiv i(mod3)$ we would have a config: $...-0^{n-i}-1^{n-i+1}....-1^n-1-1^n-0^1-2^2-0^3-..$,so the two chains which could be chosen are : $2^{n-i-1}-0^{n-i}-1^{n-i+1}$ and $1^n-0^1-2^2$,now see that $I=1,2,0$, So for $I=0$ it is : $ \lfloor \frac{n}{3} \rfloor $ $I=1$ it is :$ \lfloor \frac{n}{3} \rfloor $ +1 ,because either : $2^{n-2}-0^{n-1}-1^{n-}$ or $1^n-0^1-2^2$ could be converted as Both share same $1^n$ : $I=2$ it is :$ \lfloor \frac{n}{3} \rfloor $ +2 ,because both :$2^{n-3}-0^{n-2}-1^{n-1}$ and $1^n-0^1-2^2$ could be converted because both share different $1$.
27.01.2025 15:30
Super interesting problem.