8
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I have troubles with understanding what a wining strategy is: your game is infinite! $\endgroup$
    – Wadim Zudilin
    Commented Jul 15, 2010 at 1:32
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 15, 2010 at 3:59
  • $\begingroup$ @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. $\endgroup$
    – Qiaochu Yuan
    Commented Jul 15, 2010 at 6:58
  • $\begingroup$ @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. $\endgroup$
    – Vladimir Sotirov
    Commented Jul 15, 2010 at 13:02
  • $\begingroup$ 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.) $\endgroup$
    – Wadim Zudilin
    Commented Jul 15, 2010 at 13:52

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this journal available online? I really doubt that there is a good notion of "infinite game" (see Vladimir's comments on the OP). $\endgroup$
    – Wadim Zudilin
    Commented Jul 16, 2010 at 13:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    Commented Jul 16, 2010 at 15:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Wadim Zudilin
    Commented Jul 17, 2010 at 10:54
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ True, but if P chooses $p_n$ to be $2^{-n}$ from $p_{n-1}$ wont $(p_n)$ converge and so P will lose? $\endgroup$
    – Mark Bell
    Commented Jul 15, 2010 at 1:12
  • $\begingroup$ The game would be probably more interesting if P isn't allowed to choose distance less then $1/n$ on the $n$th step. $\endgroup$
    – Wadim Zudilin
    Commented Jul 15, 2010 at 1:16
  • $\begingroup$ Oh, P won't converge! $\endgroup$
    – Wadim Zudilin
    Commented Jul 15, 2010 at 1:24
  • $\begingroup$ 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. $\endgroup$
    – Mark Bell
    Commented Jul 15, 2010 at 13:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .