Schoolgirls do not Necessarily Form a Group

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

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?

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

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

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

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.