Monthly Archives: April 2010

Indiana Pi Bill

Today is Pi Day! The date is April 26, the day when Earth has made 2 radians of its orbit around the sun since the New Year. The time when Earth completed \frac1\pi of its orbit was at 4:23:41AM this morning, when I was asleep. Though I missed the precise time (and also failed to eat pie today), I’d still like to recognize this glorious holiday. So today, we’ll honor this holiday by recalling some history.

In 1897, the human named Edwin J. Goodwin believed that he had found a way to square the circle, and he proposed to allow the state of Indiana to use this result for free, provided that they passed a bill accepting his results and defining the \pi = 3.2. The gullible representative Taylor I. Record introduced this bill (number 246) to the Indiana House for approval. After some deliberation, the bill was endorsed by the Committee on Education and subsequently passed unanimously by the House. Luckily, just as this bill was being endorsed by the Senate, the mathematician C. A. Waldo visited the Senate and persuaded the senators to suspend a decision on the bill indefinitely. This is one of the most famous attempts to legislate mathematics.

The consideration of this bill is ridiculous in several ways. First of all, the mathematics in the bill is incorrect, demonstrating that the Indiana representatives at the time had no mathematical knowledge and no proper fact checking. Even worse, Goodwin stated that passage of the bill was a prerequisite for using his proof free of charge, despite the fact that royalties cannot be requested for mathematical results.

Thus, we see that by voting on this bill, the Indiana General Assembly showed that they are not qualified to make any decision on mathematical results, and the Committee on Education showed that they are incompetent. Though such a bill is unlikely to be considered today, the general trend still holds. Legislators in America (as well as the general public) are not well-informed about basic facts, but they still believe that they have the right to legislate on matters that they do not fully understand. Furthermore, the modern equivalent of the Committee on Education is still highly under-qualified to make decisions on mathematical education, and I still wouldn’t trust them with properly treating the value of pi. As an over-generalization, we see that many of our elected officials should never have been elected at all. Those who elected them — the general public — should be banned from voting. Dictatorship is certainly a much more efficient system than democracy.

The full text of the Indiana Pi Bill (Bill 246 of the 1897 Indiana General Assembly):

A Bill for an act introducing a new mathematical truth and offered as a contribution to education to be used only by the State of Indiana free of cost by paying any royalties whatever on the same, provided it is accepted and adopted by the official action of the Legislature of 1897.

Section 1
Be it enacted by the General Assembly of the State of Indiana: It has been found that a circular area is to the square on a line equal to the quadrant of the circumference, as the area of an equilateral rectangle is to the square on one side. The diameter employed as the linear unit according to the present rule in computing the circle’s area is entirely wrong, as it represents the circle’s area one and one-fifth times the area of a square whose perimeter is equal to the circumference of the circle. This is because one fifth of the diameter fails to be represented four times in the circle’s circumference. For example: if we multiply the perimeter of a square by one-fourth of any line one-fifth greater than one side, we can in like manner make the square’s area to appear one-fifth greater than the fact, as is done by taking the diameter for the linear unit instead of the quadrant of the circle’s circumference.

Section 2
It is impossible to compute the area of a circle on the diameter as the linear unit without trespassing upon the area outside of the circle to the extent of including one-fifth more area than is contained within the circle’s circumference, because the square on the diameter produces the side of a square which equals nine when the arc of ninety degrees equals eight. By taking the quadrant of the circle’s circumference for the linear unit, we fulfill the requirements of both quadrature and rectification of the circle’s circumference. Furthermore, it has revealed the ratio of the chord and arc of ninety degrees, which is as seven to eight, and also the ratio of the diagonal and one side of a square which is as ten to seven, disclosing the fourth important fact, that the ratio of the diameter and circumference is as five-fourths to four; and because of these facts and the further fact that the rule in present use fails to work both ways mathematically, it should be discarded as wholly wanting and misleading in its practical applications.

Section 3
In further proof of the value of the author’s proposed contribution to education and offered as a gift to the State of Indiana, is the fact of his solutions of the trisection of the angle, duplication of the cube and quadrature of the circle having been already accepted as contributions to science by the American Mathematical Monthly, the leading exponent of mathematical thought in this country. And be it remembered that these noted problems had been long since given up by scientific bodies as insolvable mysteries and above man’s ability to comprehend.


Religiosity in USAMO

I was recently asked an interesting question: What is the correlation of religiosity to the number of USAMO qualifiers?

Let’s do some data analysis to answer this. First, we measure religiosity using data from a Gallup poll. Since this poll gives religiosity by state, we’ll doing this correlation by state. Instead of computing correlation of religiosity vs number of USAMO qualifiers (which is highly population-dependent), I instead looked at correlation of religiosity vs proportion of USAMO qualifiers in the population. Using population data from Wikipedia, I inputted all of the data into an Excel spreadsheet and asked Excel to compute some correlations, and the results are as follows:

The correlation coefficient of religiosity vs number of USAMO qualifiers is -0.54, which is surprisingly strong; I was expecting a correlation of something around -0.3. This suggests that religiosity is fairly strongly negatively correlated with the number of USAMO qualifiers.

Let’s take a look at religiosity vs the number of AIME qualifiers or AMC participants:

Correlation coefficient: -0.47

Correlation coefficient: -0.42

What does this mean? First of all, it seems that the correlation becomes weaker as the contests become less selective, suggesting that the difference between contest math in states with different religiosities is not just a difference in enthusiasm or participation. There is also a difference in achievement, as students in less religious states have a better chance of becoming a USAMO qualifier. The participation difference is still very significant though, as the correlation coefficient between religiosity and AMC participation is nontrivial.

The data considered is certainly imperfect. For example, the USAMO qualifiers list is not final, and a final list is not expected to be published for a few more days. In addition, the AMC participant data varies from year to year, and the data for the 2010 tests might not be fully representative of a typical year. For example, the snowstorm in February made it very difficult for some students in the Northeast to compete, knocking out a significant number of AMC participants. In addition, some students take the AMC twice and were hence double counted in the AMC or AIME numbers, and the might have given themselves a better chance to qualify for USAMO. I suspect that this behavior is more common in states that were already good at math contests, making the fluctuations in the numbers exaggerated. The rule that every state must have a USAMO qualifier might have inflated the USAMO qualification numbers for some states, and private schools in some states recruit across the country and therefore skew their states’ numbers (which is why this analysis couldn’t be done for Putnam, for example).

Can this phenomenon of correlation between religiosity and USAMO qualifiers be explored further? Some interesting questions still remain. For example, what is the correlation between IMO scores and national religiosities? If there’s anything else I should consider, please comment on this post and tell me.

A disclaimer: Correlation does not imply causation. In this post, I pointed out that religious states tend to do less well at contest math (at least as measured by the AMC series of tests). However, I do not make any claim that religion is the cause of this achievement gap, and I refuse to speculate on why this achievement gap exists. I am not opposing religion in this post, and I’d prefer not to receive hate mail.

New Quotations

I have a collection of quotations on this blog in the quotations page, and I will periodically update that page with additional quotations. These quotations come from people who say silly things around me. You have been warned: Anything that can be misquoted to sound stupid will be misquoted. The quotations already on that page before this post come from things that various people have said around me in the past three years and were copied from my old website.

Here’s a collection of the newest quotations, along with their sources.

“I’m not alive.” — Chris (email message from 11 April 2010)

Bridge game 16 April 2010:

  • “I’m invisible.” — Moor
  • “But nobody ever says anything stupid!” — Anand
  • “America is a country that needs disaster.” — Moor
  • “America is a disappointing country.” — Moor

With the last two quotations, I’ve probably disqualified myself from ever running for political office in America. However, I think that they’re true, though a bit extreme. America as a country is incapable of positive development when it is not under pressure from other countries. Before the collapse of the Soviet Union and the end of the Cold War, America was always competing with other countries and hence achieved social and technological progress. Such advancement has slowly drastically in the past twenty years as funding for science has gone instead toward funding wars. Without competition, America is a country without direction or purpose. Luckily, some countries will catch up soon, and by doing so, they’ll save America from itself.

