Basics 0/98

Ad hoc and observation: solving with invariants · 1 of 2 Advanced

Invariants and observations

Solve small cases by hand, find the quantity a move cannot change, and turn that observation into a direct answer.

3,392 words · 16 min read

Part 1 of 9 Ad hoc problems

What is an ad hoc problem?

Some problems match a technique with a name, such as sorting, trying every case or a bit trick. Others match none of them. An ad hoc problem is one we solve by reasoning from its own rules until we notice a fact that gives the answer. Let's start with a small puzzle.

Three cards lie in a row, written 0 for face down and 1 for face up. One move flips two neighbouring cards. Starting from [0, 1, 1], can we make every card face up?

List every state you can reach

With no technique that fits, we study the moves themselves, and three cards are few enough that we can list every row we can reach. The state is everything that can affect later moves, here the row of three values. A move picks one of the two neighbouring pairs, and the goal is [1, 1, 1].

Every state reachable from [0, 1, 1]
StateFace-down countHow to reach it
[0, 1, 1]1Start
[1, 0, 1]1Flip the left pair
[0, 0, 0]3Flip the right pair
[1, 1, 0]1Flip each pair once

Flipping either pair in any of these rows gives another row already in the table, so these four are all the states we can reach, and the goal is not one of them. Now let's read the face-down counts: 1, 1, 3 and 1. Every reachable state has an odd face-down count, and the goal's count, 0, is even. For now that is only a pattern in four rows. The next part proves it for a row of any length.