Tanya Khovanova's Math Blog

Today I have my first invited guest blogger, J.B. He is a 2006, 2007, 2008 and 2009 USAMO qualifier. He was also selected to be on the US team at the Romanian Masters in Mathematics competition. Also, he placed 6th at the North American Computational Linguistics Olympiad. Here is his piece:

The analysis is based on the list of 2009 USAMO qualifiers.

There is a rule that if nobody naturally qualifies for the USAMO from a state, then the highest scoring individual will qualify. Unfortunately, this means that we must remove those states with only one USAMO qualifier. We have 33 states remaining. If we sort these strictly by number of USAMO qualifiers, then we find the following result.

States with at least 4 USAMO qualifiers (24 total) voted for Obama, with the following exceptions: Georgia, Texas, South Carolina, and Missouri. In addition, of the two states with 3 USAMO qualifiers, one voted for Obama and one for McCain. The remaining states with 2 qualifiers (5 total) voted Republican.

Now this is not really unexpected. States with very large populations tend to be democratic and also produce more USAMO qualifiers. The most notable exceptions are Georgia and Texas, both of which were indeed exceptions (major outliers, in fact) above. This prompts the following consideration.

States with at least 8 USAMO qualifiers per 10 million residents (25 total) voted for Obama, with the following exceptions: Florida, Wisconsin, South Carolina, Missouri, and Georgia. Of these, all but Georgia fall within 50% of the target 8 USAMO qualifiers per 10 million residents. Georgia has 18 qualifiers per 10 million residents. Note also that the entire USA has 16 qualifiers per 10 million residents.

Furthermore, if USAMO qualifiers had been used instead of population for determining electoral votes, Obama would have won with 86% of the vote rather than 68%. In general, if the Democrat can secure all those states with at least 1 qualifier per million residents (plus DC), he will win with 303 votes. He can even lose the three red states in that category (Georgia, Missouri, and South Carolina) for exactly 269.

USAMO qualifiers per 10 million residents (for states with more than one qualifier) are:

• NH — 122 (all of their qualifiers are from Phillips Exeter Academy)
• MA — 55
• ME — 30
• CA — 29
• NJ — 29
• CT — 29
• VA — 28
• MD — 25
• WA — 21
• IN — 19
• OR — 19
• NY — 18
• GA — 18
• IA — 17
• NM — 15
• MI — 15
• PA — 14
• MO — 14
• SC — 13
• IL — 13
• NC — 13
• OH — 9
• CO — 8
• MN — 8
• UT — 7
• KS — 7
• WI — 7
• KY — 7
• TX — 7
• FL — 6
• LA — 5
• AL — 4
• TN — 3

The states with only one USAMO qualifier are WY, VT, ND, AK, SD, DE, MT, RI, HI, ID, NE, WV, NV, AR, MS, OK, and AZ. The only blue one of these which falls below 8 qualifiers per 10 million is Nevada (we would expect it to have at least 2 qualifiers to fit the expected pattern). Otherwise, it is at least possible that each state fits the pattern of 8 qualifiers per 10 million residents if and only if it votes Democratic.

More than a year ago, when I had my employment benefits with BAE Systems, I called my benefits center with a general question. The customer service representative refused to answer until I gave her my password. I didn’t have a password, so she told me that they would mail my new password to me.

But I needed an answer, so I tried the website, only to be informed that my new password is in the mail and I should wait for its arrival.

In a week, a letter with a password arrived and I called the benefits center again. I happily told them my new password and opened my mouth to ask my question. However, they didn’t accept my password. Obviously, they had changed my password twice, first when I called and then again when I tried their website. Since only ten minutes passed between these two events, both passwords should have arrived on the same day. But that didn’t happen. So my valid password was still in the mail.

In the second it took me to recover from this news, the customer representative told me that they would be sending me a new password and hung up before I could tell her not to.

A new password arrived the next day. I knew that they had already reset that password, and that I’d have to wait a week for the third password to arrive.

I was tempted to call them again and try to create an infinite password resetting loop, but I actually needed to ask my question. So I threw away my freshly arrived, but no-longer-valid password and waited for a week for the next one.

I was lucky to figure it out so quickly, for otherwise my problem could have spiraled out forever. As a professional specifications writer, here are my suggestions to all benefits centers that have that kind of software on what they should do:

• Don’t send an extra password if a password was sent not long ago, for example, in the last two days.
• If two passwords are mailed to a client in the same week, make both of them valid.
• Use email rather than mail.
• Don’t request passwords for general questions.

