Given a linear path with $n$ dots connected by $n-1$ lines, find the minimum number of coins required to win the game provided the game features are as follows:
- In the following game, you're given a linear path as mentioned above and a set of coins will be placed randomly on the dots by your friend. (You don't know the exact location of the dots as that's not controlled by you).
- Aim of the game: You win if you can bring at least one coin to the destinated dot (as set by your friend).
- Whenever you move a coin from a dot to its adjacent dot, you take off an existing coin in the current dot permanently (as a fee). If there's no coin to remove (as a fee), you can't move a coin from one dot to its adjoining dot.
I noted that if there are $n$ dots and $n-1$ straight lines joining them, then the minimum number of coins for which you can force/guarantee a win is $2^{n-1}$. It can be easily proved by doing a bit of a backward approach and then considering the extreme case.
Q.:: If the graph isn't a straight path, how would everything work in that case? Can we determine the minimum number of coins required if the initial positions of the coins aren't known (as that's chosen randomly by your friend) but the destined location (dot) is provided (yes, your friend will tell you, as can be noted from the second enumeration above)?