Solution
I received 9-move solutions (including, more or less, proofs that the strategies defeat Bob in all cases) from Jim Tilley (USA), Barry Cox (Australia), Nagendra Gular Dwarakanath (India), and Joseph DeVincentis.
DeVincentis also submitted a proof that is inefficient, but very easy to verify, that Alice can force N colors for any N. Here is his approach.
Let us take N to be 6 and so suppose Bob is restricted to using colors 1, 2, 3, 4, 5. Alice starts by making 11 disjoint edges. Since there are only 10 pairs of colors, one pair must be repeated.
Suppose the repeated colors are 1 and 2. Alice then adds a vertex connected to the 1 on the first edge and the 2 on the second one. Bob must give this vertex a color different from 1 and 2; say 3. Call this 5-vertex structure a G3.
Then Alice can start over to get two more G3s; note that each one (and every connected graph in this proof) is a tree. Then Alice forms a G4 by connecting a new vertex to one vertex in each G3, so that the touched vertices have different colors. This is possible since there are 3 colors in each G3. Then she again starts over to get more G4s, for four in all. She then connects a new vertex to each G4, using different colors for the neighbors. Call this a G5. Then start over and get five G5s. Then connect a new vertex to each G5, using different colors for the five ends. This last vertex must receive a sixth color from Bob. This idea extends with no change to show how Alice can force N colors.
Of course, she uses a lot of vertices, perhaps NN. An improvement on this to φN is shown below.
Alice can in fact force 6 colors in just 8 moves, as was done by Laurent Lessard. Building on his approach, and using some variations contributed by Jim Tilley, I produced the complete tree showing a strategy that works in 8 moves. A PDF of the strategy, with full tree form, is available for download (53k).
Here are some other results in this area.
Let A(N) be the number of moves needed for Alice to force Bob to use N colors; clearly A(N) ≥ N. We have
A(N) = N when N = 1, 2, 3, or 4 (trivial)
A(5) = 6 (proved below)
A(6) = 8 (proved by strategy in diagram and lower bound proof below)
For A(5): Alice places vertex V1; it gets color 1. She places vertex V2 adjacent to V1; it gets color 2. She then places V3 adjacent to V1 but not V2. This is colored either 3 (case "new") or 2 (case "old").
In the new case, she places V4 adjacent to V1, V2, V3 so that all four stay exterior. It must get color 4. Next, she places V5 adjacent to all 4, succeeding in 5 moves.
In the old case, she places V4 adjacent to V1 and V2. So V4 gets color 3. Now V5 can be placed adjacent to V1, V3, and V4 so that these four vertices are still exterior. V5 must get color 4. So 5 steps suffice to get 4 colors on the exterior and the last step is as in the new case, using 6 moves in all. A proof that A(5) is not 5 will be presented below.
For A(6), we will prove below that success in 6 or 7 steps is not possible. We can use the preceding values to set up an induction that shows that Alice can force Bob to use N colors using φN moves, where φ is the Golden Ratio (1 + √5)/2, about 1.6). This is due to Tony Dillof, of Wayne State Univ. Law School, with some improvements by an anonymous poster and edits by me.
1. Alice starts by forcing 6 colors, as in the optimal strategy, but stops one move short, so we have a graph G5 using 5 colors on the exterior, formed in 7 moves.
2. Alice then makes a disjoint graph by forcing 5 colors, but again stopping one move short, so we have a graph G4 with 4 colors on the exterior, formed in 5 moves.
3a: Suppose there are 6 exterior colors in the union of G4 and G5. The Alice connects to those 6 and has forced 7 colors in 7 + 5 + 1 moves.
3b: Suppose there are not 6 exterior colors in the union of G4 and G5. Assume wlog that G5 uses colors 1, 2, 3, 4, 5 and color 1 does not appear on the exterior of G4. Then Alice adds a vertex adjacent to the full exterior of G5 so that color 1 remains on the exterior. That vertex gets color 6. Then she adds a vertex adjacent to color 6 and color 1 from G5 and all of G4; that is forced to receive color 7. The move count is 7 + 5 + 1 + 1. So this shows that A(7) ≤ 14.
This idea works the same way in general, yielding
A(n) ≤ (A(n − 1) − 1) + (A(n − 2) − 1) + 2 = A(n − 1) + A(n − 2).
The following Mathematica command yields a closed form for this recurrence as an equality.
a[n] /. RSolve[ {a[n] == a[n-1] + a[n-2], a[5] == 6 ,a[6]==8}, a[n], n]
2 (5 Fibonacci[n] − 2 LucasL[n])
In radical form, this is the following, where φ is the Golden Ratio:
2 (√5 − 2) φn + (2* (-1)(1 + n)*(2 + √5)) / φn
The first term dominates and so we get the bound A(n) &le 0.5 φn; or the weaker bound: 10 Fibonacci(n). So the outstanding question here is: Is there a linear or quadratic bound on A(n)?
Finally, here is a proof by Jim Tilley and Stan Wagon that A(6) is not 7 or less. It has points in common with the notes of Guy Moore at , but was found independently.
Theorem. A(6) = 8.
Proof. It suffices to show that A(6) is neither 6 nor 7.
Let's use the term "greedy strategy" for any strategy by Bob that uses an old color whenever that is legal. We will show that Alice cannot win in 7 moves if Bob follows a greedy strategy.
Since Bob may always use a greedy strategy, the theorem follows. We use the numbers 1, 2, 3,... as colors for vertices and V1, V2,... for the vertices Alice places in order. Note that a win in 5 or fewer moves is clearly impossible.
After 3 moves, there are only 3 possibilities with V1, V2, V3: G1, a triangle colored 1-2-3; G2, a path of length 2 colored 1-2-1; G3, a path of length 1 colored 1-2 together with a disjoint vertex colored 1. The case of 3 disjoint vertices is not possible because Bob will have colored them all 1, which would lead to at least 8 vertices.
Only G1 can lead to a win in 6 moves. But no matter where V4 is placed, it must be joined to each of V1, V2, V3 (to force a new color) and we have the complete graph K(4); this is a triangulation and the next move will allow an old color to be used — a contradiction.
For a win in 7 moves, Bob can use an old color (one that is already used) only once. For G2 and G3, that one move has already been used; for G1 it has not.
Now consider the three cases G1, G2, G3:
Case G1. Ultimately, there will be 7 vertices using 6 colors. Only one can use an old color, so among V4, V5, V6, and V7, there are three vertices with new colors. And two of these three must lie in the same face of A. The first of these must connect to V1, V2, V3, since it has a new color. But then the second must be in one of the three triangles determined by the first, and so it would receive an old color — a contradiction.
Case G2 or G3. V1 and V3 get color 1, V2 gets color 2. V4 must get a new color and so it must be connected to V2 and either V1 or V3 or both. V4 gets color 3. Each of V5, V6, V7 must get new colors, so they must all be connected to V2 and V4 and to each other; and each must be connected to either V1 or V3 or both. In all situations, the subgraph induced by V2, V3, V4, V5, and V6 is K(5), which is not a planar graph — a contradiction.
QED.
These same ideas show that A(5) is not 5. For if it were only new colors would be used and so there would be a planar K(5) — also, a contradiction.
[Back to Problem 1231]
© Copyright 2016 Stan Wagon. Reproduced with permission.