Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I recently heard of a game between two players "Line" and "Point" and wanted to look for more information on it. However, without knowing the name of it (if it has one) finding more information is hard, has anyone heard of it? Is there a winning strategy for one of the players?

The game is as follows, it is played on the unit disk $D^2$ in $\mathbb{R}^2$ with the point $p_0 = (0,0)$ marked to begin with. Play alternates between L and P (starting with L) and on turn $n$ they do the following:

L chooses a new line $l_n$ through point $p_{n-1}$ and then P chooses a new point $p_n$ on line $l_n$ inside $D^2$.

This forms a sequence of points $(p_n)_{n = 1}^\infty$ in $D^2$. L wins if this sequence converges to a point in $D^2$, P wins if it does not.

As far as I can tell P has a winning strategy, but I my formal proof for this is a sketch at best.

share|improve this question
1  
I have troubles with understanding what a wining strategy is: your game is infinite! –  Wadim Zudilin Jul 15 '10 at 1:32
1  
Suppose L always chooses a line through the point with minimum length in D^2. I see no winning strategy for P. Do you? Gerhard "Ask Me About System Design" Paseman, 2010.07.14 –  Gerhard Paseman Jul 15 '10 at 3:59
    
@Gerhard: I was convinced until I read Andreas' solution. The issue is that even though P can be trapped in a region whose diameter decreases to zero, that region itself can rotate. –  Qiaochu Yuan Jul 15 '10 at 6:58
    
@Wadim: My understanding of unboundedly unbounded games is that they cannot be formalized inductively as pairs of sets of games, a la Conway (hence they are not strictly combinatorial games). However, they (and their strategies) are still sensible though, such as the one in this question or, for a broader class of examples, back-and-forth (Ehrenfeucht-Fraisse) games on first-order equivalent structures. –  Vladimir Sotirov Jul 15 '10 at 13:02
    
Vladimir, thank you for your thoughts. (In fact, the game is bounded, as it in the unit disc. :-) ) After the answer of Andreas I understand the meaning of a wining strategy in this particular case, but I am pretty sure that settling some general setup for infinite games require some logic. The fact that a wining strategy exists or does not exist may be an unprovable statement. (This might be a good question for MO, but I am probably too far from understanding possible answers.) –  Wadim Zudilin Jul 15 '10 at 13:52
show 1 more comment

4 Answers

up vote 5 down vote accepted

Line actually has a winning strategy: it can force a convergent sequence. The problem was posed and solved in the following paper:

J. Maly and M. Zeleny (2006), A note on Buczolich's solution of the Weil gradient problem: a construction based on an infinite game, Acta Mathematica Hungarica, Vol. 113, pp. 145-158.

share|improve this answer
    
