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

The analyses in two recent MO questions, "Rolling a random walk on a sphere" and "Maneuvering with limited moves on $S^2$," suggest a Rolling-Ball Game, as follows.

A unit-radius ball sits on a grid point of a $\delta \times \delta$ regular grid in the plane, with $\delta \neq \pi/2$. Player 1 (Blue) rolls the ball to an adjacent grid point, and the track of the ball-plane contact point is drawn on the ball's surface. Player 2 (Red) rolls to an adjacent grid point. The two players alternate until each possible next move would cause the trace-path to touch itself, at which stage the player who last moved wins. In the following example, Red wins, as Blue cannot move without the path self-intersecting.
           Rolling Ball Game


Q1. What is the shortest possible game, assuming the players cooperate to end it as quickly as possible? For $\delta=\pi/4$, the above example suggests 6, but this min depends on $\delta$. It seems smaller $\delta$ need 8 moves to create a cul-de-sac?

Q2. What is the longest possible game, assuming the players cooperate to extend it as much as possible?

Q3. Is there any reasonable strategy if the players are truly competing (as opposed to cooperating)?

Addendum. We must have $\delta < 2 \pi$ to have even one legal move, and the first player wins immediately with one move for $\pi \le \delta < 2\pi$ (left below).
Two examples
The right image just shows a non-intersecting path of no particular significance for $\delta=\pi/8$.

share|improve this question
4  
Does anyone have a convincing argument that the answer to Q2 is finite? The best I have is that it's totally obvious... –  Johan Wästlund May 12 '11 at 22:08
    
@Johan: Yes, that does seem the first question to settle! I originally typed for Q2 that "it is clearly finite," but then backspaced over my typing, imagining some type of tight nesting/packing of the path. It is conceivable and so possible until explicitly excluded. –  Joseph O'Rourke May 12 '11 at 22:48
1  
I've just tried to find a proof of finiteness by using the pigeonhole principle to say that there are two long bits of path that take the same steps and start in almost exactly the same place with almost exactly the same orientation. It feels promising but I haven't managed to push it through. –  gowers May 13 '11 at 14:41
2  
If this game were played on a torus (and the nontracing parts were allowed to pass through the tracing board), I think there would be an arbitrarily long staircase path that was playyable. I would thus be impressed by any combinatorial proof that does not hinge on the metric geometry of the object being rolled. Gerhard "Ask Me About System Design" Paseman, 2011.05.13 –  Gerhard Paseman May 13 '11 at 16:40
2  
From the question: "The first player wins...if $\delta\geq\pi$." What if $\delta\geq 2\pi$ though?? –  Kevin Buzzard May 13 '11 at 20:49
show 5 more comments

3 Answers 3

The game is, indeed, finite though the reason I see is slightly different. I claim that if $L$ is a sufficiently long piece of a fixed shape and $R$ is a rotation sufficiently close to the identity, then $RL$ intersects $L$. This is a combination of three observations:

1) If the angle $a$ of rotation is small enough, then the "far" intersections are ruled out automatically, i.e., if $E'$ and $E''$ are two edges and $RE'$ intersects $RE''$, then $E'$ and $E''$ are either the same or adjacent. Also, if $L$ and $RL$ do not intersect, then topologically everything is trivial: $L$ just "shifts to one side".

2) There are very many corners on $L$ and each corner sweeps the area about $\delta a$ under the rotation $R$, so the area between $L$ and $RL$ is about $Ca$ with large $C$.

3) The angle deficiency at each endpoint (if we close the curve somehow) is at most $a$.

The ending is obvious: there are finitely many possible shapes of fixed large length, each piece can have not too many copies (otherwise there are two pieces differing by a small rotation), so the total length is bounded.

share|improve this answer
    
I do not understand your proof, could you please give more details? Also, would it work for the torus too? Because then it would contradict what Gerhard "Ask Me About System Design" Paseman claims in his comment. –  domotorp May 15 '11 at 20:23
    
Sphere has positive curvature while torus is flat, so huge area on the torus is perfectly compatible with zero angle deficiency, which, of course, destroys this argument for the torus. What exactly don't you understand? –  fedja May 15 '11 at 21:22
    
First, what is a "long piece of a fixed shape"? Do you just mean a long game? Why are far intersections ruled out automatically? Because the angle a is small compared to the length of L? If yes, then Ca would not be large... Anyhow, I am sure that your argument has some basic thing that I misunderstand and maybe I am not the only one. –  domotorp May 16 '11 at 5:50
    
"Shape" is the fixed sequence of turns: you know whether you go straight, left, or right at each step but you don't know where and in what direction you start. If you have a broken line without self-intersections, the minimal distance between non-adjacent edges is positive and if the angle is much less than this distance, they cannot meet. $Ca$ does not need to be large in absolute terms, just to be much larger than $a$ to get a contradiction (the area must equal the angle deficiency regardless of whether it is large or small). –  fedja May 16 '11 at 12:17
    
