How puzzling influenced me

My ghost of internet past

Dear readers, what was your first introduction to the internet?

I'm part of the "millenial" generation, which means I grew up with the internet.  Well, sort of--I didn't actually pay the internet any attention until high school.  The point is, I had internet at such a time that it was important to the development of my identity.

But my introduction to the internet was not through blogs or forums or anything like that.  My introduction was through a small puzzle website called Perplexus.  Surprisingly, the website is still alive after 10 years, with not much changed. Perplexus publishes daily word problems, much like the puzzles that I occasionally publish on this blog (no coincidence there).  The content is user-submitted, and also selected by higher-ranking members.  I wrote over seventy puzzles over the course of three or four years.

I think I've mentioned Perplexus a few times in the past, but never by name or in detail.  I think I've been embarrassed, as I always feel embarrassed by old internet activity.  What an awkward dork past-me was!  I probably said such stupid things!  Not that I remember anything stupid in particular.

But I do remember things.  I remember learning a bit of html code, because some parts of the site require it to make links or line breaks.  I remember learning about combinatorics, the mathematics of counting.  I remember learning modular arithmetic.  I remember arguing about the urn problem, the 1.99999... = 2 problem, and the envelope paradox.  I remember learning about Raymond Smullyan and Martin Gardner.

Some of my memories also demonstrate how Perplexus dominated my internet world.  I learned all the ins and outs of the ranking system, and the complicated queue system for submitted puzzles.  The queue itself seemed like a puzzle to me.  I dug through the forum archives once, because I was interested in the social history of the site.  I read about a kid who was once caught sockpuppeting, on a puzzle website of all places.  That fascinated me, though I did not think it strange.

I looked at the webpages of regulars who had them.  There was a guy who it seemed could solve every puzzle very quickly, and who frequently irritated other members by solving it with a computer.  I respected him a lot.  His personal webpage had a series of essays about why he left Catholicism.  Some time later, I left Catholicism, though I think that's something I would have done anyway.

I do this for fun

At the time I had this philosophy.  Doing puzzles was a thing I did for fun.  Because it was an intellectual activity, I knew that some people might think of it as a useful, virtuous activity, like exercising.  But I rejected that idea, and insisted I was doing it for fun, not to learn things.

Did my philosophy stand the test of time?  Did solving puzzles impact my later life?  I often doubt that it had much effect.  Some stuff I learned was just useless.  Like Polya theory, what's that good for?  Or the method to solve lines-through-points puzzles?  Or coin-weighing puzzles?

But when I describe my life, it seems obvious that puzzles did have an impact.  I still have a fondness for shapes, as you might have noticed.  I still like to joke about set theory.  And it affected my career too.  Because of my problem-solving skills, I always had an easy time in math and physics courses.  I used to joke that I majored in physics because it was the easiest subject, and that was really true for me.  After undergraduate, problems are much more open-ended and un-puzzle-like.  But the skills still transfer over.

On this blog, I also consider issues that are more open-ended and un-puzzle-like.  And yet my approach tends to be the same approach I have to puzzles, if that makes any sense.  A puzzle is not about the answer;  If it were about the answer, then you could just look up the answer and be satisfied.  A puzzle is about the process.  It's about the challenge.  It's about the little mathematical tidbits we learn along the way.

Most importantly, it's about fun.

In praise of non-deductive puzzles

It's a convention in many logic puzzles that there is only one solution, and you reach this solution by deductive steps.  But there are a few logic puzzles that are not entirely deductive.

I hope readers don't mind that I spoiled one of Nikoli's sample puzzles.

One of the classics is Numberlink.  In Numberlink, you're supposed to draw lines between each pair of identical numbers.  There is always a unique solution, and this solution just so happens to use every square.*  But even though there is a unique solution, you're not supposed to solve the puzzles by deduction.  You have to use a lot of guessing and intuition, or it would be too difficult.  MellowMelon has a guide on how to solve them.

*If you ever download a Numberlink app for a mobile device, they often require that every square must be used, rather than having a unique solution that just so happens to use every square.  I consider this a serious travesty, and do not recommend Numberlink apps.

I would like to contrast this with a lot of puzzle apps out there which do not have unique solutions (eg see this review).  Usually this isn't because they've been designed as non-deductive puzzles, but because the programmers couldn't be bothered to check for unique solutions.  This is the worst.

This was a randomly generated puzzle from Tatham's puzzle collection.

Moving away from pencil-and-paper puzzles, there is a game called Blackbox.  It can be played with two people, but it's really better to play against a computer.  In Blackbox, there are some balls in a box, and you're supposed to figure out their positions by shooting some lasers into the box.  You can't tell what the lasers do inside the box, but you can tell where they come out, if they come out.  There's a lot of room for deduction here, though solutions aren't unique.  But it's really more fun to try to figure it out based on the smallest number of laser beams.  Since you decide where to shoot the lasers, it tastes a bit like experimental science.

You can play Blackbox within Simon Tatham's puzzle collection, which has free mobile app versions.  I also recommend Eric Solomon's hexagonal variant.

Lastly, I'll mention a card game I just bought called Hanabi.  Have you ever seen those logic puzzles where people wear colored hats, and can only see the colors that other people are wearing?  Or perhaps the puzzle of the three foolish/wise men who wake up with marker on their faces?  Hanabi is sort of like that, because each player holds their hand backwards, so that only the other players can see.  Players cooperate by giving each other hints to play the right cards in the right order.