For the full list of quotations, visit my quotes page!

Angle Bisectors

Given the sides of a triangle, what is the length of the angle bisector? Consider the following image of triangle ABC, where the sides opposite points A, B, C have lengths a, b, c. We want to find length d.

First, we can apply the Angle Bisector Theorem to see that \frac{a}{x} = \frac{b}{y}, so that x = \frac{ay}{b} and y = \frac{bx}{a}. Plugging these into the equation c = x + y yields c = x + \frac{bx}{a} = \frac{a + b}{a} x and c = \frac{ay}{b} + y = \frac{a + b}{b} y, so that x = \frac{ca}{a+b} and y = \frac{cb}{a+b}.

We can now apply Stewart’s Theorem to see that a^2 y + b^2 x = c(d^2 + xy). Plugging in our expressions for x and y, we see that
ab = \frac{ab (a + b)}{a + b} = \frac{a^2 b}{a + b} + \frac{b^2 a}{a + b} = \frac{a^2 y + b^2 x}{c} = d^2 + xy = d^2 + \frac{c^2 ab}{(a + b)^2}.

Therefore, the length of the angle bisector at vertex C is
\displaystyle \sqrt{ab - \frac{c^2 ab}{(a + b)^2}} = \sqrt{ab \left( 1 - \frac{c^2}{(a + b)^2}\right)}.
The lengths of the other two angle bisectors can be found analogously and are given by a simple permutation of coordinates.

Here’s another way to compute the length of the angle bisector that might be a bit simpler: Let \angle C be 2\alpha, so that the angle bisector separates two angles with measure \alpha. The area of triangle ABC is the sum of the areas of the two smaller triangles, which can be expressed as \frac12 ad \sin \alpha + \frac12 bd \sin \alpha = \frac12 ab \sin 2\alpha = ab \sin \alpha \cos \alpha. Simplifying and rearranging, we see that (a + b) d = 2 ab \cos \alpha, so the length of the angle bisector is therefore
\displaystyle d = \frac{2ab}{a + b} \cos \alpha.
This is simpler than what we had before, though it also involves an angle.

We can use this expression for the length of the angle bisector to show that the sum of lengths of the angle bisectors is less than the perimeter. The length of the angle bisector to angle C is d = \frac{2ab}{a + b} \cos \alpha < \frac{2ab}{a + b}, and the other angle bisectors are similar. Therefore, it is sufficient to show that
\displaystyle \text{sum of angle bisectors} < \frac{2ab}{a + b} + \frac{2ac}{a + c} + \frac{2bc}{b + c} \le a + b + c = \text{perimeter}.

This inequality actually follows as a simple application of the arithmetic mean – harmonic mean (AM-HM) inequality, which states that
\displaystyle \frac{2ab}{a+b} = \frac{2}{\frac1a + \frac1b} \le \frac{a  +b}{2}.
Applying this three times yields
\displaystyle \frac{2ab}{a + b} + \frac{2ac}{a + c} + \frac{2bc}{b + c} \le \frac{a + b}{2} + \frac{a + c}{2} + \frac{b+c}{2} = a + b + c,
which is what we wanted to show. Therefore, we've proven that the sum of lengths of angle bisectors in a triangle is less than the perimeter.

Analysis of the 24 Game

The 24 Game is a very simple card game. Four cards are dealt at random, and the players must apply simple arithmetic operations to the four numbers on the cards; the goal is to obtain 24 as a result of these operations. Each of the four numbers must be used exactly once, and the available operations are addition, subtraction, multiplication, and division. For example, if the cards were (3, 1, 4, 1), a solution would be (1 + 1) * 3 * 4 = 24. In the simplest version of this game, we let A = 1, J = 11, Q = 12, K = 13, joker = 15. There are four cards of each normal denomination, and two jokers.

