Hilbert's Hotel

Schoolgirls do not Necessarily Form a Group

2009-05-27T11:34:00.000-07:00

In the previous blog, I said that I was not certain that defining an addition on the schoolgirls of the Kirkman Schoolgirl Problem would produce an Abelian group. The Kirkman Schoolgirl problem was to find a 7-day schedule of 3x5 schoolgirl formations among 15 schoolgirls so that each pair of girls marches in the same line once and only once. I then defined an operation + on {0, the schoolgirls} by:

0+0=0
0+a schoolgirl is that same schoolgirl back
Any schoolgirl + herself is 0
If A and B are any two schoolgirls, find the line that contains them (guaranteed by the conditions of the problem). There are three girls in that line, namely A, B, and another schoolgirl C. Define A+B = C.

The operation is defined to be commutative. Also any two schoolgirls added make another one, 0 is the identity, and each girl is her inverse. The only requirement left to make the schoolgirls and 0 into an Abelian group is the associative law:

(A + B) + C = A + (B + C)

I remarked on how hard it would be to prove this on the schoolgirls.

Today I found that the conjecture is false. Given a solution to the schoolgirls problem, if you define + like this, it may not be an Abelian group, since it may not obey the associative law. Take this situation, for example:

	1pm	2pm	3pm	4pm	5pm
Day1	ABC	DEF	GHI	JKL	MNO
Day2	ADG	BEJ	CFM	HKN	ILO
Day3	AEN	BDO	CHL	FIK	GJM
Day4	AIM	BGL	CDK	EHO	FJN
Day5	AHJ	BKM	CEI	DLN	FGO
Day6	AFL	BIN	CJO	DHM	EGK
Day7	AKO	BFH	CGN	DIJ	ELM

This comes from a column on the Mathematical Association of America website. Consider the sums (B + D) + A and B + (D + A). The first one is

(B + D) + A = O + A

This is because BDO form a line in the Kirkman schedule. Further,

O + A = K

Since this OAK tree is in the Kirkman Schedule. So (B + D) + A = K.

The second one runs:

B + (D + A) = B + G

since ADG is a line. Further,

B + G = L,

Since BGL is a line. Therefore,

(B + D) + A != B + (D + A)

So that + is non-associative.

This shows that there is a solution to the Kirkman problem that is not the standard one given by using Klein triples in Z₂⁴. In fact, I hear tell that there are 7 solutions, of which the Z₂⁴ is just one.

Kirkman's Schoolgirls

2009-05-14T20:25:00.000-07:00

I find this to be a fascinating problem. Kirkman in 1850 poses this problem:

Fifteen young ladies of a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk abreast more than once.

I find it interesting that he refers to breasts, but that's for another blog. I want to see how to solve this problem.

To solve this problem, I look to elementary binary groups (EBGs). These are groups that are products of copies of Z₂, the group whose elements are {0,1}, and 0 plus any element is that element back again, and 1 + 1 = 0. Let's take products of 0 though 4 of these:

0. Identity. Product of no Z₂s. This is the identity group. Only one element. Not much of interest.

1. Binary. Product of one Z₂; i.e., Z₂ itself. This is the 0-1 group. The subgroups are Z₂ itself and the identity group. This is the group of off and on, back and forth, 0 and 1, something and nothing, and so forth.

2. Klein triples. Product of two Z₂s; i.e., Z₂xZ₂ or Z₂². This is called the Klein 4-group. Suppose its elements are {0, a, b, c}. Then 0 + anything is that something back again. An element plus itself is 0; for example b + b = 0. If you take two non-equal non-zero elements and add them, you get the third one. For example, b + c = a, and a + c = b.

We shall meet this group later, and so I will give it a special name. I shall call the non-zero elements of an instance of this group a Klein triple. So {a, b, c} is such a triple, as is {3, 5, 6} with the operation of (logical) AND. 3 AND 5 = 6, since in binary, if we and 011 and 101, we get 110 (add the components as in Z₂).

3. The Fano Plane. Product of three Z₂s. This is a group of 8 elements, with 7 non-zero elements. How many Z₂xZ₂ subgroups does it have? How many Klein triples does it have? You can select any of 7 elements for the first element. You can't select that one again, but you can select any other for your second element, giving you 6 choices, but then that forces your third element, which is the AND of the first two elements. That's 42 possibilities. But each Klein triple occurs 6 times in this enumeration, so we have only 7 subgroups. Since subgroups isomorphic to Z₂ are essentially the same as elements of order 2, there are 7 of these. So which of these 7 4-element groups contains which of the 2 element groups?

What if you intersect two Klein triples, or Z₂xZ₂s? They have to intersect in a Z₂. This is similar to two planes in 3-space intersecting in a line. So each of seven 3-sets intersect each other in exactly one element. If you try to construct a set of 7 elements like this, you get something like:

123
145
167
246
257
347
356

This is called a Fano Plane. Fano planes have interesting properties. For example, each pair of triples intersects in a single element, and if you name two elements, one and only one triple has both of them. This makes it a magic pattern, similar to magic squares, and some cultures must have worshipped this plane. A Fano Plane is also a (7, 3, 1) design - read a book on combinatorics to find what that is.

4. Kirkman Schoolgirls. Now let's look at Z₂⁴. This has 15 elements of order 2, forming 15 subgroups of order 2. I shall call these elements schoolgirls. Linear algebra tells us that there are then 15 subgroups isomorphic to the Fano group above (Z₂³). How many groups isomorphic to Z₂xZ₂ are there, or what is the same thing, how many Klein triples are in the Kirkman group?

Number the girls 1 through 15. Pick one girl. There are 15 possibilities. Then pick another one. 14 choices. Your choice of the third girl is now forced. You must take the AND of their numbers and find that girl. So there are 14*15 or 210 triples, but each triple occurs 6 times in that total, so there are really only 35 such triples. Here are these triples, arranged in 7 columns to represent the 7 days. Given in this form, these triples solve the Kirkman problem (this arrangement is due to Brown and Mellinger):

RANK/DAY	S	U	N	M	O	N	T	U	E	W	E	D	T	H	U	F	R	I	S	A	T
1	1	2	3	1	4	5	2	4	6	1	6	7	3	4	7	3	5	6	2	5	7
2	4	10	14	2	13	15	1	8	9	2	9	11	2	12	14	2	8	10	1	14	15
3	7	8	15	3	9	10	3	12	15	4	8	12	1	10	11	4	11	15	4	9	13
4	5	9	12	6	8	14	5	11	14	3	13	14	5	8	13	1	12	13	3	8	11
5	6	11	13	7	11	12	7	10	13	5	10	15	6	9	15	7	9	14	6	10	12

The Kirkman Schoolgirls bring up some interesting problems. For example, each day consists of one even-even-even triple and four triples with two odd girls and one even one. If you divide by 2 and take the quotients in one table and the remainders in the other one, you find a lot of structure. In particular, the first table contains clusters of elements from 1 through 7, and if you look through these, you will see the Fano plane in disguise. The Fano plane also appears in the top row of the schedule above.

The most interesting problem is whether there is a solution to the Kirkman Schoolgirls essentially different from this one. Here is an idea that may shed some light on this. Suppose someone hands you a 7-day Kirkman schoolgirl schedule. Let us attempt to form a group of order 16, consisting of these girls and the number 0. I shall define an addition + on these girls like this:

1. 0 + 0 = 0.
2. 0 + any girl = that girl again.
3. Any girl + herself = 0.
4. Compute the sum of two girls as follows. These are two separate girls. By the Kirkman property, there is one and exactly one line in the Kirkman schedule that contains both these girls. The sum of these girls is defined to be the third girl in that line.

It is easy to prove that the sum of two girls is a girl, that 0 is the identity, and each girl is her own inverse. The tricky part is to show that + is associative, that is, for all elements of the group a, b, and c, a + (b + c) = (a + b) + c. If any of a, b, and c are equal to each other or to 0, that is easy to prove. The tricky one is for different non-zero a, b, and c. a + (b + c) means go to the line contain Betty and Carol and find, say Doris in the same line with them, then find the line with Doris and Anne and take the third girl in this line. (a + b) + c means go to the line containing Anne and Betty and find, say Ethyl in their line, then find the line with Ethyl and Carol in it and take the third girl in that.

Are these two third girls the same? If one can prove that is always the case, then 0, the girls and + form an abelian group isomorphic to Z₂⁴. Further, taking the 4-element subgroups of this group gives you back the original Kirkman design. But maybe one can't prove this. Is it possible to find a Kirkman schoolgirl arrangement where this set is not a group? If so, there are at least two distinct solutions to the Kirkman Schoolgirl Problem.

The Big Rip Ripoff?

2009-01-19T21:06:00.000-08:00

In the 2009 February issue of Astronomy magazine, by Liz Kruesi, Liz explains that it is possible the universe could rip itself to infinity instead of just simply expanding into the cold wilderness. The usual theory now is that the universe will continue expanding until galaxies, stars, planets, rocks, and even atoms are incredible distances apart, and they will continue to expand forever. This is called the Big Chill. What is proposed in this article is that instead, the universe will continue to expand for a while, and then the expansion will increase, slowly at first, then more rapidly. At some time, maybe a few hundred billion years from now, it will expand so rapidly that it will tear everything apart and send everything to infinity in a finite amount of time, a time called the Big Rip.

This reminds me of another situation. Suppose you have a population that is growing at a rate proportional to the population itself; for example, if it is humans, then the women have a constant rate of childbearing. To see what kind of growth rate results, differential equations can help. Suppose you have an initial population, and that the growth rate is some constant r times the population. If we let t denote the time, and x the population, the equation is:

x' = rx

or dx/dt = rx

The way to solve this is to take this last equation and invert it:

dt/dx = 1/rx

You then integrate both sides with respect to x to get:

t = log(rx) - B

where B is some constant to be determined by initial conditions. Solve for x and you get:

x = Ce^rt

where C = e^B. This is an exponential function. An exponential function grows rapidly, and the more you go out, the more rapidly it grows. Note that x = x¹, as anything to the 1 power is itself again. The number 1 here is a growth factor that in some ways tells how fast the function goes.

But suppose the increase is more than exponential. Suppose instead that we use some number greater than 1 as the power to which we take x. Suppose we take 2 instead. Then we get:

x' = rx²

or dx/dt = rx²

The way to solve this is to take this last equation and invert it:

dt/dx = 1/rx²

This is a power function, and the integral of 1/rx² is -1/rx + D. That is,

t = D - 1/rx

or upon solving for x,

x = 1/r(t-D)

I chose D because it stands for "Doomsday". Now we have t in the denominator, so something really off the wall happens when t rises to become equal to D. That means the denominator becomes 0, with the numerator not 0. Such a division can't be done, but it can be thought of in a way as representing infinity, and indeed the value of x increases without bound as t approaches the dreaded Doomsday D.

Doesn't this sound like the Big Rip scenario? If we let a represent the exponent (which is 1 for the first example and 2 for the second), then it turns out that when a is 1, then the function stays finite forever, but when it is greater than 1, then the function reaches infinity in a finite amount of time. Is there such an a around in cosmology? Yes there is, according to the article. It is a number called the "equation of state" w. If this number is -1, then the universe will always exist. If it is less than -1, the universe will cease to exist eventually. The article associates -1 with the cosmological constant, and less than -1 with something called "phantom energy" - that maybe some dark energy out there somewhere makes w less than -1 and hence the exponent is greater than one, so an infinite blowup in a finite amount of time occurs. It is also interesting that w is the negative of the a I use in these two examples.

Can such a thing as a Big Rip happen? I don't think so, because I believe in the Infinity Principle: you cannot have a far infinity in the real world. This means a mass can't have infinite density, a distance can't be infinite and so forth. You have to allow for "deep" infinity, however, else we can't go anywhere, as Zeno's paradox shows, but an infinity that is way far out there, so to speak, cannot exist in our realm of existence. So I believe that before the Rip can occur, it will stop when quantum effects stop the expansion, leaving the Universe an extremely sparse sea of elementary particles.

When Will Winner Be Known?

2008-10-30T06:36:00.001-07:00

2008 November 1. Updated. Still Iowa for Obama at 10 pm. There are some changes. North Dakota gets decided at 3:43 am for McCain, instead of after an infinite amount of time. Missouri has flipped into the McCain column, and is the last state to be decided, at 5:10 am. ElectoralVote.com says if Missouri goes McCain and Obama wins the election, Missouri loses its bellwether status. It never had it to begin with. Missouri went the other way from the entire election in 1860, 1872, 1876, 1880, 1888, 1896, 1900, and 1956, when Stevenson took the state. What would happen in this instance is that the statement "The Democrats have never won an election without taking Missouri.", which is true now, would become false.

2008 October 31. Updated. Now Iowa wins it for Obama at 10 pm, right as the polls close.

It is now only 5 days until the Great Presidential Election of 2008. After the conventions, the race was a tie, but Barack Obama has piled up a moderate lead in recent weeks. I therefore expect Election Night not to be as long as in 2000 and 2004. The 2004 race was not settled until Wednesday morning, when it became clear that Ohio, the deciding state, was going to go to Bush by a substantial margin. In 2000, the race was not decided until mid-December, with Florida being the deciding state. So I expect this night to be shorter. How much shorter?

To answer that question, look at what happens on Election Night. The networks will not announce any results for any state until the polls close everywhere in the state. However, they will be performing exit polls, and on this basis, when the polls close, they can project ("call") a state for one candidate or the other. If the race in that state is close, they will not call it then but wait until enough votes are in for them to conclude that a candidate has won it. To get an estimate of Decision Time on Election Night, we need to know how the networks are going to call a state. I have only memory to rely on for this, so I will make a guess at a possible calling function.

This function will be a function of the average poll result for the state. For this number, I am going to use the file provided by Electoral-Vote.Com, as well as their procedure, which is to take an average of all the polls for the previous week. I will use only the two major party candidates' poll numbers, which I will normalize by the usual method, namely to set the vote for Barack Obama

= Poll for Obama / (Poll for Obama + Poll for McCain)

and set the vote for McCain as being 1 - Poll for Obama. Call the poll result for Obama x. Set the closing time of the election polls for the state = c. Then my function is:

f(x) = 0 if |x-0.5| > 0.04 (networks call the state immediately upon poll closing)
= 336, if x = 0.5 (two weeks. Highly improbable in election but not in polls)
= 1/50/|x-0.5| otherwise.

The value of the function is given in hours. I choose a hyperbolic function on the difference between the vote result and 50%. If a candidate is getting 52% (he leads by 4 points), this function gives one hour; that is, the networks will wait an hour before calling the state. If a candidate gets 51%, the wait is 2 hours, and if it is 50.5% (1 point difference) the wait is 4 hours.

I then add this value to the closing time to get an estimated calling time T for the state; in other words,

T= c + f(x).

I rank-order the states by calling-times, and add up the Obama votes. I then look for that time when the Obama vote is 269 electoral votes or more (I assume that Obama wins a 269-269 tie).

I did that this morning and got that the deciding state will be Indiana, and that the calling time will be 9:45 pm. This will allow for an extra snack or drink and some discussion before going to bed for the night.

Here are the deciding states and times I have been getting the past few days, based on the polls, times in EST:

October 12, North Carolina, 10:40 pm
October 22, California+,11:00 pm
October 23, California+, 11:00 pm
October 24, Florida, 9:50 pm
October 26, Florida,10:25 pm
October 27, Florida, 10:00:05 pm
October 28, North Carolina, 10:28 pm
October 29, North Carolina, 10:19 pm
October 30, Indiana, 9:45 pm
October 31, Iowa, 10:00 pm
November 1, Iowa, 10:00 pm

By + for October 22 and 23, I mean that the election is decided by all four states that are immediately called for Obama at 11 pm EST.

From this one can deduce several points. One is that the deciding state is likely to be a large state. Indiana is the smallest state so far that has appeared as a deciding state. For some time earlier this week, McCain was gaining, causing later decision times. But now it's getting earlier again. Yesterday's polls were overwhelmingly for Obama. At 10 pm Obama will either have reached 269 or will be just short of 269. The first state in that hour, from 10-11 pm, that gets called for Obama may very well put him over the top.

This is only a model, and if I change the function, I may change the time and deciding state. But I gather from this that Election Night will be over with by 11 pm EST, and maybe even by 10 pm, and that the deciding state will probably be one of these: California, North Carolina, Indiana, Missouri, Florida, or possibly Nevada, although that is more remote.

Ambiguous Children's Number Puzzle

2008-03-04T05:07:00.001-08:00

This morning's Kidspot in the Richmond Times-Dispatch features a number puzzle entitled "Sum Fun". The puzzle is given as follows. An array of circles is given as:

	O
O	O	O
	O

The numbers 2, 3, 4, 5, and 6 are also shown. The instructions say "Here are five numbers to play with. Put one number in each circle so that the numbers down and across add up to twelve."

Call the numbers N, C, W, E, and S, for the cells in the northern, central, western, eastern and southern circles. Then we can write down two equations:

N + C + S = 12
W + C + E = 12

We have one other equation:

N + C + S + W + E = 20

as that is what the numbers sum up to. Further, all five of them have to be integers between 2 and 6. If we subtract the third equation from the first two, we get:

N + S = 8
W + E = 8

So how can one express 8 as the sum of two numbers? 1+7 is no good. 4+4 does not work because there is only one 4. There are no 1s or 7s in the puzzle. 2+6 and 3+5 are the possibilities, but because of commutativity, 6+2 and 5+3 are also possible. Therefore, one of N+S and W+E has to consist of 2 and 6 and the other one of 3 and 5.

The solution given in the puzzle is:

ANS: ACROSS: 2, 4, 6. DOWN: 5, 4, 3.

Yes, that solves the puzzle. But all the puzzle implies is that one of N+S and W+E is either {2,6} or {3,5} and the other one is the other of these. But then that means that Across: 6, 4, 2; Down 3, 4, 5 is just as good a solution. In fact there are eight solutions, because one could take either 2+6 or 6+2 and either 3+5 and 5+3 and one can put the 2 and 6 across or one could put the 3 and 5 across. The solutions are:

ANS: ACROSS: 2, 4, 6. DOWN: 5, 4, 3.
ANS: ACROSS: 2, 4, 6. DOWN: 3, 4, 5.
ANS: ACROSS: 6, 4, 2. DOWN: 5, 4, 3.
ANS: ACROSS: 6, 4, 2. DOWN: 3, 4, 5.
ANS: ACROSS: 5, 4, 3. DOWN: 2, 4, 6.
ANS: ACROSS: 5, 4, 3. DOWN: 6, 4, 2.
ANS: ACROSS: 3, 4, 5. DOWN: 2, 4, 6.
ANS: ACROSS: 3, 4, 5. DOWN: 6, 4, 2.