But while the colored hats puzzles are deductive, Hanabi is not because you can't be sure that everyone is playing perfectly (and no one knows what that would even look like).  Furthermore, there's never quite enough information to play deductively!  It's a lot of fun.

In conclusion, there is plenty of interesting puzzle-space to explore beyond deduction.

2013 US Puzzle Championship

Every year I plug the US Puzzle Championship, which occurs on June 15th this year.  You print out a pdf full of logic puzzles, solve them, and input the solutions online.  Go register now!  I need more competition.

This marks the ninth time I've participated.  Persistence paid off, because last year was when I finally broke into the top 25.  I got some sort of prize, but through a real-life comedy of errors, I haven't actually seen the prize yet (but I will soon!).

US Puzzle championship

Every year, I plug the US Puzzle Championship.  It's occurring this Saturday, 1PM ET.  It's a fun activity if you enjoy puzzles, especially the kind that appears on Nikoli, or A Cleverly-Titled Logic Puzzle Blog.

I'm excited because, according to a linear regression of my previous rankings, this year my expected ranking is 6.  I will finally complete one of my life goals: to rank under 25.  But that's not as exciting as 2013, when I will rank at -9, better than the best.  Yessssss

Question First vs Answer First

Among the interests represented on my blog, puzzles are the oldest.  Writing puzzles used to be a hobby of mine back in high school, when I'd write and submit puzzles to a website.  Naturally, the website was full of expert puzzle solvers, so that explains why I am unable to write a puzzle of reasonable difficulty.

In high school, I had a half-baked philosophy of puzzle-writing.  There are essentially two ways to write a puzzle: Question First, or Answer First.

In the Answer First method, first you think up a clever idea.  And then you try to design a puzzle such that the clever idea is the answer.  For example, a folk remedy for hiccups is to scare someone.  So there's a classic riddle based on this idea:

A man walks into a bar and asks for a glass of water.  The bartender pulls out a gun, and the man thanks her.  What happened?

I've also written Answer First puzzles of my own.  "Fast Clock, Slow Clock" is an unambiguous example, as is "Guess the Meaning".  You can usually recognize Answer First puzzles by their clever "Aha!" solutions.  All riddles are Answer First puzzles.

In the Question First method, first you think of an interesting problem.  And then you check to see if there's an interesting solution to it.  For example, a recent puzzle, "Tower of Hanoi Variant" is clearly a Question First puzzle.  I was inspired by a problem posed in the game of Freecell; I only tried to find a solution after the fact.

The Answer First method requires quite a bit of creative insight to use, but the Question First method has its own difficulties.  When you find an interesting question, there is no guarantee that there is a solution, or that the solution is interesting.  And a lot of times, you don't want to just think up one interesting question, you want to think up a whole set of interesting questions.  And then you have to look at all of those questions, and see which one has the most interesting answer.

For example, in "Ten Rows of Three", I asked solvers to arrange nine dots into ten rows of three.  But I could just as easily ask solvers to arrange X dots into Y rows of Z.  What values of X, Y, and Z lead to the most interesting puzzle?

So not only do I need to find a solution without any hints, or even a guarantee that a solution exists, as a puzzle-writer I also have to solve a much larger set of puzzles than the puzzle-solver.  This is my secret to being good at puzzle-solving.  Write lots of puzzles and then you will become very good at solving them.

But I am not sure that the Question First vs Answer First dichotomy applies to all puzzles (that's why I say the philosophy is half-baked).  For example, where does Fillomino fit in?  Designing one of these puzzles involves filling more and more clues in, while trying to see what deductions you can make from those clues.  But often, the clues we fill in are decided by something that the designer wants in the solution.  Depending on the puzzle-designer, it could be more Question First or more Answer First.

My inner skeptic wanted to write a comparison between the Question/Answer First methods of puzzle-writing and the experimental/theoretical methods of science.  But my inner skeptic's inner skeptic said that this is ridiculous.

Two puzzle competitions

Every year I plug the US Puzzle Championship, which this year happens on August 27th.  What happens is I print out the puzzles, doodle on them with colored pencils, and type numbers and letters into an online form.  It's fun!  Register ahead of time, ie now.

You should also try all these fillomino puzzles.  The puzzles are part of a different sort of competition where you're the judge.  You vote on your four favorite puzzles, using any criterion.  Vote for mine!  (I'm not allowed to say which one it is.)

US Puzzle Championship 2010

The US Puzzle Championship is an annual puzzle-solving competition conducted online. Typically, most puzzles are grid-based logic puzzles, like Battleships and Sudoku variants.

The test occurs on Saturday, August 21, 1 PM EDT.  You have two and a half hours to solve as many problems as possible.  The recommended way to do it is to print out all puzzles, and solve them on paper, then input the answers online.  Go register now.

Over the many years I've participated, my rankings have gradually improved.  But this year I have scheduling conflicts and I can't compete.  I'll be sure to solve all the puzzles on my own time anyway.

Martin Gardner passed away

I just got word that Martin Gardner passed away.  This is a sad day.  Martin Gardner was something of a hero to me.

Mind you, I never knew much about the man himself.  I was only familiar with Martin Gardner's works.

