Two players in turn play a game. First Player has cards with numbers $2, 4, \ldots, 2000$ while Second Player has cards with numbers $1, 3, \ldots, 2001$. In each his turn, a player chooses one of his cards and puts it on a table; the opponent sees it and puts his card next to the first one. Player, who put the card with a larger number, scores 1 point. Then both cards are discarded. First Player starts. After $1000$ turns the game is over; First Player has used all his cards and Second Player used all but one. What are the maximal scores, that players could guarantee for themselves, no matter how the opponent would play?
Problem
Source: ToT 2003-JA-7, SA-5
Tags: combinatorics unsolved, combinatorics
Batominovski
19.06.2011 14:12
I'm not quite sure whether this problem is correct, or maybe the statement is unclear and because of that I have misunderstood something. Basically, the second player can always get $1000$ points no matter how the first player plays (by always put a card $1$ mark higher than the one the first player puts in). The first player, on the other hand, can get $1000$ points too but only when the second player plays like a bacterium. The first player can guarantee nothing. The problem will be (only slightly) more interesting if the second player's cards have numbers $1$, $3$, $\ldots$, $1999$. Now, the first player is promised to gain $1$ point, and the second, $999$ points.
mavropnevma
19.06.2011 14:34
Maybe the winner of a round plays first at next round, or maybe they just alternate who's playing first at each round, as the "Two players in turn play a game" may suggest ...
Batominovski
19.06.2011 14:59
OK. I think I get it. At first, I thought the first player starts by placing a card. Then, the second places another card, then both cards are removed. Then, back to the first player again. He now places a new card. That seems nonsense. The correct game would be: the first player places a card, then the second. Now both cards are removed. Now, it's the second player's turn to place a card, and so on. If the first player's cards are $2$, $4$, $\ldots$, $4n$ and the second's are $1$, $3$, $\ldots$, $4n+1$, then the first is guaranteed to get $n-1$ points, while the second $n+1$ points. The first player can play this strategy: 1) On his turn, he places the lowest card in his hand. 2) On his opponent's turn, if the opponent places a lower card than $4n+1$, then he counters by playing the next card higher than his opponent's. 3) On his opponent's turn, if the opponent places the card with number $4n+1$, then he should pick the lowest card in his hand. This strategy always works as, at any moment, the first player's highest card is always higher than the highest with number less than $4n+1$ of the second's. He gains at least $n-1$ points from his opponent's turns that the opponent doesn't play $4n+1$. The second's startegy to get $n+1$ points is as follows: 1) On his turn, if it is not the last, then he plays the lowest card in his hand. 2) On his opponent's turn, he picks the next card higher than his opponent's. 3) On his last turn, he plays the highest card he currently has. This strategy makes sure that the second player's highest card is always higher than the highest one of his opponent's. So, he obtains $n$ points on his opponent's turns, and $1$ point in his last turn. PS: If the second player has cards with numbers $1$, $3$, $\ldots$, $4n-1$, then a draw will be achieved if both players play with their best strategies.