There is a chess-problems term for this type of puzzle that is given as having The Solution, but instead has many solutions. Such a puzzle is said to be cooked. This puzzle is cooked. The authors should have checked this before putting it in the paper. The answer they give is correct, but it is not the only one. A special danger of this type of misproblem is that it teaches children that there is only one way of doing things, that there is only One Answer. This stifles creativity in children. We have enough institutions in our society that insist that there is only One Answer, including government institutions, corporations, special interest groups, and especially religions. United Feature Syndicate should check their Kidspots before they publish them.

Algebra Problem Helps to Determine Who Wins in November

2008-02-07T13:49:00.001-08:00

In Beyond Opinion, I mention that Romney's quitting means that Lichtman Key 2 will probably stand. This could affect who wins in November. So the question is, how many Romney delegates would have to go to Huckabee (or Paul) to topple Key 2?

Here is the present delegate count:

McCain 714
Romney 286
Huckabee 181
Paul 16

Now suppose x of Romney's 286 delegates go to McCain. The 286 - x delegates go to Huckabee, say (they could go to Paul, too, but that does not affect the result). In that case, the delegate counts would be

McCain 714 + x
Romney 0
Huckabee 181 + (286 - x)
Paul 16

We want to know at which value of x McCain's vote is less than twice that of his competitors combined; i.e., when Key 2 falls. The resulting inequality and its solution:

714 + x <= 2(181 + (286 - x) + 16)
714 + x <= 2(483 - x)
714 + x <= 966 - 2x
x + 2x <= 966 - 714
3x <= 252
x <= 84
286-x >= 202
202 / 286 >= 72%

This means that at least 72% of the Romney vote would have to go to Huckabee. Instead, there probably will be pressure on Huckabee to withdraw, and that will clinch it for McCain and secure Key 2 as well.

Elections are good sources of algebra problems, and I will make more mention of these in the future.

Predicting a Primary Winner before CNN Does

2008-01-21T13:17:00.001-08:00

It is primary season, and several primaries are being held. After they are held, the networks show the returns and eventually call winners. Sometimes they call winners immediately after the event closes, as with the Nevada Republican caucuses on 2008 January 19, when they called Romney the winner. However, at night they did not call for a long time the winner of the South Carolina Republican primary, nor the Nevada Democratic caucuses, which were held the same day.

Nevertheless, I was able to call the winner in the South Carolina primary at 7:16 pm, as described on my Beyond Opinion site. How did I do this?

It turns out that CNN provides election totals for the candidates after the polls or caucuses close. These don't help with close contests because they can easily reverse. CNN does carry out exit or entrance polls, however. These list the vote according to various aspects of the electorate, including male/female, church attendance, party affiliation, feelings on immigration and so forth. Here is an example of one of the exit polls in the Republican South Carolina primary, after extracting to Microsoft Excel:

Feelings About Bush Administration	Candidate	Huckabee	McCain	Romney	Thompson
Enthusiastic	-0.17	0.28	0.34	0.18	0.18
Satisfied	-0.52	0.35	0.3	0.14	0.17
Dissatisfied	-0.25	0.29	0.38	0.14	0.13
Angry	-0.05	0.15	0.44	0.22	0.12

It shows the percentage of the electorate in each of four categories: Enthusiastic, Satisfied, Dissatisfied, and Angry, in parentheses. Excel thinks these are negative numbers, and so it stuck minus signs in front of each entry. But they are really positive, and they give the percentage distribution of the electorate across these four categories. Note that I have deleted the minor candidates to avoid distorting the web page with a wide table. This means that the row sums will not add up - the difference is the total of the minor candidates.

For each category, it shows the percentage of each of the votes for the category according to the candidate they voted for or supported. So those who were Satisfied with Bush voted 2% for Giuliani, 35% for Huckabee, 0% for Hunter, and so forth. The 35%, or 0.35, then shows a conditional probability: the probability that a voter voted for Huckabee given that he was satisfied with Bush. The formula for a conditional probability is:

p(A|B) = p(A & B)/p(B)

where A & B means both A and B.

Therefore:

p(Huckabee|satisfied) = p(Huckabee & satisfied)/p(satisfied)

Now if one sums over all the categories, one gets:

P(Huckabee|satisfied) = p(Huckabee & satisfied)/p(satisfied) + p(Huckabee & enthusiastic)/p(enthusiastic) + p(Huckabee & dissatisfied)/p(dissatisfied) + p(Huckabee & angry)/p(angry)

But this is the same as

P(Huckabee|satisfied or enthusiastic or dissatisfied or angry)

This is simply p(Huckabee), the percentage of the vote that went to Huckabee, assuming a person being polled could not say "none of the above". So this gives us a means of finding out for each candidate what percentage of the vote went for each candidate.

To do this, one must take pairwise products of two columns from this array, and add these together. It turns out that Excel has a function, namely SUMPRODUCT, that does this. So one could enter in the box below the Giuliani column:

-SUMPRODUCT($B2:$B5,C2:C5)

And this gives the Giuliani vote. Then simply copy across the candidates. I put a minus sign in front to counteract the unwarranted assumption that Excel made about the category distribution percentages being negative. The dollar signs tell Excel to keep this coordinate at B; that is, always use the category percentages rather than move across the spreadsheet. The result is:

Feelings About Bush Administration	Candidate	Huckabee	McCain	Romney	Thompson
Enthusiastic	-0.17	0.28	0.34	0.18	0.18
Satisfied	-0.52	0.35	0.3	0.14	0.17
Dissatisfied	-0.25	0.29	0.38	0.14	0.13
Angry	-0.05	0.15	0.44	0.22	0.12
		0.3096	0.3308	0.1444	0.1545

And this shows that McCain won with 33% of the vote, with Huckabee at 31% of the vote, Thompson with 15%, and Romney with 14%. These numbers and hence my spreadsheet analysis were available for 30-45 minutes before CNN called the race for McCain.

I did the same with the Democratic caucuses in Nevada and concluded that Hillary Clinton won. This technique will be useful for all the following primaries, provided CNN provides an exit or entrance poll immediately after the polls close and does not call a winner right away. It is good to double check by using two or three of the categories, to be sure about the same results are obtained each time.

How good is this technique? Only as good as the exit polling of CNN (and other networks). Exit polling is much more reliable than election returns, since they cover the entire state, rather than first the urban results and then the rural ones that require hand-counting, for example. There has been only one major error of an exit poll that I know about, namely the call of Florida for Gore in 2000.

Tricky Triangles

2007-12-13T16:50:00.000-08:00

One of the items I find in the comics area of my newspaper, the Richmond Times-Dispatch, is an item for children called Kidspot, by Dick Rogers. I have been watching these Kidspot cartoons ever since one such item suggested nonsensical notions like that of an eyeball room (I never want to be in one of those) or an eardrum stick, which would be met with disapproval by health professionals. See my companion blog, Beyond Opinion, for details.

Today I found another questionable cartoon. It consists of this arrangement of dots:

.

The text runs:

TRICKY TRIANGLES. How many triangles can you make by connecting three dots at a time? Connected triangles can count as larger triangles.

I am not sure what Dick Rogers means by connected triangles being larger triangles. This is what he gives as the answer:

Ans: There are 24 possible triangles.

This is wrong. There are 50 possible triangles. To show this, note that there are eight dots, and that any three dots either define a straight line or define a triangle. The total number of collections of three of these dots is:

C_8,3 = 8!/3! = 1*2*3*4*5*6*7*8/(1*2*3)*(1*2*3*4*5)