I had to wait two weeks to ask a simple question. Now I am writing and complaining about it in the hopes that someone who can fix the problem will read this. Maybe it would have been more productive to write a program that clicks on the “I forgot my password” button every second. This would have daily generated thousands of letters with new passwords to me. Maybe then this problem would have drawn attention sooner.

I just watched the film Mackenna’s Gold for the first time. I would have liked it, if not for the sunrise. It is a treasure-hunting movie with gold lying around in a hidden canyon. The secret entrance to the canyon is revealed by the shadow of a big rock tower at the moment of sunrise.

The problem with this clue is that the azimuth of the sunrise differs depending on the day of the year. For example, at the latitude of Cairo, Tel Aviv or Los Angeles, the sunrise azimuth changes from 116 degrees to 62 degrees as the seasons change. This is more than a 40 degree span!

In any map where directions include a long shadow at sunrise, it should include the day of the year. To be more precise, the trajectory — of a given spot on Earth — around the Sun is not periodic. That means the Sun never rises at the exact same azimuth twice. If we are talking about the approximate azimuth, then the Sun rises in the same region two time periods per year. These periods are mirror reflections of each other, with the winter solstice as their focal point. That means MacKenna and his companions needed to wait for several months for the right moment.

I wonder whether the filmmakers knew about this mistake. I see two possibilities.

The first one is that no one noticed. This is very bad. It confirms that this country is illiterate. In fact, it is worse than that, since you don’t really need an education to know that sunrise and sunset happen at different points in the sky depending on the time of year. You just need to look out your window from time to time and pay attention.

The second possibility is that someone noticed, but the filmmakers decided to proceed with it anyway, on the assumption that the audience is too dumb to detect the error. Although there are Internet discussions of goofs in this movie, I was disappointed that I didn’t find any complaints about this mistake.

George Lucas borrowed many ideas for the Indiana Jones movies from Mackenna’s Gold. In particular, for Raiders of the Lost Ark he borrowed the sunrise mistake without the sunrise itself. In the movie the Sun is supposed to penetrate the crystal in the headpiece of the Staff of Ra and reveal the location of the Well of Souls. To do this, the Staff must be placed in a specific spot in the map room at a certain time of day.

The fact that the poetic idea of a sunrise was removed probably means that they knew that it was a mistake. It was replaced by a non-poetic certain time of day. But they kept the mistake. The Sun doesn’t repeat its trajectory every day. Like MacKenna, Indiana Jones would have needed to wait in the map room for several months for the Sun to be in the right spot. George Lucas opted for a fast-paced movie that disregards the laws of physics. The mystery of this movie for me is: Does anyone care?

I wanted to see how different presidents affected the Dow Jones index. The index was invented at the end of the nineteenth century, so for my convenience, I will start my analysis from the beginning of the twentieth century. I skipped the presidents who were in office for only four years — four years might not be enough to rebuild a bad economy or to destroy a good one. Besides, in order to give the presidents a fair chance, I compared them for the same time period: eight years.

So I removed from my consideration all those who only served for four years: William Howard Taft, Herbert Hoover, Jimmy Carter and George H.W. Bush. I also combined two presidents together, when one succeeded the other mid-term for a total of eight years. Namely, I combined Warren Harding with Calvin Coolidge, John Kennedy with Lyndon Johnson, and Richard Nixon with Gerald Ford. For Franklin Roosevelt, I only considered the first eight years of his presidency.

Please note that it was not always precisely eight years — the inauguration date was sometimes moved. So Theodore Roosevelt and Harry Truman had slightly less than eight years. I tried to use the Dow Jones index from the exact day of each inauguration, but not all the dates were available in the file I used. So sometimes I had to pick the previous day.

Some might argue that I need to scale the Dow Jones Index. For example, the inflation rate was very different for different presidents. It is generally accepted that the value of one point in the Dow Jones Index decreases with time, but inflation is only one of many elements contributing to that change. Nonetheless, I took a look at that and the resulting picture didn’t change much anyway when I adjusted for inflation.

The Dow Jones is just one number. An increase in the Dow Jones does not completely describe the state of the economy, but it is certainly an interesting measure in its own right.

Let’s look at how the presidents and the presidential teams performed, sorting them from best to worst:

When I started this calculation I expected Clinton to be doing well and Bush badly, I just didn’t know exactly how good/bad they were. But the most interesting result of this exercise is the fact that the highest increase in DJI happened right before the Great Depression.