I was playing the 24 game on Friday night, and I claimed that fractions are not necessary in the 24 game; all problems in 24 that can be solved with fractions can also be done by division. After three examples to the contrary {(1, 5, 5, 5), (3, 3, 7, 7), (4, 4, 7, 7)}, I was forced to retract my claim. Fractions are indeed necessary to solve some hands of cards in 24. This leads to some interesting questions. First of all, how many hands require using fractions? How common is this type of hand?

To answer this question, I wrote a simple Python program to bash the 24 game. Admittedly, this program is terribly inefficient and a demonstration of bad coding style, but I think I’ve worked out the bugs. Given 3.5 minutes, my program can solve the 24 game entirely: It can generate every possible hand and give a solution for each (if a solution exists). The program can also determine if there exists a solution that does not require fractions.

Here’s a summary of the results of this program:

  • There are 2366 possible hands.
  • Out of these, 617 have no solution.
  • An additional 23 require using fractions to solve.

So we see that around a quarter of all hands are unsolvable, while less than 1% of hands require fractions. Thus, in most cases, it’s not necessary to consider fractional solutions; my claim was based on empirical evidence and is true for most hands. Indeed, I suspect that most people would give up on these problems in 24 and claim that they are unsolvable; that may explain why I hadn’t ever seen a solution involving fractions until Friday night.

I’ll admit that this isn’t precisely correct; not all hands are equally likely to appear; (3, 3, 3, 3) would appear much less often than (3, 4, 5, 6), for example. However, I assume that averaged over a large number of hands, this ratio of hands is approximately accurate. Thus, averaged over all impossible hands, I assume that impossible hands occur with probability around \frac{617}{2366} \approx 26\%.

Something that was discussed during Friday’s game was the idea of treating aces as 14 instead of 1. The rationale is that in most card games, aces are larger than kings. Under this new convention, what would be the probability of getting an impossible hand? My program computed 674 impossible hands, for an average impossibility rate of \frac{674}{2366} \approx 28\%.

This doesn’t seem like a big difference, but note that most hands don’t contain aces. What if we only looked at the impossibility rate of hands that contain aces? Here, the difference is a bit larger. There are 559 hands that contain aces, and when we set aces as ones, the probability that a random hand containing an ace has no solution is \frac{154}{559} \approx 28\%, while the probability when we set aces as fourteens is \frac{188}{559} \approx 34\%. Therefore, from a practicality standpoint, more hands are solvable when we set aces as ones. The difference isn’t huge, however, so both conventions for aces are reasonable.

If you’re interested, here’s a complete list of hands that require fractions in their solutions. It’s amusing to solve these “hardest” problems in 24, though they become much easier when it is known a priori that they require fractions.

(1, 3, 4, 6)
(1, 4, 5, 6)
(1, 5, 5, 5)
(1, 6, 6, 8)
(1, 8, 12, 12)
(1, 10, 12, 15)
(2, 2, 13, 13)
(2, 2, 11, 11)
(2, 3, 5, 12)
(2, 4, 10, 10)
(2, 5, 5, 10)
(2, 6, 10, 15)
(2, 6, 15, 15)
(2, 7, 7, 10)
(2, 7, 12, 15)
(2, 8, 12, 15)
(2, 9, 10, 15)
(3, 3, 7, 7)
(3, 13, 13, 15)
(4, 4, 7, 7)
(4, 4, 6, 15)
(5, 5, 7, 11)
(5, 7, 7, 11)

Algebra vs Analysis

Algebra and analysis are two major areas of mathematics, and much of mathematics is divided into these two categories. The algebraic and the analytic way of looking at the mathematical world can be very different, and I’ll explore some of these differences through over-generalizations. A disclaimer: All of these over-generalizations are based on what I’ve seen of these two disciplines; they might have no relationship with reality.

Algebra is the study of collections of objects (sets, groups, rings, fields, etc). In algebra, people care more about the structures of these collections and how these collections interact than about the objects themselves. In fact, with homomorphism and isomorphisms, the original objects become irrelevant. This is in direct contrast with analysis, which primarily studies individual objects; for example, an analyst might study the smoothness of an individual function. In many cases in analysis, studying collections of objects might just be too hard. For instance, the study of PDEs often focuses on individual equations instead of general theory because the general existence and uniqueness problem is simply intractable.

