A Nice Riddle

Discussion in 'Physics & Math' started by §outh§tar, Aug 6, 2009.

  1. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    We work in the closed unit disc in the plane. Point and Line play the following game - Point chooses a point \(x_{1}\) of the open unit disc \(\mathbb{D}\) then Line draws a line \(l_{1}\) through \(x_{1}\). Point chooses a point \(x_{2}\) on \(l_{1}\) contained in \(\mathbb{D}\) and so on. Line wins if the sequence \((x_{n})_{n = 1}^{\infty}\) converges, otherwise Point wins. Show that Line can force a win.

    - for high school students
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    Step 1 :

    If Point is trying to win he basically needs to prevent Line making \(l_{n}\) a point, which forces convergence, which occurs if \(x_n\) ends up on the edge. Thus Point needs to prevent \(|l_{n}|>|l_{n+1}|\) where \(|l_{n}|\) means length of the line \(l_{n}\).

    Step 2 : Highlight for answer

    Given a particular point \(x_n\) Line wants to minimse \(l_{n}\) each time, which is done by taking the line to be at right angles to the radial line in D through x_n (minimisation follows from varying the angle made by the radial line through x_n and l_n, seeing perpendicular is an extremum by symmetry and obvious less than if l_n is parallel to the radial line, thus a minimum). If \(x_{n+1} \not= x_n\) then \(|x_{n+1}|>|x_{n}|\) and if \(l_{n+1}\) is again perpendicular to the radial line through \(x_{n+1}\) then \(|l_{n}|>|l_{n+1}|\). If \(x_{n}=x_{n+1}\) then you have a convergent series because it's constant.


    Result :

    Not changing \(x_{n}\) is suicide for Point and \(x_{n}\not=x_{n+1}\) means \(|x_{n}|<|x_{n+1}|\) but \(|x_{n}|\leq 1\). Point varying his choice doesn't make any difference, the series is monotonic and bounded and so we're done.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Valentine_A Registered Member

    Messages:
    33
    Hi AlphaNumeric. That’s quite a nice solution!
    It should be pointed out that, in general, a sequence of points inside the unit circle of monotonic-increasing distance from the centre may still not converge. Their distances converge, but not the points themselves. For example, you could have the following points on the \(x\)-axis: \(x_1=\left(-\frac12\,,\ 0\right)\), \(x_2=\left(\frac23\,,\ 0\right)\), \(x_3=\left(-\frac34\,,\ 0\right)\), \(x_4=\left(\frac45\,,\ 0\right)\), \(\ldots\), \(x_n=\left(\frac{(-1)^nn}{n+1}\,,\ 0\right)\), \(\ldots\), in which, although \(|x_n|\to1\), the points \(x_n\) themselves are divergent.

    So, for this problem, maybe convergence should be established instead by considering that \(|x_{n+1}-x_n|\) can be arbitrarily small?
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Hercules Rockefeller Beatings will continue until morale improves. Moderator

    Messages:
    2,740

    Seriously? I don't remember doing any maths even close to this level of complexity in high school.

    Please Register or Log in to view the hidden image!

     
  8. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    AN, you seem to have shown that the sequence of absolute values converges but as has been pointed out this is not sufficient. ?
     
  9. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    Intuitively:

    Line wants to minimize Point's choices.
    An obvious strategy is for Line to make line with the shortest possible intersection with the circle.
    So, what happens if Line always chooses a line that is perpendicular to the radius passing through Point's point?
    It's not hard to see that if Line employs this strategy, Point is forced to make selections that are ever further from the centre and closer to the edge of the circle.
    So, it seems that Line can eventually force Point right to the edge, and win.

    But!
    Although Line can clearly constrain Point radially with this strategy, is Point necessarily constrained laterally (in the angular coordinate)? Can Point find a counter-strategy so that their choices can continually progress around the circumference?

    Edit: Reading properly, I see that my lovely intuitive solution and its objection have both already been proposed in a much more precise manner. Oh well.
     
  10. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    Though not explicitly stated, the sequence converges because the length of the line gets smaller, which is something I proved. If the length of the line is smaller with each step then the points converge. You can see this by considering the maximum angle distended by the line, which shrinks each time.
     
  11. temur man of no words Registered Senior Member

    Messages:
    1,330
    That is not sufficient since there exist divergent series with terms tending to zero, the classical example would be the harmonic series.
     
  12. AlphaNumeric Fully ionized Registered Senior Member

    Messages:
    6,699
    Ah, I see what you mean, you're referring to the change in angle arg(x_n), not to the distance in some way, hence why it might not be divergent. I'd haphazard it is divergent, I've just not proven that it is, as I'm not sure how else you'd be able to force the absolute value of x_n to increase.
     
  13. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    That's the problem with leaving your education up to the public education system..
     
  14. przyk squishy Valued Senior Member

    Messages:
    3,203
    I suppose a simple way of seeing the potential non-convergence of this method, without having to manipulate limits, would be to note that you can take any infinitely long curve starting at the initial point x[sub]1[/sub] and spiralling outward (asymptotically approaching the edge of the disc as the angular parameter tends to infinity), and use it to construct a sequence of points corresponding to a non-convergent game: given the n[sup]th[/sup] point x[sub]n[/sub], x[sub]n+1[/sub] is the point where the curve crosses the line passing through x[sub]n[/sub] and perpendicular to x[sub]n[/sub]'s radial.
     
    Last edited: Aug 8, 2009
  15. CptBork Robbing the Shalebridge Cradle Valued Senior Member

    Messages:
    6,169
    So what's the deal with this problem? I have the same issue as przyk, I've also found it's possible to construct the infinite spiral of which he speaks and I believe I have a simple mathematical way of demonstrating this if need be. So one can easily show that line can force point to converge to a limit cycle, but not to converge to any specific point on that limit cycle.

    Is there any other scheme by which line could possibly force a win? If point has the option of moving closer to the center at any given step, it spoils the whole convergence thing because in any subsequent step, point can move as close to the circle's boundary as it pleases.
     
  16. rpenner Fully Wired Valued Senior Member

    Messages:
    4,833
    I think it is possible that \(\theta\) is bounded because Point is not allowed to pick the "next point." Which I mean to say, the next Point cannot be infinitesimally distance from the previous. To choose it, it has to be a finite distance away.

    So if it given that Point can only choose points at least some \(\epsilon\) from the previous point, then Line gets to cut off a new line (perpendicular to a radius through the point). So that we go from \((r,\theta)\) to \((r',\theta') = (\sqrt{r^2+\epsilon^2}, \theta + \arctan \frac{\epsilon}{r}) \approx (r + \frac{\epsilon^2}{2 r}, \theta + \frac{\epsilon}{r})\) so that we have \(dr = \frac{\epsilon^2}{2 r} dn\) and \(d\theta = \frac{\epsilon}{r} dn\) so we have \(\frac{d\theta}{dr} = \frac{\epsilon}{r} \frac{2 r}{\epsilon^2} = \frac{2}{\epsilon}\) which can be increased without bound, but is finite for finite \(\epsilon\) so since r is bounded, so is \(\theta\).

    (It's late, and I'm not sure of my math above, let alone if the result is similar if epsilon is some fixed fraction of the chord.)
     
  17. Pete It's not rocket surgery Registered Senior Member

    Messages:
    10,167
    ...but 1/epsilon is not bounded for Point?
    Why can't Point choose new points such that the distance from the previous point tends to zero as the number of points chosen tends to infinity?

    I mean, 1/epsilon must be finite for any given choice, but it can still tend to infinity over time, right?
     
  18. CptBork Robbing the Shalebridge Cradle Valued Senior Member

    Messages:
    6,169
    Remember that you can have the distances between subsequent points tending to zero without the points all converging onto and getting arbitrarily close to a specific point. I think here's one way of looking at it as far as constructing the spiral przyk and I mentioned:

    Suppose you start at some point \(p_1\) within the unit circle, a nonzero distance \(r_1\) from the center. You draw a line in the scheme mentioned above (perpendicular to the radial line passing through \(p_1\)), the only possible way to force point towards the outside. Then the next point, \(p_2\), is subsequently chosen along that line at a distance \(r_2\) from the center, and a distance \(x_1\) away from \(p_1\). Using the Pythagorean theorem, we get:

    \((r_2-r_1)\times (r_2+r_1)=r_2^2-r_1^2=x_1^2 \Rightarrow \Delta r_1\leq \frac{x_1^2}{2r_1}\)

    We can thus proceed, through this scheme, to choose a sequence of distances \(x_1,x_2,\ldots\) such that the infinite sum \(x_1^2+x_2^2+\ldots\) converges (note that the inequality \(\Delta r_n\leq \frac{x_n^2}{2r_1}\) holds for all n since \(r_n\) is monotone increasing) and can be scaled to make as small a change to the radial distance as is desired, even after infinitely many iterations. Yet if one were to argue that confining the change of radius would prevent the construction of an infinite spiral, consider taking \(x_n=\frac{k}{n}\) for some appropriate scale factor, \(k\). Then the sum of the squares converges and can be scaled to be as little as one desires, corresponding to an arbitrarily small net change in radial distance. Yet it's clear the sum \(x_1+x_2+...\) diverges, so the only way to fit an infinitely long chain of line segments together like this is to have them going in an infinite spiral asymptoting to some circular limit cycle.
     
    Last edited: Aug 13, 2009
  19. przyk squishy Valued Senior Member

    Messages:
    3,203
    For those who don't like spirals, another trick is to express the points as complex numbers \(x \,=\, r e^{i \varphi}\). All the points on the line perpendicular to the radial passing through \(x\) can then be expressed in the form \(( 1 + i \varepsilon ) x\) for some parameter \(\varepsilon\). So if Line always uses this strategy we can cast the problem as analysing the convergence of expressions like:
    \( x_{n} \,=\, \prod_{k=1}^{n} ( 1 \,+\, i \varepsilon_{k} ) \, x_{1} \)​
    In norm this is:
    \( | x_{n} |^{2} \,=\, \prod_{k=1}^{n} ( 1 \,+\, \varepsilon_{k}^{\text{ }2} ) \, | x_{1} |^{2} \)​
    which puts the only constraint on the \(\varepsilon_{k}\)'s when we require that the sequence converges to a point within the circle.

    One possibility is to set \(\varepsilon_{k} \,=\, \frac{\tilde{\varepsilon}}{n}\), so that:
    \( x_{n} \,=\, \bigl( 1 \,+\, \frac{i \tilde{\varepsilon}}{n} \bigr)^{n} x_{1} \)​
    For sequences such as this, this becomes a phase change as we let \(n \rightarrow \infty\):
    \( \lim_{n \rightarrow \infty} \bigl( 1 \,+\, \frac{i \tilde{\varepsilon}}{n} \bigr)^{n} \,=\, e^{i \tilde{\varepsilon}} \)​
    To show what's already been demonstrated in this thread, while Point can't do "infinitely many" "infinitesimal" steps, he can still decide his next \(n\) steps will be \(x_{k+1} \,=\, \bigl( 1 \,+\, \frac{i \tilde{\varepsilon}}{n} \bigr) x_{k}\) for arbitrarily large \(n\), and so he can increase his phase by any desired amount with an arbitrarily small increase in radius (ie. he can get arbitrarily close to the limiting case of a pure phase change of arbitrary phase \(\tilde{\varepsilon}\)). Since Point has this possibility at any stage of the the game, Line can't force Point to converge in this way.
     
  20. temur man of no words Registered Senior Member

    Messages:
    1,330
    So is this still on?

     
  21. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    I checked with my source and Line can indeed force a win. Haven't figured it out though. It's on my list of many problems to solve. My own idea is to formulate the convergence of x(n) in terms of the position of the line.

    I can verify that the perpendicular line strategy fails due to the ability of Point to spiral. Clearly the only way for Line to win is for point to be trapped close to the boundary.

    EDIT:
    Alright I peeked and the solution is a letdown. You can find it in a book called 'Coffee time in Memphis'. Google books doesn't allow me to see the whole solution so can't reprint it here.
     
    Last edited: Aug 14, 2009
  22. quadraphonics Bloodthirsty Barbarian Valued Senior Member

    Messages:
    9,391
    So I am almost sure that Line also can't win by employing a fixed non-perpendicular strategy either (then Point can play games decreasing and increasing his radius to prevent convergence).

    So it seems that we should be considering some kind of mixed strategy for Line. Perhaps he can pursue a strategy of usually using the perpindicular line, but occasionally include some off-perpendicular lines to prevent point from processing around in a spiral? The question is whether Line can do that without also giving Point the opportunity to recover in reduced radius what he loses in angular procession...
     
  23. §outh§tar is feeling caustic Registered Senior Member

    Messages:
    4,832
    see my above post quadraphonics. I really doubt there is an elementary (calculus/common sense approach) solution to this. One look at the original solution and you'll see what I mean.
     

Share This Page