What can I say? I should have done this analysis eight years ago. Maybe the proximity of Clinton’s performance to the pre-depression boom could have urged me to move my 401(k) from stocks. Sigh.

It is unfortunate that crooks understand probability. Here is a scam that was very popular back in Russia.

A bad guy pretends that he has a close relative on the hiring committee of a college. He takes bribes from prospective students, promising to help them pass the entrance exams at this college. He doesn’t guarantee the admission, but he guarantees the money back. After getting the money, he does nothing. If the student passes the entrance exams, he keeps the money. If not, he returns the money. Simple probability — someone will pass the exams by chance, making him a lot of money.

Here is another Russian scam. This time the crooks have some understanding of conditional probability. These “psychics” promise to correctly predict the gender of your future child. They tell you a random gender, but for their bookkeeping they file the opposite gender. This way, even if you complain, they still keep your money. They show you their books and pressure you into believing that you misunderstood, misheard or misremembered the answer. The probability that you complain if they are right is zero.

Let us all learn probability theory to recognize scams and not fall for them.

Once I was at a party and a woman was complaining that her car insurance bills were enormous. Her expensive car was hit three times while it was parked. She was whining about how unfair it was for her to be paying increased insurance premiums when it hadn’t been her fault. I didn’t tell her my opinion then, but I’m going to write about it now.

Though such things can happen, it is possible to reduce the probability of your parked car being hit.

In my personal experience the most frequent parking accident happens when someone backs out of a driveway and there is a car parked in a space which is usually empty. People often back out of their driveways on autopilot. If you park on a narrow street with no other cars — a sign that people don’t usually park there, do not park across from a driveway or close to a driveway.

There are many other common sense ideas. Don’t park at a corner. Choose the better lit areas. Don’t park next to a truck or a van, because they might not see you very well and if they hit you, they’ll do more damage. Don’t park next to an old, battered car because they have less to lose than you do. New cars are the best neighbors. Not only are owners of new cars usually more careful, but new cars are also often leased. And people who lease a car are even more careful, because they have to return it in good order.

When you are choosing a perpendicular parking spot, here’s a cute idea. Pick cars with four doors as your neighbors. Cars with two doors have bigger doors and if you are too close, they might scratch you.

Here’s what I would have told that woman: If your car has been hit so many times while parked, you should rethink your parking strategy.

One of the questions from the Microsoft employment interviews for creative thinkers is: “How would you design Bill Gates’ bathroom?” I gave this question to my students at the Advanced Math and Science Academy Charter School. Most of them started by suggesting it be big and gold, but they also suggested more interesting ideas:

• Heat the floor and the toilet seat.
• Run a medical test automatically for every flush.
• Provide a shampoo dispenser with a choice of 20 smells.
• Paint the portrait of a favorite enemy inside the urinal.
• Create a shower that looks and feels like a waterfall.
• Install a face recognition system that immediately adjusts all the default settings according to who enters the bathroom.
• Build a very simple bathroom and give the leftover money to charity.

Tell me your own ideas.

I recently updated my collection of my favorite xkcd webcomics.

Today I would like to discuss the comic entitled “Regrets”. When I saw this comic, the first thing I did was go to Google to check the numbers. All my numbers were taken on September 9, 2008 at around 3:00 p.m.

Here are the Google hit counts:

• “I should have kissed her” — 10,600
• “I shouldn’t have kissed her” — 3,220

The numbers are slightly different than those in the cartoon, but the idea is the same; we regret we didn’t kiss. Does it mean that if you want to kiss someone you should go ahead, or otherwise you would contribute to this pile of regrets? The answer is coming later, but first, let’s see what happens if we change gender:

• “I should have kissed him” — 3,170
• “I shouldn’t have kissed him” — 1,240

The same story overall, but for some reason, there are fewer reports by people who either tried or didn’t try to kiss HIM. Is kissing him less interesting or important? Most probably we still expect men to take the initiative in kissing her.

Then I checked the genderless case:

• “I should have kissed you” — 15,700
• “I shouldn’t have kissed you” — 1,800

Wow. Looks like we really should start kissing each other. Right? But wait. Let’s check the point of view of a kissee, rather than a kisser:

• “You should have kissed me” — 494
• “You shouldn’t have kissed me” — 1,020