I've been a puzzle enthusiast for a long time, since high school if not earlier.  You do not get to be a serious puzzle enthusiast without hearing about Martin Gardner.  For decades, Martin Gardner wrote a column in Scientific American called "Mathematical Games".  And though he stopped writing the column before I was born, he made enormous contributions to puzzling and recreational mathematics.

Case in point, the puzzle I posted earlier today is credited to Martin Gardner.  This was a complete coincidence, but it is not a surprising one, because a significant number of the "classic" puzzles were at some point collected and popularized by Martin Gardner.

If that weren't enough, Martin Gardner is also considered one of the earliest skeptical writers, in the sense of the modern skeptical movement.  He wrote a book called Fads and Fallacies in the Name of Science, which sounds like a very typical introduction to scientific skepticism, much like others written by Carl Sagan, James Randi, and Michael Shermer.  But this book was written in 1952!  CSICOP (Committee for the Scientific Investigation of Claims of the Paranormal) didn't even exist until 1976.  In fact, Martin Gardner was a founding member of CSICOP too.

Finally, there is one more way in which Martin Gardner is important to me.  I must admit that I've only read one book by him, but in retrospect it seems significant.  I read Relativity Simply Explained back in high school, before I started majoring in physics.  It was the first sensible description of Relativity I had ever seen.  I would not be surprised if this book was part of what motivated me to go into physics.

So perhaps now you've figured my blog out.  I talk about so many different things, but the unifying theme seems to be, "Areas of discussion that are indebted to Martin Gardner."  Thank you, Martin Gardner.

Google Puzzle Championship 2009

Some of my readers are puzzle enthusiasts, correct? You should register for the 2009 US Google Puzzle Championship. The championship occurs on Saturday, June 20, from 1:00-3:30 PM EDT. You must register before this Thursday, June 18.

You take the test from home. You just print out all the puzzles, solve them on paper, and then submit your answers online. Typical puzzles include Sudoku, Arrow ring, Battleships, and all sorts of other "grid" puzzles. But there's also a "spot the difference" puzzle every year. You can look at last year's test to get a better idea.

My tips: Try the practice test first. Use colored pencils. Don't expect to win. I never get close. Do it just for fun.

Tell us if you're participating!

Infamous bricks and wishful thinking

Some examples of wishful thinking are harmful, some are harmless. One example that is probably completely harmless: people who insist that it must be possible to solve the Infamous Brick Puzzle. This is a puzzle I posted over a year ago. You should take a look at the comments--they're quite entertaining at times.
The goal of the Infamous Brick Puzzle (as I call it) is to draw a continuous curve that goes through each of the sixteen line segments in the above diagram exactly once. The Infamous Brick Puzzle is impossible--that's why it's infamous.

Though it's only a harmless delusion, I find that it still aggravates me! It annoys me because it demonstrates how easily people can fool themselves, and simultaneously demonstrates how bad people are at math.

Of course, I may be a bit biased here, because I think the Brick Puzzle is just the easiest thing ever. Surely, it should be obvious that we should check parity considerations first! But upon further thought, I suppose most people wouldn't even know what I mean by that.

Part of the reason the Brick Puzzle fools people so easily is because it foils expectations. To demonstrate, let's take a look at this optical illusion.

They sure look crooked, but because I already told you it's an optical illusion, you know they're really parallel. This is called the Zollner illusion! If you check it carefully, you'll find that they are actually parallel.

Did anyone try checking it? If you did, you'd find that I was lying--they really aren't parallel at all. If you were fooled, you can't blame your eyes this time! You were fooled because of the context. You were told it was an optical illusion, so you naturally expected that whatever you plainly saw was only an illusion.

Similarly, if someone gives you a puzzle, you naturally expect there to be a solution. If you can't find the solution, it's probably because there's some kind of special trick to it. It is a classic puzzle after all, so it must be really clever. The one trick you do not expect is that there is no solution after all. That wouldn't be clever at all, would it?

