It’s a cruel irony: As the citizens of Zimbabwe sink into bitter poverty, they are becoming millionaires and billionaires. Inflation is eroding the value of the Zimbabwean dollar so rapidly that everyday transactions turn into lessons in the arithmetic of large numbers. When the photo above was made on July 17, the largest currency denomination in circulation was a note for ZW$50,000,000,000. Last week the nation’s central bank issued a ZW$100,000,000,000 bill. (I’ll spare you the trouble of counting zeroes: That’s 10¹¹, or 100 billion by American reckoning.)

The Zimbabwean inflation is the worst in the world at the moment, but it is not (yet) setting all-time records. Probably the most famous episode of extreme inflation was that of the German Weimar Republic (a story told vividly in Erich Maria Remarque’s novel The Black Obelisk.) In 1921, German marks traded at about 60 to the U.S. dollar; two years later, in December of 1923, the exchange rate was 4.2×10¹² per dollar. The Hungarian inflation following World War II reached even greater numerical heights. In a single year the exchange rate for the Hungarian pengo went from 100 per U.S. dollar to 4×10²⁹. As Feynman said, astronomical numbers are dwarfed by economical ones.

Takayuki Mizuno, Misako Takayasu and Hideki Takayasu have analyzed the German and Hungarian episodes of “hyperinflation.” (Citation: Physica A 308 (2002) 411; there’s also an arXiv preprint.) Inflation at its worst, they find, proceeds at a doubly exponential rate. In other words, prices rise not just as an exponential function of time—exp(t)—but as an exponentiated exponential—exp(exp(t))—or:

This growth law has a simple meaning in terms of everyday experience. With “ordinary,” single-exponential inflation, prices have a constant doubling time. If bus fare was 1 million last month and 2 million this month, it will be 4 million next month. Under double-exponential growth, the doubling time itself decreases exponentially. In the last months of the Hungarian inflation the doubling time fell from about 20 days to 15 hours.

On a logarithmic scale, a simple exponential function yields a straight-line graph. Here is the Mizuno-Takayasu evidence that the final phase of the Hungarian inflation was superexponential:

And here are the data for the final six months plotted as log(log(p(t))), showing a simple linear trend:

How does the Zimbabwean economy look when submitted to this kind of scrutiny? I don’t know of a reliable source of data on prices in Zimbabwe, but foreign exchange rates can serve as a rough proxy. Until three months ago, the official ZW$ rate was pegged at roughly 30,000 per US$, but on May 10 the currency was allowed to float free, and the rate immediately jumped to 190,000,000 ZW$ per US$. By July 31 the rate had reached 57,381,544,140. Thus the 50 billion ZW$ note in the photo above was worth a little less than a 1 US$ by the end of last month. And that’s at the official rate of exchange; the street value is reportedly about a tenth of the official quote.

Here’s how the official exchange rate has varied in the 84 days between May 10 and August 1, as plotted on a linear scale:

And here’s the same data after a logarithmic transformation:

Although there’s more bumpiness here than in the Mizuno-Takayasu data, the trend looks reasonably linear to me. The fitted line has slope 0.03358, which yields a doubling time of about nine days. I see no hint of superexponential growth. I’d like to think this is an encouraging sign, a glimmer of hope that Zimbabwe will be spared an even more pernicious phase, when even inflation has inflation.

Runaway inflation is usually blamed on the incompetence or malevolence of governments and the central banks that implement their policies. In the case of Zimbabwe, the government of Robert Mugabe certainly has a lot to answer for. The country was once the shining success story of southern Africa—I have friends who migrated across the continent to go to school there—but the nation is now a basket case, and inflation is only one of many urgent crises. (The unemployment rate is reported to be 80 percent.) The Mugabe regime can’t escape blame for this situation. Still, it seems that hyperinflation is not to be explained purely in terms of fundamental economic imbalances—too many dollars and not enough goods. Sometimes it seems there is also a psychological component. When you believe that prices will double next week, you raise your own prices in anticipation. It’s a self-reinforcing process.

One sign of such a feedback loop in the inflationary spiral is that inflation sometimes stops even though the underlying economic situation hasn’t really changed. The Weimar hyperinflation ended with the introduction of the Rentenmark, which was set equal to 10¹² old marks but really had no firmer backing than the earlier Papiermark. The change in currency did nothing to solve Germany’s problems of debt and unemployment, but the inflation ended anyway. Evidently, people chose to believe that the value of the Rentenmark would remain stable, and it did.

The central bank of Zimbabwe has just announced a similar effort at currency reform, devaluing the ZW$ by a factor of 10¹⁰. In other words, the ZW$100,000,000,000 note introduced a week ago is equal in value to a new ZW$10 bill. According to press reports, the main motive for the change was simply logistical convenience:

Gideon Gono, the Central Bank governor, … acted because the high rate of inflation was hampering the country’s computer systems. Computers, electronic calculators and automated teller machines at Zimbabwe’s banks cannot handle basic transactions in billions and trillions of dollars. (AP/Baltimore Sun)

But perhaps one can hope that the newly denominated currency will bring more than numerical benefits. Over the weekend, the official exchange rate has held at 6.569 new Zimbabwe dollars to the U.S. dollar. We’ll have to wait a few more days to see if the curve has really flattened out.

Update 2008-09-04: With another month of exchange-rate data, here’s what the situation looks like:

The blue line in the semilog graph is the same as the one in the corresponding earlier graph—that is to say, it is fitted to the first 80 days of data. It appears that the inflation rate has diminished slightly since the revaluation at the end of July. But that slightly lower rate is still formidable; in a little more than a month the value of the new Zimbabwe dollar has fallen from about 15 cents (U.S.) to about 2 cents.

Update 2008-10-02: After another month, what passes for good news is that the rate of exponential growth does not seem to be growing:

On the other hand, news reports suggest that the situation in Harare is bleaker than ever. Money is scarce as well as nearly worthless; people stand in line all night for the privilege of withdrawing the equivalent of a dollar or two from their own bank accounts. (Note that the equivalent of $1 U.S. is $ZW137 in the devalued currency issued in August. In pre-devaluation Zimbabwe dollars, it comes to $ZW1.37 trillion.)

Isn’t it curious that both here in the U.S. and in Zimbabwe, the financial pages are filled with such enormous numbers.

Update 2008-11-02: One more month of data:

Still no sign of “hyperinflation”—if that term is taken to mean doubly exponential growth—but that can’t be much solace to the Zimbabweans whose currency has yet again lost three-fourths of its value over the course of a month. Adjusting for the August devaluation, one U.S. dollar now buys 5.6 trillion Zimbabwean dollars.

I’ve been Scrabbling by email lately. In today’s game my partner started out by playing

                    H
                    E
                    X

and I responded with

                   A H
                   W E
                   E X

At this point my opponent might well have continued with another three-letter word to make a tidy square block such as:

                  Y A H
                  E W E
                  S E X

In actuality she did something quite different. She played a seven-letter “bingo,” using all her letters to earn a 50-point bonus; as a result I’m hopelessly far behind in the scoring. But let us say no more about the tawdry details of winning and losing; there’s a puzzle here. Looking at that three-by-three block of letters and words, it occurs to me there must surely be legally reachable configurations of a Scrabble board that have no legal continuation. Scrabble rules say that, except for the first move, letters can be added to the board only on squares adjacent to existing letters, and all sequences of two or more letters (both vertically and horizontally) must be dictionary words. The rules say nothing about the situation where continued play is impossible.

I’m sure there must be many stymied positions, where no words can be formed, regardless of what letters you have on your rack. Or so I assert; but, the fact is, I haven’t been able to find even one such configuration. A cursory examination of the list of all allowed two-letter words argues that no two-by-two block of letters can be stymied. What about two-by-three or three-by-three blocks? Somebody must have settled these questions, but my Googling has failed to find the answer. What is the smallest stymied position? (I don’t require that a solution be a rectangular block of letters, but having stray letters dangling off the edges of a block makes it easier rather than harder to form words.)

A few weeks ago I playfully suggested that the Democratic nominee for POTUS might be selected this year by a game of hex played on the map of the lower 48 states. I emphasize the word “playfully.” This was not a serious suggestion. But life has a way of overtaking us, even in our most frivolous moments. As the primary season now spirals down to the last bitter dregs, the nomination remains undecided, and so does the game of electoral hex.

The goal in this version of hex is to assemble a continuous chain of states that spans the country either east to west or north to south (or both). As the map below shows, both candidates are tantalizingly close to this goal, but neither has actually achieved it. The recent round of voting in North Carolina and Indiana, and then yesterday’s result in West Virginia, failed to clinch it.

But it will all be over soon. Kentucky is the key. The nomination may or may not be settled after that state’s primary election next Tuesday, but the game of hex will surely be decided, one way or the other. Whichever candidate wins Kentucky will form both east-west and north-south chains, and his or her opponent will be shut out from creating either kind of chain.

Update 2008-05-21: Game over. As the map from today’s Times shows, Hillary Clinton percolates. She can drive coast to coast or border and border and never stray outside of states that supported her candidacy. As far as I know, she has not yet cited this fact in support of her decision to stay in the race; maybe she’s saving that argument for the convention.

The interesting thread of comments on Wednesday’s post about “electoral hex” led me to look more closely at the graph for the Lower 48 states:

I’ve constructed the graph—and it wasn’t easy, by the way—on the rule that two states are linked by an edge if they share a common boundary of more than one point. National boundaries are determined in the same way. Nodes half-shaded orange are east coast or west coast states; those half-shaded blue are north coast or south coast states. Underwater boundaries count in this scheme. Thus, for example, Illinois is adjacent to Michigan because there’s a section of boundary line between them in the middle of Lake Michigan. Similarly, Wisconsin is not a north coast state, even though it abuts Lake Superior, because it has no shared boundary with Canada.

Some properties of the graph:

• It has 48 vertices (no surprise!), 107 edges, and 60 faces (excluding the outer, embedding, face).
• It’s a planar graph (again no surprise).
• All but one of the faces are triangles. The exception is a quadrilateral formed by the Four Corners states.
• The degree sequence runs: 8 8 7 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 2 1. (The two octopus states are Missouri and Tennessee. The singleton is Maine.)
• The diameter is 11, and the characteristic path length (the length of the shortest path between two vertices, averaged over all pairs of vertices) is 4.1.

What about playing hex on this graph? In standard hex, one player tries to connect east to west, and the other player has to find a path from north to south. Those rules would hardly be fair with such an asymmetrical graph. So let’s adopt a modified version of the rules that I suggested for the political primaries: The players take turns, and the first to create a pathway either from north to south or from east to west is the winner. (Barry Cipra suggested that we call this the game of pox.)

Is the game a sure win for either the first or the second player (assuming correct play on both sides)? If so, what’s the right opening move?

It’s easy to find some really bad moves. As Paul Zorn noted, the New England states are not worth bothering with, because they’re sealed off by New York. But it turns out New York is not a very smart choice either. (If you take New York, I take Pennsylvania; then, if you want to get anywhere, you have to win all three of New Jersey, Delaware and Maryland, which gives me three chances to block you.)

The shortest bridging paths are along the I-5 and I-15 corridors, out west. In particular, there are five ways to construct a path of length 3 from north-to-south with the states WA, OR, CA, ID, NV, UT, AZ. But I don’t believe there’s any way a player can force a win using these states alone.

In hex, the best opening moves are generally near the middle of the board. The analogous pox strategy would choose one of the central and highly connected states such as MO, TN or KY. This seems sensible, but the games are too complicated to work out by hand.

On a regular 7 × 7 board, hex has been fully solved: The entire game tree is known for every possible opening move, so that each cell of the board is classified as a win or a loss for the first player. (This impressive feat of analysis and computation was done by R. Hayward, Y. Björnsson, M. Johanson, M. Kan, N. Po and J. van Rijswijck of the University of Alberta.) The Lower 48 graph is roughly the same size as the 7 × 7 hex board, so a similar method would presumably be feasible. Feasible but not easy.

Another question is whether the game can end without a winner. Jim Ward asked about this in the comments to the previous post, but I didn’t really understand the full force of the question. In the game of presidential primaries—where elections can occur simultaneously in multiple states—two or more winning paths could be created at the same time. Enforcing a strict alternating-turns policy, as I’m assuming here, eliminates that problem. But there’s another way the game might possibly fail to yield a winner, namely if all the states are chosen but there’s still no path along either axis.

In hex it’s easy to show that no such drawn game is possible. You can block the progress of a north-south path only by completing an east-west path. Hex is played on a regular and symmetrical lattice whose structure is equivalent to this graph:

The graph of the Lower 48 is not quite so uniform. The diagonals don’t all go the same way, and there’s that quadrilateral with no diagonal at the Four Corners. Does that feature (or some other oddity of the graph) allow all the states to be divided into two categories without creating either a north-south or an east-west path? I don’t think so; I haven’t been able to find such an assignment. But I’m not quite sure it can’t exist.

Update 2008-03-17: By popular request, I’ve posted a PDF version of the lower-48 graph and a text file with the vertex list and edge list. The vertex and edge lists actually take the form of a Scheme definition, but the semantics should be obvious and translation to other formats should be straightforward.

Democrats here in the U.S. are having quite a primary season. With high hopes of winning the general election in November, we are deadlocked over which candidate to nominate. Should we just wait to let the delegates slug it out at the convention in August? Should the trailing candidate withdraw in the interest of party unity? Could the two contenders flip a coin to decide who gets to head the ticket and who gets to drink the bucket of warm piss?

I have a proposal. Here’s the geography of the current situation, following Obama’s victory in Mississippi yesterday (map brazenly swiped from the New York Times):

The solution is obvious, no? We follow the rules of the game of hex: The nomination goes to the first candidate to form a continuous chain of states either east to west (Atlantic to Pacific) or north to south (from the Canadian border to Mexico or the Gulf Coast). Thus the three key states are Pennsylvania (which votes April 22), North Carolina (May 6) and Kentucky (May 20). Clinton could create an east-west chain by taking North Carolina, or a north-south path by winning Kentucky. For Obama, Kentucky creates an east-west link; to construct a north-south chain, Obama would have to win both North Carolina and either Kentucky or Pennsylvania.

I get to cast my ballot on May 6 in North Carolina. All I’m saying for now is that I’m not voting for Ralph Nader.

The answer to the question in the headline is: Too many. After I wrote about Sudoku a couple a years ago, I thought I had cured my addiction; but I’ve been a shameless backslider.

I return to the subject now, in this public confessional mode, to correct an error in my 2006 column. Citing a paper by Bertram Felgenhauer and Fraser Jarvis (pdf), I stated that there are 6,670,903,752,021,072,936,960 Sudoku solutions. This is simply the number of ways of filling in the 81 squares without violating the no-two-alike constraints in rows, columns and blocks. I then went on to discuss the symmetries of the Sudoku grid, and noted:

When all these symmetries are taken into account, the number of essentially different Sudoku patterns is reduced substantially…. although [the reduction] still leaves an impressive number of genuinely different solutions: 3,546,146,300,288, or 4×10¹².

The latter number also comes from Felgenhauer and Jarvis, but I misinterpreted it. Contrary to my statement, it takes into account only a few of the simplest symmetries. The true number of essentially distinct Sudoku solutions is reported in a slightly later publication by Ed Russell and Jarvis. The correct tally is smaller by three orders of magnitude: 5,472,730,538.

Thanks to Richard E. Dickerson for pointing out my error.

It needs to be emphasized that both of these calculations count the number of solutions, not the number of puzzles. For any given solution, there are many possible puzzles, each created by erasing a different subset of the entries in the solution. How many puzzles per solution? Does anyone know? An exact count seems beyond reckoning, but random sampling ought to yield a rough estimate. For example, consider just those puzzles that have 17 initial clues (the apparent minimum). For any given solution grid, there are (81 choose 17) ways of forming a 17-clue puzzle; this works out to 128,447,994,798,305,325. Most of those puzzles will not have a unique solution, and so they are disqualified as proper Sudokus. The random sampling is needed to estimate how many of the potential puzzles are admissible.

I’d try doing the calculation myself, but I’m too busy solving Sudokus.

Update 2008-04-05: Richard E. Dickerson discovered the error mentioned above in the course of preparing his own discourse on Sudoku-solving strategies. That work now has its own web site, The Sudokerson Matrix, where you can download the 61-page PDF file and an accompanying spreadsheet. Dickerson also mentions some other resources on Sudoku strategy, including a recent book by Andrew C. Stuart that I haven’t yet seen. Dickerson comments:

Few books on Sudoku go into strategies in any depth. Stuart’s The Logic of Sudoku (Michael Mepham, 2007) is a wonderful exception. But his book and mine represent the two opposite poles of Sudoku-solving strategy. I regard many of his methods as superfluous, and I am sure that he regards most of my strategies as heretical. You need to have a close look at both.

What I find intriguing in all this is the very idea that we could have contending doctrines of Sudoku strategy. But before the talk of “heresy” gets out of hand and leads to Sudoku holy wars, I’d like to remind everyone that there’s another view of Sudoku in which all strategies become superfluous. Give me a computer and a program for solving constraint-satisfaction problems, and every 9×9 Sudoku yields in milliseconds.

Don Elgee, a retired teacher of mathematics and computer science from Ottawa, sends the following inquiry:

In hockey, when a team is down by a goal with about one minute to go, the goalie is pulled in favor of another offensive player. This illustrates a key point in the strategy of most games.

The object is not to maximize points for, and minimize points against; rather, it is to win or tie the game. As the game nears its conclusion the winning team plays more conservatively and the losing team more radically. But when—and to what extent—should a team change its style of play? 

To clarify the problem I tried to conceive the simplest possible example. It turned out to be much more complex than I expected.

Consider the following simple game: Two players toss a die on alternate turns. The first one to reach 100 is the winner. Players have a choice of two dice—one is normal (6, 5, 4, 3, 2, 1) and the other has faces with 6, 6, 5, 1, 1, 1. When should the losing player switch to the second die?

Is there a mathematical solution? Could you determine this by experimental computer simulation? Does the best strategy depend on the strategy the opponent is likely to choose next?

This simple problem is difficult enough, but the sports situation could better be simulated by adding a third die with 4, 4, 3, 3, 3, 3.

Has this issue been subject to mathematical study? With all the statistics used in professional sport has anyone tried to include this factor? Has it ever been incorporated in computer simulations?

Hockey is not my sport, but these are interesting questions. Inspired by Elgee’s letter, I’ve run a few of the obvious simulations. For the time being, however, I’m not going to say much about the results. What I’ve learned so far does not lead to any simple, pithy rule of thumb that a hockey coach could use to decide when to pull the goalie. Nor do I have a clear grasp of how best to play the dice game. I’m hoping someone else will offer a sharper analysis. Toward that end I have some further notes and observations.

Under the stated rules—alternating turns, with victory going to the first player who reaches 100—the privilege of moving first brings a substantial advantage. In a 100-point game with standard dice, the first player can expect to win about 55 percent of the time. If two players are tied at 99, the first to roll is definitely going to win, regardless of which die is chosen. Because of this bias, we probably need to consider different strategies for the first and second players (like white and black in a chess game). An alternative is to add a further element of randomness to the game: In each round, the player to move is determined by the toss of a fair coin.

Elgee’s two nonstandard dice have faces that sum to 20, less than the standard die’s 21. As a model of hockey tactics, this bias makes sense: It reflects the risk of leaving the goal untended. But if we ignore hockey and just consider the dice game on its own merits, it might be more interesting to explore a symmetrical contest with dice marked 6, 6, 6, 1, 1, 1 and 4, 4, 4, 3, 3, 3. Then we’d be looking at three distributions that have the same mean but different shapes.

Generalizing further, we could allow dice marked with any six non-negative integers that sum to 21. What would happen to the game if we allowed dice such as 100, -16, -16, -16, -16, -15? Or, we could allow the players to choose continuous probability density functions.

It’s easy to imagine circumstances where a “high-risk” die should be advantageous. If the score is 99 to 94, then the trailing player should be willing to accept any trade-off that improves the odds of rolling a 6; even a 6, 6, 0, 0, 0, 0 die is preferable to the standard die. Conversely, if you’re ahead near the end of the game, the “low-risk” die seems favorable. All this suggests there ought to be some fairly simple guidelines for choosing the best die in any situation. But, as Elgee noted, it’s more complicated than you might expect.

In my simulations I found that with the score tied at 94, switching to the 6, 6, 5, 1, 1, 1 die (while your opponent continues to play the standard die) yields an advantage of 2.9 percent. But when the score is 96 to 96, making the same switch produces a deficit of 3.7 percent. Interestingly, choosing the 4, 4, 3, 3, 3, 3 die brings similar results: a gain at 94 to 94 but a loss at 96 to 96. (The simulations used the coin-flip protocol, but the same kind of anomalies appear under other rules.)

It gets even more complicated. The results cited above are for players who always choose the same die, no matter what the circumstances. But Elgee’s rules allow a player to choose a different die on each roll. Presumably, players who adapt or learn will do better than any player with a fixed strategy. I find that a very simple adaptive strategy—use 6, 6, 5, 1, 1, 1 when behind, 4, 4, 3, 3, 3, 3 when ahead, and 6, 5, 4, 3, 2, 1 when the score is even—gives mostly but uniformly good results in end-game situations.

I echo Elgee’s questions about whether this problem has been analyzed previously. As it happens, I’ve been able to find a bit of literature on the original hockey issue. Tom Benjamin’s NHL Weblog has pointers to three papers published in the 1980s in Interfaces, an operations research journal. In those papers several authors—fans of rival teams—derive a formula for the optimal time to pull the goalie. (They find that coaches almost always wait too long.)

I would have thought that Elgee’s nonstandard dice would also have been investigated before. Some years ago Bradley Efron invented a wonderful set of nontransitive dice, which Martin Gardner wrote about (Scientific American, December 1970, pp. 110–114). Gardner also had a column on various kinds of rigged and trick dice (Scientific American, November 1968, pp. 140–146). A game called Piggy has certain elements reminiscent of Elgee’s game, but those elements don’t include dice that differ in variance.

Perhaps I’ve just failed to find the right search term on Google or MathSciNet, and a reader will supply a reference.

Update: Minutes after posting the above, I discovered an article by B. De Schuymera, H. De Meyera and B. De Baetsb, “Optimal strategies for equal-sum dice games” (Discrete Applied Mathematics 154 (2006) 2565–2576), that covers some of the territory. They analyze a game in which players can choose any die whose n faces have the same sum σ. But they consider only games in which players bet independently on each throw of the dice. Under these conditions, they show that with six-sided dice summing to 21, the optimal die is the standard one, with faces marked 6, 5, 4, 3, 2, 1. Again, however, if I understand correctly, this result applies only to individual throws of the die.

Among the 250 million Rubik’s cubes manufactured since 1980, how many lie abandoned in a scrambled state, having never regained their original configuration since being taken out of the box? Most of them, I would guess. Now comes word that those cubes might be restored to pristinity with a little less effort. The upper bound on the number of moves required to solve any state of Rubik’s cube has been lowered from 27 to 26. The result is reported by Daniel Kunkle and Gene Cooperman of Northeastern University in a preprint available here.

It’s well-known that Rubik’s cube isn’t really a toy or a puzzle but rather a group-theory machine in disguise. Each possible move, or twiddle—rotating a face by some multiple of 90 degrees—is a transformation that permutes the positions and orientations of the 26 “cubies.” From any position there are just 18 distinct nontrivial moves, but in various combinations they generate a total of 43,252,003,274,489,856,000 permutations. What is the maximum number of moves needed to transform any one state of the cube into any other? That’s the question Kunkle and Cooperman are addressing. In other words, they are looking for the longest shortest path.

