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
S.Ragnork1729
19.01.2025 15:50
I guess maximum value is $1998$ and minimum is $665$ Sillied , $668$ will be the answer for min.
HogRIDA
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.......
Mquej555
19.01.2025 17:18
I was getting 1998 as maximum and 668 as minimum.
Rg230403
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.
Siddharthmaybe
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
HogRIDA
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)
Saucepan_man02
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).
Scilyse
20.01.2025 15:42
S.Ragnork1729 wrote: I guess maximum value is $1998$ and minimum is $665$ Bros actually dotted
someonefromearth
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?
The_light
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..
L_BarySaneTan37
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
Saucepan_man02
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.
Well, consider $I_k = a_k+a_{k+1}$. Note that: $I_k=2$ initially, and it decreases if we play at $k-1$ or $k+2$ vertex, else it will remain same (even if we play at $k$ or $k+1$).
Also, to have $a_k = 2$ for some vertex $k$, we must have played at vertex $k$. Note that, from $I_{t} \le 2$ for any vertex $k$, we are forced to have
$a_{k-1}=a_{k+1}=0$.
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.
HogRIDA
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.
Ultimate_Frisbee
22.01.2025 18:38
am I the only one who noticed the Harry Potter and the Deathly Hallows reference?
Scilyse
22.01.2025 18:39
a) no; and b) it's not just deathly hallows, iirc he appeared first in philosopher's stone
Mathgloggers
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$.
Safal
27.01.2025 15:30
Super interesting problem.
$\textbf{Terminologies:}$Weight to a vertex means the number of coins in that vertex. Any $r-$ tuple denotes the weight of $r$ consecutive vertex in order clockwise.
Level the vertices, $a_1,a_2,...,a_{n}$
Define, $b_i=a_i+a_{i+1}+a_{i+2}$ with $a_{n+1}=a_1$ and $a_{n+2}=a_2$.
Consider the tuple,$B=(b_1,b_2,...,b_n)$, and let ,$B(k)$ denotes the the sequence after $k$ moves Note that initially, $B(0)=(3,3,...,3)$.Also, $a_{t}(s)=$ $\text{Weight in the vertex}$ $a_{t}$ at $s^{th}$ $\text{stage}$. Analogusly define $b_{t}(s)$ and $A(S)=(a_1(S),...,a_n(S))$. Observe that in any move to $B(j)$ can effect a sequence where three coordinates of $B(j)$ decreases and other coordinates remain invariant. Also it is easy to see that if $b_{k}(j)$ decreases then other two coordianates that decrease are $b_{k-2}(j)$ and $b_{k+2}(j)$.Also observe after any move none of the coordinate gets negative. Thus after any stage, Only possible coordinates of $B(r)$ are $0,1,2,3$.This implies at any stage the values of the weights of the vertices of the polygons are $0,1,2,3$.Suppose for the sake of contrary, some $a_{l}(s)=3$ which we get for the first time at the $s^{th}$ stage ,and then $a_{l-1}(s)=0$ and $a_{l+1}(s)=0$ also then ,$a_{l-2}(s)=0$ and $a_{l+2}(s)=0$. Thus there is no way to decrease $3$. But since $3$ was achieved by some move
at the $s^{th}$ stage for the first time, only way to achieve it is at $B(s-1)$ by backtracking is $a_{l}(s-1)=2$ and $a_{l+1}(s-1)=1$ and $a_{l-1}(s-1)=1$ implying $3\geq b_{l-1}(s-1)=4$ Contradiction!!!. Thus in all moves each coordinates can take for $0,1,2$.Now we will show three terms of $b_l(m)$ cannot be in order $(0,1,2)$ or $(0,2,1)$ or $(1,2,0)$ or $(2,1,0)$.Now assume that $u$ is the smallest index just such that one the of above four appear first at $u$ stage,then backtracking to $u-1$ stage we cannot get sum of these three coordinates $4$.Thus sum must be inavraunt at $u-1$ and $u$ which is $3$ but perturbation of any of one the coordiantes must have taken place implying from $u-1$ to $u$ sum is not invariant Contradiction!!.
$\textbf{Fact 1:}$ All of the vertex has weight $0,1,2$ at any stage
$\textbf{Fact 2:}$ Sum of weight any three consecutive vertices is atmost $3$ and atleast $0$.
$\textbf{Fact 3:}$ There cannot be there consecutive vertex with weight $(0,1,2)$ $(0,2,1)$ or $(1,2,0)$ or $(2,1,0)$ in order.
$\textbf{Observation:}$ Now note Griphook has minimum number of coins if sum of the weight is maximum among all possible moves such that we cannot make any further move. Note that if each term of $b_l(j)$ is greater than zero we can always decrease that sum.So after we cannot make any move we must have atleast one coordinates among any three consecutive coordinate must be $0$ and we know no coordinate can be $3$ at any stage.Now at this stage if we get a three coordinates with center like $(a,0,c)$ where $a,c$ both nonzero then we can again make moves contradicting to the fact we cannot make move.
Now suppose after $\phi^{th}$ stage griphook cannot make a move ,so $(a,0,c)$ where both $a,c$ is not nonzero is not there,also then if there is a tuple $(a,0,c)$ Then one of $a,c$ is zero, thus we ruin the possiblibles when griphook cannot make a move are $(2,0,1)$ and $(1,0,2)$ and $(1,1,1)$ and $(2,1,0)$ and $(1,2,0)$ and $(0,2,1)$ and $(0,1,2)$ and $(1,0,1)$ then each $b_i(\phi)$ contains a term which is $0$ , and So by $\textbf{Facts,Observation}$ we have proven then we must have a stage say $\beta$ where for weight sum to be maximum. Also note griphook now cannot make move , so all the above possiblites are now reducted. Thus for any three consecutive vertex possibilities are those such that sum of three consecutive vertex is atmost $2$
Now, we need weight sum to be maximum.
Also we know sum of three consecutive must be atmost $2$ , when griphook cannot make a move , thus $b_{i}\leq 2$ for all $i=1,2,3,...,3x+2$.Suppose maximum weight $2x+2$ is achievable.Since $b_1\leq 2,b_2\leq 2$ and so till $b_{3x+2}\leq 2$ then , $3(a_1+...+a_n)=b_1+b_2+...+b_{3x+2}\leq 2(3x+2)=6x+4$, thus $a_1+...+a_n\leq 2x+\frac{4}{3}$. $a_1+...+a_n\leq 2x+1$.
We will show latter that $a_1+a_2+...+a_n=2x$ can be achieved showing griphook's minimum is $x+2$
Clearly, after all moves are Over if all vertices are $0$ then to backtrack from that stage one vertex must be $-1$ which is not possible. Now note if we reach a situation with three vertex $(0,2,0)$ this situation cannot be backtacked to $(1,2,0)$ or $(0,2,1)$ because we aleardy know next two tuples cannot appear. Thus as $(0,2,0)$ must backtracked to $(1,1,1)$. Also while backtracking if we reach a stage $(0,2)$ for two vertex then the next vertex after two after $2$ say(e) i.e. the tuple $(0,2,e)$ then $e$ cannot be $1$ ,Also $0+2+e\leq 3$ thus $0\leq e\leq 1$ thus $e$ forced to be $0$ which can always transfered to $1$. Thus WLOG, If $A(\chi)=(1,0,0,...,0)$ after backtracking we only choose the possibility to mark vertex $0$ or $1$ beacuse we know by $(0,2),(2,0)$ must backtracked to $(1,1)$ and $(1,2)$ or $(2,1)$ cannot appear thus while backtracking we can perform sequence of moves to to always make the vertex while backtracking $1,0$, now we know very time we backtrack we decrease the value of griphook by $1$ and increase the sum of the weight of the polygons vertex by $1$ thus we must reach a stage after backtracking that is $A(\tau)=(1,1,...,1,0)$. Note that this cannot be backtracked to all vertex being $1$ and sum of all weights being $n$. Thus maximum griphook have collected is $n-2$.Now to show atleast one sequence of moves to reach $(1,1,1,...,1,0)$.
Perform this,We will do for $n=6$ , this can be generalized easily in the same manner,(by backtrack)
$((0,1,0),0,0,0)\rightarrow (1,(0,1,0),0,0)\rightarrow (1,1,(0,1,0),0)\rightarrow (1,1,1,(0,1,0))\rightarrow (1,1,1,1,0,1)$
$\textbf{Achiveing the maximum or Achiveing minumum vertex weight:}$
By following algorithim. We have the polygon $((1,1,1),1,1,...,1)\rightarrow(0,(2,0,1),1,...,1)\rightarrow (0,1,(1,0,1),1,...,1)\rightarrow(0,1,0,(1,0,1),1,...,1)\rightarrow (0,1,0,0,(1,0,1),...,1)\rightarrow \cdots$. Keep repeating in this way we are left with two $1$. Thus $n-2$ is the maximum.
$\textbf{Achiveing the minimum for Griphook or Achiveing maximum vertex weight:}$ Here, $n=3k+2$
$((1,1,1),1,1,...,1)\rightarrow((2,0,2),(0,2,0),...,(0,2,0),(1,1))$
Now consider the last two three tuples, $(0,2,0,1,1)\rightarrow (0,1,1,0,1)\rightarrow(0,1,0,1,0))$. Thus ,now we have the tuple $(0,2,0,0,2,0,....,0,2,0,0,1,0,1,0)$. Now we cannot proceed further hence $k+2$ is achievable.
Note $k+1$ is not achievable beacuse if it is achievable then $a_1+a_2+...+a_{3k+2}=2k+1$. Thus as we know $b_{i}\leq 2$ then $b_1+b_2+...+b_{3k+2}=6k+3$. Thus suppose $\tau_1$ of these $b_{i}$ is $2$ and $\tau_0$ of them is $1$ ,then $\tau_1+\tau_0=3k+2$ and $2\tau_1+\tau_0=6k+3$, $\tau_{1}=3k+1$ and $\tau_0=1$.Thus let, $a_1+a_2+a_3=1$, WLOG, $a_2=1$ beacause $B(r)$ at anystage is cyclic.Since now all $b's$ are $2$ other than $b_1$
So, $a_1=0$ and $a_3=0$,since $a_2=1$ so $a_4=1$,so $a_5=1$, so $a_6=0$ thus $a_7=1$ and $a_8=1$ and $a_9=0$, Inductive $a_{3r}=0$ , for all $r=1,2,...,x$,thus $a_{3x+1}=1$ and $a_{3x+2}=1$ but then, $a_1=0$ and $a_2=1$. Thus we get the tuple $(a_{3x+2},a_1,a_2)=(1,0,1)$ but this can again be reduced Contradiction.Hence griphook cannot collect $k+1$ coins.
$\blacksquare$