Another thing is that the Brick Puzzle is typically presented by a teacher to his or her (often very young) students. The teacher promises that there is in fact a solution, and that she'll award fifty dollars to the first student to solve it. Well, the teacher wouldn't dare give us a puzzle with a stupid answer like "It's actually impossible", would he/she? We have greater faith in authority than that. Besides, if we try to look for a solution, we have nothing to lose and fifty bucks to gain. If we try to prove it's impossible, there's nothing to lose or gain (Pascal's wager all over again). Hope springs eternal.

There are a lot of rumors floating around which say the puzzle is possible. Some of it comes from people who like to keep the legend alive. It's pretty funny, in an evil maniacal laughter sort of way. Other times, these rumors originate because a person thinks he's found a solution, but hasn't checked it over thoroughly enough. When that person comes back to the puzzle, he discovers that he can't find a solution anymore. He attributes this to a failure of memory rather than a failure to count the number of line-crossings.

Another interesting thing that happens, is that I get all sorts of "creative" solutions. People seem to prefer a trick solution to a non-solution. Just fold the paper! Use a thick marker! Draw a line incidental with the edge of a brick!

These "creative" solutions exploit loopholes in the puzzle. People seem to think that those loopholes were intentionally placed there by the puzzle's author. Sometimes that is true, but let me tell you a little something about writing word puzzles. It is very difficult to close every loophole! I've found that if people are desperate enough to solve a puzzle, they find all sorts of loopholes, real or imagined. And if I try to close them all, I might end up with a very clunky and verbose presentation. We puzzle-writers are not gods! We are not perfect! Even classic puzzles are frequently imperfect (the ur-example being the -gry puzzle).

I don't mean to say that I'm annoyed when people keep on coming up with loopholes in my puzzles. Loopholes are fun to look for, after all. But sometimes people just use loopholes as an excuse to give up. Anyways, an impossibility proof is just as clever as any of those! Don't people appreciate a good mathematical proof?

Why I don't like sudoku

Because I am a puzzle enthusiast, many a person has naturally assumed that I am also a sudoku enthusiast. Not so. Sure, sudoku is a puzzle of sorts, but I have standards. I am somewhat picky about puzzles, in fact. It is a consequence of seeing so many of them--I have a fairly good conception of what constitutes a "good" puzzle and a "bad" puzzle.

Have I ever told the story about why I dislike Mensa? I was once deeply unimpressed by a set of puzzles that they had published... Deeply unimpressed. But I digress.

As for sudoku, sudoku has no soul.

Forgive me. I forgot to explain what sudoku is. It's an enormously popular puzzle that has been replacing crossword puzzles in newspapers everywhere. It looks like this:

You must fill each of the blank squares with a digit 1 through 9 such that no column, row, or 3x3 square contains two of the same digit. (This one was taken from Wikipedia)

As I was saying, sudoku has no soul. Okay, I'll concede that it has a soul, but only one, and it's fragmented among all of the many many sudoku puzzles that have ever been created. Sudoku is the Lord Voldemort of puzzles.

The sudoku puzzle is one of those puzzles that is easily manufactured. There's software out there that can simply create these puzzles with no real human input. Just tell the computer what difficulty you want, and it will generate a brand new puzzle with different numbers filled in the squares. It's sort of like those factory-made hamburgers that everyone loves to hate (but in practice are very popular). If you like human ingenuity in your puzzles, you won't find it in sudoku. Even if you have one of those hand-made sudoku puzzles, it's only marginally better. The point is that it could have been made by a computer.

To solve pretty much any sudoku puzzle, you just have to learn three or four elementary steps. The rest of the puzzle is just learning to use them more efficiently. Learning to do it more quickly. But never, in all the sudoku puzzles you ever see, will you ever encounter anything truly different. It's always the same. Not exactly the same, but the same on some level of abstraction. I don't like crossword puzzles either, but at least they have new trivia questions every day.

It's sort of like giving a daily Rubik's cube puzzle. There are only a few tricks you have to learn to solve any Rubik's cube arrangement. Thus, one Rubik's cube arrangement is about the same as any other. The Rubik's cube cannot be a daily puzzle, because it is only one puzzle, not many. Likewise, sudoku is only one puzzle, with one soul. Its soul is fragmented once more every time a computer produces another sudoku puzzle.

As far as puzzles with fragmented souls go, sudoku isn't even a particularly interesting one. Yes, there are a whole bunch of other pencil-grid puzzles, each with different rules. The Japanese puzzle magazine Nikoli has created and popularized many of these puzzles. There are also a bunch of examples here, and more unusual examples here. Yes, I have lots of sites like these bookmarked, because for all my griping, I still like to do these puzzles on occasion. But not sudoku; I skip over those. Sudoku has got to be the most boring of them all. Most of the ones besides sudoku require more than 4 different elementary steps, or at least more interesting elementary steps. Some of the more difficult puzzles even require that you look at the puzzle hollistically rather than using elementary steps.

The general population has managed to pick out the driest puzzle of the bunch. For some reason, I do not think this is a coincidence.

Monochromatic triangles in multi-colored planes

My earlier puzzle "A painted plane II" asked the following question:

Let's say I've painted each point on an infinite, continuous plane. Each point is either painted red or blue. Prove that there must exist three points of the same color which form the corners of an equilateral triangle.

I did not invent this puzzle. I took it from one of the many sources in my memory. However, the second question was my invention. This is one of those puzzles that just begs to be modified and generalized, so it was just a matter of finding a variation that was still reasonably challenging.

The most obvious way to vary the problem is by adding more colors. Is it possible to prove it for three colors? Four? Must there always exist a monochromatic triangle (meaning an equilateral triangle whose corners are all the same color), no matter how many colors we have?

I've long wondered about this variation, but I've found it too difficult. It is tempting to give up. After all, the mathematical ocean is a large place, and even trained professionals cannot do more than find a few pretty shells on the shore. But I did find a solution! It turns out that you can always find a monochromatic triangle, as long as there are a finite number of colors. The proof follows.

The key is to reduce the number of colors, one by one. Given n colors, we prove that there must exist a set of points which only use n-1 colors. Within that set, there is a subset which only uses n-2 colors. Another subset of that only uses n-3 colors. We keep going until finally we're left with a set of three points--an equilateral triangle--which must use exactly one color. That's the monochromatic triangle we were looking for.

To see how we might reduce the number of colors, let's first try reducing the number of colors from 2 to 1.
All we need to do is find three points (in this case, red, but they could be blue too) all in a row such that they are evenly spaced. If we assume there are no monochromatic triangles, we can deduce that the upper three points are not red, and therefore blue. Those three blue points form a monochromatic triangle, which contradicts our original assumption.

Let's generalize a bit more, reducing from n colors to n-1 colors.
All we need to do is find X number of points, all of the same color, all in a row, and all evenly spaced. Here, we found a row of blue points, but we could have used any of the n colors. Here, X is 7, but it could have been any number. Assuming there are no monochromatic triangles, there are a bunch of points (shown in black) that cannot be blue. In other words, there exists triangle-shaped set of points which is made up of no more than n-1 colors. Hopefully we have enough space to further reduce the number of colors to n-2, then n-3, and so on until we have only one color left. This last color will form a monochromatic triangle.

But what if we don't have enough space to reduce down to one color? We simply choose X to be larger!

This proof assumes that we can find X evenly spaced points in a row and of the same color. It assumes that this is true, no matter how large X is. How do we know this is the case?

Lucky for us, mathematicians have already proven that this is the case. It is called van der Waerden's Theorem. Van der Waerden's Theorem states that for any natural numbers r and k, there exists a number n(r,k) for which the following is true: If we paint each of the natural numbers from 1 to n(r,k), using no more than r different colors, then there must exist a monochromatic arithmetic sequence of length k. That's exactly what we need! (For an incomplete proof of the theorem, see Wikipedia.)

If we have two colors, we only have to look at n(2,3) points in a row, and we're guaranteed to find a row of three evenly spaced points all of the same color. If we have two colors, we need to find a monochromatic row that is longer than n(2,3) so that we're guaranteed to have enough room to reduce down to a single color. To find a monochromatic row of n(2,3)+1 points, we need to look at a row of n(3,n(2,3)+1) to be guaranteed to find one. If we have four colors, we need to look at a row of length n(4,n(3,n(2,3)+1)+1).

The caution is that though van der Waerdan's theorem tells us that n(r,k) exists, it doesn't tell us what precisely n(r,k) is. Mathematicians only have an upper bound for n(r,k). The best current upper bound was found by Timothy Gowers.*

[Here, V(r,k) just means the same as n(r,k)]

The actual value of n(2,3) is known to be 9, but the formula above gives us a number so large that I don't even have the tools to calculate it. I don't know how much n(3,n(2,3)+1) is, but it's probably extremely large. But luckily we're on an infinite continuous plane, so we can have as many points in as small a space as we like.

Did I forget something? Oh, yeah: QED

*see "A new proof of Szemerédi's theorem"

M24 puzzle solved

Remember that Scientific American article about some new permutation puzzles based on simple sporadic groups? There was the M12 puzzle (for which I gave a few hints), along with the M24 puzzle and dotto puzzle. The last two puzzles I described as "ridiculously complicated", but it seems that someone out there has gone and solved the M24 puzzle. You can congratulate Baumann Eduard.

See his solution here
You will also need this table

That's really amazing.


In other news, it was recently proven that at most, 22 moves are required to solve any Rubik's cube. Positions are known that require 20 moves, so we now know that the optimal solving algorithm requires between 20 and 22 moves.

Factoring dice

Required reading for this post: Generating functions

We have two normal six-sided dice. We roll both of them, and sum the number of pips. There is a certain probability that we get a 2, or a 3, or a 4, and so on all the way to 12. What we want is a new pair of six-sided dice with the exact same probabilities as the normal dice, but with different numbers of pips on the faces. Each side must have a positive integer number of pips. Can you create such a pair of dice?

To solve this problem, we must have a better understanding of generating functions. Each sequence generates a unique function. Each function corresponds to a unique sequence. If we add two generating functions together, the resulting function corresponds to the sum of their respective sequences. But what happens if we multiply generating functions together?

Let's say we have some arbitrary sequence {a₀, a₁, a₂, a₃, a₄, a₅, ...} and another arbitrary sequence {b₀, b₁, b₂, b₃, b₄, b₅, ...}. Let's see what happens when we multiply them together.

F = a₀ + a₁*x + a₂*x² + a₃*x³ + a₄*x⁴ + a₅*x⁵ + ...
G = b₀ + b₁*x + b₂*x² + b₃*x³ + b₄*x⁴ + b₅*x⁵ + ...
F*G = a₀*b₀ + (a₀*b₁ + a₁*b₀)*x + (a₀*b₂ + a₁*b₁ + a₂*b₀)*x² + ...

It might be a little difficult to make sense out of what's going on here. It's important to pay attention to the subscripts. Pay attention to the sum of the subscripts. I'll make this a bit more explicit.

All the sums in the first box add up to zero. All the sums in the next box add up to 1. The sums in the next box add up to 2. Note that every possible way sum to 2 with two non-negative integers is represented in that box. This pattern will continue. The next box would contain every possible way to sum to 3. The next box contains all the sums to 4. And so on.

Have you figured out yet how this might relate to the dice? The answer follows.

We can say that each sequence represents some sort of generalized dice. a_j represents the number of ways for dice "a" to roll the number j, and b_k represents the number of ways for dice "b" to roll the number k. If we multiply the functions generated by each sequence, then we get a new sequence {c₀, c₁, c₂, c₃, c₄, c₅, ...}. c_n represents the number of ways for dice "a" and "b" to have a sum of n.

We can prove that this is the case. If we take any term c_n, it can be represented by the following sum:

c_n = a_n*b₀ + a_n-1*b₁ + ... + a₁*b_n-1 + a₀*b_n

If we recall the definition of a_j and b_k, the proof becomes obvious. The first term "a_n*b₀" represents the number of ways to roll n on dice "a" and 0 on dice "b". The next term represents the number of ways to roll n-1 on dice "a" and 1 on dice "b". And so on.

So let's try it with normal six-sided dice!

We can easily get the generating function D for a normal six-sided dice, and the generating function D*D for two normal dice.

Sequence for normal dice: {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, ...}
Let D = generating function for normal dice
D = x + x² + x³ + x⁴ + x⁵ + x⁶
D = x * (1 + x) * (1 + x² + x⁴)
D = x * (1 + x) * (1 + x + x²) * (1 - x + x²)
D*D = x² * (1 + x)² * (1 + x + x²)² * (1 - x + x²)²

Now what we want are two new six-sided dice with generating functions A and B such that A*B = D*D. So what we have to do is split D*D into two groups of factors, one for A and one for B. Each group must have the factor x, because that ensures that each side has a nonzero number of pips. Each group must also have (1 + x) * (1 + x + x²), to ensure that they have exactly six sides. However, we can split the factor (1 - x + x²)² in any way we want.

A = x * (1 + x) * (1 + x + x²) * (1 - x + x²)²
B = x * (1 + x) * (1 + x + x²)
A = x + x³ + x⁴ + x⁵ + x⁶ + x⁸
B = x + 2x² + 2x³ + x⁴

These correspond to dice with sides {1, 3, 4, 5, 6, 8} and {1, 2, 2, 3, 3, 4}. There's your solution, right there.

Well, that was quite a mathematical adventure! I've been having fun factoring other kinds of dice as well.

Generating functions

It's time for some math! No, wait, come back!

Here's the teaser:

We have two normal six-sided dice. We roll both of them, and sum the number of pips. There is a certain probability that we get a 2, or a 3, or a 4, and so on all the way to 12. What we want is a new pair of six-sided dice with the exact same probabilities as the normal dice, but with different numbers of pips on the faces. Each side must have a positive integer number of pips. Can you create such a pair of dice?

I would not pose this as a lone puzzle, because it is rather difficult, and requires a specialized trick. That specialized trick is called generating functions. A generating function is a function that is related to a sequence of numbers. For example, consider the following sequence:

1, 1, 1, 1, 1, 1, ...

The above sequence generates the following function:

1 + x + x² + x³ + x⁴ + x⁵ + ...

Here's a slightly more complicated sequence and its generating function

1, 2, 3, 4, 5, 6, ...
1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + ...

Essentially, you turn the sequence into the coefficients of an infinite polynomial.

We could leave the generating function in the form of a polynomial, but there's often a simpler way to express it. For example, take the generating function of the sequence {1, 1, 1, 1, 1, ...} We can simplify it with a bit of math.

Let H be the generating function of {1, 1, 1, 1, ...}
H = 1 + x + x² + x³ + x⁴ + x⁵ + ...
H*x = x + x² + x³ + x⁴ + x⁵ + x⁶ + ...
H - H*x = 1
H*(1-x) = 1
H = 1/(1-x)

Thus the sequence {1, 1, 1, 1, 1, ...} generates the function 1/(1-x).

Let's try the same for the sequence {1, 2, 4, 8, 16, ...}

Let G be the generating function of the sequence {1, 2, 4, 8, 16, ...}
G = 1 + 2x + 4x² + 8x³ + 16x⁴ + ...
G*2x = 2x + 4x² + 8x³ + 16x⁴ + 32x⁵ + ...
G - G*2x = 1
G*(1-2x) = 1
G = 1/(1-2x)

Thus the sequence {1, 2, 4, 8, 16, ...} generates the function 1/(1-2x).

You may be thinking, "That's nice, but what does that do for me?" Honestly, not a whole lot. But here's one problem you can solve.

Find an expression for the nth term of the Fibonacci sequence. In the Fibonacci sequence, the first two terms are {1,1}, and each term thereafter is the sum of the previous two terms.

We should first try to find the generating function of the Fibonacci sequence.

Let F be the generating function of the Fibonacci sequence {1, 1, 2, 3, 5, 8, 13, 21, ...}
F = 1 + x + 2x² + 3x³ + 5x⁴ + 8x⁵ + 13x⁶ + ...
F*x = x + x² + 2x³ + 3x⁴ +5x⁵ + 8x⁶ + ...
F*x² = x² + x³ + 2x⁴ +3x⁵ + 5x⁶ + ...
1 + F*x + F*x² = 1 + x + 2x² + 3x³ + 5x⁴ + 8x⁵ + 13x⁶ + ...
1 + F*x + F*x² = F
F = 1/(1-x-x²)

Good, now we've got the generating function: 1/(1-x-x²). We can actually simplify this a bit further. But to do this, we'll need some irrational numbers, which I'll just call A, B, and C. [See footnote for the actual values]*

1/(1-x-x²) = A/(1-Bx) - A/(1-Cx)

If I'm able to express the generating function as the sum of two other functions, that means I can also express the sequence as the sum of two other sequences. Makes sense? If you recall, the sequence {1, 2, 4, 8, 16, ...} generates the function 1/(1-2x). Similarly, we can prove that the sequence {1, B, B², B³, B⁴, ...} generates the function 1/(1-Bx). The fibonacci sequence is the sum of the following two sequences:

{1, 1, 2, 3, 5, 8, 13, 21, ...} = A*{1, B, B², B³, B⁴, ...} - A*{1, C, C², C³, C⁴, ...}

Thus, the nth term of the Fibonacci sequence is A*(B^n-1 - C^n-1). This is called Binet's formula for the Fibonacci sequence. Pretty cool?

Now, there are lots of other ways to find Binet's formula, and some of them are easier than this. But next time, we'll try to solve the dice problem, which is extremely difficult by any other method.

See the next page

[This is one of the things I learned at math camp. Well, *I* thought it was fascinating. My regards to the professor.]

*A is sqrt(1/5). B is the golden ratio, or 1/2 + sqrt(5)/2. C is 1/2 - sqrt(5)/2.

An intuitive thinker

One of the students at the math camp is very clearly an intuitive thinker. I'm not exactly sure how I know this; I just know. Listening to him speak--and he speaks a lot--is like listening to a stream of consciousness. A lot of it is nonsense. As if he is thinking out loud, not really expecting anyone to understand.

But more tellingly is the way he solves math puzzles. It is so very hard to describe, especially to those who haven't had much experience with math or puzzles themselves. I will try.

So some of our lectures were about number theory. The following warm-up problem was given:

Prove that any common divisor of x and y is also a divisor of the greatest common divisor of x and y.

If you're like me, you first wonder why this needs proof. It's so obvious. At least to me. It has to do with the prime factorization, and the gcd function, and the... but darn it, this is no proof! Such is the problem with intuitive thought. You can look at many problems and think they're so obvious, but that doesn't always help you with proof. Who knows what underlying assumptions our intuition makes. It could be using circular reasoning, for all we know. Sometimes a flash of intuition lights the way, but other times it's so bright that it blinds us.

The above question is an example of very basic number theory. This kind of question gives even non-intuitive thinkers problems, because it asks us to prove something we are so used to assuming. For a highly intuitive thinker, this occurs all the time, even for math that is less basic. Everything seems so obvious, but it is difficult to say why.

And so it was, intuition was often an obstacle for this student. And sometimes, his intuition not only prevented him from finding a proper proof, but also gave him the wrong final answer. Such is the peril of intuition; it cannot always be trusted.

Not to say that the student was the worse because of it. He was a star student, one of the youngest and brightest.

I, too am a bit of an intuitive thinker, and I intend to defend intuition, even praise it.

Intuition is not some innate knowledge, gained at birth. It's not encoded into our ancient genes. At least, not always (I think phobias are pretty amazing myself). Carl Jung would have you believe that intuition is opposed to sensation, that intuition comes from within and sensation comes from without. But I don't put much stock into the MBTI, so I don't see why "within" and "without" should be necessarily opposed. I think that intuition is a skill that can be acquired from the outside. It can practiced and improved. It can be a learning tool, a way of internalizing new knowledge.

If I'm learning something, say special relativity, I find it useful to visualize. As we boost spacetime, the axes scissor together such that the determinant is conserved. If we go near the speed of light, objects will flatten. Distances will shorten. Clocks will slow down, but the plane of simultaneity tilts as you accelerate. Sorry if none of this makes any sense--but this is how I do it. I can easily visualize the resolution to the twin paradox, as if there were no paradox at all.

I use special relativity as an example, because it's so often thought to be counterintuitive. But it really can be intuitive, if you work on it hard enough. I worked on it for a long time myself, looking at relativity from all sorts of viewpoints. I try to do the same for other "counterintuitive" concepts (quantum mechanics, anyone?). It's possible, but it takes work. Intuition doesn't start out as a reliable way of knowing, after all. (Spiders aren't that dangerous.)

