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.

Tricky Triangles

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

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

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

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.