The way mathematicians go about studying the algebraic and analytic parts of the world is also quite different. Just as algebra is the study of structures, algebraic theory is also quite structured. There are endless similarities between algebraic objects, and the goal is often to classify these objects and show when they can be thought of as the same. In this way, seemingly unrelated problems can be linked and solved by the same methods. A good example of this is category theory, which leaves even the details of algebraic objects behind. The analytic world, on the other hand, is full of ad hoc methods designed to circumvent technical difficulties such as convergence issues. In fact, the ad hoc nature of analysis even makes it difficult to over-generalize.

Part of the reason for this difference between algebra and analysis is that they often have different ultimate goals. In algebra, people are always looking for equalities: Are these objects isomorphic? Can we classify all objects of this type? Analysis, on the other hand, deals in inequalities and error terms. This is evident from the very beginning, in the theory of epsilons and deltas. Instead of obtaining precise values, it’s sufficient to show that epsilon and delta are within a certain range. In order to show convergence, we just need to show that the error terms are small. Thus, there’s often no perfect bound or best approximation, and there doesn’t need to be; all that is needed is for the bound or the approximation to be good enough. In that sense, analysis doesn’t require so much structure, and people can get away with being less general.

It appears, then, that analysis deals with details while algebra takes a broader view. Both are important to have in mathematics, and any interesting problem would most likely contain a mix of the two. As much as many mathematicians would like to avoid having to deal with any area that is not their own, everyone has to learn about and understand mathematics as a whole.

Putnam vs USAMO

The 2009 Putnam competition was in December 2009, and the results came out a few weeks ago. My score on the Putnam was much higher than my score on USAMO from April 2009, but I know I hadn’t improved much in contest math in the eight months between the USAMO and the Putnam; this increase in score is due primarily to the different formats of the tests. This leads to some interesting questions.

First, an overview of the differences between USAMO and Putnam. The USAMO is a 9 hour exam with 6 problems; that comes out to 90 minutes per problem. The Putnam, on the other hand, is a 6 hour exam with 12 problems, for 30 minutes per problem on average. The topics covered on USAMO and Putnam are similar, with only one major difference: geometry on USAMO is replaced by calculus and linear algebra on Putnam.

It seems that Putnam problems are more straightforward and more approachable. Since there are only 30 minutes per problem, each problem can usually be solved by one insight or one trick. USAMO problems, however, often require a series of insights. In the end, Putnam is more about being clever and writing solutions carefully, while USAMO is more about solving difficult problems. That’s not to say that USAMO is harder than Putnam; they are simply different. Some people are better at quickly finding clever tricks, while others are more persistent.

This difference is interesting because high school mathematics is usually thought of as the domain of clever trickery and quick problems, while college mathematics usually has harder problems that require more persistence — approaching the types of problems seen in research. I suppose that this seemingly contradictory difference in USAMO and Putnam is a result of tradition and not of conscious choice.

Another item of interest in USAMO and Putnam are the median scores. The median score on the 2009 USAMO is 4/42, while the median score on the 2009 Putnam is 2/120. By that measure, the Putnam seems to be even harder than USAMO despite the arguments above for why the Putnam should be more approachable. However, that’s not quite true. The USAMO in 2009 selected the top 500 students from AMC and AIME to take the test, so USAMO participants are already highly filtered. If it were opened to everyone, the number of people taking USAMO would be in the thousands and the median would be much lower, probably 0. This is in fact what happens to the Putnam: 4000 people took the 2009 Putnam, and 43% scored zero. Indeed, the median for the top 500 on Putnam is around 30/120, much higher than the median for USAMO.

So what do my Putnam score and USAMO score say about the way I think about math? It appears that I’m better at solving easier problems quickly than at working through hard problems (especially given the time limit of USAMO). Another possible explanation is that I’m much better at calculus than at geometry; I couldn’t solve 2009 USAMO Problem 1, but I could solve 2009 Putnam A2.