Equally importantly, you have to work on other skills to support intuition. You must be able to translate intuition into reasoning. You must be able to break down your intuition into its constituent parts, and examine them if needed. Without these supporting skills, intuition is impossible to verify. Some intuition is bad, and some is good. If we have the skills to distinguish between the two, it becomes a powerful tool.

Misplaced pluralism

Via EvolutionBlog, I found this article in American Scientist covering the Monty Hall problem. Good coverage, but I disagree with this last paragraph:

Making progress in the sciences requires that we reach agreement about answers to questions, and then move on. Endless debate (think of global warming) is fruitless debate. In the Monty Hall case, this social process has actually worked quite well. A consensus has indeed been reached; the mathematical community at large has made up its mind and considers the matter settled. But consensus is not the same as unanimity, and dissenters should not be stifled. The fact is, when it comes to matters like Monty Hall, I'm not sufficiently skeptical. I know what answer I'm supposed to get, and I allow that to bias my thinking. It should be welcome news that a few others are willing to think for themselves and challenge the received doctrine. Even though they're wrong.

No, dissenters shouldn't be stifled. But in this case I can't think of any way in which dissent is a good thing. The Monty Hall problem isn't just considered settled, it is settled, with deductive certainty. Oh, sure, the principle of pluralism says it's healthy to have a diversity of views, but you have to think about why we value pluralism. I think pluralism is good because of the possibility that the consensus is wrong. That possibility simply doesn't exist here. Pluralism is bad in this case. It's okay, I'm sure we can find other things to disagree about.

