Given $n$. Two players in turn write different real numbers $x_1,x_2,x_3,\dots$ The player after whose turn there is a monotone subsequence of length $n$ loses. I guess that the question 'who wins' may be hopeless (nice if not so), but possibly there exists a better estimate of the number of turns than Erdős–Szekeres bound $(n-1)^2+1$ (which works not only for optimal, but for all strategies)?
$\begingroup$
$\endgroup$
5
asked Mar 9, 2015 at 13:38
-
$\begingroup$ For $n=3$, it is a first player win in four steps instead of five, so it is already better than Erdős-Szekeres. WLOG we can assume that the first palyer plays $1$, and the second player plays $3$. then the first player plays $2$ and wins. I am not sure what is the exact question. You would like a better bound than the Erdős-Szekeres, for all $n$ for optimal players? $\endgroup$– Daniel SoltészCommented Mar 9, 2015 at 15:59
-
$\begingroup$ In a sense this is also a similar question: mathoverflow.net/questions/143547/a-ramsey-avoidance-game As there is a game, and a Ramsey-type result, that guarantees that the game ends in a finite number of steps, but it turned out that the game with optimal play "ends earlier". $\endgroup$– Daniel SoltészCommented Mar 9, 2015 at 16:11
-
1$\begingroup$ Well, let the exact question be "does number of turns grow as $\Omega(n^2)$ for large $n$"? $\endgroup$– Fedor PetrovCommented Mar 9, 2015 at 16:17
-
1$\begingroup$ You may be interested in Harary, Sagan, and West, Computer-aided analysis of monotonic sequence games, Atti Accad. Peloritana Pericoanti Cl. Sci. Fis. Mat. Natur. 61 (1983) 67-78, MR1006269 (90d:90100). $\endgroup$– Gerry MyersonCommented Mar 9, 2015 at 22:43
-
1$\begingroup$ @GerryMyerson wow, they claim that in this game the first player wins for any $n\geq 4$ by some clever reason! researchgate.net/publication/2126205_Monotonic_Sequence_Games (Theorem 10) $\endgroup$– Fedor PetrovCommented Mar 9, 2015 at 23:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
As noted in the comments (but with not quite the right reference) the game is a first player win for $n \geq 4$. The question here is about the misere form, so this is a combination of Proposition 7, Theorem 10 and a bit of Proposition 9 in the paper Monotonic Sequence Games by Albert (who he?), Aldred, Atkinson, Handley, Holton, McCaughan and Sagan. This also appeared in Games of no chance 3. We did not address the question of the length of the game when one player is playing using a winning strategy, and the other to lose as slowly as possible (obviously, if the players cooperate to lengthen the game then it reaches the Erdos-Szekeres bound). The proof uses a "strategy stealing" argument, but one which is not entirely clear cut. In common with most such arguments it does not actually yield a strategy for the first player to win, only a proof that such a strategy exists.
-
$\begingroup$ Thank you, this stealing argument is amazing. Have you try similar tricks for other Ramsey type games, like, say, forbidden convex $n$-gon on the plane? $\endgroup$ Commented Mar 10, 2015 at 17:40
-
$\begingroup$ No, we didn't really consider such games. As the heart of the argument is a symbolic representation of a game state based on encoding the "bumping" algorithms for finding longest increasing and decreasing subsequences, it's not clear to me how one would emulate it. Of course the general idea of looking for a strategy stealing argument would certainly be a line to pursue. $\endgroup$ Commented Mar 10, 2015 at 18:33