Heads and Tails

Form a triangle with three small pins. Each pin has two ends. One is blunt, the other is pointed. The blunt end is known as the head, the pointed one is the tail. At a vertex of the triangle where two pins meet, they may meet either head to head, or head to tail, or tail to tail. There are just three possible vertex configuration. Now, the task is to prove (and later generalize) the following

Theorem 1

With three pins forming a triangle, either all vertex configurations are the same, or all vertex configurations are different.

The applet below helps you experiment with various configurations and even prove the theorem by enumeration of all possible cases. (With a click on a pin you can change that pin's orientation.)

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Heads and Tails

What if applet does not run?

Proof

With three pins forming a triangle, either all vertex configurations are the same, or all vertex configurations are different.

Would not you like to try your hand at proving the theorem before actually reading the proof.

Now, what about four pins? With four pins, it's possible to have all vertex configurations equal. But since there are 4 vertices and only 3 possible configurations, it's impossible to have all 4 configurations different. Does it mean that we can't make a meaningful statement for 4 or more pins that generalizes our theorem. No, it does not. There exists a very nice generalization, and the applet above may help formulate it as well. Just note that when you click on (or drag the cursor over) the number, i.e. the number of pins, in the lower left corner of the applet, the number changes. To increase the number keep the cursor a little to the right of its vertical central line, to decrease it keep the cursor to the left.

Well, there are in fact several proofs. A proof by enumeration is a real, albeit not very elegant, mathematical proof, because the number of possible cases is finite.

Here's the proof I like most:

Proof #1

Let's introduce orientation on the perimeter of the triangle. There are just two possible orientations: one is clockwise, the other is counterclockwise. (I do not know how to prove this assertion and hope you will accept it as true, for otherwise my proof will prove nothing. At least for you.)

An individual pin may be endowed with an orientation as well. The movement form tail to head may or may not agree with the selected orientation of the triangle. We say that the pin is oriented positively or negatively depending on whether or not there is an agreement.

As there are only two possible orientations, two of the three pins are bound to have the same orientation. If the third pin is oriented similarly to the first two, all vertex configurations are the same - head to tail. We write HT = 3, HH = 0, and TT = 0. If the third pin is oriented differently than the other two, then HT = 1, HH = 1, and TT = 1. Q.E.D.

This is a nice proof that fits very well into the three pin configuration, but does not seem to be of help with more than three pins.

Proof #2

Select a pin. This pin joins two vertices, or we may say that it joins the endpoints of two other pins. These endpoints may be head/head, head/tail, tail/head, or tail/tail. What happens to the numbers HH, HT, and TT when the selected pin changes its orientation? The results are collected in the following table:

"Left" pin	"Right" pin	Selected pin	Count after the change
head	head	head/tail	HH, HT, TT
head	tail	head/tail	HH-1, HT+2, TT-1
tail	head	head/tail	HH+1, HT-2, TT+1
tail	tail	head/tail	HH, HT, TT

As we see and can verify by experimenting with the applet, the number of vertex configurations HH and TT always change simultaneously: either both grow, or both decline by 1. Since every possible sequence of vertex configurations can be obtained by starting with the one in which all pins are oriented similarly, in which case both HH and TT are 0 and thus equal, and swivelling a few pins as above, we conclude that always HH = TT.

If HH = TT = 0, then HT = 3, and all vertex configurations are the same. If HH = TT = 1, then also HT = 1 and all configurations are different. Q.E.D.

In the course of Proof #2 we have shown that always HH = TT. This is a clear generalization of Theorem 1:

Theorem 2

HH = TT.

As we just saw, when the number of pins is 3, both theorems claim the same result.

Proof #3

Let N pins be arranged in a closed chain. Since each of them has one head and one tail, the total number of heads (N) equals the total number of tails (N). There are TH head/tail configurations each containing one head and one tail. Disregard all such configurations. Configurations that remain contain equal number of tails (N - TH) and heads (N - TH). But those are only included in TT and HH configurations. It thus follows that TT = HH, and, naturally, the number of ends in both is even.

Related material Read more...
	3-Term Arithmetic Progression
	Aliquot game (An Interactive Gizmo)
	Euclid's Game (An Interactive Gizmo)
	Euclid's Game on a Square Grid
	Sums and Products
	Sums and Products, a Generalization
	Sums, Products, and 1-1 Functions
	Zeros and Nines
	A Candy Game: Integer Iterations
	A Candy Game (Change Discharged)
	Loop or Halt - An Interactive Gizmo
	Breaking Chocolate Bars (An Interactive Gizmo)

72193021