The same goes for the following claims:

• 3.9999... is not equal to 4
• Maybe the brick puzzle has a solution, and we just haven't found it
• Math can't possibly handle concepts like infinity
  

M12 Sporadic Group Puzzle

You didn't think I had any particular reason for rambling about the Rubik's Cube? I started talking about it because in the recent issue of Scientific American, there is a very interesting article about the Rubik's Cube and similar puzzles. Sorry, it's subscription only, but I'll explain the basic ideas.

Permutation puzzles, as I previously explained, are puzzles where you have to arrange a number of items (like cubies or numbers) into the correct order. The underlying mathematics of permutation puzzles is called Group Theory. That's right, you're doing advanced mathematics when you turn a Rubik's Cube! Basically, all the possible positions of a permutation puzzle constitute a "group". For a Rubik's Cube, the size of this group is 43,252,003,274,489,856,000. But don't be intimidated by the size. As I said, the vast majority of permutation puzzles are easy. I mean, sure, you've got a 4-dimensional Rubik's Cube that boggles the mind, but they're easy in principle.

The mathematical reason that most permutation puzzles are easy is because they are based on symmetric or alternating groups. In a symmetric group, every single permutation is possible. In an alternating group, half of the permutations are possible. Maybe the previous three sentences made no sense to you, so allow me to translate to a concrete example: the Rubik's Cube. If the Rubik's cube is based on a symmetric group, that means you can find a way to switch two cubies without changing anything else. If it is based on an alternating group, that means you can find a way to switch three cubies without changing anything else.

But what happens if you've got a puzzle based on a much more complicated group? What if the simplest algorithm possible must switch 4 cubies at a time, or more? If we look to the mathematical research, there are lots of different finite simple groups. There are exactly 16 families of groups, plus 27 oddball groups, called the sporadic groups. (What's really amazing to me is that mathematicians can prove that there are no other finite simple groups.) So what happens if we build a puzzle based on one of those sporadic groups?

Well, that's what the Scientific American article did. They built puzzles based on the M₁₂ sporadic group, the M₂₄ sporadic group, and the Co₀ group (aka the dotto group). Try them yourself!

The M₂₄ puzzle and the dotto puzzle look ridiculously complicated, and I don't, at the moment, have enough patience to solve them. But let's look at the M₁₂ puzzle.

Basically, you've got two moves called Invert and Merge. You can also create a custom macro, if you ever find an algorithm that you like. To solve this puzzle, I followed the same basic steps as I explained for the Rubik's cube. However, they are no longer easy. It is impossible to find an algorithm that switches exactly 2 or 3 numbers. In fact, you must switch at least 8 numbers at a time! Nevertheless, I came up with some useful algorithms.

So do you want some tips on solving the M₁₂ puzzle? Try these simple algorithms. I came up with cryptic names for them too!

2-invert: MIM10I
2-bike: M2IM9
6-bike: M10IM
4-trike: M3IM8I
3-bike: M9IM2
bike/invert: M8IM3

