The Problem with Hard-with-a-Capital-H Problems
I sat down to my very first Caltech math problem set with the adorable exuberance that only a freshman could muster. Pencils sharpened, whiteboard ready, textbooks unwrapped, I read the first problem:
I read it again, hoping I’d missed something—additional constraints or guidance, perhaps? This was on page 15, and the few preceding pages yielded no tutorial for this type of problem. I blinked.
I did not attend a high school with an “of Math and Science” suffix like so many of my new classmates. We were taught math in the same way most high schools teach the subject: algorithmically. Apply this procedure to solve problems which look like that. Students had only to identify the type of the problem at hand, memorize the corresponding technique, and execute a mechanical process.
I was fairly certain I had not been taught a technique for problems of the Rational Set Membership Proof type. My notes had nothing of the sort. Subsequent lectures did not return to the subject.
When I visited office hours, the professor wouldn’t help me with the problem because its only challenge lay in discovering a critical insight which, once found, rendered it trivial. He solved some other simple proofs in front of me. I nodded along: each step was indeed true. But how on earth did he generate the steps? He shrugged and offered to do some more examples. Each seemed just as obvious as the last—but only in hindsight.
I later learned that my professor’s insights came from intuition. No one could explicate or decompose that sense for me, so I wrote these problems off. Who needs proofs to write software?
But I didn’t realize that these proofs are hard in the same sense as the most interesting problems in all fields: they have no obvious, closed-form solution. They’re Hard with a capital ‘H,’ and the contents of their toolbox apply just as well to, say, design problems.
Much to my dismay, I also learned at Caltech that a field’s greatest masters are likely not its greatest teachers. Pedagogy requires a different art entirely. So how can we teach insight, intuition, analytical thought?
My answer (as to most things): cognizance. Let’s articulate the inner monologue in solving a Hard (though fairly simple) analytical problem.
The Snowman Problem
You’ve got a 5×5 grid of Unicode snowmen at a tea party. When you blow a whistle, every snowman must move to a new space. But a snowman can only move to a cardinally adjacent square, and we can’t end up with two snowmen sharing the same square.
How should the snowmen move to do this? Or prove it’s impossible.
Start by trial and error. Draw arrows on a whiteboard. Tear bits of paper into ☃ stand-ins. Make little groups that can move successfully. But no matter how you arrange them, one seems left without nowhere to go.
By this point, we might suspect impossibility. But how can we prove it?
Let’s try decomposing the problem. How about a 2×2 grid? In that case, the solution is simple. Maybe I can use this simple solution to generate more complex solutions: for 4×4 grids, I can repeat this smaller scheme in each corner. But that only works for boards with even widths and heights.
So, generalizing, maybe odd-sided boards can’t be solved! But if we try the next-largest grid, we see that 2×3 can be readily solved with a slightly altered “looping” approach.
3×4 is just two 2×3 boards next to each other, so that’s solved, too. Studying composition a little more, you’ll find that we can combine 2×2 and 2×3 boards to solve any even-sided or even-by-odd-sided board.
But 3×3 seems just as hard as 5×5. Notice that if we could solve 3×3, we’d be done, since we could make a 5×5 from it by adding a 2×2 and two 2×3s. So we’ve just reduced the problem to a simpler one.
What makes 3×3 so hard? Intuitively, there’s always an “odd man out.” What else is different about 3×3 and 5×5 from all the other cases we’ve considered? Well, both side lengths are odd. The boards that worked have at least one even side length. And one of the properties of even numbers is that an even number times any other number is always even. Aha: “hard” boards have an odd number of squares.
How else does parity apply to this problem? Consider a snowman’s coordinates. A snowman at (1, 1) must move to (0, 1), (1, 0), (2, 1), or (1, 2). A snowman at (2, 2) moves to (1, 2), (2, 1) (3, 2), or (2, 3). Notice: either the X or Y coordinate must change parities when moving.
Let’s consider this result graphically. Overlay a checkerboard over our problem. Now it’s clear: a snowman on a black space must move to a white space, and vice versa. But when there are an odd number of squares, there will be one more square of one color than the other.
Since only one snowman can occupy each space, at least one snowman will have nowhere to go when the colors are uneven.
A 5×5 board has an odd number of squares, meaning it has more tiles of one color than another. Which will make the move impossible. QED.
I suspect that most who excel at Hard problems have no idea how they solve them. This example illustrated a number of key approaches: reduction, composition, (failed) induction, synthesis, comparison and contrast, and visualization. Once mastered, we could use these techniques to solve problems in any number of fields.
I realized recently that some of these techniques are a bit like playing Set! with the problem space. Which parameters restrict us most? Which parameters are similar? Are some irrelevant? I imagine we could devise more apparently innocent games to train lateral thinking.