We see a completely different picture. It is easy to explain why the numbers are smaller: passive people would be less likely to discuss their feelings. But, even so, they claim that they preferred not to be kissed. Maybe it is OK that people mostly regret that they didn’t kiss. After all, if they had tried to kiss, they might not have been greeted with enthusiasm. This leaves you with a choice between your own regrets that you should have kissed and his/her regrets after you did.

I did regret that I hadn’t kissed you, but I so much prefer that I regret not kissing you than you regret being kissed by me. This small research made me feel better. I will not continue regretting any more.

Here is an arithmetic problem for you:

You have $700 dollars in your checking account. You are sloppy and forget how much you have. You write three checks for $600, $200 and $200. For every bounced check you are fined $25 by your bank. How much in fines will you have to pay for your sloppiness?

Solution: the fine depends on the transaction order. If they process your $600 check first, you will have two bounced checks. If they process a $200 check first, then only your $600 check will bounce.

The question is, what will your bank do if all three checks need to be processed at the same time? There are three options:

• Your bank doesn’t have a good mathematician on the staff and is not aware of this situation, and it processes the checks in random order. In this case you will have either two bounced checks (with a probability of 1/3) or one bounced check (with a probability of 2/3).
• Your bank is evil, and purposefully processes your $600 check first. In this case you are guaranteed to have two bounced checks.
• Your bank cares about its soul and purposefully processes the $600 check last. In this case you are guaranteed to get only one bounced check.

Assuming the worst — your bank is evil — what is the answer to the problem? Do you think you will be fined $50? If so, you are wrong. The company to whom you wrote the check will fine you too. Supposing that the company has the same $25 fine as the bank, can we say that you will be fined $100? Nope, this is not correct either. You are forgetting that companies will reprocess your bounced checks two days later and the checks will bounce again. You will be fined twice for each check by two different entities. Thus, you can face $200 in fines.

My next question is: what do you think is a fair fine in my arithmetic problem above?

Banks and companies have never heard of double jeopardy and do not think that it is unconstitutional to fine you twice for the same mistake. No doubt, the second reprocessing of your checks is done “for your convenience”. “For your convenience” they assume that the bouncing was due to a computer glitch, so they should reprocess your check immediately after it has bounced. “For your convenience” no-one will disturb you to notify you that your checks are bouncing. I also believe that if your fine depends on the random order of processing of checks, the banks should be graceful and shouldn’t pick the more profitable order for themselves. I do think that charging you more than $50 in my example is against the law and is not fair.

The law should protect us against entities that rob us “for our convenience.”

One of Microsoft’s biggest contributions to humanity is the popularization of manhole covers. The most famous question that Microsoft asks during job interviews of geeks is probably, “Why are manhole covers round?” Supposedly the right answer is that if a manhole cover is round it can’t be dropped into the hole. See, for example, How Would You Move Mount Fuji? Microsoft’s Cult of the Puzzle – How the World’s Smartest Company Selects the Most Creative Thinkers. This book by William Poundstone is dedicated exclusively to Microsoft’s interview puzzles.

All we need, actually, is for the cover not to fit into the hole. For example, if the hole is small, the cover could be almost any shape, as long as the diameter of the cover is bigger than any straight segment that fits into the hole.

Microsoft makes an implicit assumption that the cover is about the same shape and size as the hole; otherwise we would waste a lot of extra cover material.

Even with this assumption, there is a good deal of flexibility in possible shapes if our only concern is that the cover shouldn’t fit into the hole. It is sufficient for the cover to be any shape with a constant width.

Here are some additional answers to why the cover should be round. Microsoft accepts the answer that a round cover is easier to roll. I’m not sure why a cover would ever have to be moved away from its hole. But I agree that if kids try to steal a cover, it would be much easier to escape with a round one.

Another answer that Microsoft supposedly accepts is that you do not need to rotate a round cover to align it with the opening when you are putting it back. This way if there is a lane divider painted on the cover it will point in a new random direction.

You can find many other explanations at the wiki article devoted to this subject. The most reasonable is that manhole covers are round because manholes are round. Duh!

Thanks to Microsoft there are now many websites with pictures of and discussions on the shape of manhole covers. For example, Manhole Covers Etc. or Manhole.ca or Manhole Covers of the World. As you can see many manhole covers are square or rectangular. They say that New Hampshire had triangular covers at some point.

But my favorite answer to this interview question was sent to me by Jorge Tierno:

Since manhole covers are not necessarily round, but you are asking why they are round, you are probably asking why round manhole covers are round. Round manhole covers are round by definition.

Now I have my own favorite question to ask you during a job interview: “Why are some manhole covers square?”