Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Best sites for teachers
Sites for teachers
Sites for parents
Terms of use
Awards

Interactive Activities
CTK Exchange
CTK Insights - a blog

Games & Puzzles
What Is What
Arithmetic/Algebra
Geometry
Probability
Outline Mathematics
Make an Identity
Book Reviews
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
Visual Illusions
My Logo
Math Poll
Cut The Knot!
MSET99 Talk
Other Math sites
Front Page
Movie shortcuts
Personal info
Privacy Policy

Guest book
News sites

Recommend this site

Best sites for teachers
Sites for teachers
Sites for parents

Education & Parenting

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

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.)


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


Buy this applet
What if applet does not run?

Proof

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.

Copyright © 1996-2008 Alexander Bogomolny

 

 

 

 

 

 

 

 

 

 

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 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 configuration? 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 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.

Copyright © 1996-2008 Alexander Bogomolny

29284641Page copy protected against web site content infringement by Copyscape


Search:
Keywords:


Latest on CTK Exchange
calculator suitable for high scho ...
Posted by albert1950
1 messages
10:42 AM, Jun-17-08

Constucting a triangle instructions
Posted by Gerald B.
3 messages
01:32 PM, May-20-08

Missing information
Posted by roboknight
2 messages
07:32 AM, Jun-22-08

An Interesting Formula And Algorithm
Posted by ddixonslc
1 messages
01:44 PM, Jun-19-08

Mistake on the page (an aside, Be ...
Posted by Max
4 messages
10:28 AM, Feb-28-08

Statistical estimation question
Posted by Ralph
2 messages
02:21 PM, Jul-01-08

fusc pseudocode
Posted by azi
1 messages
08:02 PM, Jun-29-08