Is this journal available online? I really doubt that there is a good notion of "infinite game" (see Vladimir's comments on the OP). –  Wadim Zudilin Jul 16 '10 at 13:57
1  
@Wadim: The journal is available on Springerlink and is quite nice. I can send you a copy if you can't access it. This particular infinite game is perfectly well-defined as far as I am concerned. However, whether either player has a winning strategy is another issue. In this case, a stragegy for $L$ is just a sequence of functions $f_k$, where $f_k$ takes the imput from the first $k−1$ steps of the game and outputs a choice for $L$. Similarly for $P$. It turns out that $L$ has a strategy that wins regardless of the strategy that $P$ follows. –  Tony Huynh Jul 16 '10 at 15:06
    
Thanks, Tony! It explains in a few lines the point in ths story (something I cannot see from the answer above). I added the doi-link to the article (which I now have). My main concern about existence of wining strategies for both players in an infinite game remains, but in this special case one could use the epsilon-delta language about decision on who wins in finite time. –  Wadim Zudilin Jul 17 '10 at 10:54
add comment

Edit: The following has a serious gap, but I'll leave it up, for now, in case it gives someone an idea for a correct proof. The error is that, because P always chooses the more distant (from $p_{n-1}$) of the two options for $p_n$, $L$ can cause him to go back and forth, rather than "farther and farther".

I think P can win with the following strategy. Fix a series $\sum_1^\infty t_n$ of positive terms, with sum 1, such that $\sum_1^\infty \sqrt{t_n}$ diverges. Let $r_n=\sum_1^n t_k$. Let P choose his $n$-th point $p_n$ so that its distance from the origin is $r_n$. This is always possible, because $r_n>r_{n-1}$ and $l_n$ extends from $p_{n-1}$ all the way to the boundary of the disk. In fact, P always has two options at the desired distance from the origin; let $p_n$ be the one farther from $p_{n-1}$ (or either one in case of a tie). This completes the description of the strategy. Now why does it win? Easy estimates show that, once $r_n$ is close to 1 (i.e., for sufficiently large $n$), the angle between the radii from the origin to $p_{n-1}$ and from the origin to $p_n$ is at least of order $\sqrt{t_n}$. (The smallest angle occurs when $l_n$ is perpendicular to the radius through $p_{n-1}$, and this smallest angle is close to $\sqrt{2t_n}$ if I've done the arithmetic correctly.) Since $\sum_1^\infty \sqrt{t_n}$ diverges, it follows that the radii keep rotating farther and farther, not approaching a limit. Therefore, the sequence $(p_n)$ fails to converge, and P wins.

share|improve this answer
add comment

Here is a sketch of a proof building on the ideas of Andreas Blass.

Let $C(r)$ be the circle of radius $r$ centered at the origin $O$. Suppose that $P$ starts at $p \in C(r)$ for some $r \in (0,1]$. To begin, let us analyze what happens if $P$ follows the simple strategy of always staying on $C(r)$. That is, after $L$ chooses a line $l$ through $p$, $P$ picks the other point of $l$ that is also on $C(r)$ (if $l$ happens to be the tangent to $C(r)$ at $p$, then $P$ picks $p$). This is clearly not a winning strategy for $P$. For example, $L$ could force $P$ to always stay at $p$ by always picking the tangent to $C(r)$ at $p$. However, if $(p_i)_{i=1}^\infty$ is the set of chosen points and if $\theta_i$ is the smaller of the two angles made by $p_{i}, O$, and $p_{i+1}$, then $P$ will win if the $\theta_i$ do not tend to 0.

Returning to the original game, the second observation is that if $L$ follows the strategy of always choosing tangent lines, then $P$ has a winning strategy. This strategy was suggested by Gerhard Paseman in the comments. The fact that $P$ has a winning strategy follows by Andreas' answer, because in this case there are always two choices for $p_n$, and so we can always move clockwise when jumping from $C(r_n)$ to $C(r_{n+1})$.

Putting these two observations together yields a winning strategy for $P$ as follows. As in Andreas' answer, fix a series $\sum_1^\infty t_n$ of positive terms, with sum 1, such that $\sum_1^\infty \sqrt{t_n}$ diverges. Let $r_n=\sum_1^n t_k$. Inductively assume that $P$ is currently on $p \in C(r_n)$. At this point, $P$ follows the strategy of staying on $C(r_n)$. Recall that this is winning for $P$ unless $\theta_i \to 0$. So, $P$ simply needs to wait until $\theta_i$ is sufficiently small at which point he jumps to $C(r_{n+1})$ in the clockwise direction.

Edit. In light of Ravi Boppana's answer, I see an error (there must be) in the above argument. While $P$ is waiting on $C(r_n)$, it is true that $L$ must eventually pick a line that is arbitrarily close to being a tangent. However, $P$ has no control when this will happen. In particular, there is no guarantee that the sequence $(p_i)_{i=1}^{\infty}$, where $p_i$ is the first point chosen by $P$ on $C(r_i)$, diverges.

share|improve this answer
add comment

P can always choose $p_n$ to be at distance $2^{-n}$ from $p_{n-1}$.

EDIT: Never mind, I misread the problem, thought P would win if the sequence converged.

share|improve this answer
    
True, but if P chooses $p_n$ to be $2^{-n}$ from $p_{n-1}$ wont $(p_n)$ converge and so P will lose? –  Mark Bell Jul 15 '10 at 1:12
    
The game would be probably more interesting if P isn't allowed to choose distance less then $1/n$ on the $n$th step. –  Wadim Zudilin Jul 15 '10 at 1:16
    
Oh, P won't converge! –  Wadim Zudilin Jul 15 '10 at 1:24
    
Regarding the game where P wins if the sequence converges - this is trivial as P just chooses the same point each time (the new line, chosen by L just before, still has to contain the old point) and so P wins. –  Mark Bell Jul 15 '10 at 13:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.