There are $ m + 1$ horizontal lines and $ m$ vertical lines on the plane so that $ m(m + 1)$ intersections are made. A mark is placed at one of the $ m$ points of the lowest horizontal line. 2 players play the game of the following rules on this lines and points. 1. Each player moves a mark from a point to a point along the lines in turns. 2. The segment is erased after a mark moved along it. 3. When a player cannot make a move, then he loses. Prove that the lead always wins the game. PS I haven't found a student who solved it. There can be no one.
Problem
Source: 2009 Korean MO #5
Tags: analytic geometry, combinatorics proposed, combinatorics
31.03.2009 15:34
nobody here too???
01.04.2009 04:36
Working on it. Gotten some win cases and nothing really substantial. Definitely would not have solved this in 3 hours.
01.04.2009 23:27
02.04.2009 01:35
pythag: Suppose the counter starts at $ (2,1)$. You move to the paired point $ (1,1)$. I move to $ (1,2)$. You move to the paired point $ (2,2)$. I move back to $ (2,1)$ (that segment has not been erased). You can't move to $ (1,1)$; what do you do?
02.04.2009 05:04
Also, if player 2 moves horizontally and player 1 also moves horizontally, player 2 can win if he uses perfect play. EDIT: Problem solved. Solution will be posted before two days are up unless I find a flaw.
04.04.2009 10:21
Sorry, I got sidetracked off of other cool problems. Guess my 2 day restriction didn't help much, although it did force me to finish this today instead of reading http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=219017 . I am without a doubt the worst proof writer on AoPS, so I'm sure there are many flaws. I would highly appreciate it if you would point them out for me. Note: I filled in an empty grid instead of erasing a filled grid. The problem is identical, except it's easier to picture and work with. Proof: Points not on an edge or corner are "interior" points, and edge/corner points are "exterior" points. Define the "diamond" as the structure that arises with diagonal sides (with breaks if the second player creates them) that touches both the left and right edges. A "completed" diamond is one in which neither player can continue moving inside of it. As an inherent part of its structure, the top must be the endpoint and the bottom must be its start. Assume that player 1 is playing with perfect play. If player 1 moves in a direction, and player 2 continues in that direction, and player 2 had a winning strategy, then player 1 could have moved to player 2's position and become player 2, utilizing that winning strategy. Thus, any player must change courses to win against a player who is using perfect play. A player will always be able to turn in the interior points if he moves only one unit at a time. A player can only lose on an exterior point, as each interior point contains an even number of paths leading to and from it. Player 1's first move will be to move up one unit, making him the vertical player. He will only move one unit at a time, so there will be no problems with player 2 forcing him to become the horizontal player. Player 2 must then move horizontally. Each turn, if player 1 can force a win, he will do that. Otherwise, he will move one down, staying above the diagonal of the first move (illustrated in diagram 1) if possible, or will move one up if possible. If the other player strays out of the confines of that diagram (illustrated in diagram 2) we will continue on with the new point as our diagonal basis. This strategy will continue until it is no longer possible to continue within the illustrated diamond. (Lemma 1): Player 1 can avoid moving out of the diamond-shaped structure The only way player 1 will be forced out is if there is a vertex that already has two paths leading it, and player 2 takes another one of the paths, and the only path left leads out of the diamond. However, the only way this is possible is if the mark has already been outside. As we start on the diagonal, this is impossible. (Lemma 2): The diamond has a maximum height of the top of the board. Player 2 can only change the diamond by lengthening the diamond's width at the top or the bottom. Case 1: width is increased at bottom The diamond will actually have a smaller vertical height. Case 2: width is increased at top Player 2 can only increase the width by moving two or more spaces, creating a lengthened segment. Then, when player 1 moves down one space (it is possible because player 1 is outside the diamond) player 2 will be stuck beneath the segment, and will be unable to force player 1 to go back above it because player 1 will be able to force a win. As there is a limited amount of moves below the lengthened segment and player 1 has an answer for each of them, player 2 will eventually run out of moves and player 1 will win. (Lemma 3): The diamond, when completed, will have all its sides filled. Instead of analyzing strategies or the like, we can simply note that each point must have an even number of paths going to and from it. Assume we have a completed diamond that does not have all its sides filled. Thus, at least one of the points on its sides does not have two paths going to and from it, with the exception of the start and the finish. This means an entire side must be missing, which leads to a lowered endpoint inside the diamond, which means the player whose turn it is can continue to move within the diamond. Thus, the diamond is incomplete, and we have a contradiction. (Lemma 4): when the diamond is completed, player 1 can force a win. The endpoint is a segment sticking up, so it must be player 2's turn. Player 2 must move right or left. As the diamond encompasses the entire horizontal grid, player 2 cannot end up over an empty space. There are 3 cases for player 2: Case 1: player 2 ends up over a horizontal segment. Player 1 has the option of moving down to that segment and forcing player 2 to move vertically. Thus, player 1 has the win. Case 2: player 2 ends up over an edge of the diamond. Player 1 can move all the way down to the edge, and player 2 can only move horizontally away from the diamond. The y coordinate of the mark decreases each time this case occurs. As the board size is finite, this must eventually come to a stop. Case 3: player 2 ends up on the edge of the board. Player 1 can move all the way down, and player 2 has nowhere to go. Thus, player 1 wins. QED
Attachments:
