A puzzle about splitting up numbers into groups

A puzzle from David Radcliffe: "Split {1,2,...,16} into two groups of the same size having equal sums, equal sums of squares, and equal sums of cubes."

Solution: one group is A, D, E, G, J, K, M, P; the other is B, C, E, H, I, L, N, O. (I've replaced each number with the corresponding letter of the English alphabet to obscure things a bit.)

Here's how I found this. It's often useful to look at cubes mod 9, because any cube of an integer is either a multiple of 9, one less than a multiple of 9, or one more than a multiple of 9. These cases correspond to the integer itself being a multiple of 3, one less than a multiple of 3, or one more than a multiple of 3. So 1³ + 2³ + 3³ is a multiple of 9; so are 4³ + 5³ + 6³, ..., 13³ + 14³ + 15³. Since 16³ is one more than a multiple of 9, so is the sum of the first sixteen cubes, which we'll call N.

We want to find eight integers in 1, ..., 16 that have sum of cubes equal to N/2. Now, if N is congruent to 1 mod 9, then N/2 is congruent to 5 mod 9. This means it's relatively far from a multiple of 9, so a lot of the numbers that are one more than a multiple of 9 are going to have to go into the same group. In particular, each group must contain either five more 1 mod 3 than 2 mod 3 integers, or four more 1 mod 3 than 2 mod 3 integers. Keeping in mind the limited supplies -- we only have six integers in our set congruent to 1 mod 3, and five each congruent to 0 and 2 mod 3, the only possible groups are:

≅ 0 (mod 3)	≅ 1 (mod 3)	≅ 2 (mod 3)
3	5	0
1	6	1
4	0	4
2	1	5

Furthermore we either have a group of the type given in the first row and one of the type given in the fourth row, or one of the second-row type and one of the third-row type, in order to meet the supply restrictions.

But it's not possible to have a group of the first-row type and a group of the fourth-row type. Let's consider a group of the fourth-row type -- that is, it has two multiples of three, one number that's one more than a multiple of three, and five that are one less than a multiple of three. The five that are one less than a multiple of three must be 2, 5, 8, 11, and 14. The square of each of these is one more than a multiple of three, so 2² + 5² + 8² + 11² + 14² is congruent to 2 mod 3. Call the other three members of this group x, y, and z. From the table above, two of these are multiples of 3.

But the square of every integer is either 0 mod 3 (if it's a multiple of 3) or 1 mod 3 (if it's not a multiple of 3) and so the sum of the first sixteen squares is 2 mod 3. So each group must have sum of squares congruent to 1 mod 3. The five integers that we've already put in the group have squares summing to 2 mod 3; thus x² + y² + z² is also 2 mod 3, contradicting the fact that exactly one of x, y, and z is not a multiple of 3.

So we must have groups of the type in the second row and of the type in the third row. Let's look at the group of the second-row type. It contains all six integers in {1, 2, ..., 16} congruent to 1 mod 3 -- that's 1, 4, 7, 10, 13, and 16. By symmetry the other two elements -- call them t and u -- must sum to 17. Furthermore the sum of the first 16 squares is (16)(16+1)(2×16+1)/6 = 1496; so the sums of the squares in each group must be 1496/2 = 748. 1²+4²+7²+10²+13²+16² = 591 and so we must have t² + u² = 748 - 591 = 157. So we need two integers that sum to 17, with squares summing to 157; solve the quadratic t² + (17-t)² = 157 to get t = 6 or t = 11, and correspondingly u = 11 or u = 6.

So if there's any way at all to do what we were asked, it's with one group being 1, 4, 6, 7, 10, 11, 13, 16 -- and this checks out.

Of course, it would be trivial to write a program to check this...

Turning clocks upside down

Apparently this is a puzzle blog now.

This morning at 9:30 I picked up my watch and turned it upside down. It appeared to read 4:00. The hour hand was actually in the position it would be at at 3:30, of course. But the minute hand was pointing straight up, so the time must be on the hour. Since I could easily tell that the hour hand wasn't pointing directly to the right, I suppose my brain interpreted it as 4:00 instead of 3:00. Of course I did not think any of this consciously, but only reconstructed it after the fact; my thought process was more like "hey, 9:30 upside down looks like 4:00. that's weird."

Is it ever possible to interpret the hands of a clock, turned upside-down (i. e. rotated by 180 degrees), unambiguously as a time? (Fudging like my brain apparently did this morning does not count.)

A puzzle with lights

Since I seem to be getting this question a lot lately: yes, I'm still alive! But I am writing a dissertation. (And waiting to hear back from places where I applied for jobs, but that is not an excuse because those applications are already out there.)

Here's a puzzle I heard a couple weeks ago. You have a 10-by-10 grid of lights. Some of them are on, some are off. You are allowed to make the following moves:
(a): you pick one of the lights which is the center of some 3-by-3 square (i. e. it is not on the edge of the grid) and switch all the lights in that 3-by-3 square (on becomes off, off becomes on).
(b): like in (a), but with a 5-by-5 square.

Is it possible to get from an arbitrary starting position to the all-off position?

A puzzle

2²⁹, expressed in base 10, is a nine-digit number. All nine of its digits are different. Find the digit that is missing without explicitly calculating 2²⁹. (Thanks to Kate for this one; a solution is there, so don't look until you've thought about it.)

God and some humans play dice

From Tierney Lab at the New York Times:A puzzle in which God, Einstein, and Oppenheimer play dice, and its solution.

What time is it?

I looked at my watch at 12:05. I wasn't sure, for a moment, whether it was 12:05 or 1:00; I had to carefully look to determine which of the two hands was the longer one.

A question for you: how many times in a given twelve-hour period could I have this problem? More rigorously, suppose I have an ordinary twelve-hour analog clock, with an hour hand and a minute hand but no second hand. Furthermore suppose I can measure the position of the hands absolutely precisely, and they're "sweep" hands (i. e. they move at a constant angular rate, without "ticks"). At how many times between (say) noon and midnight could I interchange the hands of the clock and still have the hands in a position that corresponds to some time -- but not the time that it actually is? Noon, for example, is not such a time; if I interchange the minute and hour hands at noon I get a valid position of the hands, but that's the position the corresponds to noon. (I won't give an example of a valid time because giving one would be a big hint.)

Bonus: what are these times?

Another bonus: Add a second hand; are there still times which give rise to ambiguous hand configurations? (I don't know the answer to this one.)

(No fair looking up a solution; this is actually a pretty well-known brainteaser. It's well-known enough that I probably knew it existed, somewhere in the back of my mind, before I reinvented it today.)

edit (1:14 pm): Boris points out that he wrote a very similar question as question 23 of this test (PDF).

Two to the sixty-fourth minus one

I noticed yesterday that the number 2⁶⁴ - 1 appears at least twice in the mathematical folklore.

The first place is in the Tower of Hanoi puzzle. This puzzle is as follows: you are given n disks, all of different sizes, with holes on them, and three posts. The disks are originally stacked on one of the posts in order of size, with the small disks on the top and the large disks on the bottom. Your job is to move the disks to one of the other posts, subject to the following constraints:
1. you can only move one disk at a time;
2. the disks on any post, at any time, must be in order of size.
This can be solved in 2ⁿ-1 moves. The solution is given by a nice recursion. To move n disks from post A to post B, first move the smallest n-1 disks from post A to post C. Then move the largest disk from post A to post B. Then move the smallest n-1 disks from post C to post B. Thus moving n disks takes twice as many moves as moving n-1 disks, plus 1. Moving a stack consisting of one disk of course takes one move; solving the recursion gives the answer.

There's a story that goes along with this. It involves some monks in some temple somewhere whose job is, basically, to do this for n = 64. When they finish the universe will end. If they can make one move per second, this takes 2⁶⁴ - 1 seconds, about six hundred billion years, which is suspiciously close to the actual expected lifespan of the universe for such a crude model...

The other place that 2⁶⁴ - 1 occurs is in the story about the invention of chess. Supposedly the ruler of the land where the inventor of chess lived really liked chess, and he offered the inventor a reward. The inventor of chess said that he wanted one grain of wheat placed on the first square of the chessboard, two on the second square, four on the third square, and so on, each square having double the number of grains of the square before. The total number of grains works out to be 2⁶⁴ - 1, which is a lot. Wikipedia has an article on this. A grain of wheat is about 50 milligrams; this works out to about 15,000 kilograms of wheat for every person who has ever lived. (I'm assuming sixty billion people have ever lived, which I have no evidence for but it's a number I've heard.) If we assume an average historical lifespan of 40 years, that's one kilogram per day per person. In other words, you could approximately feed everyone ever for their whole lives with this amount of wheat. It's a lot.

Hats, colors, and algebraic structures

Here's a game: there are a hundred people arranged in a circle. Some of them are wearing blue hats, some of them are wearing yellow hats. None of them can see the color of their hat, but everybody can see the color of everybody else's hats. Each of them in turn has to say "yellow" or "blue". What strategy can they use to ensure that the largest number of them say the color of their own hat? (And how many is that?)

Obviously the first person to speak can't be ensured of saying the color of their own hat. But everyone else can! The strategy is as follows: the first person says "yellow" if they see an even number of blue hats, and "blue" if they see an odd number of blue hats. Say they say "yellow". Then each person after that counts the number of blue hats they see. If they see an even number of blue hats, then their hat must be the same color as the first person's; if they see an odd number of blue hats, their hat must be the opposite color from the first person's. (This is reversed if the first person said "blue".) We can do no better.

The problem pretty easily generalizes to any finite number of colors of hats and finite number of people; the trick is to think of the n colors as the group Z/nZ, that is, the integers under addition modulo n. (It starts seeming very unnatural to express the strategy here in terms of colors, though.)

And it turns out -- this is a bit more surprising -- that we can always do this even when there are an infinite number of people or an infinite number of colors, or both. With an infinite set of colors and a finite number of people the key fact is that any set of colors can be given the structure of an abelian group, even if it's infinite. With an infinite number of colors and an infinite number of people things get kind of weird, and you have to endow the set of colors with a field and invoke Zorn's lemma.

This is basically a summary of Des chapeaux, des couleurs et des structures algébriques (in French, of course) by Florent Benaych-Georges, which I have translated into rather rough English for no good reason.

The elevator paradox

Saw Friday's episode of Numb3rs, which I usually skip because the mathematical content is usually laughable from my point of view. But I learned about the elevator paradox, which says that when you're at the bottom of a building, usually the first elevator which comes will be going down, but when you're at the top of a building, it'll usually be going up. The reason, according to the Wikipedia article, is:

Essentially, the explanation seems to be this: a single elevator spends most of its time in the larger section of the building, and thus is more likely to approach from that direction when the prospective elevator user arrives. An observer who remains by the elevator doors for hours or days, observing every elevator arrival, rather than only observing the first elevator to arrive, would note an equal number of elevators traveling in each direction.

But this raises an interesting question: how do we know that you'd have an equal number of elevators traveling in each direction? This is, it appears, basically by conservation of elevators. If in general more elevators go upwards than downwards past a certain point, then the number of elevators below that point will steadily decrease. Surprisingly, none of the online expositions seem to mention this. They seem to think it's obvious that the first elevator passing a point has an equal probability of going up and down. But I've spent enough time with probability to know it's ridiculously counterintuitive.

Also, should Wikipedia have mathematical proofs?, from Slashdot. I haven't thought about this; if I think of anything worth saying I'll post it here, but the link alone didn't seem worth its own post.

Scrabble, part two

After the post I made a few moments ago, I saw how to do the count.

The answer's 3,199,724, which apparently is the standard answer accepted in Google.

The method is pretty straightforward. First, find the number of "partial racks" (i. e. sets of zero to seven tiles) consisting of just A; there's one with no tiles, one with one tile, and so on up to seven tiles. (There are 9 As, so a rack full of them is possible.) Then find the number of "partial racks" containing A and B; there's one with no tiles (the empty rack), two with one tile (A and B), three with two tiles (AA, AB, BB), and three with each of three through seven tiles. (There are only two Bs.) Repeating this for each of the 27 tile types (26 letters plus the blank) gives the answer of 3199724, not far from my sampling-derived estimate of 3224068.

The solution to the triangle puzzle

Yesterday, I asked a question:

Given a scalene right triangle with sides of integer length and perimeter P, show that there is a corresponding scalene triangle with one angle which is 60 degrees and perimeter 1.5P.

For example, the 3-4-5 triangle is a right triangle with perimeter 12; the 3-7-8 triangle has a 60-degree angle (the one opposite the side of length 7) and has perimeter 18.

As promised, here's the solution.

First, how do we check that a triangle has a 60-degree angle? We use the law of cosines. When I originally did the analysis, I assumed that larger angles of a triangle had to be opposite longer sides. This is actually only guaranted to be true for triangles in which all angles are acute (in which case it follows from the law of sines). The sixty-degree angle in a scalene triangle (for those of you who don't know the word, it just means that all three sides have different lengths) must be the second largest angle. It can't be the largest angle, because then the sum of the angles would be less than 180 degrees; similarly it can't be the smallest angle, because then the sum of the angles would be greater than 180 degrees. In the following analysis I will assume that the side opposite the 60-degree angle is the second-longest side. It turns out that we can answer the problem under this assumption;

So we're looking for triples a < c < b of positive integers, with c² = a² + b² - (2 cos 60^o) ab. But cos 60^o = 1/2, so we need to find triples for which c² = a² + b² - ab. For example, the 3-7-8 triangle is one of these; we have a = 3, c = 7, b = 8, and 3² + 8² - 2(3)(8) = 7², as you can check.

To get an idea of what the correspondence might look like, I tried to figure out which triangles with 60-degree angles corresponded to the 5-12-13 and 7-24-25 right triangles. On a bit of a wild guess, I noticed that the shortest side of the 3-4-5 and 3-7-8 triangles was the same, so I assumed that the shortest side of the triangle corresponding to the 5-12-13 would be 5. The perimeter of the triangle we seek is 45, so it has sides 5, 40-b, b. Setting up the equation above, we have

(40-b)² = 5² + b² - 5b

which is actually a linear equation (the b² terms cancel), with the single solution b = 21. This gives us a 5-19-21 triangle. The same procedure applied to the 7-24-25 right triangle gives 7-37-40.

At this point I have enough data that I can try to guess what the pattern is. I remember that all primitive Pythagorean triples-- that is, triples of integers (a,b,c) such that a² + b² = c², and a, b, and c don't have a common multiple -- can be written in the form

(r² - s², 2rs, r² + s²)

for some r and s, with r > s, where r and s relatively prime and not both odd. The perimeter of this right triangle is 2rs + 2r², so I sought a corresponding triangle with a 60-degree angle and perimeter 3rs + 3r². It seems reasonable to guess that the three side lengths will be linear combinations of r², rs, and s².

In the case of the 7-24-25 triangle, we have r = 4, s = 3. Thus r² = 16, rs = 12, s² = 9. I observe that 7 = 16-9, 37 = 16 + 12 + 9, 40 = 16 + 2(12). More generally, from the general triple listed above we get

(r² - s², r² + rs + s², r² + 2rs).

It only remains to check that these three numbers sum to 3rs + 3r² -- they do -- and this triple, if we call it (a, c, b), obeys the relation c² = a² + b² - ab; it does, but I'll spare you the algebra.

I conclude by giving the primitive Pythagorean triples with hypotenuse less than 100, and their corresponding triangles with a sixty-degree angle and one and a half times the perimeter:

r	s	right-angled	60-degree
2	1	3-4-5	3-7-8
3	2	5-12-13	5-19-21
4	1	15-8-17	15-21-24
4	3	7-24-25	7-37-40
5	2	21-20-29	21-39-45
5	4	9-40-41	9-61-65
6	1	35-12-37	35-43-48
6	5	11-60-61	11-91-96
7	2	45-28-53	45-67-77
7	4	33-56-65	33-93-105
7	6	13-84-85	13-127-133
8	1	63-16-65	63-73-80
8	3	55-48-73	55-97-112
8	5	39-80-89	39-129-144
9	2	77-36-85	77-103-117
9	4	65-72-97	65-133-153

If we're given a non-primitive Pythagorean triple, it's a constant multiple of a primitive one; for example, 6-8-10 is twice 3-4-5, so we get twice 3-7-8, i. e. 6-14-16. Alternatively, the triple 8-6-10 (in that order) comes from r=3, s=1; applying the formulas above gives 8-13-15. "Blinding Insight" gives a solution that's different from mine in the comments to yesterday's post, since it's based on a different parametrization; this solution gives different, but still valid, answers.

Note that this doesn't necessarily generate the triangles with a sixty-degree angle and integer sides in "primitive" form. For example, r = 5, s = 2 gives the triple (21, 39, 45) were we might hope for (7, 13, 15). Indeed, if s-r is divisible by 3, then all three sides of the sixty-degree triple will be divisible by three. Furthermore, the perimeter of the sixty-degree triple is always divisible by three, so we'll never get (7, 13, 15) in that form.

A puzzle

Given a scalene right triangle with sides of integer length and perimeter P, show that there is a corresponding scalene triangle with one angle which is 60 degrees and perimeter 1.5P.

For example, the 3-4-5 triangle is a right triangle with perimeter 12; the 3-7-8 triangle has a 60-degree angle (the one opposite the side of length 7) and has perimeter 18.

I'll post the solution tomorrow.

(The puzzle isn't mine; it's from the puzzle column in the March/April 2007 issue of Technology Review, which I was flipping through earlier today.)

The "lights out" puzzle

Remember the puzzle Lights Out? You have a five by five array of buttons with lights under them. When you push one of the buttons, that button and its neighbors to the north, south, east, and west are toggled -- they turn on if they were off, and off if they were on. You start with some random configuration of lights, and the object is to turn them all off.

I remember being very frustrated by the physical version of this puzzle when I first encountered it, because I could never get it to work. It's easy to get most of the lights out, not surprisingly, but hard to get all of them.

It turns out there's a solution, but it's kind of frustrating in that it involves a lookup table. Basically, you look at the first row; whichever lights are on, you press the corresponding lights in the second row. Now, whichever lights are on in the second row, you press the corresponding lights in the third row, and so on. (This is known as "chasing the lights".) Now some lights in the bottom row are on. You then press some apparently randomly selected lights in the top row, according to the table, and repeat; when you get to the bottom this time, all the lights will be off.

This is very inefficient. For one thing, you can see that the order in which the lights are pressed doesn't matter (unlike, say, the Rubik's cube) -- what determines whether a light is on is just its starting position, and the parity of the number of times it and its neighbors have been pressed. Furthermore, if you press a light twice that's the same as not pressing it at all, and this solution in general leads to pressing a lot of lights twice.

In a 9-by-9 version of the puzzle, it turns out that there are only two possibilities for the final row if you do the analogous thing; either all the lights are off (and then you win) or the first, third, fifth, seventh, and ninth lights are on. Then you press the square in the upper right corner and repeat the whole procedure. It looks to me (although I don't have that many 9-by-9 examples of the puzzle, and so can't be sure) that pressing the upper left square toggles the puzzle between these two things, so there ought to be a solution of this form:
- press, or don't press, the top left square.
- proceed by the "chasing the light" method.

In either of these cases one can find a better (although not quite minimal) solution for any starting configuration, by doing the two-pass chasing-the-lights algorithm, noting which buttons one pressed, and then starting from the same original configuration, not pressing those buttons which were pressed twice the first time. For example, today's 9-by-9 lights out at logicgamesonline.com is solved in 58 moves by the crude two-pass method; it turns out that there are ten lights which are pushed on each pass, so eliminating the corresponding 20 presses, one can solve it in 38 moves. (The web site claims there's a 28-move solution, but I'm not bored enough to look for it.)
In the 5-by-5 case there are certain nice-looking patterns which don't do anything. This page describes them as being in the "null space of the adjacency matrix of Lights Out", which kind of makes sense. For more on this, see Mathworld's description of the puzzle; it turns out that the puzzle can be described as the solution of a system of 25 equations with mod 2 coefficients. What I wonder is if there is some way to find the minimal solution, or at least a solution that doesn't involve pressing the same button twice (we might call this an "efficient" solution), that doesn't require actually solving the system of equations, but can be done "by inspection". I suspect there isn't, but I may be wrong.

links for 14 August

The "is the new" diagram attempts to document all instances of "X is the new Y", which is a fairly common phrase, with an arrow from X to Y. Not surprisingly, the node of highest indegree appears to be "black". You can try to make a partial order here, assuming that if X is the new Y and Y is the new Z, then X is the new Z; for example, local is the new kosher (local is the new organic, organic is the new kosher) -- but there aren't any really large components in this graph. It seems like most of the time, when people say "X is the new Y", nobody has ever made a statement "X is the new Z" or "W is the new Y" before. It's interesting to see if you can get why these things are true -- why is Ohio the new Florida? gadget bag the new man purse? individuality the new conformity? And isn't this last one impossible by definition? Is it really individuality if everyone's doing it? (Via information aesthetics.) It would be interesting to see how this network evolves with time; eventually people will start talking about things that have already been talked about and larger components will start to emerge.

[edit, 9:18 am: a particularly perplexing entry here is "Canada is the new Estonia". If you google this phrase, you get a lot of confused people, but eventually you find the beginning of a New York Times article from 2005, which says "America's next top model? she's [sic] likely from canada.Canada is the new Estonia - at least when it comes to modeling." I didn't realize Estonia was the old Estonia.]
Bad countries come with long names, from Social Science++, via Language Log. The theory is that a country with a good-sounding name like "Great Socialist People's Libyan Arab Jamahiriya" or "Democratic People's Republic of Korea" probably has something to hide; it seems to be borne out, although the United Kingdom of Great Britain and Northern Ireland would probably disagree. This is related to a pet theory of mine that restaurants advertising "authentic X cuisine" probably have something very far from authentic X cuisine. If you really were a democratic country, or you really served authentic food, you wouldn't go to the trouble of advertising it; building up a reputation would be enough. (But how is reputation built? This is a question I wouldn't mind studying from a mathematical perspective.)

Atle Selberg died, from Terence Tao; a mathematical obituary. Selberg and Erdos produced the first elementary proof of the prime number theorem; the story goes that Erdos got the lion's share of the credit, to the point where someone walked up to Selberg (not knowing that it was him) and said "did you hear that Erdos and some Scandinavian came up with an elementary proof of the Prime Number Theorem?" Then again, that seems like the sort of thing Erdos himself might have done; supposedly late in life he forgot who people were, even the people he collaborated with often.

The Quant Bloodbath, at Secret Blogging Seminar: how will the current crisis on Wall Street affect the job market for quants? Will Wall Street decide it doesn't need mathematicians after all (because the quantitative models don't seem to be working), or will it decide that it needs more mathematicians to make better quantitative models?

Ken Jennings (yes, that Ken Jennings) writes about Pic-Tac-Toe puzzles, in which nine images are arranged in a three-by-three grid, and the images in each of the three rows, three columns, and two diagonals have a common theme. An alternative is if you're given eight of them and you have to fill in the ninth; see this example from the 2003 MIT Mystery Hunt.

Science after Sunclipse has launched MathSciJournalWiki, which is what it sounds like -- a freely editable source of information about scientific journals. Also of interest is Scientific Publishing: A Mathematician's Viewpoint, by Joan Birman, from the July 2000 issue of the Notices of the AMS.

Yesterday I wrote about men having more sex than women?; over at Statistical Modeling, Causal Inference, and Social Science they're going on about the inaccuracies of the NYT article I mentioned there, which conflates the mean and the median. Not surprising, since they're statisticians over there; I still think that people lying about their sexual activities is the big thing, though.

13th roots and Rubik's cube

In the comments here a few days ago, commenter Michael S. pointed to this article telling us that the record for finding the 13th root of a 200-digit number has been broken by Alexis Lemaire. It is mentioned that the record for the 13th root of a 100-digit number was 23 minutes in 1970, and now Lemaire can do it in under four seconds. This seems a bit suspicious to me, because it seems like it would take more than four seconds just to read the problem and write down the answer, but presumably it's legitimate. I found what looks like a set of rules here.

What I'm curious about is how much of this improvement is an improvement in the existing methods, and how much of it is coming up with new methods. I suspect that some part of the method takes advantage of certain strange properties that only someone who was looking really hard could find. For example, in the case of cube roots it turns out that the cubes of 0, 1, 2, ..., 9 each end with a different digit (0, 1, 8, 7, 4, 5, 6, 3, 2, 9). So if, for example, you have a number that you know is a perfect cube and it ends in 3, it must be the cube of something that ends in 7. There's a similar trick for fifth roots -- n⁵ and n always end in the same digit.

From what I can gather the methods for the 13th root are a little less ad hoc; at least one person's method basically works by taking the logarithm of the 100-digit number and dividing it by thirteen to get the most significant digits of the 13th root of a 100-digit number; then looking at the last few digits of the 100-digit number gives you the last few digits of its 13th root. One occasionally sees large numbers given in this way, where the first few digits can be found by logarithms, the last few digits by modular arithmetic, but the middle is a lot harder to compute. I can't find descriptions of the method which these mental calculators use for finding 13th roots of 200-digit numbers; one might expect it to be similar, but it doesn't necessarily have to be.

An analogy comes to mind with solving the Rubik's cube. There are people who can solve it very quickly. But there are two metrics for the speed of solving it -- how many "moves" do you have to make to get it back to the starting position, and how many seconds does that take? The first of these is the more mathematically interesting question. A simple combinatorial argument says that there must be positions which are 18 moves from the initial position. The number of positions the Rubik's cube can take is (8! × 38) (12! × 2¹²)/12 = 43,252,003,274,489,856,000. To see this, note that to specify a position of the Rubik's cube, one must specify:

• the positions of the eight corner pieces, in 8! ways


• how each of these is "twisted", in 3⁸ ways


• the positions of the twelve edge pieces, in 12! ways


• how each of these is "flipped", in 2¹² ways

and the factor of 12 arises because it turns out not to be possible to get every possible combination of flips and twists. (Douglas Hofstadter referred to these as "conservation laws" in one of his Metamagical Themas columns, because they reminded him of certain laws about conservation of spin or color in particle physics.) Now, let's say you're randomly scrambling a Rubik's cube. There are twelve "moves" you can make from the initial position -- you can twist each of the six faces in either direction. After that, at each juncture there are eleven moves you can make -- it would be redundant to turn a face clockwise and then counterclockwise on the next move. So the number of positions that you can reach in exactly n moves is 12 × 11ⁿ; summing these up for 1, 2, ..., 17 gives a number which is less than the number of possible positions of the Rubik's cube. So there are positions which are at least 18 moves from the start. It turns out that there are positions that need 26 such moves ("quarter turns"), and an algorithm is known that can solve any position of the Rubik's cube in 35 quarter turns; see this Wikipedia article, or this paper for an idea of the methods. (They use a different metric, in which turning a face by 180 degrees counts as one move, not two; this lets one replace 18, 26 and 35 above by 15, 20 and 26.)

But the people that solve the cube very quickly are interested in the actual amount of time, which means first that they would not want a method that required lots of standing around thinking, and second that there are considerations of manual dexterity that just don't come into play if you're trying to minimize the number of moves. You can imagine a Rubik's cube competition where people are challenged to unscramble the cube in a minimal number of moves, as opposed to the smallest amount of time; however it would be a much different game.

Unfortunately, the analogy to the 13th-root problem breaks down. That's because in the Rubik's cube case, you can see what the players are doing. So it's possible to count the number of moves they make. You can't count the number of elementary arithmetic operations that someone does in their head when trying to extract a 13th root, and furthermore there seems to be an element of synaesthesia in some of their calculations, so hat they see as an elementary arithmetic operation might not be how a "normal" person would define it. What model of computation one uses is tremendously important here.

Greater-Than Sudoku

(I apologize if this post is giving you trouble when you read it; for some reason Blogger doesn't seem to like the large numbers of inequality signs in this post.)

A sort of puzzle that I find incredibly frustrating is the "Greater-Than Sudoku".

This is like Sudoku, except that none of the numbers are given. But greater-than or less-than sign indicate which of any two adjacent squares contains the greater number. (The adjacencies are only within the 3-by-3 squares that make up the larger 9-by-9 square, so there's no possiblity that these could be equal.)

An example can be found about halfway down at Ed Pegg Jr's column, "Sudoku Variations", which appears to be part of his approximately monthly column Math Games at MAA Online. Not surprisingly, this gives a wide variety of Sudoku variations. Personally I prefer the variant called "Sums Sudoku", in which the 9-by-9 grid is broken up into regions containing a few cells and the sum of the numbers in each of these is given. I went through a whole book of those last summer. They were fun.

There's a greater-than sudoku in the July 26 issue of the Philadelphia City Paper, by Matt Jones, the author of "Psycho Sudoku", who believe it or not is not the guy behind Jonesin' crosswords, which that paper also includes. (Jonesin' crosswords are by Matt Gaffney.) You can find a whole bunch of Jones' variant Sudokus at the Boston Phoenix. These include Greater-Than Sudoku, Sum Sudoku, Stepping-Stone Sudoku, and Kaidoku, which really has nothing to do with Sudoku (it's a word puzzle) but has a similar-sounding name. The reason I like the first three of these is because they require more mathematical thinking than the standard Sudoku, which is exactly the reason that most people probably like them less. I have often found things explaining Sudoku to people who haven't seen it yet that say "it doesn't involve any math, just logic" -- and that's true, at least with the common understanding of those words.

The problem with not being given any numbers, as in the Greater-Than Sudoku, is that there's nowhere, really, to start. The way I've usually started these puzzles is as follows: the number 9 must be in a square that contains a number greater than that in each of the adjacent squares. That allows one to rule out most squares from containing 9; if you're lucky, it rules out enough squares that, combining this with the rule that there is exactly one 9 in each row, column, and 3-by-3 square, you know where all the 9's are. Replacing "greater than" with "less than", you can determine where the 1's go. Next, the 8's can be placed -- they must be in squares that are greater than everything adajcent to them, except they could be less than an adjacent 9. This seems to lead to more possible places where 8's can go, in general, than 9's, so the "ruling out" is harder. By symmetry, one can do the same thing with the 2's. My theory is that if I could follow this far enough, I would have enough numbers that I could solve basically like a regular Sudoku puzzle; unfortunately this doesn't seem to work. (And even when it does seem to be working, it requires scratch paper -- it gets too messy to fit all the notes I want to make in the squares -- which just feels wrong for a newspaper puzzle.)

Another method that has occurred to me is to try to determine what range the number in each square falls in. For example, consider the bottom-left 3-by-3 square in the Greater-Than Sudoku in Ed Pegg's article. It has

A > B < C
v   ^   v
D < E < F
v   v   v 
G < H > I

where v and ^ are meant to be downward-pointing and upward-pointing analogs of < and >, and A, B, ..., I are 1, 2, ..., 9 in some order. We have, of course, the twelve inequalities that are given explicitly: B<A, B<C, D<A, B<E, F<C, D<E, E<F, G<D, H<E, I<F, G<H, I<H. These specify a partial order of A, ..., I (for those who don't know what this means: it just means that we know some of them are larger than others, and that if x is larger than y and y is larger than z, then x is larger than z); what we want to do is extend this to a total order. If we knew, for example, that G<D<E<F<C<B<H<I<A (incidentally, this isn't true), then we'd have G = 1, D = 2, E = 3, ..., A = 9.

Since the relation "less than" is transitive, we end up with various "chains" of inequalities, the longest of which is G<D<E<F<C. We also know that G<A (since G<D and D<A). Finally, G is less than H, and we can't compare G with B or I. So there are six numbers greater than G; thus G is at most 3. I suspect that doing this sort of reasoning for each square would help.

However, the twelve comparison signs in any 3-by-3 square are not themselves enough to specify how the numbers 1, ..., 9 are arranged. There are only 2¹² = 4096 ways we can set them up, and 9! = 362880 ways to arrange the integers 1, ..., 9 in those boxes; on average, if we arrange the < and > signs randomly, there will be 9!/2¹² = 88.59375 ways to fill in the numbers 1 through 9 in that square which are consistent with that choice of inequality signs. And it is clearly possible for there to be many less. For example, we can never have a square with

A > B
^   v
D < E

(the rest being irrelevant), since we have A<D<E<B<A and thus A<A. Thus, to offset this, in some cases there will be many more; we need the Sudoku constraints to help fit things together. The total number of Sudoku puzzles is widely reported to be 6,670,903,752,021,072,936,960 (see Russell and Jarvis, which also gives a nice heuristic that gets very close); this is about 2⁷², so it's at least plausible that the 108 comparison signs in a 9-by-9 Greater-Than Sudoku give enough information to specify a unique solution.