In principle we could get the answer by exhaustive search. It would be done by constructing the “Cayley graph” for the Rubik group: a graph in which each possible configuration of the cube is represented by a node, and two nodes x and y are connected by an edge if some single move allows configuration x to be transformed into y. The most efficient solution for any state is the shortest path (i.e., sequence of edges) leading from that state to the node representing the solved state. The worst-case solution length for the entire puzzle is the maximum of the shortest solution paths for all the nodes. The Cayley graph approach was used by Cooperman and two colleagues to find the worst-case path for the 2 × 2 × 2 version of Rubik’s cube. The Cayley graph for this device has 88,179,840 nodes, and it turns out the longest paths within it have 11 steps. For the 3 × 3 × 3 cube, however, exhaustive search is just too exhausting.

To make the search feasible, Cubists have had to scale back their ambitions and accept an upper bound rather than a true maximum. First it was shown that the worst-case solution path cannot require more than 52 moves; then the bound was lowered to 30, and then 29; a year ago Silviu Radu got the number down to 27.

Kunkle and Cooperman’s strategy is to factor the problem into two pieces by segregating half-turn (180-degree) and quarter-turn (±90-degree) moves. The subgroup of states reachable by half-turn moves is quite small by Rubik group standards, with just 663,552 elements, and the number is further reduced to only 15,752 after various symmetries are eliminated. Calculating the best solution for each of these states took only about a day on an ordinary PC. The longest such paths have 13 steps.

The second phase of the analysis tackles the “cosets” of the half-turn subgroup. For each of the 663,552 positions reachable by making half-turns only, there are 65,182,537,728,000 additional positions reachable by making quarter-turn moves. Kunkle and Cooperman had to search for the longest shortest path connecting any two elements of this set. They exploited various symmetries to reduce the scope of the problem and devised fast algorithms for some of the basic steps in the calculation. Even so, they wound up running their computer program for 63 hours on 128 processors at the San Diego Supercomputer Center. At one point the data store for intermediate results ballooned to seven terabytes. At the end of the run, they found that the longest shortest path consisted of 16 moves.

Combining the two phases of this solution yields 13 moves for the half-turn part of the path and 16 moves for the coset part, for a total of 29 moves. This is not an improvement over the best existing result of 27. However, Kunkle and Cooperman found that the two-stage algorithm reports path lengths greater than 26 only for a comparative handful of states—about 14,000. By a brute-force search they were able to find solutions of length 26 or less for each of these states, and thereby established the 26-move bound overall. It’s possible that further brute-force searching will lower the limit further to 25 moves.

Other experiments done by Herbert Kociemba, Richard Korf and others have shown that most randomly selected cube states can be solved in 18 moves or less. Korf has conjectured that all configurations are solvable in about 20 steps. We’ll see whether this is true—but probably not soon.

This is a belated update to my most recent post (which is not at all recent!). If you recall, we were discussing simple playground protocols for assigning players to teams. In one case the captains of teams A and B choose players in the order ABAB…; the alternative order is ABBA…. I presented some simulation results showing that the ABBA algorithm gives more evenly matched teams, at least for a certain range of parameters. Soon after that article appeared, my friend Leonardo Maffi wrote to say that he had re-implemented my program. His results agreed with mine in the ABAB case, but they were different for ABBA. Knowing from experience that Leonardo usually gets things right, I went looking for a bug in my code.