I see, thank you! Now I see why the ending works and why 1 and 2 are true but I do not see how you can get a contradiction from 3 (maybe because I am not sure I know what angle deficiency means). –  domotorp May 17 '11 at 7:23
show 2 more comments

For testing potential answers to Q3, let me suggest http://www.math.chalmers.se/~wastlund/Quirks/Game.html.

The appearance as well as the specific set of bugs might depend on your browser, but as I hope will be clear, the length of the longest path as a function of the angle $\delta$ is quite funny (this is part of the reason I spent too much time on this problem, although I'm also interested in similar path-forming games for more "serious" reasons).

After drawing a couple of quick sketches I realized I wasn't even able to figure out the behavior when $\delta$ approaches $\pi$ from below. As it turns out, the number of edges in the longest path is 5 throughout the interval $3\pi/4 \leq \delta < \pi$. For $\pi/2 < \delta < 3\pi/4$ it's 7 (although the game-tree changes also at $2\pi/3$). At $\delta = \pi/2$ it has an isolated local minimum of 5, and for angles just smaller than $\pi/2$, it seems to jump to 23.

Here's why I couldn't let go of this problem: In all the cases where I can visualize the entire game-tree, which is when $\delta\geq \pi/2$,

(1) Alice, who draws the first arc, wins the game-version.

(2) Bob, while losing, can force Alice into a maximal-length path. In other words, Alice cannot force a win in fewer moves than the length of the longest path. This property holds for some similar path-forming games where there are explicit winning strategies.

(3) As a consequence of (1) and (2), the length of the longest path is always odd.

A couple of other observations: If we allow players to cross their own edges but not the opponent's, then an edge is never a liability, and consequently Alice has a non-losing strategy. If on the other hand we allow players to cross the opponent's edges but not their own, then an extra edge cannot be an advantage, and now Bob has a non-losing strategy (two more questions arise here: are these games too necessarily finite, and can the (winning?) strategies be made explicit rather than just exhibited by strategy-stealing?).

Therefore I thought for a while that I was on to something, and that there might be a beautiful reason that Alice must win.

So I let Maple analyze the game for some suitably chosen angles, working symbolically to get reliable results. This is feasible when $\delta$ is such that the ring $\mathbb{Z}[\cos\delta, \sin\delta]$ where the coordinates of the points lie, is either a sub-ring of $\mathbb{Q}$ or of some nice algebraic field (degree 2 or 4).

To summarize, I found counter-examples to each of (1), (2) and (3): For $\delta = \arctan(24/7)$, Bob wins at move 16 but the longest path has length 23. For $\delta = \arctan(12/5)$, the longest path has length 24 (but Alice can force a win in 13). Moreover, for $\delta=\pi/3$ there is a path of length 29 but Alice wins in 17. For $\delta=\arctan(4/3)$, Bob wins in 16 (I don't know the length of the longest path).

Addendum. (by J.O'Rourke). I took the liberty of adding an image of Johan's $\pi/3$ longest path from his applet, as detailed in his comment below. Note the near miss where the 28th segment just misses the 1st segment.
Pi/3

share|improve this answer
1  
This is amazing analysis!!! And your game applet is awesome! I haven't absorbed it all yet, and so have no substantive remark to make, but I wanted to register my admiration. It might be useful if you could list those $\delta$ for which you know the longest paths. I would be interested to see a path that illustrates the jump to length 23, or the $\pi/3$ path of length 29, just to get some intuitive sense of their structure. Thanks for sharing all this information! –  Joseph O'Rourke Jun 1 '11 at 13:48
    
Here's an example of a path of length 29 for $\delta=\pi/3$ (f,l,r = forward, left, right): f-f-f-r-l-r-r-f-l-l-r-l-f-f-f-f-r-l-r-r-f-l-l-r-l-f-f-f. And one of length 23 for $\delta=0.49\pi$ (actually based on rational arithmetic in Maple with $\delta=\arctan(5101/101)$, which seems to be equivalent). f-l-r-r-l-f-r-r-l-l-f-f-r-r-l-l-f-r-l-l-r-f. Several moves in this sequence are possible with small margins, but at the ninth move (tenth edge) it's really close. Amazingly, at the next move, a right turn would not have been legal. If you follow with the applet you see what I mean. –  Johan Wästlund Jun 3 '11 at 7:27
add comment

I can show the game is finite which answers one of the questions in the comments and shows the answer to question two is not infinity. The arcs in on the sphere from the rolling are sections of circles of unit radius the angles between the arcs are either 90 or zero. Furthermore there is finite limit to the number of rotations without switching the direction of rotation. So for a large number of rotations there will be a set of arcs with a large number of 90 degree angles. But this will mean a large angle deficiency and an arbitrarily large area but there is a finite limit to the area of subset of the surface of the sphere so there is a contradiction.

share|improve this answer
    
Why can't the deficiency be low due to cancellation between $\pi/2$ and $-\pi/2$ angles? –  Douglas Zare May 13 '11 at 6:39
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.