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?
I first proved a result, then used that result to prove that Calvin will get a coin.
Result:
For any circular arc covering x people and having total coins greater than equal to x+1 will result in at least one coin leaving the arc from one of the sides.
Proof:
I use Strong Mathematical Induction on P(x).
P(x): the above result statement
Base case: P(1)
Trivially satisfied as for one person having >= 2 coins, will have to give one coin on the left side and one on the right side. So at least one coin leaves the arc. Here the arc just covers that single person.
So we know that an arc covering x persons has at least x+1 coins. First let's establish some facts about this case.
1. The person with the most coins in this arc has at least 2 coins. Why? By Pigeon Hole Principle, for x persons having total sum of coins between them to be >= x+1, at least one person will have >= 2 coins. Clearly the person with the most coins has >= 2 coins.
2. If a person with >= 2 coins is sitting on the edge of the arc, the result is trivially satisfied. Why? As part of the move, one coin will move to the left of the person and one to the right. So at least one coin leaves the arc from either the left side (if that person is sitting on the left edge) else the right side (if he/she is sitting on the right edge).
So this leaves us with cases where the persons with >= 2 coins are not sitting on the edge. This means that the inner arc (arc - edge positions) that covers x-2 persons has total sum of coins >= x-1. Why? Because if the edge positions have < 2 coins, then that leaves at least ((x+1) - 2) coins in the inner arc. But P(x-2) is true by Strong Inductive Hypothesis. This means at least one coin will leave the inner arc. This means that the one of the edge positions will have >= 2 coins at some point of time. This takes us back to the state of fact 2, which proves that at least one coin will leave the arc from either left or right side.
Using the result to prove Calvin gets a coin:
1. Trivial case: Calvin has a neighbour with >= 2 coins.
Calvin gets a coin in this case as in the next move itself, the neighbour of Calvin will give Calvin one coin.
2. Calvin does not have a neighbour with >= 2 coins.
I will prove for the case where both the neighbours of Calvin have just 1 coin. Rest cases, i.e., (1,0), (0,1) and (0, 0) where the first coordinate denotes the number of coins Calvin's left neighbour has and second the number of coins his right neighbour has are similar to prove using repetitive application of the result.
Consider the arc excluding Calvin and his neighbours. So we have an arc covering 2019 persons. By the condition, we know that the total coin sum in this arc is 2021, which is >= 2020. Hence at least one coin will leave this arc from either the left side or the right side. This means that either the left neighbour of Calvin or the right neighbour will have >= 2 coins at some point in future. But then in the next move itself, Calvin will have a coin as he now has a neighbour with >= 2 coins.
not sure about this solution, since it is not mandatory that someone having >= 2 coins must make the move. The only condition is that if there is at least one person in the circle with >= 2 coins, then a move will be made.
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?
I first proved a result, then used that result to prove that Calvin will get a coin.
Result:
For any circular arc covering x people and having total coins greater than equal to x+1 will result in at least one coin leaving the arc from one of the sides.
Proof:
I use Strong Mathematical Induction on P(x).
P(x): the above result statement
Base case: P(1)
Trivially satisfied as for one person having >= 2 coins, will have to give one coin on the left side and one on the right side. So at least one coin leaves the arc. Here the arc just covers that single person.
Inductive case: P(x) considering P(x-1), P(x-2), P(x-3) .... P(1) are true
So we know that an arc covering x persons has at least x+1 coins. First let's establish some facts about this case.
1. The person with the most coins in this arc has at least 2 coins. Why? By Pigeon Hole Principle, for x persons having total sum of coins between them to be >= x+1, at least one person will have >= 2 coins. Clearly the person with the most coins has >= 2 coins.
2. If a person with >= 2 coins is sitting on the edge of the arc, the result is trivially satisfied. Why? As part of the move, one coin will move to the left of the person and one to the right. So at least one coin leaves the arc from either the left side (if that person is sitting on the left edge) else the right side (if he/she is sitting on the right edge).
So this leaves us with cases where the persons with >= 2 coins are not sitting on the edge. This means that the inner arc (arc - edge positions) that covers x-2 persons has total sum of coins >= x-1. Why? Because if the edge positions have < 2 coins, then that leaves at least ((x+1) - 2) coins in the inner arc. But P(x-2) is true by Strong Inductive Hypothesis. This means at least one coin will leave the inner arc. This means that the one of the edge positions will have >= 2 coins at some point of time. This takes us back to the state of fact 2, which proves that at least one coin will leave the arc from either left or right side.
Using the result to prove Calvin gets a coin:
1. Trivial case: Calvin has a neighbour with >= 2 coins.
Calvin gets a coin in this case as in the next move itself, the neighbour of Calvin will give Calvin one coin.
2. Calvin does not have a neighbour with >= 2 coins.
I will prove for the case where both the neighbours of Calvin have just 1 coin. Rest cases, i.e., (1,0), (0,1) and (0, 0) where the first coordinate denotes the number of coins Calvin's left neighbour has and second the number of coins his right neighbour has are similar to prove using repetitive application of the result.
Consider the arc excluding Calvin and his neighbours. So we have an arc covering 2019 persons. By the condition, we know that the total coin sum in this arc is 2021, which is >= 2020. Hence at least one coin will leave this arc from either the left side or the right side. This means that either the left neighbour of Calvin or the right neighbour will have >= 2 coins at some point in future. But then in the next move itself, Calvin will have a coin as he now has a neighbour with >= 2 coins.
not sure about this solution, since it is not mandatory that someone having >= 2 coins must make the move. The only condition is that if there is at least one person in the circle with >= 2 coins, then a move will be made.