At this point the story gets a little twisted. It turns out that Leonardo had interpreted the problem differently and had therefore implemented a different algorithm; no surprise, then, that our results diverged. But that doesn’t mean my results were correct! On looking closely at my code I found that I had indeed made a clumsy mistake, which led to bogus output for the ABBA simulation. The ABBA protocol is still superior to ABAB, but by a smaller margin. For the record, here’s a corrected version of the table from the earlier post. I’ve also added results for the one remaining four-turn protocol, AABB.

                             discrepancy

   n        m       ABAB       ABBA       AABB     exact
   4        4        1.4        0.9        3.0       0.7
   6        8        3.3        1.7        9.0       0.9
   8       16        7.0        2.7       14.1       1.2
  10       32       14.5        5.5       33.0       1.7
  12       64       29.5        9.3       59.0       2.3
  14      128       59.7       18.7      129.0       3.6
  16      256      120.4       33.0      240.9       5.7
  18      512      242.5       66.3      513.1       8.4
  20     1024      487.7      120.0      975.2      14.2
  22     2048      979.4      240.8     2049.0
  24     4096     1966.1      442.8     3932.4
  26     8192     3944.2      889.9     8194.7
  28    16384     7909.3     1654.7    15821.0
  30    32768    15853.9     3317.9    32774.0
  32    65536    31768.5     6245.8    63554.1

And here is the corresponding graph:

A while ago I wrote about the playground ritual of choosing teams for a ball game. The simplest algorithm has two captains, A and B, who take turns choosing players until everyone is assigned to one team or the other. Call this the ABAB algorithm. Donald B. Aulenbach suggested a very easy modification that produces more closely matched teams. Aulenbach’s proposal is the ABBA algorithm, where A gets the first pick in the first round but B goes first in the second round, and they continue alternating in successive rounds. (Another way of describing the same process is that A begins with a single turn and thereafter both captains take two turns in a row.)

For a quantitative model of this process, let’s suppose each player’s ability is represented by an integer chosen uniformly at random from the interval 1 through m. We’ll let the total number of players, n, always be even, so that the two teams will be of the same size. After we have divvied up all the players, we sum the strengths of the two teams and calculate the discrepancy—the absolute value of the difference. Stephan Mertens of the the Otto von Guericke Universität in Magdeburg (who put me onto this problem in the first place) has shown that the expected discrepancy for the ABAB algorithm is m/2 × (n–1)/n; thus as n becomes large the discrepancy approaches m/2.

What about the ABBA algorithm? Here are some numerical results:

                         discrepancy

  n        m       ABAB     ABBA     exact

  4        4        1.4      0.7       0.7
  6        8        3.4      1.4       0.9
  8       16        7.0      2.3       1.2
 10       32       14.7      4.2       1.7
 12       64       29.2      7.2       2.3
 14      128       59.5     13.7       3.6
 16      256      122.4     23.9       5.7
 18      512      244.6     47.6       8.4
 20     1024      490.6     90.6      14.2
 22     2048      970.4    168.9
 24     4096     1944.9    315.7
 26     8192     3972.5    621.5
 28    16384     7907.9   1177.9
 30    32768    15892.6   2291.4
 32    65536    31877.2   4520.0

For each line of this table I ran the ABAB and ABBA algorithms on 1,000 randomly generated sets of numbers with the indicated values of n and m, then averaged the results. Up to n=20 I also found the optimum partitioning of each set, by a brute-force enumeration. The values of m are chosen so that log₂m = n/2. Most sets with these values of m and n have many perfect partitions, with discrepancy zero—but of course neither the ABAB nor the ABBA algorithm is guaranteed to find these ideal solutions.

Here are the same data in graphic form:

Clearly, ABBA is superior to ABAB, just as one might expect.

Questions:

1. What is the expected discrepancy of the ABBA algorithm, as a function of n and m?
2. Is ABBA the optimal algorithm of its type? Of course it is not the best of all algorithms; brute-force enumeration is better, at the cost of exponential computing time. There are also superior heuristics, but they cannot be implemented with a fixed sequence of choices, determined in advance. ABBA is a “blind” algorithm: It applies the same sequence of operations to all sets of data. Is there any other blind algorithm that outperforms it?
3. The uniform random distribution of abilities is probably not very realistic; a normal distribution would be more plausible. Would this make any difference in the performance of the algorithms?
4. Surely someone has worked on this problem before?

Going back to my own childhood, I don’t think the kids in my neighborhood ever discovered the ABBA algorithm. We did recognize the inherent advantage of choosing first, and we compensated by adopting a separate ritual to decide who got the first pick. In baseball, this involved a hand-over-hand struggle for a grip on the bat. Sometimes I think the preliminaries were more fun than the game.