=(8*7*6)/(1*2*3) (since the 1*2*3*4*5's cancel)

= 56.

There are 6 ways of constructing straight lines. There are two vertical lines, and four straight lines that make one X on top of another one. Subtracting this from 56 gives 50 possible triangles.

Here are some possible triangles:

Mr. Rogers should have checked his calculations. Maybe he did not consider the magenta or green triangles.

Sodoko

2007-07-09T11:44:00.001-07:00

One of the latest crazes to hit the world recently is Sudoku, the game of Number Place, wherein you are given a 9x9 square divided into 3x3 squares or blocks, with some of the cells filled in with numbers from 1 to 9. The object is to fill the remaining cells so that each row, column and 3x3 block has one and only one of each number from 1-9. That automatically makes a completed Sudoku puzzle a Latin Square.

Just today I received in the mail a book written by Philip Riley and Laura Taalman, entitled Color Sudoku. It is a collection of unusual Sudoku puzzles. The cells in these puzzles are colored with usually 9 colors, and the object now is to make it so that you have one and only one of each color in each row, column, and color; or in some cases, in each row, column, 3x3 block, and color. Some of these have each position in the blocks as a separate color. For example, the upper left cell of each block will be one color, the center left will be a different color, and so forth.

I call this game Sodoko, and I would like to show why I call it that and show an interesting symmetry; in particular, for each Sodoko puzzle, there is another Sodoko puzzle that looks completely different, yet is essentially the same puzzle; I call this the "dual puzzle".

In an ordinary Sudoku grid, some of the cells are filled in with numbers. For example, in row 3, column 6, there could be a 7. This can be thought of as the triple 367. However, we can break down the 9 digits into doubles of digits from 0, 1, and 2: 1 is 00, 2 is 01, 3 is 02, 4 is 10, 5 is 11, 6 is 12, 7 is 20, 8 is 21, and 9 is 22. Then our cell with the 7 in it can be expressed as 021220. This shows that each filled cell can be represented as a 6-tuple of elements from {0, 1, 2}, or alternatively, as a 6-tuple of elements from the finite field of 3 elements, Z3. A Sudoku puzzle then is a database, where there are 6 fields, and each record has an element of Z3 in it for each field.

The requirement that there be only one and only one digit of each kind in each row can be expressed by saying that if you specify only fields F1, F2, F5, and F6, then the resulting database contains no duplicates. In SQL language, that could be rendered as something like "select F3, F4, F5, F6 from sudoku". The requirement then says that this query contains no duplicates and contains each combination of digits in F3 and F4. Note that we omit F1 and F2 from the fields, so we can say that this requirement is a 12 requirement.

The requirement that there be only one and only one digit of each kind in each column can be expressed by saying that if you specify only fields F3, F4, F5, and F6, the resulting query has no duplicates and contains each combination in fields F1 and F2; hence this is a 34 requirement. Finally the requirement that each 3x3 block has one and only one digit of each kind is the same as saying that if you specify only digits F2, F4, F5, and F6, there are no duplicates. So we say that this is a 24 requirement. This is because specifying F1 and F3 specifies a 3x3 block. Note that the three requirements can be diagramed 12. 24; 43, and this diagram would have 1 and 3 at the upper corners of a square, and 2 and 4 at the lower cornerss. Connecting the diagram using 12. 24; 43 results in something that looks like a U, and I note that there are two U's in "Sudoku".

How about the requirement that each color has one and only one of each digit? That can be thought of as specifying F1, F3, F5, and F6 and requiring that this have no duplicates. This is because F2 and F4 describe the coordinates within a 3x3 square, for example, 12 is the bottom center cell of the square. All the bottom center cells is a color. So now we are including requirement 13, which connects the two top ends of the U and makes it into an O. So likewise, I replace the U's in "Sudoku" with O's and get Sodoko.

I also note that each Sodoko puzzle has a twin puzzle that looks different but is essentially the same puzzle. This is done by interchanging fields F2 and F3. A row is represented by the first two coordinates, but now this is F1 and F3, so this corresponds to a block in the original puzzle. A column now corresponds to a color. A block corresponds to a row, and a color corresponds to a column. I call this the dual puzzle of the original puzzle. Therefore the two puzzles have equal difficulty, and if you complete one, you can complete the other simply by reading the numbers off from the first puzzle.

Sodoko is in some ways more satisfying than Sudoku, as it is more symmetrical. It is a little harder, and adds a bit of pizzazz to Sudoku, so go buy "Color Sudoku" and try a few of them.

Virginia's 74th Magisterial District Democratic Primary

2007-06-14T06:05:00.001-07:00

On 2007 June 12, primaries were held in the state, or Commonwealth, of Virginia. Among these were the Democratic primary for the 74th Magisterial District, which includes a huge portion of Henrico County and parts of the cities of Richmond and Hopewell and Charles City County. This primary was hotly contended by five candidates. It looked like a four-candidate race until Joseph D. Morrissey, a former Commonwealth's Attorney, barged into the race. Here are the results:

Joseph Morrissey	2,055	38 %
Floyd Miles	1,488	27 %
J.M. "Jackie" Jackson	1,053	19 %
David Lambert	545	10 %
Shirley McCall Goodall	285	5 %

Morrissey won easily, leading his next challenger by 11%. Sic semper tyrannis. This character has been disbarred by the Virginia bar and cannot practice law. He has gotten into two fist fights with others in the courtroom, and has been the object of lawsuits and has served time in jail. How did he get elected, then? Part of it was that the people don't like what government is doing. That is why Morrissey, a white person, got a huge vote in a mostly black district. But that does not explain it all. 62% of the voters voted against Morrissey; they voted for someone else. So how did Morrissey win?

It is the election system that allowed him to win. The 62% that were opposed to him split among four candidates. All of Morrissey's support went to Morrissey. So Morrissey won. Is this a fair system? I wouldn't think so. 62% of the electorate did not want him in. However, 95% did not want Shirley Goodall elected. But Shirley has hit no one, that I know of, has not served jail time or otherwise been controversial. The difference is that although Morrissey was first place among 37% of the voters, I suspect most of the rest rated him last or next to last.

That is why a runoff system would be better. In that system, if a candidate wins more than 50% of the vote, he wins. Otherwise, there is a runoff election involving only the top two candidates. If that had happened, I suspect the result would have been something like:

Floyd Miles	3,071	57%
Joseph Morrissey	2,355	43%

This is because all but 300 of the voters of the other candidates voted for Miles rather than Morrissey (these figures are hypothetical). The flaw with the existing system is that although it reflects voters' first choice among those running, it does not reflect their second or later choices.

This type of paradox has happened before, sometimes with devastating results. In Chile, Salvador Allende was elected president in a three-way race; his percentage was in the upper 30s. He was a Marxist, and that displeased some people in the administration of the United States. Some undercover figures there engineered a coup, resulting in a repressive dictatorshop under Augusto Pinochet for many years. In Minnesota in the late 1990s, the world champion wrestler Jesse Ventura won as an independent over the Democrat and Republican with a vote in the mid to upper 30s. I don't know if Jesse would have won if a runoff had occurred.

There are other voting systems around. An improvement in the runoff scheme is what I call the Olympic system, because the Olympics use it to decide sites for their Games. In this system, if a majority vote occurs, that wins the election. If it does not, the last place city is dropped from contention and another runoff occurs. If a majority occurs, that wins the election. Otherwise, the last place of those remaining is dropped and another runoff occurs. This continues until a majority occurs, which it will unless it ends in a tie between the remaining two candidates. There are flaws in these systems as well. No system will be perfect.

One system seems to stand out. In approval voting, voters are asked to pick any number of candidates, not necessarily one. Of course voting for all the candidates is equivalent to throwing your vote away, because you are not expressing a preference among them. This system (and all the others I have described here) are the same for two-candidate contests. In a three-way contest, voting for two of the candidates is effectively a vote against the third one. This allows voters to express dissatisfaction with a candidate. The Mathematical Association of America and American Mathematical Society use this system in their elections.

I suspect that if approval voting had occurred, so many votes for {Miles, Goodall, Jackson, Lambert} would have occurred that there is no way Morrissey would have won.

Baseball Musical Chairs

2006-09-23T16:45:00.000-07:00

It happened sometime in the spring of this year (2006). The Ottawa Lynx AAA baseball team was bought out by two Philadelphia businessmen, Joseph Finley and Craig Stein. They reached an arrangement with the Philadelphia Phillies by which the Lynx would become the Phillies AAA farm team, which would move to Allentown in 2008, when a new stadium there is built. Allentown and Philadelphia are only 54 miles apart as the crow flies.

Would you believe that just this little double play by these two men would cause a free for all, and then a five-way swaperoo of AAA minor league teams among the majors?

When the Scranton Wilkes-Barre Red Barons, the current Phillies farm team, found out about this, their fans were upset. They wanted to find another major league team to be their parent team. The early word was that this team would wind up being a Baltimore farm team. Seems logical. Swap teams. But the fans clamored for something better. They appealed to major league teams all over the place, and especially the ones in New York City. Pretty soon both the Yankees and Mets became interested and they jumped in the fray.

Discussions between the Red Barons and the Yankees got the Columbus Clippers, present farm team of the Yankees, worried. Columbus started appealing all over the place, and the Orioles and Mets showed an interest. The Norfolk Tides became annoyed. Actually they were annoyed for some time. They did not like their parent team, the Mets. The Mets ignored them. So they took this ruckus as an opportunity to search for something better. This is another case of a minor team turning its back on its parent major league team, with the first one being the Rochester Red Wings' rejection of the Baltimore Orioles in 2002. To top it off, the Washington Nationals did not want any more of the New Orleans Zephyrs. Too far, it seemed. So they jumped in the fray.

Today the whole thing settled out to what amounts to a five-way circle-around among the five major league teams. The Phillies got their Lynx, which will become the Allentown Allies, I suppose. The parent team of the Lynx, the Baltimore Orioles, got into an agreement with the Norfolk Tides. (How strange. The Tides, rejecting the Mets, picked the team that was rejected by the Red Wings.) The New York Mets got left out and were forced to sign with the New Orleans Zephyrs. That's even farther than Washington. The Washington Nationals got into a deal with the Columbus Clippers, and the New York Yankees got their team in Scranton Wilkes-Barre to complete the cycle.

I am wondering why the Mets settled for the Zephyrs. Couldn't they have gone after the Durham Bulls, which would have resulted in the Zephyrs getting something closer also - the Tampa Bay Devil Rays?

So how does this affect the travel budget of these pairs of teams for players and other officials going back and forth between the major league city and the AAA city? This year, the total of the crow-miles for the five pairs of teams was 2267 miles. After the swap, the total miles will be 2160. So they saved some mileage. They will save even more after the Lynx move to Allentown; the miles will go down to 1830.

But this is not the best they could achieve. If the ten teams had gotten together and picked the assignment that minimizes the crow-mile total, they would have paired as follows:

Baltimore Orioles - Columbus Clippers
Washington Nationals - New Orleans Zephyrs
Philadelphia Phillies - Norfolk Tides
New York Mets - Ottawa Lynx (and then Allentown Allies)
New York Yankees - Scranton Wilkes-Barre Red Barons

The total crow-miles would now be 1983, and after the move to Allentown, they would be 1723. The optimal assignment is the same regardless of the location of the Lynx.

This shows that major league teams use other criteria for locating their minor league teams than distance (hence fuel) costs. With shortages of oil coming up, they should have considered the minimal-mile arrangement above.

By the way, I tried this for all 30 pairs of major and AAA minor league teams a year ago, and published the result in Blogtrek. I thought it strange that it assigned the Twins to the Norfolk Tides and the Columbus Clippers to the Milwaukee Brewers. Today I found that I had entered the latitude and longitude incorrectly for Columbus and Norfolk. In addition, the Red Barons will relocate to Allentown. I will have to redo the overall assignment. Watch for the results.

Note to operations research instructors. This blog provides an example of an assignment problem and the use of the Hungarian algorithm to solve the problem. I used the Hungarian method to come up with the above pairing. The hardest part of setting this problem up is finding the 435 distances between major and AAA cities. I just simply used the latitude and longitude and used a trigonometric formula to find the crow-distances.

Knoxville Mathematics

2006-08-29T13:23:00.000-07:00

Earlier this month I attended Mathfest 2006, a conference sponsored by the Mathematical Association of America in Knoxville, TN. It was an interesting convention, held in the downtown area at the hotel I was staying at and at the Knoxville Convention Center, which was next door to the yellow sphere that symbolizes the World's Fair that was once held in Knoxville.

Most of the talks were on how to teach mathematics and what are the best way to teach a certain theory to the public at large. There were three talks on Sudoku, the 9x9 square craze of the past couple of years. One gave us the variations on Sudoku, another told us to some extent how to solve a Sudoku, and the third one showed how to program a computer to solve a Sudoku puzzle.

The invited addresses included an interesting one on knots, in which the presenter enumerated the types of knots there were, and gave us some knot invariants, such as the Alexander polynomial. None of these completely characterized knots; in fact the Alexander polynomial flunked tenderfoot, because it can't tell a square knot from a granny knot. Another talk was about the Yawp of Mathematics. What is Yawp? Watch the movie "Dead Poets Society" and find out. It means getting excited about finding something striking or beautiful in mathematics.

Another talked about whether 9 to the 9 to the 9 to the 9 to the 9 power or 9!!!! was bigger. The presenter asked for the biggest number with 5 symbols. I tried 9^^^9, where ^ is an up arrow, but he would not allow that type of notation and wanted to stick to ^ (exponentiation) and below. Turns out the answer is neither but rather (9 to the 9th)!!!

One section dealt with mathematics in popular culture. Now this is interesting. Popular culture is dominated by prima divas, murder cases, silly sitcoms, wardrobe malfunctions and other such highly illogical and immathematical pursuits. So how can mathematics slice through this muck? The TV show NUMB3RS helps, and one presenter analyzed the mathematics of this show. The Simpsons had one episode wherein the equation 3987^12 + 4365^12 = 4472^12 was written on the board. No, Andrew Wiles. Your proof of the Tanayama-Shimura conjecture is still intact. Note that the left side is divisible by 3 but the right isn't. One presenter showed us how to model Yoda's robe which was swinging around all over the place. It wasn't too easy. Another analyzed mathematics in movies after noting that these movies never made it to the Box Office: Math Wars, f(x)Files, Lord of the Ring of Matrices, and e^t, as in e^t phone home. Another speaker delved into mathematics and mental illness, using A Beautiful Mind and Proof as examples. He could have included Georg Cantor, Kurt Gödel, Theodore Kaczynski (the Unabomber), and Paul Morphy (the chess genius). This is an interesting topic - is there a relationship between mathematics and mental illness, or are there enough Paul Cohens running around to disprove such a relationship?

The most interesting night was when we all went on a riverboat cruise aboard the Star of Knoxville on a stormy night, which gave us a dramatic scene of Knoxville in twilight with a severe storm's lightning in the area, and in which we got back to our hotel rooms just minutes before the storm hit.

So when am I going to another major mathematics conference? The American Mathematical Society/Mathematical Association of America conference this January is in New Orleans. How can this be? The convention area was not hit by floods, and holding a convention pumps money into an economy that desperately needs it. The convention's events will be at two large hotels, not at the infamous Convention Center. All the fixings of New Orleans, including the Vieux Carré and New Orleans jazz, will be there. So maybe that is a good convention to go to, but I will drive there if I go, even though it is a two-day drive, because of all the stuff that has been occurring on the airlines recently.

How to Find a Lock Combination

2006-06-13T19:39:00.002-07:00

I sorted out my safe recently and decided that many papers and other items don't need to be in a safe. I saw a couple of Master padlocks there and wanted to keep them outside the safe. But I wanted to keep them only if I knew the combinations. I had a whole bunch of note papers with combinations on them and tried them out on the two locks. I quickly opened one of them, so I tagged it with its combination and put it away. But the other one would not open. So I threw it out.

I wondered about that. It's a perfectly good lock. The only reason why I want to throw it out is that I did not know its combination. Was there some way I could get that combination by fooling around with lock somehow? The existence of some way could endanger the security of the lock, but I wanted to do something other than throw it out.

I looked on the Web using Google and found Electroatomics. The site gave a procedure for finding the combination of a Master padlock. It's a good site, and is its owner's most favorite page. I looked through the instructions and it said to turn the lock to 0 (the numbers range from the real numbers 0 through 40, but combinations are given in integers). So I did that. Then it said to pull on the hasp and turn the dial. Which direction? It did not say. I turned it towards the forward numbers, 1, 2, and so forth. But how can I when the hasp was pulled? After some monkeying around I found that I could hop from stable "settle" point to point. The instructions say to move the dial of the lock until it hits these points and record them. They say there should be 12 of them. I tried that and got a series of numbers. They could be right on the integers, as 13, or they could be in between, like between 18 and 19. In that case record an 18.5.

He then says that there should be seven numbers ending in .5. He says these are decoys. He says look at the numbers that end in .0; i.e., integers. There should be five of these. In his example, he said he got 32, 22, 19, 12, and 2. They all end in the same digit except one. That one is the third number of the combination. So in his case, the lock's combination ended in a 19.

I tried that with the lock I had and got a series of numbers. But different times I did it, I got slightly different numbers, and I was getting 6, or 8, or something like that numbers ending in .5. The whole thing was wishy washy to me, and the integers I got had at least two repetitions of two integers, so I could not identify the third number of the combination. I reread the instructions and it said to turn it back and forth to see what range of numbers it would go in. He said if it went between 4.5 and 5.5, record a 4, and if it went between 4 and 5, record 4.5. I was not getting just exact readings and .5s however. I was also getting .8s and .3s and other such stuff. So the whole thing became really confusing. I put these results in a table, where left is as far left as I can get the stop point, and right is as far right. Avg is simply the average of those two numbers:

	Left	Right	Avg
1	-0.5	0.5	0
2	2.8	3.8	3.3
3	6.0	7.0	6.5
4	9.8	10.8	10.3
5	12.8	13.8	13.3
6	16.0	17.0	16.5
7	19.6	20.5	20.05
8	22.8	23.8	23.3
9	26.0	27.0	26.5
10	29.5	30.5	30.0
11	32.8	33.8	33.3
12	36.0	37.0	36.5

This still did not tell me much. I tabulated the 0s, the .3s, and the .5s, and got 3, 5, and 4 readings respectively. This did not match at all what Liam Bowen said I would get. I looked at the readings. The five .3s gave me 3, 10, 13, 23, 33, which according to Bowen's rules would say that 10 was the third number of the combination. But these are .3s, not integers. I noticed that the .5s gave 6, 16, 26, and 36, so that there is more than one sequence of numbers all ending in the same digit. So I tried something different. I rearranged the numbers into a 3x4 array:

0	3.3	6.5
10.3	13.3	16.5
20.05	23.3	26.5
30	33.3	36.5

Now it comes out. Each column looks like it lines up nicely except the first, where the 10.3 sticks out like a sore thumb. I was now certain that the third digit of the combination was 10.

I tried this out on a lock whose combination I knew. The combination ended in a 27. I tried the same table technique and, sure enough, the 27 was different from the others.

So that now I know the third number is a 10, Bowen then makes a lengthy explanation of what "mod 4" means. What he says is that that x - z = 0 mod 4, and that x - y = 2 mod 4, where the combination is x-y-z. This means the first number is one of 2, 6, 10, and so forth, and the second number is one of 0, 4, 8, and so forth. So now there are only 100 combinations to try.

I tried them one at a time, and none of them worked. Just as I was about to exhaust all the combinations, I pulled on the hasp. It unlocked! I had found it! I memorized the number (of course I won't give the result here as it would compromise the lock). But I had found the combination and now don't have to throw the lock out.

So the procedure for finding the combination of a Master Lock (it has to be a Master, according to Bowen) is:

1. Turn the dial while pulling the hasp out. There should be 12 points at which it "settles" (Bowen calls them "clicks").

2. At each point, turn the dial back and forth until it won't go and record the results to one-decimal accuracy. The result should be a table giving 12 left and right readings.

3. Take the average of each row of this table.

4. Rearrange these averages into a 3x4 table, putting 3 readings in the first row, 3 in the second and so forth.

5. Find the number whose decimal does not jibe with the other entries in its column. This number is the third number of the combination. Call this z. Call the combination x-y-z

6. Test all combinations of values of x and y, where x is congruent to z mod 4, and y+2 or y - 2 is congruent to z mod 4.

7. One of these should be the lock's combination. If this does not work, you made an error somewhere or they have manufactured a new type of lock.

Baseball Sudoku

2006-05-18T19:20:00.000-07:00

The latest craze hitting the world is Sudoku, the American game of putting the digits 1-9 into a 9x9 grid separated into nine 3x3 sections such that each row, column, and section contains exactly one of the digits from 1-9. Sudoku puzzles appear in the paper each day, and there are many web sites with puzzles on them. There are many variations on the Sudoku theme, including overlapping puzzles, Sodoko (certain 9-patterns must have 1-9 as well), the Monster (certain sums have to add up), and so forth.

A rather unusual application appeared recently on the Web, although I had thought of it months ago. Nine is the number of cells in a row or column in Sudoku, but 9 is also the number of members of a baseball team. So how about a baseball sudoku? The one I had thought of was to replace the numbers (which really aren't numbers; adding 2 to 4 to get 6 in a puzzle does not make sense) with baseball positions. Certain cells are filled with positions, such as c (catcher), 1b (first baseman), cf (center fielder) and so forth. The idea is to fill in the rest so that each row, column, and block constitutes an entire baseball team. Big deal. This is just ordinary Sudoku with baseball positions in it.

As any baseball fan knows, many players can play several positions. For example, a center fielder can play right field, a shortstop can play second base and so forth. So the idea is to provide as clues not positions, but real major league players, some of whom can play more than one position. The idea is to fill in the remaining squares with real players and designate the positions of each of these players so that each row, column, and block contains a complete baseball team. This is equivalent to a variation of Sudoku where the clues are choices of numbers, saying this square is either a 3 or a 5. A variation on this would be to make it so some special rows, columns, or blocks are from the same team, so that it's conceivable that this team of players could actually be fielded in a real baseball game.

So if you are going to do baseball sudoku, do it right. Don't just make it plain old Sudoku with baseball labels. Get some baseball into it, too. And by the way, make sure you use only National League players. If you use American League players, that injects a tenth position into the puzzle - the designated hitter. You no longer then have the nice 9x9 square, if 10 positions have to be filled.

Bigamy Logic

2006-03-03T16:57:00.000-08:00

I heard about a bigamy case in Fairfax, Virginia today. This man had married seven women, with some of these overlapping, and was exposed when a woman who would be his eighth wife saw him on Dr. Phil and called police. Last year, charges were pressed against him for marrying his seventh wife while married to his sixth wife. However, the authorities dropped the charges when it was decided that the marriage to number 6 was invalid because at that time he was still married to number 5.

This must have been some character, all right. I suspect his motive was money; in each case, he seemed to have cleaned out his wife's bank accounts. But this brings up an interesting question. When someone starts committing bigamy like this over and over again, which of the marriages are valid and which are not? For example, in the case above, maybe the authorities could have convicted him because he was validly married to his sixth wife, because his marriage to his fifth wife was invalid because at the time of that marriage, he was married to his fourth wife. I don't know if this was really the case; I suspect it was not. One can continue with this for some time; for example, maybe the marriage to number 7 was invalid after all because the marriage to number 4 was invalid since he was married to number 3 at the time. Or maybe it was valid, because marriage 3 could have been void because he was married to number 2 at the time. Or maybe it is invalid because when marrying number 2, he could have been married to number 1. But that ends it. Any marriage that you make with your first spouse is valid; or at least it can't be invalid because of bigamy. So the lout's marriage to his seventh wife was invalid. But that's only if all this overlapping occurred.

Suppose then that a man does the following:

Marries Annette;
Marries Betty while still married to Annette;
Divorces Annette;
Marries Cindy while still married to Betty;
Marries Dorothy while still married to Cindy;
Divorces Cindy;
Marries Ethel while still married to his other wives;
Divorces Betty;
Divorces Ethel.

Which of these marriages were valid? I am assuming that statements saying he divorced someone are to be striken from this account if the marriage that is being divorced is invalid. Don't scroll any farther if you want to find out.

Answer: His marriage to Annette was valid. His marriage to Betty was not valid. His marriage to Cindy was valid, since his marriage to Betty was not valid, and he had divorced Annette. His marriage to Dorothy was not valid. His marriage to Ethel was valid, since he divorced Annette and Cindy and since his marriages to Betty and Dorothy were not valid. After divorcing Ethel, he is all by himself with no wives.

In general, how do you determine who a bigamist is legally married to when you are given his list of marriages and divorces?

A Tale of Two Numbers: Omega and The Number

2006-02-10T08:47:00.000-08:00

Yesterday (2006 February 9), I ran into two numbers that are important in our lives. They help describe the logical world we live in, as well as our state of well being in it. Neither of these numbers can be computed precisely, for different reasons, but they nevertheless exist.

One came in an issue of Scientific American which arrived in my mail yesterday. That magazine contained an article called "The Limits to Reason", which describes a number defined by Gregory Chaitin and denoted by Ω, capital Omega. This number is defined by the probability that if a randomly chosen computer program is chosen, that it will halt. Now programs on these PCs that we use need to be designed to halt. If it doesn't, the computer freezes up, and I call that "bombing" or "crashing". So in a sense, Ω is the probability that if a computer program is run, that it will not bomb the computer. This number is not computable. In terms of my paper Hamlet II, it is an ultimately indescribable number. In that article, I show how Georg Cantor demonstrated that such numbers exist, but I did not give any examples of such numbers. Ω is an example of such a number. (Don't confuse Ω with ω, the first transfinite ordinal number, defined by Cantor, and Ω, sometimes used to denote the class of all transfinite ordinal numbers. Ω is a real number.)

Why? It derives from the famous Halting Theorem of Turing, which says that no computer program can be constructed that inputs a computer program as input and outputs whether the program, if executed, will halt or not. Another way of putting it: There can be no perfect Crash Guard. The proof of this, in a sketchy form, can be given like this. Suppose there were such a program P. Let's hack that program. Find the places in the code where it says that the input program will halt, take out the termination statement and replace it with something like A: go to B; B: go to A. Then go to those places that say that the input program will never halt, and put in the warning "Do not execute this program. It will never end, and it will bomb your computer." and follow that with a statement that halts the program. Call the hacked program H. H still inputs computer programs as input, so feed it the program H itself. Suppose this program halts. Then H will detect that, and it will go into the AB loop above and never halt. Contradiction. Suppose H never halts. Then H will detect that, print out the warning and stop. That is also a contradiction. This shows that H cannot exist, and therefore P can't either. There are many important derivative results of this theorem. For example, given a group with generators and relations and an element of the group, no computer program can compute whether that element is the identity element or not. Also there is no terminating algorithm that solves all Diophantine (answers have to be integer) systems of general polynomial equations.

And it shows that Ω is ultimately indescribable. For if I could describe it to you, then I could write a computer program to compute it, and then I could hack that program to yield a program that tells whether a computer program will halt, counter to Turing's theorem.

Chaitin has a number of other interesting observations. The most interesting, I found, was this remark:

Comprehension implies compression.

This says that in order to comprehend something, a simple description or program needs to be found for it. For example, to describe π, I can say add up with alternating signs all the reciprocals of odd integers and multiply the result by four. Or perhaps I can simply say the circumference of a circle divided by the diameter. On the other hand, to describe 0.92659876193865, the simplest way I know is to say 9, 2, 6, 5, 9, …, 5 after the decimal point, which is as long as the number is. So π is a simple number, but 0.92659876193865 is not. To understand π, I think of the circle. So the more I compress a description of a number or mathematical concept, the more I understand. Hence Chaitin's statement.

Another comment he made was on the principle of sufficient reason. That says that everything has a cause. The condensation of water vapor causes rain, for instance. But Chaitin says that there has to exist "irreducible" numbers, numbers as complicated as 0.92659876193865 that can't be described any simpler than naming the digits. If we generalize this to arbitrary mathematical concepts, there must exist mathematical statements that have no cause. Not even for mathematics is the principle of sufficient reason true. Some things are just the way they are. "Cause was not the reason for the evening", says the singing group America; in fact, the entire song "Tin Man" seems to have no cause or reason for it; it just is.

The other number I met yesterday was in a library book entitled The Number, by Lee Eisenberg. This number is more prosaically defined. Each person has The Number, and for him it is that sum of money, such that if he possesses it, it will enable him to live comfortably for the rest of his life. There is a simple way to compute this number, given you can get the inputs. Total up all the expenses you have or would have in the life style you want. Divide the result by the interest that a typical money market fund or a CD gives, and the result is, for you, The Number. For example, if your expenses are $50,000 per year and the interest rate is 5%, then $50,000/0.05 = $1,000,000 is The Number. That's right, a modest amount like that yields a million dollars. That is a point made by the author: many, in fact, the majority, of Americans simply don't have The Number. This will result in trouble for them later when they age and retire, and the sum total of them will seriously jolt the national economy. So it is an important discussion, and I ask you to figure out what is Your "The Number". And by the way, it is computable, given that your expenses and the ongoing interest rates, are computable. It is not a Chaitin's Ω.

Cryptorithm in a Store Sales Receipt

2006-01-04T19:35:00.000-08:00

Cryptorithms are puzzles wherein one replaces the digits in an arithmetic computation with letters. The puzzle is presented with the letters, and the object is to find out what the digits were. A famous example is (ignore the dot)

. S E N D
+ M O R E
_________
M O N E Y

Don't read too much below if you want to solve the problem yourself. In this case, the M sticks out as an additional digit on the front end of the sum, so it has to be 1. S + M = O then becomes S + 1 = O. The possibilities are 9 + 1 = 0 and 8 + 1 = 0, because 9 + 1 = 1 is eliminated becayse that would make both M and O equal to 1. Therefore, O is 0. O is often confused with zero, as in calling this year Oh-Six. Usually, O is not 0. But this case is an exception. We were told that O is some digit, and we wound up proving that it is 0.

This reduces the problem to:

. S E N D
+ 1 0 R E
_________
1 0 N E Y

If S were 8, then a carryover would have to had to occur in E + 0 = N. This implies that E would have to be 9 and N would have to be 0; however, we have already assigned O to 0. Therefore, S is 9:

. 9 E N D
+ 1 0 R E
_________
1 0 N E Y

The sum now says EN + 0R = NE. So adding 0R to EN reverses EN's digits. When you reverse the digits of a number and subtract from the number, the result is always a multiple of 9. So with no carryover, 0R has to be a multiple of 9. If there is a carryover, 0R has to be 1 less than a multiple of 9. With zero as the first digit, that means that R has to be 8 or 9. 9 is already taken, so R = 8, and N = E + 1. The digits that are left are 234567. We can choose EN to be any two consecutive digits from this. But then two of the remaining digits have to differ by 10 minus the lesser of these digits, because of D + E = Y, which carries over. So if we select 23, two of 4567 have to differ by 8, which they don't. with 34, two of 2567 differ by 7; they don't. With 45, two of 2367 differ by 6; they don't. With 6 and 7, two of 2345 differ by 4. They don't. With 56, two of 2347 differ by 5; 7 and 2 differ by 5. So D = 7, Y = 2, E = 5, N = 6, and the solution is:

. 9 5 6 7
+ 1 0 8 5
_________
1 0 6 5 2

So that is what a cryptorithm, and this shows how you can solve one. SEND MORE MONEY is a moderately difficult cryptorithm. I expect cryptorithms, as interesting puzzles, to appear in puzzle books, newspapers, and recreational mathematics books. But take a look at what I found on a store receipt the other day!

What kind of a receipt is this? It says the Megan doll costs TOO. Well, yeah, things do cost too much nowadays. But then it gives as the subtotal QQOI. Whaaa?? Then I realized that the entire thing is a cryptorithm! Why would JC Penney put a cryptorithm on their sales receipts? Maybe they want their customers to solve puzzles. But I am game for this one. The complete cryptorithm is:

Megan Doll...TOO
Plush Dolls..TOO
Subtotal....QQOI
Sales Tax.....YP
TOTAL.......QWTI

I thought maybe O was a misprint or was intended to be a zero. It can't be, as 0 + 0 = 0, not I, whatever I is. For the same reason as before, Q must be 1. This means the double of a digit is 11. The only possibility is 5 with a carry, 5 + 5 = 11. So O + O must be O, with a carry. The only digit which has this property is 9: 9 + 9 = 19. So O is 9, and both dolls cost $5.99. This means that the Subtotal is $11.98, making I = 8. Now here at this point I used the fact that Virginia sales tax is 5%. This gives either 59 or 60 for YP. Since 9 has been used, YP must be 60. The total of QWTI then must be $12.58. Sure enough, this amount matched a figure on my check account statement.

So there it is. A cryptorithm on a sales receipt solved. Where else can we get mathematical puzzles? Suppose 9 players play 9 different other players in some 1-1 game, such as chess or racquetball. Suppose each of 9 weeks, each player must play a different player from the other team, and suppose there are three places for the games, and that every three weeks, the players rotate places. Suppose someone has half scheduled this tournament. The scheduling the remaining players is a Sudoku puzzle!

Or how about having Rubik's Cubes show up as airline schedules? Airline scheduling is harder than solving that infamous cube. There are many ways in which services and manufacturers could confront customers with puzzles.

In this case, I noticed some words. "Gift Receipt". Does a cryptorithm come with each gift? Maybe the idea was to hide the price, since most givers don't like to disclose the price to receivers. But look what happens when you substitute the numbers for the letters in the JC Penny cryptorithm:

0 1 2 3 4 5 6 7 8 9
P Q W . . T Y . I O

What does that say? Qwerty, that's what. The first line of characters on the typewriter keyboard. But P following O on the keyboard means that the 0 must follow the 9:

1 2 3 4 5 6 7 8 9 0
Q W E R T Y U I O P

But someone could have typed in these prices simply by typing the real prices with your hands off the home keys. What a code that is! It's easily cracked. But not everyone is going to solve cryptorithms or type prices in the computer with the hands misplaced. So I guess this code is safe.

Interesting. Penney's receipt cryptarithms. What will they think of next?

The Mathematics of Hybrid Cars

2005-09-28T18:19:00.000-07:00

This week I found an article on CNN's web page entitled "Hybrids: Don't Buy the Hype". Note that this link may become invalid soon. Here is a quote from it:

A hybrid Honda Accord costs about $3,800 more than the comparable non-hybrid version, including purchase, maintenance and insurance costs. Over five years, assuming 15,000 miles of driving per year, you'll make up that cost in gasoline money if the price of gas goes up immediately to $9.20 a gallon and averages that for the whole period.

This sounds like a math problem. Some of the questions that may be asked are "How much does a hybrid Honda Accord cost?" or "How many miles per gallon does the hybrid Honda Accord get? This is not a real type of question. It only exists because some people chose not to give some information. In this case, CNN chose not to state what the price of a Honda Accord was or how many miles per gallon it gets.

But what if we try to solve it? Let

H = cost of a hybrid Honda Accord
C = cost of a non-hybrid standard Honda Accord

The first statement then says:

H = C + 3800

The second statement assumes you will drive 15,000 miles per year over a 5-year period. That is 5 * 15,000 or 75,000 miles.

The third statement says that if it costs $9.20 a gallon for gasoline, then the costs of the two Hondas are the same. This seems somewhat more complex. Let the miles per gallon of the hybrid be h and let the miles per gallon of the standard car be c. Then the cost of fuel for the hybrid is:

75,000 miles / h miles per gallon * $9.20/gallon = $690,000/h

And for the non-hybrid:

75,000 miles/c miles per gallon = $690,000/c

The total cost of the hybrid is the purchase cost plus the fuel cost, or

H + $690,000/h = C + $3,800 + $690,000/h

And that for the standard car is:

C + $690,000/c

The story now states that these two are equal:

C + $3,800 + $690,000/h = C + $690,000/c

Or

$3,800 + $690,000/h = $690,000/c

This means we can't solve the problem for we have two unknowns in this equation and can't solve for either unless we know something more about these cars.

So now I leave these two problems as exercises:

1. Find c on the Internet; one way may be to Google for "Honda Accord 2005 mpg" or something like that. Then find h, H, and C.

2. Find h in terms of c and graph the result. What type of curve do you get?

Polyhedra and Conway's Notation

2005-08-05T20:17:00.000-07:00

It has been two weeks since SUUSI and it's a long wait until 2006. One of the things I did at this camp or conference was that I gave a workshop on how to weave polyhedra out of various construction paper strips. This led me to think about the polyhedra and reminded me of a neat site for them. This is George Hart's site, at www.georgehart.com in which he has VRML files of many polyhedra models. He even has a page on which you can design and construct your own VRML polyhedra, at

http://www.georgehart.com/virtual-polyhedra/conway_notation.html

This introduces a code by John H. Conway, author of "Numbers and Games" and of numerous neat mathematical things. Conway introduces about 12 operators or so, and 8 objects on which to operate. The operators include a for "ambo", which means take the in-between model (e.g., the cuboctahedron for the cube/octahedron pair) , t for "truncate", j for "join" (make rhombuses out of all the edges) and so forth. I found that there was only one basic object letter (except for prisms, pyramids, and antiprisms) and 6 basic operations. The letter is T for Tetrahedron. The operations are a (ambo), t (truncate), s (snub), d (dual), r (mirror-reverse), and p (propeller - not Conway's invention). I am going to consider only the first 4. I note that Cube, for instance, is daT, and Icosahedron (or I) is actually sT, the snub tetrahedron. Here are some of the other examples:

aaT Cuboctahedron (or aC)
asT Icosadodecahedron (or aD)
taT Truncated octahedron (or tO)
daaaT Trapezoidal Icosatetrahedron (or 24-hedron) (or deC)
ssaT The snub of the snub cube (Hart points out that there are four versions of this)

and so forth. These symbols form a logic of sorts with syntax rules; for example, dd = identity, ad = a, and sd = s. Not all of these can be formed with regular polygons; for example, datsT is Hart's favorite solid, the rhombic enneacontahedron (90-hedron). atsT is its dual, and this turns out to have pentagons, triangles and hexagons. However, these polygons cannot be regular, as atsT (the truncatedicosahedronpentakisdodecahedron or ambo-truncated icosahedron) is not one of the 13 regular Archimedean polyhedra. Presumably Hart has a formula for producing an image of these polyhedra and figuring out where the points on them go, and this might not be easy; for example, the pentakis dodecahedron is made up of somewhat irregular triangles. Where are the midpoints of the faces?

Also, the site does not work right. It is supposed to pop up a VRML window showing the polyhedron defined by the entered Conway notation. Instead, when you enter the notation in the blank, and click "generate", you get a window with VRML code in it. You can copy this by dragscrolling through the document, and putting it in word and making sure each comment is on a line of its own, then saving it as a text document of type .vrml. But one should not have to go through this. George Hart should fix it so you get the image immediately.

But it is one of the best sites on the Internet, in my opinion, and you can enter any of the codes in this blog into that site and after copying to Word and fixing the comments, you can get a VRML page showing the polyhedron whose code you selected.

The Scarlet Algorithm

2005-06-30T06:14:00.000-07:00

In writing a short-story comedy about people sticking messages in library books and the like, I created a book about an algorithm or procedure for finding out who your best romantic partner is. I called this fictional book "The Scarlet Algorithm". The idea is that such an algorithm would help people find conjugal partners. This idea is something that has been around a long time. In 1966, my college was introduced to something called Operation Match. The idea is that people going to a certain dance would fill out a questionnaire about themselves and who they want as a partner, and the computer would find for each such person a list of persons of the opposite sex that are the most compatible with them. This did not always turn out right, partly because people put down on paper who they think they want rather than who they want. Nowadays this practice continues in the plethora of dating services on the Internet. To me this is not the best way to meet someone. The best way is through joining clubs or organizations that represent your interests and finding people there.

But if one were going to organize an Operation Match dance, what would be the algorithm? Probably some variant of the Hungarian algorithm, which matches elements of one set with elements of the other to optimize total worth, or of the Gale-Shapley algorithm, which eliminates the chance that "affairs" will form; i.e., two people who prefer each other to the people that they have been assigned to. Recently I used the Hungarian method to pair major league baseball teams with their AAA affiliates, and found that major league baseball could cut major-league-team-AAA-affiliate costs by 40%.

Other mathematical schemes describe love itself. John Alan Lee describes something called the "Colors of Love", in which he describes love as a two-dimensional continuum, specifically the triangle described by x + y + z = 1, with x, y, z >= 0. The three variables in this are "primary colors", which Mr. Lee describes as eros, ludus, and storge. He then describes three secondary colors, with mania between eros and ludus, pragma between ludus and storge, and agape between eros and storge. He then describes tertiary colors, but only for combinations involving mania, including manic storge, which would be a mix of a secondary color with its opposite complement. I therefore conclude that Mr. Lee is really dealing with a four-dimensional model, with four primary colors of eros, ludus, storge, and mania, however, it is hard to picture colors in four dimensions.

Then there are rating schemes. One is the familiar "10" or "perfect 10". This envisions that a man, for example, will rate women on a scale from 1-10, and that what he really wants is a perfect 10. There is even a movie with the name "10", which describes such a desirable woman. First of all, it should be a scale of 0-10. This is the most natural way of rating a scale on two extremes, with 0 at one end and 1 at the other; just multiply this scale by 10.

But another problem is that one will find that there are too many 10s out there. The scale suggests that each number from 0 to 10 will have the same number of people in them; since we meet hundreds of people there will be tens of 10s out there. A better idea is to use a logarithmic scale; see Logarithms Keep Dr. Brown in Perspective". In this scale, a 1 is one out of 10, and so is the counterpart of the "perfect 10". A 2 is one in a hundred, a 3 is one out of a thousand, out of 1,000 with 3 zeroes after the 1. A 6 would have six zeroes after the one, and would be one in a million.

So even though the two subjects of mathematics and romance don't seem to have much in common, there are ways of applying the mathematics to help out with finding a suitable partner. These ways I call "The Scarlet Algorithm".

Mathematical Baseball

2005-06-22T19:17:00.000-07:00

This week I have been noticing that of all the team sports, especially those that are broadcast extensively, baseball is the most mathematical. It is a discrete game; that is, the game proceeds by innings, which are composed of outs, which are composed of trips to the plate, which are composed of discrete pitches. It is almost as though a pitch was an "atom" of baseball. Baseball games are composed into box scores, which total the number of items that occurred in the game by categories. For example, you will see the number of runs by each team, the number of hits by each player, the number of walks allowed by each pitcher, and so forth, and from these statistics can be developed, such as standings and batting averages. One can even simulate baseball based on what has happened in previous games.

One of my main interests is what can happen in baseball? What are the logical extremes? For example:

1. What is the fewest number of pitches in a game?

This one is a little tricky. Think about it a while and then come back to this blog.

Did you say 54 pitches? Each player bangs into an out on the very first pitch, 3 pitches a half inning, and so 3 x 2 x 9 = 54 pitches in a game? Almost, but not quite. If the home team is ahead, the bottom of the 9th will not be played, and that makes it 51 pitches. But that's not correct, either. If it were 51 pitches, every one would be an out, and the score would be tied, 0-0. One more pitch is needed somewhere to score a run for the home team, probably a solo home run. So the answer is 52.

2. What is the most number of pitches in a game?

The answer is infinity. This gets into a concept I have invented in games called entropy. In games, some moves are reversible; you can go back to the same situation again. Others are irreversible. In chess, for example, moving a knight to an open square is reversible; you can move him back again. But capturing a piece is irreversible, as the piece can never return, and moving a pawn is irreversible, as pawns can't move backward. And so it is with baseball. An out is irreversible; one can't undo the out and go back from 1 out to none, for instance. A hit, however, is reversible, since a team and hit and hit and hit over again and the situation will still remain the same, especially if the hits are home runs. Conceivably the team could score run after run after run as the New York Yankees did yesterday (against Tampa Bay on 2005 June 21) without ever getting the third out. So the game goes infinite. (Well actually, the Yankees stopped after 13 runs) There are four ways a game can go infinite:

a. Run infinite. A team scores run after run after run in an inning without the third out ever coming.

b. Inning infinite. The game goes into extra innings, one after another, for an infinite amount of time because the two teams score the same number of runs in each inning.

c. Foul ball infinite. A foul ball after two strikes (unless it is a tip or is bunted) does not count anything in baseball - it's reversible. So have a batter hit foul after foul after foul without ever causing an out or hitting and getting safe on first. There is even a book written about this idea, "The Boy who Batted 1.000".

d. Pickoff infinite. The pitcher over and over again attempts to pick off a runner with a throw to that base, and with the runner making it back on time each time. There may be a rule against this one, something about delay of game.

If one assumes that none of these infinites can occur, then a baseball game must end. However, the maximum number of pitches depends on the limits you place on innings, batter-friendly events, foul balls, and pickoff attempts.

3. Suppose a pitcher gets 7 strikeouts in a single inning. Show that a run must have scored.

This one is strange. How can a pitcher get more than 3 strikeouts? 3 outs ends the inning. The answer is that if the catcher can't catch the ball, and there are two outs or first base is open, then the batter who is struck out can run for first base, and if he beats the ball, he is safe at first. The pitcher still gets a strikeout. So 7 strikeouts means 7 people to the plate, and one can fit only 3 of these in outs and 3 on the bases, so at least one run must have scored.

4. How many hits must a team get before a team is certain of scoring a run?

You think it may be something like 10? 15? 22? Try 55. That's right. A team must get 55 or more hits in a game before it becomes certain that a run must have occurred. A team can get 54 hits, and furthermore, 27 of these can be triples, without scoring a single run. Here's how:

A. Hits triple and is out trying to score.
B. Hits triple and is out trying to score.
C. Hits triple.
D. Hits single; 3rd base coach holds runner at 3rd.
E. Hits single; 3rd base coach holds runner at 3rd.

Here is where the problem occurs. If the next runner is out, that ends the inning with only 5 hits. If the next runner hits, with the bases loaded, a run must score. It seems like we need a hit and an out simultaneously and how do we get that? Here's how:

F. Hits ball, batted ball hits a runner. F is credited with a single. The runner is automatically out.

And there it is, 6 hits and no runs. Repeat that over 9 innings and you get 54 hits, with 27 triples, and no runs. We can fire this third base coach.

5. Can a pitcher lose a no-hitter?

Yes he can. A pitcher must win a shutout, because you need runs to win a game. A pitcher must win a perfect game, for you must get on base before you can score. But a pitcher can very well lose a no-hitter. Hits are not necessary for a win. All you need is 3 errors, as happened on 1990 July 1 with a game between the New York Yankees and the Chicago White Sox. The Yankees had 4 hits but 0 runs, and the White Sox had 0 hits but 4 runs. The no-hit White Sox won the game by a substantial margin.

2005-06-15T18:26:00.000-07:00

This starts my newest blog, one devoted to mathematics and science, but mostly to mathematics. I called it Hilbert's Hotel after the fabulous hotel that was constructed with an infinite amount of space that will hold a countable infinity of guests, and there is always room for one more, since if John Q. Onemoreguest should arrive, we just tell everybody to move out of their rooms and into the room with the next highest number; e.g., from 107 to 108. Then we can fit John in room 1.

Today I got a question to the math help website I belong to, Mathnerds, concerning cubic equations. These have fascinated me since I was small. There was a formula for quadratic equations, but how about cubics? The best way to understand these is to first of all convert the general cubic

ax³ + bx² + cx + d = 0

into one of the form
x³ + px + q = 0

by dividing everything by a and then by applying the transform y = x - a/3 (and then of course x = y). Let w be an imaginary cube root of 1; i.e., w = -1/2 + sqrt(-3)/2. Compute this product:

(x - u - v)(x - wu - w²v)(x - w²u - wv)

You get:

x³ - 3uvx - (u³+v³)

which is exactly in the form of the reduced cubic equation. Then set

-3uv = p

p³ + q³ = -q

and solve by solving for v in the first equation, and plugging into the second, yielding a quadratic in p³. Solve this using the formula, and select a cube root of the result for u. Then solve for v in the first equation, and then the roots are

u + v
wu + w²v
w³u + wv

This is essentially the method of Lagrange resolvents, and the question in Mathnerds asked about those. Another interesting way of looking at it is through Dan Kalman's circulants.

There is also a discriminant D. If D is 0, the roots are probably rational and two of them are the same. If D > 0, then there is one real root and two imaginary ones, and one can actually come up with a formula for the real root, but it will be somewhat complex looking, being a sum of the cube roots of two quadratic expressions.

The really confusing case is the irreducible one, where D < 0, and my favorite equation here is x3 - 3x + 1 = 0. If you use the formula above, you get w^1/3 + w^2/3 for one of the roots. The thing is, this is real, yet it is expressed in imaginary quantities. I searched all over when I was young for a real solution, until I realized that there are none. There is no way of expressing the roots of this equation in real radicals. If you are willing to use trig functions, there is a way: 2cos(40 degrees) or 2 cos (2*π/9) is one of the roots, for instance.

Cubic equations were originally solved by the Italian mathematicians Tartaglia and Cardano, and Galois added a lot to the theory by associating with equations and field extensions a structure called a Galois group, which for most cubic equations is the group of permutations of three objects, known as S₃. Most of the time when confronted with one, one uses Newton's method to approximate the real roots. But cubic equations solved algebraically have a fascination with me and they will continue to do so.