Once you figure out what they do, you'll have to come up with a super-algorithm that combines them to solve the puzzle. It isn't easy, even with my hints.

Google Puzzle Championship results

Did anyone take the Google Puzzle Championship besides me? If so, what were your scores? I ranked in the top 50. This is the result of much practice, taking the test for several years.

If you didn't take it, you can still try the test here.

Rubik's Cube non-walkthrough

Ok, so I can solve the Rubik's Cube. You're probably not surprised. Well, if I may boast a bit here... I've been able to solve it for at least seven years. I figured it out completely on my own, without any walkthroughs. No, I didn't even ever see the hint booklet that comes with the Rubik's Cube. Ours was really old, and the hint booklet was long gone. As a result, I solve the cube in a completely different order than most people do (I think the way I do it makes much more sense). I also own a 4x4x4 Rubik's Cube (16 squares to a face) and can solve that.

The internet will probably not be impressed--not until I can videotape myself solving it in 30 seconds while simultaneously doing interpretive dance. But in real life, people tend to be impressed. The thing is, people don't realize how easy the Rubik's Cube is. There are a few very simple principles to solve any permutation puzzle. By permutation puzzles, I mean the kind of puzzle where you have to arrange the numbers in the right order, put the cubies in the correct place, or otherwise sort a number of items into the "correct" order. I'm not going to go into the details of how to solve the Rubik's Cube. I'll do better: I'll reveal the secret to solving pretty much any permutation puzzle without a walkthrough.

Step 1: Sort as many items as common sense will take you. On the Cube, most people solve one face; I solve for some other weird combination. This is where most people tend to fail--luckily, this step is skippable.

Step 2: Develop several algorithms that will change the position of only a few items. That way, you can solve the remaining part of the puzzle without messing up your previous work. Developing an algorithm is pretty much a trial and error process. Just try a bunch of moves, write down the steps, and note the changes. Once you find an algorithm, it behaves like a blackbox--you can just memorize the process without knowing exactly what's going on during the process. (However, if you're good, you can open the blackbox, and manipulate the algorithm without trial and error.)

Step 3: Combine these algorithms to solve the rest of the puzzle. The difficulty of this step depends on how good your algorithms are. For example, if you find a way to simply switch two cubies, you can easily repeat this over and over, putting each cubie into its place one by one. However, it is impossible to find any such algorithm on a Rubik's Cube. You must switch at least three cubies at a time. But if you've got enough thinking power, such an algorithm is enough to solve the puzzle. (Incidentally, you can switch two cubies for the 4x4x4, though there are other limits to what you can do.)

And that's it! Easy, right? Well, if you were looking for a solution to the Rubik's Cube, I probably didn't help you in the slightest bit. But now you know what you're looking for.