Bitcoin game
An interesting puzzle asked in Tower Research Capital
2022 boys are seated around a round table. There are 2023 bitcoins distributed among them. Calvin is seated at the table and currently has no bitcoin. A “move” involves one boy who possesses NOT LESS than two pieces of bitcoins giving 1 each to the boy on his left and on his right. If the moves are to continue until Calvin gets a bitcoin, is it guaranteed that the moves terminate?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
This problem has such an elegant solution.
Let p_i -> the position of bitcoin i and let the seats be labelled in the circle from 1 to 2022 and let Calvin be seated in the seat labelled 1.
We make a claim that Bitcoin never reaches Calvin.
Consider k = sum of squares of all p_i
After each move, k increases by 2
As k can not continue to increase indefinitely, it is constrained to decrease at some point. This can only occur if candy reaches Calvin.
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!
I think pigeon hole principle can also explain this.
I thought we could see this as somewhat similar to the gambler's ruin problem.
We see the round table as a straight line with Calvin as the person joining the two ends of the line. So we can use Calvin as the absorbing state. The problem starts with some initial state, considering just the additional coins(coin with players who have more than 1), where we will eventually land on one of the absorbing states. Is this a viable approach?