Given 98 points in a circle. Mary and Joseph play alternatively in the next way: - Each one draw a segment joining two points that have not been joined before. The game ends when the 98 points have been used as end points of a segments at least once. The winner is the person that draw the last segment. If Joseph starts the game, who can assure that is going to win the game.
Problem
Source: Spanish Communities
Tags: induction, combinatorics unsolved, combinatorics
23.08.2007 01:52
I think Jose can always win the game. Jose must only care to notice when there are only 3 unused points, he can almost do wahtever he wants with the other 95 and he will still be the winner. From here we have two possibilities: a)If it is Jose's turn when this situation gives, his next turn will join to used points. b)If it is Maria's turn and she uses one of the 3 points, Jose wins. If she join to used points Jose returns to situation a). This can continue untill all 95 points have been joined with each other, and as this need $ 95*47$ segments to be drawn, it will be Maria's turn when there are no more points left to joined within this 95 so we are in b) and Jose wins the game.
06.09.2007 22:14
Unless both of us are mistaken, ElChapin gets this one right!
14.02.2012 18:59
I think Joseph can always win. Here's my solution: Let S be the number of points which are not used in a segment, at the beginning of the game S=n(where n is the number of given points, in this case 98). since none of the points have been "used" at the beggining Jose always decreases S by 2 (joins 2 points that have not been used) so, Mary has n-2 points and can decrease S by -1 or by -2 (-1 if she joins a point that has been used with another un-used and -2 if she joins 2 un-used points). So we can turn this game into a simple Nim, with 1 heap of n-2 counters and , you can take 1 or 2 counters, where the second player begins. We know that 0 is a losing position to this game , so 1 is winning (just do -1 and lead to a losing position) 2 is also winning (do -2), 3 is losing because it leads to 2 or 1 which are winning positions. and so on... it is easy to prove by induction that 3k for some k is a losing position for the second player, so if n-2=3k (note that we started this game with n-2 counters) it is a losing position for the second player, so n=3k+2 , in this case n=98=3k+2 so it is losing for the second player, winning for the first one. A winning strategy would be: - if the second player joins a segment with 2 unusued points , the first one joins a used point with one unused and viceversa.
03.11.2024 02:42
We will show that Joseph has a winning strategy. If the game is not over, on his turn, there are either 2 or less non-used points, so he can immediately win by using them, or there exist 3 non-used points. In this case, let m be the number of turns each one of them has played, then the number of edges that are still not connected in the other 95 points is equal to $\frac{95 \times 94}{2} - 2m = 4465 - 2m > 0$, which means Joseph can leave those 3 points non-used, so Mary will not be able to win on the next turn, meaning Joseph will play one more turn. Since there are a finite number of points, the game must eventually end, but Joseph can guarantee he never loses, so he will always win. We could even generalize to show that for $n = 4k+1, n = 4k+2$ Joseph has a winning strategy, while for $n = 4k, n=4k+3$, Mary has a winning strategy, because $\frac{(n-3)(n-4)}{2}$ is odd in the first case, while even in the second case.