This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of blog entries.
If you enjoy this page you can support it by shopping at amazon through this link. Thank you.
I am a milk person. I can easily drink half a gallon of milk a day. The problem with half a gallon of milk a day is that it is about half of my target calorie intake. That is why I switched to the reduced-fat milk. It didn't taste good, but I was very proud of myself. That is, I was proud for about a year until I finally decided to read the labels. One serving of whole milk is 150 calories, while one serving of reduced-fat milk is 130 calories. All this year-long suffering saved me an insignificant 13%. Not to mention that the amount of sugar is the same.
I decided to look into this more closely. I went to my nearest super-market and checked the milk. The low-fat milk is 110 calories per serving, while non-fat milk is 90 calories.
If I had just reduced my milk intake by half, I would have consumed fewer calories than by replacing whole milk with non-fat milk, but I would have enjoyed it so much more. The lesson? Read the labels and do the math!
Forty years ago, it took about 18 months for us to find the rules that eventually became the Game of Life. We thought in terms of birth rules and death rules. Maybe one day's death rule would be a bit too strong compared to its birth rule. So the next day at coffee time we'd either try to weaken the death rule or strengthen the birth rule, but either way, only by a tiny bit. They had to be extremely well-balanced; if the death rule was even slightly too strong then almost every configuration would die off. And conversely, if the birth rule was even a little bit stronger than the death rule, almost every configuration would grow explosively.
What's wrong with that, you might ask. Well, if the "radius" grows by 1 unit per generation, then after 9 or 10 moves, it's off the (19 by 19) Go board. We can probably find more Go boards, of course, but after another 20 or so moves it will outflow the coffee table and then it is awfully hard to keep track. We wanted to be able to study configurations for much longer than that, which meant that we had to disallow rules that might lead to linear growth. Of course, we weren't interested in rules that usually led to collapse.
Who were "we"? Well, I was the chief culprit and had an aim in mind — to find a simple set of rules that would lead to a system able to simulate a universal computer. Von Neumann had already shown that this was possible, but his system had 29 states and a very complicated set of rules. The rest of "us" were mostly graduate students who had no higher aim than amusing themselves. Every now and then some rather older colleagues or visitors took an interest.
So my plan was, first, to find a set of rules that almost always prevented explosive growth and catastrophic collapse. Second, I wanted to study it long enough to learn how it could be "programmed". I hoped to find a system whose rules were much simpler than Von Neumann's, preferably with only two states (on and off) per cell, rather than his 29.
I'll just describe the last few rule fiddles. We had in fact given up on finding a two-state system, in favor of one with three states: 0, A, B. State 0 represented an empty cell, and it was natural to think of A and B as two sexes, but we only found their proper names when Martin Huxley walked by and said, "Actresses and bishops!"
Perhaps I should explain this. There is a British anecdote that starts like this:
"The actress sat on the left side of the bed, and removed her stockings. The bishop, on the right side of the bed, removed his gaiters. Then she unbuttoned her blouse and he took off his shirt…"
You are supposed to be getting excited, but it all ends quite tamely, because it turns out that the bishop was in his palace, while the actress was in her bedsit near the theater. There are lots of stories in England about the actress and the bishop, and if a person says something that has a salacious double meaning, it's standard to respond "as the actress said to the bishop," or "as the bishop said to the actress".
Okay, back to Life! To inhibit explosive growth, we decided to imitate biology by letting death be a consequence of either overcrowding or isolation. The population would only grow if the number of neighbors was neither too large nor too small. Rather surprisingly, this turned out to mean that children had to have three or more parents. Let's see why. If two parents could give birth, then in the figure below, the parents A and B, who are on the border of the population, would produce children A' and B' at the next time step, followed by grandchildren A" and B" and so on, thus giving us linear growth!
So we moved to threesomes. Children were born to three parents, made up of both sexes. Moreover, the sex of the child was determined by the sex of its parents — two bishops and one actress would give birth to a little actress, while two actresses and one bishop would produce a tiny bishop. This was "the weaker-sex birth rule," and it was accompanied by "the sexual frustration death rule," which made death the punishment for not touching somebody of the opposite sex!
However, the weaker-sex birth rule lived up to its name, by being weaker than the death rule. Remember we weren't interested in rules that led to disappointingly swift collapses, as the actress said to the bishop. Therefore, we strengthened the birth rule by allowing same-sex conception, but again by applying the weaker-sex rule — so that three actresses would produce a bishop or three bishops an actress. However this strengthened the birth rule too much, causing us to apply the death penalty more often.
We decided to apply the death penalty to those who weren't touching at least two other people, whatever their sex. At first sight it was not obvious that this was stronger than the sexual frustration rule, but in fact it was, because the weaker-sex rule ensured that the sexes were fairly evenly mixed, so if you were touching at least two other people, there was a good chance that one of them would be of the opposite sex.
According to our new set of rules, the sex of parents played no role except to determine the sex of the children, so we abolished sex. After all, according to the bishop, Life without sex is much cleaner.
This is now called the Game of Life and these rules, at last, turned out to be clean and well-balanced.
The article Daring to Discuss Women in Science by John Tierney in the New York Times on June 7, 2010 purports to present a dispassionate scientific defense of Larry Summers's claims, in particular by reviewing and expanding his argument that observed differences in the length of the extreme right tail of the bell curves of men's and women's test scores indicate real differences in their innate ability. But in fact any argument like this has to acknowledge a serious difficulty: it is problematic to assume without comment that the abilities of a group can be inferred from the tail of a bell curve. We are so used to invoking bell curves to talk about group abilities, we don't notice that such arguments usually use only the mean of the curve. Using the tail is a totally different story.
Think about it: it is reasonable to question whether a single data point — the test score of an individual person — is a true indication of his/her ability. It might not be. Maybe a single test score represents a dunce with hyper-overachieving parents who push him to study all the time. So does that single false reading destroy the validity of the curve? No of course not: because some other kid might have been a super-genius who was drunk last night and can barely keep his eyes open during the test. One is testing above his "true ability" and the other is testing below his "true ability," and the effect cancels out. Thus the means of curves are a good way to measure the ability of large groups, because all the random false readings average out.
But tails are not. On the tail this "canceling out" effect doesn't work. Look at the extreme right tail. The relatively slow but hyper-motivated kids are not canceled out by the hoard of far-above-the-mean super geniuses who had drunken revels the night before. There just aren't that many super-geniuses and they just don't party that much.
Or let's look at it another way: imagine that you had a large group which you divided in half totally at random. At this point their bell curve of test scores looks exactly the same. Lets call one of the group "boys" and the other group "girls". But they are two utterly randomly selected groups. Now lets inject the "boys" with a chemical that gives the ones who are very good already a burning desire to dominate any contest they enter into. And let us inject the "girls" with a chemical that makes the ones who are already good nonetheless unwilling to make anyone feel bad by making themselves look too good. What will happen to the two bell curves? Of course the upper tail of the "boys'" curve will stretch out, while the "girls'" tail will shrink in. It will look like the "boys" whipped the "girls" on the right tail of ability hands down, no contest. But the tail has nothing to do with ability. Remember they started out with the same distribution of abilities, before they got their injections. It is only the effect of the chemicals on motivation that makes it look like the "boys" beat the "girls" at the tail.
So, when you see different tails, you can't automatically conclude that this is caused by difference in underlying innate ability. It is possible that other factors are at play — especially since if we were looking to identify these hypothetical chemicals we might find obvious candidates like "testosterone" and "estrogen".
The possibility of alternative explanations for these findings calls into question Tierney and Summers' claims to superior dispassionate scientific objectivity. Moving from the mean to the tail of a bell curve makes systematic effects on averages irrelevant, true, but it is instead susceptible to systematic effects on deviations, which are irrelevant at the mean. An argument that uses this trick to dodge gender differences in averages cannot claim the mantle of scientific responsibility without accounting for gender differences in deviations. I am deeply disappointed that Tierney and Summers did not accompany their assertions with a suitable reminder of this fact.
I recently published a puzzle about wizards, hats of different colors and rooms. Unfortunately, I was too succinct in my description and didn't explicitly mention several assumptions. Although such assumptions are usual in this type of puzzle, I realize now, from your responses, that I should have listed them and I apologize.
The Sultan decided to test the wisdom of his wizards. He collected them together and gave them a task. Tomorrow at noon he will put hats of different colors on each of the wizard's heads.
The wizards have a list of the available colors. There are enough hats of each color for every wizard. The wizards also have a list of rooms. There are enough rooms to assign a different room for every color.
Tomorrow as the Sultan puts hats on the wizards, they will be able to see the colors of the hats of the other wizards, but not the color of their own. Without communicating with each other, each wizard has to choose a room. The challenge comes when two wizards have the same hat color, for they must choose the same room. On the other hand, if they have different hat colors, they must choose different rooms. Wizards have one day to decide on their strategy. If they do not all complete their task, then all of their heads will be chopped off. What strategy would you suggest for the wizards?
In his comment on the first blog about this problem, JBL beautifully described the intended solution for the finite number of wizards, and any potentially-infinite number of colors. I do not want to repeat his full solution here. I would rather describe his solution for two wizards and two colors.
Suppose the colors are red and blue. The wizards will designate one of the rooms as red and another as blue. As soon as each wizard sees the other wizard's hat color, he chooses the room of the color he sees. The beauty of this solution is that if the colors of hats are different, the color of the rooms will not match the color of the corresponding hats: the blue-hatted wizard will go to the red room and vice versa. But the Sultan's condition would still be fulfilled.
JBL's solution doesn't work if the number of wizards is infinite. I know the solution in that case, but I do not like it because it gives more power to the axiom of choice than I am comfortable with. If you are interested, you can extrapolate the solution from my essay on Countable Wise Men with Hats which offers a similar solution to a slightly different problem.
The International Math Olympiad started in Eastern Europe in 1959. Romania was the first host country. The Olympiad grew and only in 1976 did it move outside the Eastern bloc. The competition was held in Austria.
I was on the Soviet team in 1975 and 1976, so I was able to compare competitions held in Eastern vs. Western countries. Of course, the Austrian Olympiad was much better supported financially, but today I want to write about the differences in how our team was prepped.
Before our travel to Austria the Soviet team members were gathered in a room with strangers in suits for a chat. I assumed that we were talking to the KGB. They gave us a series of instructions. For example, they told us not to leave the campus during the competition, to always walk in groups, and to avoid talking to kids from countries that are enemies of the USSR. They warned us that they would be watching, and I was scared to death.
Now that I am older and wiser, I understand that their goal was to frighten us. Our team traveled with adult supervisors, who were trusted by the KGB. But for several days during the grading period of the competition, our supervisors were not allowed to see us. So the KGB wanted us to be too afraid to be very adventurous when we were left on our own.
In addition, the KGB had a Jewish problem. In general, Jews were not allowed to go abroad. I had many Jewish friends who qualified for the pre-IMO math camp where the team was chosen, but who were not able to get on the IMO because of delays with their travel documents. Some local bureaucrats were eager to impress the KGB and therefore held up visas for Jewish students, preventing them from being on the team. But the team selection process itself wasn't yet corrupt in 1976. So every year despite the efforts of the system, some young Jewish mathematicians would end up on the team.
Before 1976, the Olympiad was in the Eastern bloc, so the KGB wasn't quite so concerned about having Jewish members on the team. But Austria was not only a Western country, it was also the transition point for Jewish refugees from the Soviet Union. The speed with which the IMO moved their competition to a Western country was much faster than the Soviet bureaucratic machine could build a mechanism for completely preventing Jews from joining the team.
One very strong candidate, Yura Pass, didn't get his documents, but two other Jewish boys made it on to the team that was going to Austria. They were joking that they would be the only Soviet Jews who would go to Austria and actually come back. They did come back, only to go forward later: both are now math professors working in the US.
Because we had Jewish members on our team, it gave the KGB a special extra reason to scare us. But the biggest pressure was to win. We were told that 1976 was the most important year for the Soviet team to be the best. We were told that capitalist countries spread rumors that the judges in Eastern bloc countries favored the Soviet team and that the relative success of the Soviet team throughout the years had not been fully deserved. Now that the competition was in Austria, the suits told us, the enemies of the USSR were hoping for the downfall of the Soviet team. Our task was to prove once and for all that the Soviet students were the best at math, and that the rumors were unfounded. We had to win the team competition not only to prove ourselves, but also to clear the name of the Soviet team for all the previous years.
We did have a very strong team. The USSR came out first with 250 points, followed by the UK with 214 points and the USA with 188 points. Out of nine gold medals, we took four.
We could have gotten one more gold medal if Yura Pass had been allowed on the team. Yura was crushed by the machine's treatment of Jews and soon afterwards quit mathematics.
I just received a mass email on how to live longer and it made these points:
Tip 1. Delay your retirement. Studies show that people who retire at 65 live longer than people who retire at 60.
Tip 2. Sex makes you younger. Studies show that older people who have sex twice a week look ten years younger than their peers who do not have sex at all.
People who draw conclusions from such studies usually do not understand statistics. Correlation doesn't mean causality. Let me use the above-mentioned studies to reach different conclusions by reversing the causality assumption of the unknown writer of the mass email. You can compare results and make your own decisions.
Case 1. Studies show that people who retire at 65 live longer than people who retire at 60. Reversed causality: People who live longer are healthier, so they are able to keep working and to retire later in life.
Case 2. Studies show that older people who have sex twice a week look ten years younger than their peers who do not have sex at all. Reversed causality: Older people who look ten years younger than their peers can get laid easier, so they have sex more often.
Sergei just came back from MOP — Mathematical Olympiad Summer Program, where he was a grader. The first question I asked him was, "What was your favorite math problem there?" Here it is:
There are wisemen, hats and rooms. Hats are of different color and there are enough hats of each color for every wisemen. There are enough rooms, so that you can assign a different room for every color. At some moment in time the sultan puts hats on the wisemen's heads, so as usual they see all other hats, but do not see their own hat color. At the same time, each wiseman has to choose a room to go to. If two wisemen have the same hat color, they should go to the same room. If they have different hat colors, they should go to different rooms. What strategy should the wisemen decide upon before this event takes place?
Oh, I forgot to mention the most interesting part of this problem is that you shouldn't assume that the number of wisemen or hats or rooms is finite. You should just assume that they have the power of choice.
My son Alexey Radul and I were discussing the Tuesday's child puzzle:
You run into an old friend. He has two children, but you do not know their genders. He says, "I have a son born on a Tuesday." What is the probability that his second child is also a son?
Here is a letter he wrote me on the subject. I liked it because unlike many other discussions, Alexey not only asserts that different interpretations of the conditions in the puzzle form different mathematical problems, but also measures how different they are.
If you assume that boys and girls are symmetric, and that days of the week are symmetric (and if you have no information to the contrary, assuming anything else would be sheer presumption on your part), then you can be in one of at least two states.
1) You say that "at least one son born on a Tuesday" is all the information you have, in which case your distribution including this information is uniform over consistent cases, in which case your answer is 13/27 boy and your information entropy is
− ∑27 (1/27) log(1/27) = − log(1/27) = 3.2958.
2) You say that the information you have is "The guy might have said
any true thing of the form 'I have at least one {boy/girl} born on a
{day of the week}', and he said 'boy', 'Tuesday'." This is a
different mathematical problem with a different solution. The
solution: By a symmetry argument (see below [*]) we must assign uniform
probability of him making any true statement in any particular
situation. Then we proceed by Bayes' Rule: the statement we heard is
d, and for each possible collection of children
− ∑ p log p = − 1/14 log 1/14 − 26/28 log 1/28 = 3.2827
Therefore that assumed additional structure really is more information, which is only present at best implicitly in the original problem. How much more information? The difference in entropies is 3.2958 - 3.2827 = 0.0131 nats (a nat is to a bit what the natural log is to the binary log). How much information is that? Well, the best I can do is to reproduce an argument of E.T. Jaynes', which may or may not really apply to this situation. Suppose you have some repeatable experiment with some discrete set of possible outcomes, and suppose you assign probabilities to those outcomes. Then the number of ways those probabilities can be realized as frequencies counted over N trials is proportional to eNH, where H is the entropy of the distribution in nats. Which means that the ratio by which one distribution is easier to realize is approximately eN(H1-H2). In the case of N = 1000 and H1 - H2 = 0.0131, that's circa 5x105. For each way to get a 1000-trial experiment to agree with version 2, there are half a million ways to get a 1000-trial experiment to agree with version 1. So that's a nontrivial assumption.
[*] The symmetry argument: We are faced with the following probability assignment problem
Suppose our subject's first child is a boy born on a Tuesday, and his second child is a girl born on a Friday. What probability must we assign to him asserting that he has at least one boy born on a Tuesday?
Good question. Let's transform our coordinates: Let Tuesday' be Friday, Friday' be Tuesday, boy' be girl, girl' be boy, first' be second and second' be first. Then our problem becomes
Suppose our subject's second' child is a girl' born on a Friday', and his first' child is a boy' born on a Tuesday'. What probability must we assign to him asserting that he has at least one girl' born on a Friday'?
Our transformation necessitates p(boy Tuesday) = p(girl' Friday'), and likewise p(girl Friday) = p(boy' Tuesday'). But our state of complete ignorance about what's going on with respect to the man's attitudes about boys, girls, Tuesdays, Fridays, and first and second children has the symmetry that question and question' are the same question, and must, by the desideratum of consistency, have the same answer. Therefore p(boy Tuesday) = p(boy' Tuesday') = p(girl Friday) = 1/2.
My classmate Misha gave me a math problem. Although I liked the math part, I hated the setup. Here is the problem using the new setup:
You are hoping to get very rich one day and you base your hopes on your new invention: a diet pill. The pill works beautifully and doesn't have side effects. Patients simply take a pill when they get hungry. Within one hour they will fall asleep and will be unable to awake for exactly two hours, at which time they will awake by themselves feeling completely sated.
You have just arrived at your lab, when you realize that one of your interns has misplaced your bottle of wonder pills. After some investigation, you come to the conclusion that your bottle is on the shelf with 239 other bottles that contain a placebo. Unfortunately, those placebo bottles were custom-designed for your statistical tests to exactly match your medicine bottle.
You need to bring the medicine bottle to your boss in two hours. While you panic, all your five interns volunteer for experiments, hoping to be mentioned in your paper. Can you find your bottle in two hours?
The problem Misha gave me had 240 barrels of wine, one of which contained deadly poison and five slaves who could be spared.
I do not like killing people even when they are imaginary. But while I was slow in inventing my own setup, the original version of the puzzle started making the rounds on the Internet. So I decided to kill the problem by writing the solution.
The strategy is to give out some pills immediately, wait for one hour and see who falls asleep. The next step is to give some other pills at the beginning of the next hour to some of the interns who are awake.
Let's count the information you can get out of this. Each intern will experience one of three different situations: falling asleep in the first hour, in the second hour, or not falling asleep at all. Thus, you can have a total of 35 = 243 different outcomes.
If you had more bottles than 243, there would be no way to distinguish between them. The fact that you have 240 bottles might mean that 243 will work too, but apparently the designer of the puzzle didn't want to hint into powers of three and picked the largest round number below 243. These considerations should increase your willingness to look into this problem base 3.
Let us label the bottles with different 5-character strings containing three characters 0, 1, and 2. Now we can use the label as instructions. The first character will be associated with the first intern and so on. Suppose the fourth character on the bottle's label is 0, then the fourth intern doesn't need to struggle with digesting a pill from this particular bottle. If the fourth character is 1, then the fourth intern gets the pill in the first hour. If the fourth character is 2, the fourth intern gets the pill in the second hour.
Note this minor detail: Suppose the fourth character on a bottle is 2, but the fourth intern is asleep by the second hour. That means, the bottle doesn't contain the medicine, and we can put it aside.
At the end of two hours you know who fell asleep and when. This data will exactly match the label on the bottle with the medicine.
Once I read a book in Russian that mentioned a study of the children of Soviet military personnel who had to move often. The conclusion was that frequent relocation is very damaging for children's psyche. The children had to build new friendships, which they would lose the next time they had to move. After several moves they would stop making friends; later, as adults, they would be afraid of getting close to anyone.
In September 1996, my husband, my two children and I came to Princeton from Israel for my husband's month-long visit to the Institute for Advanced Study. After the visit we were supposed to go back to Israel, but that didn't happen. My husband returned alone and I stayed in Princeton with my children. That's a long and sentimental story for another time.
Meanwhile, my older son Alexey started going to Princeton High School. By this time he had attended seven schools in three different countries. In light of the evidence presented in that book about the impact on children of moving, I felt very guilty. Alexey was entering 10th grade. Moving him again not only would further damage his ability to make friends, but would also screw up his college chances. He needed a stable environment leading up to college. For example, recommendation letters are better written by people who are involved with kids for several years. I was afraid to mess up his future. I promised myself not to move him again during high school, especially as Princeton High School was one of the best public schools in New Jersey.
At the same time, I got a Visiting Scholar position at Princeton University. Although it didn't pay me any salary, through that position I received university housing, library privileges and an office. I was living on my personal savings and the monthly check my husband was sending me from Israel. My money was running out and I felt completely lost, like so many immigrants. I was new to Princeton; I didn't have friends there; and I was struggling with English. On top of that, I had medical problems, not the least very low energy.
Ingrid Daubechies noticed me at the Princeton math department and approached me. After our conversation, she found some money for me to work on the Math Alive course she was designing. That work was a breath of fresh air. I enjoyed it tremendously, but the part-time salary was not enough. Then I received more help from Ingrid. She appreciated my work on Math Alive a lot, but realized that I needed a different solution. She sacrificed her own interests and started recommending me around. She arranged an interview for me at Telcordia, who offered me a job as a systems engineer.
The decision to accept this job was very painful, because I did not want to leave academia. However, considering that my priority was to keep Alexey in Princeton High School, I didn't feel I had other options. I knew that I couldn't stay much longer at Princeton University and I was aware that getting a University job often requires relocation.
Looking back, I think the reasons behind this decision were more complex than sacrificing my career for my child. If I had known more about social supports for poor families and about other possible research jobs, or if I had been more confident in my research abilities, I might not have left academics.
Alexey triumphed at Princeton High School. The school allowed him to take math courses at Princeton University. He took several, including the course in logic by John Conway and two courses in graph theory by Paul Seymour. Alexey's multi-variable calculus professor complained to me that she couldn't fit her grades into the required curve. If she gave Alexey 100%, the others would have to get less than 20. Luckily, it turned out that because her class was small, she didn't need to bother about making a curve. After three years in Princeton High School, Alexey secured an impressive resume and great recommendation letters and went to MIT to pursue a double major in mathematics and computer science.
Alexey translated from a Russian joke site:
American scientists finally developed a car that runs on water. Unfortunately, at the moment it only runs on water from the Gulf of Mexico.
I've heard about many mathematicians running polymath projects through their blogs. I wasn't planning to do that. It just happened. In this essay, I describe the collaborative effort that was made to solve the following problem that appeared in my blog on July 2009:
Baron Münchhausen has n identical-looking coins weighing 1, 2, …, n grams. The Baron's guests know that he has this set of coins, but do not know which one is which. The Baron knows which coin is which and wants to demonstrate to his guests that he is right. He plans to conduct weighings on a balance scale, so that the guests will be convinced about the weight of every of coin. What is the smallest number of weighings that the Baron must do in order to reveal the weights?
The sequence a(n) of the minimal number of weighings is called the Baron Münchhausen's omni-sequence to distinguish it from the Existential Baron's sequence where he needs the smallest amount of weighings to prove the weight of one coin of his choosing.
In this essay I will describe efforts to calculate a(n). The contributors are: Max Alekseyev, Ilya Bogdanov, Maxim Kalenkov, Konstantin Knop, Joel Lewis and Alexey Radul.
The sequence starts as a(1) = 0, because there is nothing to demonstrate. Next, a(2) = 1, since with only one weighing you can find which coin is lighter.
Next, a(3) = 2. Indeed you can't prove all the coins in one weighing, but in the first weighing you can show that the 1-gram coin is lighter than the 2-gram coin. In the second weighing you can show that the 2-gram coin is lighter than the 3-gram coin. Thus, in two weighings you can establish an order of weights and prove the weight of all three coins.
As you can see in the case of n = 3, you can compare coins in order and prove the weight of all the coins in n − 1 weighings. But this is not at all the optimal number. Let us see why a(4) = 2. In his first weighing the Baron can put the 1- and the 2-gram coins on the left pan of the balance and the 4-gram coin on the right pan. In the future, I will just describe that weighing as 1 + 2 < 4. This way everyone agrees that the coin on the right pan is 4 grams, and the coin that is left out is 3 grams. The only thing that is left to do is to compare the 1-gram and the 2-gram coins in the second weighing.
Later Konstantin Knop sent me a different solution for n=4. His solution provides an interesting example. While looking for solutions, people usually try to have an unbalanced weighing to be "tight". That is, they make it so that the heavier cup is exactly 1 gram heavier than the lighter cup. If you are trying to prove one coin in one weighing, "tightness" is a requirement. But it is not necessary when you have several weighings. Here is the first weighing in Konstantin's solution: 1 + 3 = 4; and his second second weighing is: 1 + 2 < 3 + 4. We see that the second weighing has a weight difference of four between pans.
Next, a(5) = 2. We can have the first weighing the same as before: 1 + 2 < 4, and the second weighing: 1 + 4 = 5. The second weighing confirms that the heavy coin on the right pan in the first weighing can't be the heaviest one, thus it has to be the 4-gram coin. After that you can see that every coin is identified.
Next, a(6) = 2. The first weighing, 1 + 2 + 3 = 6, divides all coins into three groups: {1,2,3}, {4,5} and {6}. We know to which group each coin belongs, but we do not know which coin in the group is which. The second weighing: 1 + 6 < 3 + 5, identifies every coin. Indeed, the only possibility for the left side to weigh less than the right side is when the smallest weighing coin from the first group and 6 are on the left, and the two largest weighing coins from the first two groups are on the right.
When I was writing my essay I suspected that n = 6 is the largest number for which a solution can be established in two weighings, but I didn't have any proof. So I was embarrassed to show my solutions of three weighings n equals 7, 8 and 9.
On the other hand I published the solutions suggested by my son, Alexey Radul, for n = 10 and n = 11. In these cases the theoretical lower bound of log3(n) for a(n) is equal to 3, and finding solutions in three weighings was enough to establish the value of the sequence a(n) for n = 10 and n = 11.
So, a(10) = 3, and here are the weighings. The first weighing is 1 + 2 + 3 + 4 = 10. After this weighing, we can divide the coins into three groups {1,2,3,4}, {5,6,7,8,9} and {10}. The second weighing is 1 + 5 + 10 < 8 + 9. After the second weighing we can divide all coins into groups we know they belong to: {1}, {2,3,4}, {5}, {6,7}, {8,9} and {10}. The last weighing contains the lowest weighing coin from each non-single-coin group on the left and the largest weighing coin on the right, plus, in order to balance them, the coins whose weights we know. The last weighing is 2 + 6 + 8 + 5 = 4 + 7 + 9 + 1.
Similarly, a(11) = 3, and the weighings are: 1 + 2 + 3 + 4 < 11; 1 + 2 + 5 + 11 = 9 + 10; 6 + 9 + 1 + 3 = 8 + 4 + 2 + 5.
After publishing my blog I wrote a letter to the Sequence Fans mailing list asking them to expand the sequence. Max Alekseyev replied with the results of an exhaustive search program he wrote. First of all, he found a counter-intuitive solution for n=6. Namely, the following two weighings: 1 + 3 < 5 and 1 + 2+ 5 < 3 + 6. He also confirmed that it is not possible to identify the coins in two weighings for n=7, n=8 and n=9.
So now I can stop being embarrassed and proudly present my solution for n=7 in three weighings. That is, a(7) = 3 and the first weighing is: 1+2+3 < 7, and it divides all the coins into three groups {1,2,3}, {4,5,6} and 7. The second weighing, 1 + 4 < 6, divides them even further. Now we know the identity of every coin except the group {2,3}, which we can disambiguate with the third weighing: 2 < 3.
In many solutions that I've seen, one of the weighings was very special: every coin on one cup was lighter than every coin on the other cup. I wondered if that was always the case. Konstantin Knop send me a counterexample for n=7. The first weighing is: 1 + 2 + 3 + 5 = 4 + 7. The second is: 1 + 2 + 4 < 3 + 5. The third is: 1 + 3 + 4 = 2 + 6.
Later Max Alekseyev sent me two more special solutions for n=7. The first one contains only equalities: 2 + 5 = 7; 1 + 2 + 4 = 7; 1 + 2 + 3 + 5 = 4 + 7. The second one contains only inequalities: 1 + 3 < 5; 1 + 2 + 5 < 3 + 6; 5 + 6 < 2 + 3 + 7.
Moving to the next index, a(8) = 3 and the first weighing is: 1 + 2 + 3 + 4 + 5 < 7 + 8. The second weighing is: 1 + 2 + 5 < 4 + 6. After that we have identified all coins but two groups {1,2} and {3,4} that can be resolved by 2 + 4 = 6.
Meanwhile my blog received a comment from Konstantin Knop who claimed that he found solutions in three weighings for n in the range between 12 and 17 inclusive and four weighings for n = 53. I had already corresponded with Konstantin and knew that his claims are always well-founded, so I didn't doubt that he had found the solutions.
Later I began to write a paper with Joel Lewis on the upper bound of the omni-sequence, where we prove that a(n) ≤ 2 ⌈log2n⌉. For this paper, we wanted a comprehensive set of examples, so I emailed Konstantin asking him to write up his solutions. He promptly sent me the results and mentioned that he had found the weighings together with Ilya Bogdanov. They used several different ideas in the solutions. First I'll describe their solutions based on ideas we've already seen, namely to compare the lightest coins in the range to the heaviest coins.
Here is the proof that a(13) = 3. The first weighing is: 1 + … + 8 = 11 + 12 + 13, and it identifies the groups {1, 2, 3, 4, 5, 6, 7, 8}, {9, 10} and {11, 12, 13}. The second weighing is: (1 + 2 + 3) + 9 + (11 + 12) = (7 + 8) + 10 + 13, and it divides them further into groups {1, 2, 3}, {4, 5, 6}, {7, 8}, {9}, {10}, {11, 12}, {13}. And the last weighing identifies all the coins: 1 + 4 + 7 + 11 + 9 + 10 = 3 + 6 + 8 + 12 + 13.
Similarly, let us show that a(15) = 3. The first weighing is: 1 + … + 7 < 14 + 15, and it divides the coins into three groups {1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13}, and {14, 15}. The second weighing is: (1 + 2 + 3) + 8 + (14 + 15) = (5 + 6 + 7) + (12 + 13), and this divides them further into groups {1, 2, 3}, {4}, {5, 6, 7}, {8}, {9, 10, 11}, {12, 13} and {14, 15}. The third weighing identifies every coin: 1 + 5 + 8 + 9 + 12 + 14 = 3 + 7 + 11 + 13 + 15.
As I mentioned earlier it is not always possible to find the first weighing which will nicely divide the coins into groups. We already discussed an example, n = 5, in which neither of the two weighings divided the coins into groups. Likewise, the same thing happened in the second mysterious solution for n = 6. What these solutions have in common is that the first weighing nearly divides everything nicely. The left pan is almost the set of the lightest coins and the right pan is almost the set of the heaviest coins. But not quite.
That is not our only situation in which the first weighing does not quite divide the coins into groups. For example, here is Konstantin's solution for a(9) = 3. For the first weighing, we put five coins on the left pan and two coins on the right pan. The left pan is lighter. This could happen in three different ways:
The second weighing, 1 + 2 + 3 = 6, in which we took three coins from the left pan and balanced them against one coin – again from the left pan – could only happen in case "C." After the two weighings, the following groups were identified: {1, 2, 3}, {4}, {5, 7}, {6}, {8, 9}. The third weighing, 1 + 4 + 5 + 8 < 3 + 7 + 9, identifies all the coins.
A similar technique is used in the solution that Konstantin sent to us to demonstrate that a(12) = 3. The first weighing is: 1 + 2 + 3 + 4 + 5 + 6 < 10 + 12. The audience which sees the results of the weighings understands that there are three possibilities for the distribution of coins:
The second weighing, (1 + 2 + 3) + (7 + 8) + 10 < (9 + 11 ) + 12, convinces the audience that the left pan must weigh at least 31 if the first weighing was case "A" above (31 = 1 + 2 + 3 + 7 + 8 + 10) or "C" (31 = 1 + 2 + 3 + 6 + 8 + 11), and at least 32 (32 = 1 + 2 + 3 + 7 + 8 + 11) if the first weighing was case "B." At the same time the right pan is not more than 12 + 9 + 11 = 32 for case "A" above, not more than 12 + 9 + 10 = 31 for case "B" and not more than 12 + 9 + 10 = 31 for case "C."
Hence the inequality in the second weighing is only possible when the first weighing was indeed as described by case "A" above. Consequently, the first two weighings together identify groups: {1, 2, 3}, {4, 5, 6}, {7, 8}, {9}, {10}, {11} and {12}. The third weighing, 1 + 4 + 7 + 11 + 12 < 3 + 6 + 8 + 9 + 10, identifies all the coins.
Other cases that Konstantin Knop sent me used a completely different technique. I would like to explain this technique using the mysterious solution for n = 6 found by Max Alekseyev. Suppose we have six coins labeled c1, … c6. The first weighing is: c1 + c3 < c5. The second weighing is: c1 + c2 + c5 < c3 + c6.
Let us prove that these two weighings identify all the coins. Let us replace the two inequalities above with the following: c1 + c3 − c5 ≤ −1, and c1 + c2 + c5 − c3 − c6 ≤ −1. Now we multiply the first inequality by 3 and the second by 2 and sum the results. We get: 5c1 + 2c2 + c3 + 0c4 − c5 − 2c6 ≤ −5. Note that the coefficients for labels are in a decreasing order. By the rearrangement inequality the smallest value the expression 5c1 + 2c2 + c3 + 0c4 − c5 − 2c6 reaches is when the labels on the coins match the indices. This smallest value is −5. Hence, the labels have to match the coins.
The technique that Konstantin and his collaborators are using is to search for appropriate coefficients to multiply the weighings by, rather than searching for the weighings themselves. In lieu of lengthy explanations, I will just list the weighings that he uses together with coefficients to multiply them by for their proof that the weighings differentiate coins.
We will start with showing that a(14) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 < 11 + 13 + 14, and: 1 + 2 + 3 + 8 + 11 + 13 = 7 + 9 + 10 + 12, followed by 1 + 4 + 7 + 10 = 3 + 6 + 13. The coefficients to multiply by are {9, 5, 2}.
Next we will show that a(16) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 6 + 8 < 14 + 16, and 1 + 2 + 3 + 7 + 9 + 14 = 8 + 13 + 15, followed by 1 + 4 + 7 + 10 + 13 < 3 + 6 + 12 + 15. The coefficients to multiply by are {11, 5, 2}.
Next we will show that a(17) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 + 10 < 15 + 16 + 17, and 1 + 2 + 3 + 8 + 11 + 15 + 16 < 7 + 9 + 10 + 14 + 17, and 1 + 4 + 7 + 8 + 12 + 14 = 3 + 6 + 10 + 11 + 16. The coefficients to multiply by are {11, 5, 2}.
Next we will show that a(53) = 4. The weighings are: (1 + 2 + … + 23) + 25 < 47 + (49 + … + 53), and (1 + … + 9) + 24 + (26+ … + 31) + 47 + (49 + … + 52) < (16 + … + 23) + 25 + (41 + … + 46) + 48 + (51 + 52), and (1 + 2 + 3) + (10 + 11) + (16 + 17 + 18) + 24 + (26 + 27) + (32 + 33 + 34) + (41 + 42 + 43) + 47 + 49 + 53 =(7 + 8 + 9) + 15 + (22 + 23) + 25 + (30 + 31) + (38 + 39) + 40 + (45 + 46) + 48 + (51 + 52), and the last one 1 + 4 + 7 + 10 + 12 + 16 + 19 + 22 + 24 + 28 + 30 + 32 + 35 + 38 + 41 + 45 + 47 + 51 + 53 < 3 + 6 + 9 + 11 + 14 + 18 + 21 + 25 + 27 + 29 + 34 + 37 + 40 + 43 + 48 + 49 + 50 + 52. The coefficients to multiply by are {43, 15, 5, 2}.
When I was working on the paper with Joel Lewis I re-established my email discussions about the Baron's onmi-sequence with Konstantin Knop. At that time Konstantin's colleague, Maxim Kalenkov, got interested in the subject and wrote a computer search program to find other solutions that can be proven with the rearrangement inequality. Thus, we know two more terms of this sequence.
The next known term is a(18) = 3. The weighings are: 1 + 2 + 4 + 5 + 7 + 10 + 12 = 9 + 15 + 17, and 1 + 3 + 4 + 6 + 9 + 11 + 17 = 7 + 12 + 14 + 18, and 2 + 3 + 7 + 8 + 9 + 14 + 15 = 4 + 10 + 11 + 16 + 17. The corresponding coefficients are: {8, 7, 5}.
Similarly, a(19) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 7 + 8 + 10 + 13 = 16 + 18 + 19, and 1 + 2 + 3 + 6 + 9 + 11 + 16 = 8 + 10 + 13 + 17, and 1 + 4 + 6 + 8 + 12 + 18 = 3 + 7 + 11 + 13 + 15. The coefficients are {12, 7, 3}.
Maxim Kalenkov continued his search. He didn't find any new solutions in three weighings, but he found a lot of solutions in four weighings, namely for numbers from 20 to 58. Below are his solutions, with multiplier coefficients in front of every weighing:
a(20) ≤ 4
18: 1+2+3+4+5+10+14+16+18 = 6+7+11+12+17+20
19: 1+2+4+5+12+15+17+19 < 6+8+10+14+18+20
21: 2+6+11+17+18 = 4+9+10+15+16
26: 1+6+7+8+9+10+20 = 2+5+17+18+19
a(21) ≤ 4
18: 3+5+6+11+15+17+19 = 7+8+9+13+18+21
19: 4+6+9+13+16+18+20 = 1+7+11+12+15+19+21
21: 1+4+5+7+12+18+19 = 3+9+10+11+16+17
26: 1+2+3+7+8+9+10+11+21 = 4+5+6+18+19+20
a(22) ≤ 4
18: 3+5+6+12+15+17+20 = 7+8+10+13+18+22
19: 1+2+4+10+13+16+18+21 = 7+9+12+15+20+22
21: 1+6+7+18+19+20 = 2+3+10+11+12+16+17
26: 2+3+7+8+9+10+11+12+22 = 6+18+19+20+21
a(22) ≤ 4
18: 1+2+5+6+12+16+18+22 < 3+7+8+10+13+19+23
19: 1+3+4+6+10+17+19+21 = 7+9+12+14+16+23
21: 3+7+13+14+19+20 = 2+6+10+11+12+17+18
26: 2+7+8+9+10+11+12+23 = 19+20+21+22
a(24) ≤ 4
18: 1+3+6+12+17+19+21+23 < 2+4+7+8+10+13+15+20+24
19: 1+2+4+5+6+10+15+18+20+22 < 7+9+12+14+17+21+24
21: 4+7+13+14+20+21 = 3+6+10+11+12+18+19
26: 2+3+7+8+9+10+11+12+24 = 20+21+22+23
a(25) ≤ 4
18: 1+2+3+5+6+8+9+14+17+19+22 < 10+12+16+20+24+25
19: 2+6+7+9+12+16+18+20+23 = 10+11+14+15+17+22+24
21: 1+2+4+7+8+10+15+20+21+22 = 3+6+12+13+14+18+19+25
26: 3+10+11+12+13+14+24+25 = 2+7+8+9+20+21+22+23
a(26) ≤ 4
18: 1+2+3+5+6+8+9+14+18+20+23 = 10+12+15+21+25+26
19: 2+3+4+6+7+9+12+19+21+24 = 11+14+16+18+23+25
21: 7+8+15+16+21+22+23 = 2+6+12+13+14+19+20+26
26: 1+2+10+11+12+13+14+25+26 = 7+8+9+21+22+23+24
a(27) ≤ 4
18: 1+3+4+6+7+8+9+14+19+21+23+25 < 10+11+13+15+17+22+26+27
19: 1+2+3+5+7+9+13+17+20+22+24 < 4+10+12+14+16+19+23+26
21: 2+3+4+8+10+15+16+22+23 = 1+7+13+14+20+21+27
26: 1+10+11+12+13+14+26+27 = 3+8+9+22+23+24+25
a(28) = 4
18: 3+6+8+9+10+15+19+21+24+26 = 1+5+11+13+16+18+22+27+28
19: 1+4+5+7+9+10+13+18+20+22+25 = 3+6+11+12+15+17+19+24+27
21: 5+6+11+16+17+22+23+24 = 4+9+13+14+15+20+21+28
26: 1+2+3+4+11+12+13+14+15+27+28 = 10+22+23+24+25+26
a(29) = 4
18: 1+3+5+6+7+9+10+16+20+22+25+27 < 11+12+14+17+18+23+28+29
19: 4+8+10+14+18+21+23+26 = 2+3+6+11+13+16+20+25+28
21: 1+2+6+8+9+11+17+23+24+25 = 4+5+14+15+16+21+22+29
26: 2+3+4+5+11+12+13+14+15+16+28+29 = 8+9+10+23+24+25+26+27
a(30) = 4
18: 2+8+10+16+21+23+26+27+28 = 5+11+12+14+17+19+24+29+30
19: 2+4+5+7+9+14+19+22+24+28 = 11+13+16+18+21+26+29
21: 1+5+6+9+10+11+17+18+24+25+26 = 4+14+15+16+22+23+28+30
26: 1+3+4+11+12+13+14+15+16+29+30 < 9+10+24+25+26+27+28
a(31) = 4
18: 1+2+6+9+10+16+21+23+26+28+29 < 3+4+7+11+12+14+17+19+24+30+31
19: 1+2+4+7+14+19+22+24+27+29 < 6+9+11+13+16+18+21+26+30
21: 2+3+7+8+9+11+17+18+24+25+26 = 14+15+16+22+23+29+31
26: 1+3+4+5+6+11+12+13+14+15+16+30+31 = 2+24+25+26+27+28+29
a(32) = 4
18: 1+5+8+9+10+12+13+22+24+27+29 = 6+14+16+18+20+25+30+31
19: 4+6+10+11+13+16+20+23+25+28 = 1+2+8+15+19+22+27+30+32
21: 1+2+6+7+8+11+12+18+19+25+26+27 = 4+5+10+16+17+23+24+31+32
26: 1+2+3+4+5+14+15+16+17+30+31+32 < 11+12+13+25+26+27+28+29
a(33) = 4
18: 1+2+6+7+8+9+10+12+13+23+27+29+30 = 3+14+15+17+19+21+25+31+32
19: 1+2+10+11+13+17+21+24+25+28+30 = 4+6+8+14+16+20+23+27+31+33
21: 1+3+4+8+11+12+14+19+20+25+26+27 < 7+10+17+18+24+30+32+33
26: 3+4+5+6+7+14+15+16+17+18+31+32+33 = 11+12+13+25+26+27+28+29+30
a(34) = 4
18: 2+3+4+8+10+12+13+19+24+28+30+31 < 6+14+15+17+20+22+26+32+33
19: 1+2+3+5+6+9+11+13+17+22+25+26+29+31 = 4+8+14+16+19+21+24+28+32+34
21: 1+3+6+7+8+11+12+14+20+21+26+27+28 = 2+5+17+18+19+25+31+33+34
26: 1+2+4+5+14+15+16+17+18+19+32+33+34 = 3+11+12+13+26+27+28+29+30+31
a(35) = 4
18: 1+3+4+6+8+10+11+13+19+24+26+29+31+32 = 14+15+17+20+22+27+33+34+35
19: 1+4+7+9+11+12+17+22+25+27+30+32 = 6+14+16+19+21+24+29+33+35
21: 2+12+13+14+20+21+27+28+29+35 = 4+7+8+11+17+18+19+25+26+32+34
26: 1+2+3+4+5+6+7+8+14+15+16+17+18+19+33+34 = 12+13+27+28+29+30+31+32
a(36) = 4
18: 1+2+3+4+5+9+11+12+14+15+20+25+29+31+32 < 6+16+18+21+23+27+33+34+36
19: 1+2+4+5+6+8+10+12+13+15+18+23+26+27+30+32 < 16+17+20+22+25+29+33+35+36
21: 1+3+5+13+14+16+21+22+27+28+29+36 = 2+8+9+12+18+19+20+26+32+34+35
26: 2+6+7+8+9+16+17+18+19+20+33+34+35 = 5+13+14+15+27+28+29+30+31+32
a(37) = 4
18: 1+2+3+6+8+10+12+13+15+16+21+27+30+32+33 = 4+9+17+19+22+24+28+34+35+37
19: 1+2+3+7+9+11+13+14+16+19+24+26+28+31+33 = 5+6+10+17+18+21+23+30+34+36+37
21: 3+4+5+9+10+14+15+17+22+23+28+29+30+37 = 1+7+8+13+19+20+21+26+27+33+35+36
26: 1+4+5+6+7+8+17+18+19+20+21+34+35+36 = 3+14+15+16+28+29+30+31+32+33
a(38) = 4
18: 2+3+4+7+9+11+13+15+16+21+26+28+31+33+34 = 5+10+17+18+19+22+24+29+35+36+38
19: 1+3+4+8+10+12+13+14+16+19+24+27+29+32+34 = 7+11+17+21+23+26+31+35+37+38
21: 1+2+4+5+10+11+14+15+17+22+23+29+30+31+38 = 8+9+13+19+20+21+27+28+34+36+37
26: 5+6+7+8+9+17+18+19+20+21+35+36+37 = 4+14+15+16+29+30+31+32+33+34
a(39) = 4
18: 1+2+4+7+9+11+13+14+16+22+27+29+32+34+35 = 10+17+18+20+23+25+30+36+38+39
19: 2+3+4+8+10+12+14+15+20+25+28+30+33+35 = 5+7+11+17+19+22+24+27+32+37+38
21: 1+2+3+5+10+11+15+16+17+23+24+30+31+32+38 < 8+9+14+20+21+22+28+29+35+36+37
26: 1+5+6+7+8+9+17+18+19+20+21+22+36+37 = 15+16+30+31+32+33+34+35
a(40) = 4
18: 1+2+3+4+5+8+9+12+14+15+17+18+23+27+29+32+34+35 < 7+10+19+21+24+26+30+36+37+39+40
19: 1+3+4+5+7+10+13+15+16+18+21+26+28+30+33+35 < 6+8+12+20+23+25+27+32+36+38+39
21: 1+5+6+10+11+12+16+17+24+25+30+31+32+39 < 3+9+15+21+22+23+28+29+35+37+38
26: 2+3+6+7+8+9+19+20+21+22+23+36+37+38 = 5+16+17+18+30+31+32+33+34+35
a(41) = 4
18: 1+3+5+6+8+10+12+14+15+17+18+23+28+30+33+35+36 < 7+11+19+21+24+26+31+37+38+40+41
19: 1+2+4+5+6+7+9+11+13+15+16+18+21+26+29+31+34+36 = 8+12+19+20+23+25+28+33+37+39+40
21: 1+4+6+11+12+16+17+19+24+25+31+32+33+40 < 9+10+15+21+22+23+29+30+36+38+39
26: 2+3+7+8+9+10+19+20+21+22+23+37+38+39 = 6+16+17+18+31+32+33+34+35+36
a(42) = 4
18: 1+3+5+6+7+11+13+15+16+18+24+29+31+34+36+37 = 2+8+12+19+20+22+25+27+32+38+40+41
19: 1+2+4+6+7+10+12+14+16+17+18+22+27+30+32+35+37 = 3+13+19+21+24+26+29+34+39+40+42
21: 1+2+3+4+5+7+8+12+13+17+19+25+26+32+33+34+40 = 10+11+16+22+23+24+30+31+37+38+39
26: 2+3+8+9+10+11+19+20+21+22+23+24+38+39 = 7+17+18+32+33+34+35+36+37
a(43) = 4
18: 1+2+5+6+7+10+12+14+16+17+19+20+29+31+34+36+37 = 8+21+23+25+27+32+38+39+41+42
19: 2+4+5+6+7+8+11+15+17+18+20+23+27+30+32+35+37 = 10+14+22+26+29+34+38+40+41+43
21: 1+2+3+7+13+14+18+19+25+26+32+33+34+41 < 5+11+12+17+23+24+30+31+37+39+40
26: 1+3+4+5+8+9+10+11+12+21+22+23+24+38+39+40 < 7+18+19+20+32+33+34+35+36+37
a(44) = 4
18: 1+2+5+6+7+8+10+11+14+16+17+19+20+25+30+32+35+37+38 = 3+12+21+22+23+26+28+33+39+40+42+44
19: 1+2+3+7+8+12+15+17+18+20+23+28+31+33+36+38+44 = 9+10+14+21+25+27+30+35+39+41+42+43
21: 2+3+4+6+8+9+12+13+14+18+19+21+26+27+33+34+35+42 = 11+17+23+24+25+31+32+38+40+41+44
26: 1+3+4+5+9+10+11+21+22+23+24+25+39+40+41 = 8+18+19+20+33+34+35+36+37+38
a(45) = 4
18: 2+4+5+6+11+13+16+17+18+20+21+26+31+33+36+38+39 = 7+9+14+22+24+27+29+34+40+42+43+45
19: 1+2+4+6+9+12+14+18+19+21+24+29+32+34+37+39+45 = 8+11+16+23+26+28+31+36+40+41+42+44
21: 1+2+3+5+7+8+14+15+16+19+20+27+28+34+35+36+42 = 4+12+13+18+24+25+26+32+33+39+41+45
26: 1+3+4+7+8+9+10+11+12+13+22+23+24+25+26+40+41 = 19+20+21+34+35+36+37+38+39
a(46) = 4
18: 1+2+3+5+6+8+9+14+16+17+19+21+22+26+31+33+36+38+39 = 10+12+23+27+29+34+40+41+42+43+45
19: 2+4+6+7+8+9+12+15+18+20+22+29+32+34+37+39+45 = 3+11+14+17+23+24+26+28+31+36+40+42+44
21: 1+3+7+9+10+11+17+20+21+23+27+28+34+35+36+42 = 6+15+16+25+26+32+33+39+41+45+46
26: 1+2+3+4+5+6+10+11+12+13+14+15+16+23+24+25+26+40+41 = 9+20+21+22+34+35+36+37+38+39
a(47) = 4
18: 2+3+5+7+8+9+13+14+16+18+19+21+22+27+32+34+37+39+40 < 11+23+24+28+30+35+41+42+43+44+46
19: 1+3+6+7+8+9+11+17+19+20+22+30+33+35+38+40+46 < 5+10+13+16+23+25+27+29+32+37+41+43+45
21: 1+2+4+5+9+10+15+16+20+21+23+28+29+35+36+37+43 < 7+14+19+26+27+33+34+40+42+46+47
26: 1+2+3+4+5+6+7+10+11+12+13+14+23+24+25+26+27+41+42 < 9+20+21+22+35+36+37+38+39+40
a(48) = 4
18: 3+5+6+7+8+13+17+19+20+22+23+28+33+35+38+40+41 < 9+11+15+24+26+29+31+36+42+44+45+47
19: 1+4+6+8+11+14+15+18+20+21+23+26+31+34+36+39+41+47 < 3+10+13+17+24+25+28+30+33+38+42+43+44+46
21: 1+2+3+7+8+9+10+15+16+17+21+22+24+29+30+36+37+38+44 = 6+14+20+26+27+28+34+35+41+43+47+48
26: 1+2+3+4+5+6+9+10+11+12+13+14+24+25+26+27+28+42+43 = 8+21+22+23+36+37+38+39+40+41
a(49) = 4
18: 2+3+6+7+8+9+10+15+18+20+21+23+24+29+34+38+40+41+49 < 12+16+25+26+30+32+36+42+43+44+45+47
19: 1+3+5+7+9+10+12+14+16+19+21+22+24+32+35+36+39+41+47 < 11+18+25+27+29+31+34+38+42+44+46+49
21: 1+2+3+4+8+10+11+16+17+18+22+23+25+30+31+36+37+38+44 < 7+14+15+21+28+29+35+41+43+47+48+49
26: 1+2+4+5+6+7+11+12+13+14+15+25+26+27+28+29+42+43 = 10+22+23+24+36+37+38+39+40+41
a(50) = 4
18: 1+2+3+4+6+7+9+10+11+15+16+19+20+21+23+24+34+36+39+41+42+50 = 12+17+25+26+28+30+32+37+43+44+45+46+48
19: 2+3+5+7+8+10+11+17+21+22+24+28+32+35+37+40+42+48 = 4+13+15+19+25+27+31+34+39+43+45+47+50
21: 1+3+4+8+9+11+12+13+17+18+19+22+23+25+30+31+37+38+39+45 = 7+16+21+28+29+35+36+42+44+48+49+50
26: 1+2+4+5+6+7+12+13+14+15+16+25+26+27+28+29+43+44 = 11+22+23+24+37+38+39+40+41+42
a(51) = 4
18: 2+3+4+6+8+10+11+15+17+19+20+21+23+24+30+35+37+40+42+43+50 < 12+13+18+25+26+28+31+33+38+44+46+47+49+51
19: 1+3+4+7+9+11+13+16+18+21+22+24+28+33+36+38+41+43+49 < 6+15+19+25+27+30+32+35+40+45+46+48+50
21: 1+2+4+5+6+9+10+11+12+18+19+22+23+25+31+32+38+39+40+46+51 < 16+17+21+28+29+30+36+37+43+44+45+49+50
26: 1+2+3+5+6+7+8+12+13+14+15+16+17+25+26+27+28+29+30+44+45 < 11+22+23+24+38+39+40+41+42+43+51
a(52) = 4
18: 2+5+7+8+10+11+12+17+19+22+25+26+31+35+37+40+42+43+51 = 3+13+15+20+27+28+29+32+38+44+46+47+49+52
19: 1+2+3+6+8+9+11+12+15+18+20+23+24+26+29+36+38+41+43+49 = 5+14+17+22+27+31+33+35+40+45+46+48+51
21: 1+3+4+5+9+10+12+13+14+20+21+22+24+25+27+32+33+38+39+40+46+52 = 8+18+19+29+30+31+36+37+43+44+45+49+50+51
26: 1+2+3+4+5+6+7+8+13+14+15+16+17+18+19+27+28+29+30+31+44+45 = 12+24+25+26+38+39+40+41+42+43+52
a(53) = 4
18: 2+3+4+7+8+9+10+11+12+17+19+21+23+25+26+31+36+38+41+43+44+52 < 5+13+15+27+29+32+34+39+45+46+47+48+50+53
19: 1+3+4+5+9+11+12+15+18+22+23+24+26+29+34+37+39+42+44+50 = 7+14+17+21+27+28+31+33+36+41+45+47+49+52
21: 1+2+4+5+6+7+10+12+13+14+20+21+24+25+27+32+33+39+40+41+47+53 < 9+18+19+23+29+30+31+37+38+44+46+50+51+52
26: 1+2+3+5+6+7+8+9+13+14+15+16+17+18+19+27+28+29+30+31+45+46 = 12+24+25+26+39+40+41+42+43+44+53
a(54) = 4
18: 2+3+4+6+8+9+11+12+13+18+20+23+25+26+28+29+33+37+39+41+42+43+51 = 5+14+16+21+30+31+32+35+44+45+47+48+49+52+54
19: 1+3+4+5+7+9+10+12+13+16+19+21+24+26+27+29+32+35+38+43+49+54 < 6+15+18+23+30+33+34+37+41+44+46+47+51+53
21: 1+2+4+5+6+10+11+13+14+15+21+22+23+27+28+30+34+40+41+47+52+53 < 9+19+20+26+32+33+38+39+43+45+46+49+50+51
26: 1+2+3+5+6+7+8+9+14+15+16+17+18+19+20+30+31+32+33+44+45+46 < 13+27+28+29+40+41+42+43+52+53+54
a(55) = 4
18: 2+3+6+8+9+11+12+13+18+19+22+24+25+27+28+32+37+39+42+44+45+54 < 4+14+16+20+29+31+33+35+40+46+47+49+50+52+55
19: 1+2+3+4+7+9+10+12+13+16+20+23+25+26+28+31+35+38+40+43+45+52 < 6+15+18+22+30+32+34+37+42+46+48+49+51+54
21: 1+3+4+5+6+10+11+13+14+15+20+21+22+26+27+33+34+40+41+42+49+55 = 9+19+25+31+32+38+39+45+47+48+52+53+54
26: 1+2+4+5+6+7+8+9+14+15+16+17+18+19+29+30+31+32+46+47+48 = 13+26+27+28+40+41+42+43+44+45+55
a(56) = 4
18: 2+3+4+7+9+10+12+13+14+18+20+23+25+26+28+34+39+41+44+46+47+55 < 5+15+16+21+29+30+32+35+37+42+48+50+52+53+56
19: 1+3+4+5+8+10+11+13+14+16+19+21+24+26+27+28+32+37+40+42+45+47+52 < 7+18+23+29+31+34+36+39+44+49+51+54+55+56
21: 1+2+4+5+6+7+11+12+14+15+21+22+23+27+29+35+36+42+43+44+53+54 < 10+19+20+26+32+33+34+40+41+47+48+49+52+56
26: 1+2+3+5+6+7+8+9+10+15+16+17+18+19+20+29+30+31+32+33+34+48+49+56 = 14+27+28+42+43+44+45+46+47+53+54+55
a(57) = 4
18: 2+3+4+7+9+10+12+14+18+19+22+24+27+32+35+36+39+43+45+49+51 < 5+13+16+21+26+28+31+34+38+41+42+48+50+53+56
21: 1+3+4+5+8+10+11+14+16+18+20+21+25+29+31+35+38+40+41+46+51+53+57 < 7+15+19+24+26+30+36+37+39+42+45+47+48+52+55+56
25: 1+2+4+5+6+7+11+12+13+15+18+21+23+24+26+29+32+34+37+41+44+45+48+55 = 10+20+22+31+33+36+40+43+47+51+53+54+56+57
33: 1+2+3+5+6+7+8+9+10+13+15+16+17+19+20+22+26+28+30+31+33+36+42+47+56 = 18+29+32+35+41+44+45+46+49+51+55+57
a(58) = 4
17: 2+3+4+8+9+10+12+13+14+21+22+25+26+27+29+30+37+42+43+45+46+47+56 < 5+15+16+20+31+32+33+35+36+41+48+49+51+52+53+55
20: 1+3+4+5+7+10+11+13+14+16+19+20+24+27+28+30+33+36+40+41+44+47+53 = 8+17+21+25+31+37+38+42+45+48+50+51+56+57
21: 1+2+4+5+6+8+11+12+14+15+17+20+23+25+28+29+31+35+38+41+45+51+55+57 < 10+19+22+27+33+34+37+40+43+47+49+50+53+54+56
26: 1+2+3+5+6+7+8+9+10+15+16+17+18+19+21+22+31+32+33+34+37+48+49+50 < 14+28+29+30+41+44+45+46+47+55+57+58
You might ask why this piece is titled George Hart, when the only man in the photo on the left is John Conway. George Hart is related to this picture in three different ways.
First, this picture is of the math department common room at Princeton University. It was taken during a joint event of the WaM and SWIM programs in June, 2009. It shows the Zometool workshop conducted by George Hart that resulted in the construction of the expanded 120-cell, which appears in the photo's foreground.
The second connection to George Hart is that beautiful shiny object under the lights on the far left. The object is the propello-octahedron sculpture that George Hart created out of 150 CDs. The sculpture has been in the common room for many years, and I have always loved it.
Unfortunately, the sculpture was slowly degrading, even losing some of its parts. I visited Princeton in August 2008 and realized that the sculpture was facing a short life expectancy, so I took the picture of it that is below. I couldn't find any angle to shoot the photo that hid the lost pieces. The sculpture survived until my visit in June 2009, as evidenced by the first picture. But unfortunately it wasn't there any more during my last visit in May 2010.
Oops, I almost forgot. I promised you a third way in which George Hart relates to the first picture. He is the one who took it.
My coauthor Konstantin Knop publishes cute math problems in his blog (in Russian). Recently he posted a coin weighing problem that was given at the 2010 Euler math Olympiad in Russia to eighth graders. The author of the problem is Alexander Shapovalov.
Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin. How would we find at least one genuine coin using two weighings on a balance scale?
It is conceivable that your two weighings may find more than one genuine coin. The more difficult question that Konstantin and his commentators discuss is the maximum number of genuine coins you can guarantee to identify in two weighings. Konstantin and the others propose 14 as the answer, but do not have a proof yet.
I wonder if one of you can find a bigger number than Konstantin or alternatively a proof that indeed 14 is the largest possible.
You might ask, considering the title of this piece, why I think that coins are scary. No, I am not afraid of coins. It scares me that this problem was given to eighth graders in Russia, because I cannot imagine that it would be given to kids that age in the USA.
By the way, ten eighth grade students in Russia solved this problem during the competition.
I recently wrote two pieces about the puzzle relating to sons born on a Tuesday: A Son born on Tuesday and Sons and Tuesdays. I also posted a beautiful essay on the subject by Peter Winkler: Conditional Probability and "He Said, She Said". Here is the problem:
You run into an old friend. He has two children, but you do not know what their gender is. He says, "I have a son born on a Tuesday." What is the probability that his second child is also a son?
A side note. My son Alexey explained to me that I made an English mistake in the problem in those previous posts. It is better to say "born on a Tuesday" than "born on Tuesday." I apologize.
Despite this error, I was gratified to hear from a number of people who told me that I had converted them from their solution to my solution. To ensure that the conversion is substantial, I've created a new version of the puzzle on which my readers can test out their new-found understanding. Here it is:
You run into an old friend. He has two children, but you do not know what their gender is. He says, "I have a son born on a Tuesday." What is the probability that his second child is born on a Wednesday?
I was terribly shy when I was a teenager. I worked on this problem and overcame it. But when I moved to the US my shyness returned in a strange form. I was fine around Russians but shy around Americans. At first I assumed that it was a language problem.
I became friends with a Russian sexologist and psychotherapist. He pointed out that I never initiated a conversation with Americans and so I realized that my shyness had returned. He prescribed an exercise for me: I had to invite a new American guy to lunch once a week.
Why guys? Maybe because he was a sexologist or maybe because my problems with self-esteem were more pronounced when I was around men. In any case, I decided to do the exercise.
To paint the full picture I need to add some relevant details. At that time I was married, although I didn't wear a ring, and wasn't especially interested in other men. The reason I didn't wear a ring was that Joseph, my husband at the time, did not himself want to wear a ring. As I love symmetry in relationships more than I love rings, I didn't wear one either.
The men I was about to invite to lunch were mere acquaintances, because I had not yet made any American friends. So although I didn't intend to hide it, they may not have realized that I was married.
Two things surprised me in this exercise. First, it was very easy. Most people agreed to do lunch with me.
Second, every man I invited mentioned his girlfriend. This was unexpected. From my experience with Russians, I anticipated that every man would hide his involvement with someone else, even with a wife, at least for some time. At the very least, many Russian men would try to flirt.
The Americans were different. Unclear why I had invited them out, they wanted to be upfront with me from the start, just in case I was interested in them. Since that experience, I admire the way that American men come clean.
I never invited any of these guys out twice: I just needed a supply of new men for my exercise in overcoming my shyness. I wonder if they thought I was put off by their confessions. Perhaps my loss of interest in them after the first lunch confirmed their suspicions that I was attracted to them.
The sexologist's exercise was a success. Today I have no trouble inviting someone to lunch.
John Conway has a T-shirt with his theorem on it. I couldn't miss this picture opportunity and persuaded John to pose for pictures with his back to me. Here is the theorem:
If you continue the sides of a triangle beyond every vertex at the distances equaling to the length of the opposite side, the resulting six points lie on a circle, which is called Conway's circle.
Poor John Conway had to stand with his back to me until I figured out the proof of the theorem and realized which point must be the center of Conway's circle.
Heard somewhere:
Teacher: What's bigger: 22/7 or 3.14?
Student: They are equal.
Teacher: Why do you say that?!
Student: They are both equal to π.
For the last three years I've been coming to the Institute for Advanced Study in Princeton every spring for the Women and Mathematics program. Every year I am assigned to an office in the main building: Fuld Hall.
The problem is that there is a different office that I crave. Every year I go and check on it over in Simonyi Hall, where the Mathematics Department is located. This year I took this photo of the empty name-tag, hoping that one day it will say Tanya Khovanova.
Credit cards often keep your mother's maiden name in their database for security purposes. This so called "security" is based on two assumptions:
Were these assumptions true, only your close relatives would know your mother's maiden name. In reality, if your mother was never married, then your last name is the same as your mother's last name. So, crooks who are trying to steal identities can try to use your last name as your mother's presumed maiden name. Very often they will succeed. Besides, many women do not change their last names. If you have a different last name from your mother, but your mother uses her maiden name, then the bank's security question is not very secure at all.
If you want your identity to be secure you might need to invent a maiden name for your mother. Alternatively, perhaps your parents can tell you a family secret that will help you choose a name that is related to you, but not transparent to the public.
My relative Martin took his wife's last name after their marriage. Before his children apply for credits cards and bank accounts, he needs to explain to them that it is better for them to use his maiden name as their mother's maiden name for banking purposes.
I was driving on MassPike when, for no apparent reason, a car driving in the opposite direction started flashing its headlights. I remembered the Russian tradition of informing the oncoming traffic that the police are nearby. So I adjusted my speed and very soon I saw a police car. I got this warm feeling in my heart because I didn't need to panic or check my speedometer. I mentally thanked that anonymous Russian driver and started wondering why the tradition had not been adopted in the USA. Is it because we are so responsible that we want to punish speeders, or do we think that the police are on our side?
The following problem was sent to me by Joel Lewis.
You have 12 mice, one of which eats faster than all the others. You need to find it. You have a supply of standard cupcakes that you value very much and want to minimize how many of them you have to use. The only way you can find the mouse is to give cupcakes to several groups of mice and see which group is the fastest.
We assume that mice chew at a constant speed and all the mice in one group can attack the cake at the same time. I love this puzzle because I love coin problems. Let me restate the puzzle as a coin problem:
You have 12 coins, one of which is fake and weighs less than all the others. You have a balance scale with multiple pans, that is you can weigh several things at once and order them by weight. You do not care about the total number of weighings as in most classical coin puzzles, instead, this time using a pan is expensive and you want to find the fake coin with as few pan-uses as possible.
Spoiler warning: below I will discuss the solution for n mice.
You can, of course, give a cake to every mouse and see which one finishes first. You can save one cake by giving cakes at the same time to all but one of the mice. If everyone finishes simultaneously, the faster mouse is the unfed one.
It wastes cakes to give them to unequally-sized groups of mice. We can do better by copying the classical way to find a fake coin with the minimum number of weighings. That is, for each test, divide the mice into three groups as evenly as possible and give a cake to each of two equally-sized groups. The number of cakes you use is about 2log3n.
I wouldn't have written this essay if that was the solution. Sometimes you can do even better. For example, you can find the faster mouse out of 12 using only 5 cakes.
First, if you give out k cakes in one test, the test tells you which of k+1 groups the mouse is in. In the worst case, the faster mouse will be in the biggest group, so you should minimize the biggest group. Hence, your groups that get cakes should have ⌈n/(k+1)⌉ mice.
A test with one cake gives no information. I argue that giving out more than three cakes doesn't gain anything. Indeed, suppose we use four cakes in a test. That is, we divide the mice into five groups A, B, C, D and E, of which the first four are the same size. We can simulate the test by two tests in each of which we give out two cakes. In the first test we give cakes to A+B and C+D. If one of the groups is faster, say A+B, then in the second test give cakes to A and B; if not, E has the faster mouse. I leave it as an exercise to simulate a test with more than four cakes.
Thus, in an optimal strategy we can use two or three cakes per test. Also, if you give one test with k − 1 cakes and the next one with m − 1 cakes, you can switch them with the same effect. The largest group after either order of tests will have at most ⌈n/km⌉ mice.
I don't need two tests of three cakes each, which would give me a group of size at least ⌈n/16⌉. I can achieve the same result with three tests of two cakes each, with the faster mouse restricted to a group of size at most ⌈n/27⌉.
That means all my tests use two cakes, except I might use three cakes once. It doesn't matter in what order I conduct the tests, so I can wait until the end to use three cakes. I leave it as an exercise to the reader that the only small number of mice for which we would prefer three cakes is four. From this it follows quickly that for numbers of mice between 3 * 3i + 1 and 4 * 3i, the number of cakes is 2i + 1. For numbers between 4 * 3i + 1 and 3i+2 the answer is 2i + 2.
A week ago I chatted with my son Sergei about memorable math problems. He mentioned problem 5 from USAMO 2007. The problem can be reduced to the following:
Prove that (x7 + 1)/(x + 1) is composite for x = 77n, where n is a non-negative integer.
Perhaps Sergei remembered this problem because as far as he knew, he was the only one in that competition to solve it. That made me curious as to how he solved it. His solution is available as solution 2 at the Art of Problem Solving website. His solution seemed mysterious and impossible to invent on the spot. I became even more curious to understand the thought process underlying his solution.
Here is his recollection:
We need to factor x6 − x5 + x4 − x3 + x2 − x + 1. If such factoring existed it would have been known. Therefore, we need to somehow use the fact that x = 77n. What is the simplest way to factor? We should try to represent the polynomial in question as the difference of squares. Luckily, x is an odd power of 7. We can make it a square if we multiply or divide it by 7 or another odd power of 7. So with a supply of squares on one side, we need to find a match for one of them to build the difference.
Let us simplify the problem and see what happens for (y3 + 1)/(y + 1) for y = 33n, when n = 1. In other words we want to represent 703 as a difference of squares. This can be done: 703 = 282 − 92. Now let us see how we can express 282 and 92 through y which in this case is equal to 27. The first term is (y + 1)2, and the second is 3y.
Now let's go back to 7 and x, and check whether (x + 1)6 − (x6 − x5 + x4 − x3 + x2 − x + 1) is 7x. Oops, no. The difference is 7x5 + 14x4 + 21x3 + 14x2 +7x. On the plus side, it is divisible by 7x which we know is a square. The leftover factor is x4 + 2x3 + 3x2 +2x + 1, which is a square of x2 +x + 1.
The problem is solved, but the mystery remains. The problem can't be generalized to numbers other than 3 and 7.
I decided to take a closer look at the Putnam Competition. I analyzed the results of the three top contenders for the best Putnam teams: Harvard, MIT, Princeton. I looked at the annual number of Putnam Fellows from each of these three schools starting from 1994.
| Year | Harvard | MIT | Princeton |
|---|---|---|---|
| 1994 | 2 | 0 | 1 |
| 1995 | 3 | 0 | 0 |
| 1996 | 2 | 0 | 0 |
| 1997 | 4 | 0 | 0 |
| 1998 | 2 | 0 | 1 |
| 1999 | 2 | 1 | 0 |
| 2000 | 2 | 2 | 0 |
| 2001 | 2 | 1 | 0 |
| 2002 | 2 | 2 | 0 |
| 2003 | 1 | 2 | 1 |
| 2004 | 0 | 3 | 2 |
| 2005 | 2 | 3 | 1 |
| 2006 | 1 | 3 | 0 |
| 2007 | 1 | 2 | 1 |
| 2008 | 1 | 3 | 0 | 2009 | 1 | 2 | 0 |
As you may notice MIT couldn't even generate a Putnam Fellow until 2000, but starting from 2003 MIT consistently had more Putnam Fellows than Harvard or Princeton.
Richard Stanley, the coach of the MIT team, kindly sent me the statistics for the most recent competition, held in 2009.
| Category | Overall | MIT |
|---|---|---|
| Number of participants | 4036 | 116 |
| Mean score | 9.5 | 34.7 |
| Median score | 2 | 31 |
| Geometric mean | 0 | 0 |
| Percent of 0 score | 43.7 | 4.3 |
Furthermore, MIT had 40% in the top 5, 33% in the top 15, 32% in the top 25, and 35% in the top 81. For comparison, in the top 81, MIT had 28 winners — more than the next three schools together: Caltech 11, Harvard 9, Princeton 7.
No comment.
OnlineDegree.net selected the 50 Best Blogs for Math Majors, and I am pleased that Tanya Khovanova's Math Blog is number two. Since they did not explain their criteria, I suspected that it might be according to the number of Google hits. To double check, I Googled "math blog" and once again my blog was number two.
This might be the right moment to acknowledge the others involved with my blog. First, Sue Katz, my writing teacher and editor, corrected the English in most of my posts. Now I do not "do" mistakes in English any more, I make them.
My sons, Alexey and Sergei, are a huge support. Sometimes my poor kids have to listen endlessly to my latest idea, until I am ready to write about it. And then they will even read the final piece, and continue to encourage me.
But the most important motivators are you, my readers. Your comments, your personal emails and your feedback keep me writing.
I am usually disappointed with American math text books. I have had an underwhelming experience with them. Often I open a book and in the next 15 minutes, I find a mistake, a typo, a misguided explanation, sloppiness, a misconception or some other annoyance.
I was pleasantly surprised when I opened the book Introduction to Algebra
Look at problem 7.3.1.
Five chickens can lay 10 eggs in 20 days. How long does it take 18 chickens to lay 100 eggs?
There is nothing wrong with this problem. But the book is accompanied by the Introduction to Algebra Solutions Manual
The number of eggs is jointly proportional to the number of chickens and the amount of time. One chicken lays one egg in 10 days. Hence, 18 chickens will lay 100 eggs in 1000/18 days, which is slightly more than 55 and a half days.
What is wrong with this solution? Richard Rusczyk is human after all.
I like this book for its amazing accuracy and clean explanations. There are also a lot of diverse problems in terms of difficulty and ideas. Richard Rusczyk has good taste. Many of the problems are from different competitions and require inventiveness. I like that there are a lot of challenge problems that go beyond the boring parts of algebra. Also, I like that important points of algebra are chosen wisely and are emphasized.
This book might not be for everyone. It doesn't have pretty pictures. It doesn't have color at all. This is not a flaw for a math book. The book concentrates on ideas and problems, not entertainment. So if you're looking for math entertainment, you'll find it on my blog. For solid study, try Richard Rusczyk's books
I love Raymond Smullyan's books
This happened at the Gathering for Gardner 8. We were introduced and then later that day, the conference participants were treated to a dinner event that included a magic show. In one evening I saw more close-up magic tricks than I had in my whole life. This left me lightheaded, doubting physics and my whole scientific outlook on life.
Afterwards, Raymond Smullyan joined me in the elevator. "Do you want to see a magic trick?" he asked. "I bet I can kiss you without touching you." I was caught off guard. At that moment I believed anything was possible. I agreed to the bet.
He asked me to close my eyes, kissed me on the cheek and laughed, "I lost."
As a writer of books on mathematical puzzles I am often faced with delicate issues of phrasing, none more so than when it comes to questions about conditional probability. Consider the classic "X has two children and at least one is a boy. What is the probability that the other is a boy?"
It is reasonable to interpret this puzzle as asking you "What is the probability that X has two boys, given that at least one of the children is a boy" in which case the answer is unambiguously 1/3—given the usual assumptions about no twins and equal gender frequency.
This puzzle confounds people *legitimately*, however, because most of the ways in which you are likely to find out that X has at least one boy contain an implicit bias which changes the answer. For example, if you happen to meet one of X's children and it's a boy, the answer changes to 1/2.
Suppose the puzzle is phrased this way: X says "I have two children and at least one is a boy." What is the probability that the other is a boy?
Put this way, the puzzle is highly ambiguous. Computer scientists, cryptologists and others who must deal carefully with message-passing know that what counts is not what a person says (even if she is known never to lie) but *under what circumstances would she have said it.*
Here, there is no context and thus no way to know what prompted X to make this statement. Could he instead have said "At least one is a girl"? Could he have said "Both are boys"? Could he have said nothing? If you, the one faced with solving the puzzle, are desperate to disambiguate it, you'd probably have to assume that what really happened was: X (for some reason unconnected with X's identity) was asked whether it was the case that he had at least one son, and, after being warned—by a judge?—that he had to give a yes-or-no answer, said "yes." An unlikely scenario, to say the least, but necessary if you want to claim that the solution to the puzzle is 1/3.
Consider the puzzle presented (according to Alex Bellos) by Gary Foshee at the recent 9th Gathering for Gardner:
I have two children. One is a boy born on a Tuesday. What is the probability I have two boys?
If the puzzle was indeed put exactly this way, and your life depended on defending any particular answer, God help you. You cannot answer without knowing, for example, what the speaker would have said if he had one boy and one girl, and the boy was born on Wednesday. Or if he had two boys, one born on Tuesday and one on Wednesday. Or two girls, both born on Tuesday. Et cetera.
Now, there is nothing mathematically wrong (given the usual assumptions, including X being random) about saying that "The probability that X has two sons, given that at least one of X's two children is a boy born on Tuesday, is 13/27." But if that is to be turned into an unambiguous puzzle attached to a presumed situation, some serious hypothesizing is necessary. For instance: you get on the phone and start calling random people. Each is asked if he or she has two children. If so, is it the case that at least one is a boy born on a Tuesday? And if the answer is again yes, are the children both boys? Theoretically, of the times you reach the third question, the fraction of pollees who say "yes" should tend to 13/27.
Kind of takes the fun out of the puzzle, though, doesn't it? Kudos to Gary for stirring up controversy with a quickie.
I recently discussed the following problem:
You run into an old friend. He has two children, but you do not know their genders. He says, "I have a son born on Tuesday." What is the probability that his second child is also a son?
I had heard this problem at the Gathering for Gardner 9 in a private conversation. My adversary had been convinced that the answer to the problem is 13/27. I came back to Boston from the gathering and wrote my aforementioned essay in which I disagreed with his conclusion.
I will tell you my little secret: when I started writing I substituted Wednesday for Tuesday. Then I checked my sons' birthdays and they were born on Saturday and Tuesday. So I changed my essay back to Tuesday.
After I published it people sent me several links to other articles discussing the same problem, such as those of Keith Devlin and Alex Bellos, both of whom think the answer is 13/27. So I invented a fictional opponent — Jack, and here is my imaginary conversation with him.
Jack: The probability that a father with two sons has a son born on Tuesday is 13/49. The probability that a father with a son and a daughter has a son born on Tuesday is 1/7. A dad with a son and a daughter is encountered twice as often as a dad with just two sons. Hence, we compare 13/49 with 14/49, and the probability of the father having a second son is 13/27.
Me: What if the problem is about Wednesday?
Jack: It doesn't matter. The particular day in question was random. The answer should be the same: 13/27.
Me: Suppose the father says, "I have a son born on *day." He mumbles the day, so you do not hear it exactly.
Jack: Well, as the answer is the same for any day, it shouldn't matter. The probability that his second child will also be a son is still 13/27.
Me: Suppose he says, "I have a son born …". So he might have continued and mentioned the day, he might not have. What is the probability?
Jack: We already decided that it doesn't depend on the day, so it shouldn't matter. The probability is still 13/27.
Me: Suppose he says, "I have a son and I do not remember when he was born." Isn't that the same as just saying, "I have a son." And by your arguments the probability that his second child is also a son is 13/27.
Jack: Hmm.
Me: Do you remember your calculation? If we denote the number of days in a week as d, then the probability of him having a second son is (2d−1)/(4d−1). My point is that this probability depends on the number of days of the week. So, if tomorrow we change a week length to another number his probability of having a son changes. Right?
At this point my imaginary conversation stops and I do not know whether I have convinced Jack or not.
Now let me give you another probability problem, where the answer is 13/27:
You pick a random father of two children and ask him, "Yes or no, do you have a son born on Tuesday?" Let's make a leap and assume that all fathers know the day of the births of their children and that they answer truthfully. If the answer is yes, what is the probability of the father having two sons?
Jack's argument works perfectly in this case.
My homework for the readers is: Explain the difference between these two problems. Why is the second problem well-defined, while the first one is not?
On March 5, 2010 I visited Princeton and had dinner with John Conway at Tiger Noodles. He gave me the second Doomsday lesson right there on a napkin. I described the first Doomsday lesson earlier, in which John taught me to calculate the days of the week for 2009. Now was the time to expand that lesson to any year.
As you can see on the photo of the napkin, John uses his fingers to make calculations. The thumb represents the DoomsDay Difference, the number of days your birthday is ahead of DoomsDay for a given year. To calculate this number you have to go back to my previous post.
The index finger represents the century adjustment. For example, the Doomsday for the year 1900 is Wednesday. Conway remembers Wednesday as We-are-in-this-day. He invented his algorithm in the twentieth century, not to mention that most people who use his algorithm were born in that century. Conway remembers the Doomsday for the year 2000 as Twosday.
The next three fingers help you to calculate the adjustment for a particular year. Every non-leap year has 52 weeks and one day. So the Doomsday moves one day of the week forward in one year. A leap year has one extra day, so the Doomsday moves forward two days. Thus, every four years the Doomsday moves five days forward, and, consequently, every twelve years it moves forward to the next day of the week. This fact helps us to simplify our year adjustment by replacing every dozen of years with one day in the week.
The middle finger counts the number of dozens in the last two digits of your year. It is important to use "dozen" instead of "12" as later we will sum up all the numerals, and the word "dozen" will remind us that we do not need to include it in the sum.
The ring finger represents the remainder of the last two digits of the year modulo 12, and the pinkie finger represents the number of leap years in that remainder.
John made two sample calculations on the napkin. The first one was for his own birthday — December 26, 1937. John was born exactly on Doomsday. I suspect that that is the real reason he called his algorithm the Doomsday Algorithm. The century adjustment is Wednesday. There are 3 dozens in 37, with the remainder 1 and 0 leap years in the remainder. When we add four more days to Wednesday, we get Sunday. So John Conway was born on Sunday.
The second napkin example was the day we had dinner: March 5, 2010. March 5 is 5 days ahead of the Doomsday. The century adjustment is Twosday, plus 0 dozens, 10 years in the remainder and 2 leap years in the remainder. 5 + 0 + 10 + 2 equals 3 modulo 7. Hence, we add three days to Tuesday, demonstrating that we dined out together on Friday. But then, we already knew that.
Do you know that some Russian letters are shaped exactly as some letters in the English alphabet? The shapes are the same, but the sounds of the letters are not. My Russian last name can be completely spelled using English letters: XOBAHOBA.
The adequate translation of my last name into English is Hovanova. You might ask where the first "K" came from. For many years French was considered the language of diplomacy and the USSR used French as an official language for traveling documents.
But "H" in French is silent and "Hovanova" would have been pronounced as "Ovanova." To prevent that, Russians used "kh" for the "h" sound.
Now to my first name. I was born Tatyana, for which Tanya is a nickname. Back in Russia, Tanya is used for children and students and Tatyana for adults and teachers. As I was a student throughout my 30 years of life in Russia, I was always Tanya. When I moved to the US, I decided to keep using Tanya, which I much preferred to Tatyana.
A psychiatrist might think that I wanted to be a student forever or refused to grow up. Or I could be accused of being lazy, as Tanya is shorter. In reality, I was just trying to be considerate. Tanya is easier to write and to spell for Americans. Anyway, I already had enough problems spelling out my last name in this country.
Now that more information is getting translated from Russian into English, I keep stumbling on references to me as to Hovanova or Tatyana. For example, the IMO official website used Russian sources to come up with the names of the Russian participants. They then translated the names directly into English, instead of going through French. As a result, on their website I am Tatyana Hovanova. This is not unique to me: many Russian names on the IMO website differ from those peoples' passport names.
By the way, if you Google my last name you will encounter other Khovanovas. Khovanova is not a particularly unusual name. Only one of the Khovanovas that came up in my search results is a close relative. Elizabeth Khovanova is my father's second wife and a dear friend. She is also an accomplished geneticist.
Khovanova is used only for females in Russia. The male equivalent is Khovanov. Surely you have heard of my half-brother Mikhail Khovanov and his homologies.
I gave you the Wise Men Without Hats puzzle in one of my previous posts:
A sultan decides to check how wise his two wise men are. The sultan chooses a cell on a chessboard and shows it to the first wise man. In addition, each cell on the chessboard either contains a pebble or is empty. The first wise man has to decide whether to remove one pebble or to add one pebble to an empty cell. Next, the second wise man must look at the board and guess which cell was chosen by the sultan. The two wise men are permitted to agree on their strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?
My readers solved it. The solution is the following. Let us assign a number between 0 and 63 to every cell of the board. The second wise man takes numbers corresponding to cells with pebbles, converts them to binary and XORs the result. The answer is the cell number that he is seeking. The first wise man can always add or remove a pebble to make the XORing operation of the remaining pebbles produce any given number from 0 to 63.
This solution only works for boards that have a power of two as the number of cells.
Let's look at the solution more closely. Let us create a graph corresponding to this problem. The vertices of the graph will correspond to the positions of pebbles. That means vertices are in one-to-one correspondence with the subsets of the set of 64 elements. Let us connect two vertices if we can get from one position to another by removing or adding a pebble. That means vertices are connected if two corresponding sets differ by exactly one element. We can see that the resulting graph is regular and each vertex is connected to exactly 64 other vertices.
Let us assign one out of 64 colors to each cell of the chessboard. The second wise man can guess the cell by looking at the chessboard. From this we can conclude that there is a bijection from the vertices of the graph to chessboard cells. In other words, we can color the graph in 64 colors. The existence of the strategy for wise men means that we can color the graph in such a way that each vertex is connected to the vertices of all colors.
As each vertex in our graph has exactly 64 neighbors, the graph has the following property: It can be colored in 64 colors in such a way that every vertex is connected to exactly one vertex of every color.
As soon as I realized that there is such a graph-theoretical object, I started to run around MIT asking everyone if such objects were studied or have a name.
It appears that indeed such an object has a name. A graph that can be colored into k colors in such a way that every vertex has exactly one neighbor of every color is called a rainbow graph.
Andrew Woldar discusses properties of such graphs in his paper. In particular, rainbow graphs are matching graphs. Indeed, every vertex is connected to exactly one vertex of the same color. Hence there is a natural pairing on vertices. From here, we can conclude that the smallest size of a rainbow graph is 2k.
Several MIT students liked the wise men problem and the associated graph object so much that they decided to study them. Hwanchul Yoo, SuHo Oh, and Taedong Yun enumerated all rainbow graphs of size 2k. The number of non-isomorphic rainbow graphs of size 2k equals mitthe number of switching classes of graphs with k vertices. The corresponding sequence A002854 starts as: 1, 1, 2, 3, 7, 16, 54. The paper is soon to appear. It is titled "Rainbow Graphs and Switching Classes."
Just received from Victor Gutenmacher:
Fibonacci salad: For today's salad, mix yesterday's leftover salad with that of the day before.
New additions to my trick problems collection:
* * *
It takes 12 minutes to saw a log into 3 parts. How much time will it take to saw it into 4 parts?
* * *
The Davidsons have five sons. Each son has one sister. How many children are there in the family?
* * *
A caterpillar wants to see the world and decides to climb a 12-meter pole. It starts every morning and climbs 4 meters in half a day. Then it falls asleep for the second half of the day during which it slips 3 meters down. How much time will it take the caterpillar to reach the top?
First Name: David
Last Name: (hidden for privacy protection)
Year of Birth: (hidden for privacy protection)
email: buchanan1985@gmail.com
I remember a math problem from my childhood: divide an L-shaped triomino into four congruent parts. The answer is in the picture on the left. Such division is quite appropriately called a reptile (repetitive tiling). Solomon Golomb invented the name many years ago. He wasn't aware that his definition would end up creating Googling problems, for when you search for such a mathematical object you will stumble upon a lot of amphibians.
Similarly, you can divide the same shape into 9 congruent pieces (see the figure on the left).
Suppose you want to divide a shape into pieces that are similar, but not necessarily of the same size. Such tiling is called an irreptile (irregular reptile).
At the Gathering for Gardner 9 I listened to Carolyn Yackel's talk about the L-reptiles and L-irreptiles. One of the ways to create an irreptile is to start with a reptile, then to make a sub-tiling of one of the existing tiles. This procedure can be repeated many times.
Carolyn brought a ceramic table to the Gathering for Gardner. This table is made of two L-shapes. Both shapes are irreptiles, created by this procedure. In one part of the table she started with a 9-reptile, and in the other with a 4-reptile. She sent me this picture of her table to use in this essay.
After her talk I started wondering how many tiles can an L-irreptile be comprised of. We start with one piece: the L-shape itself. If we divide a tile into four smaller tiles we add three more pieces. If we divide it into nine tiles we add eight more pieces. We can mix sub-dividing into four and nine tiles. The total number of tiles that an L-shape can be comprised of by this procedure is all the numbers you can get from 1 by adding three or eight. The sequence is 1, 4, 7, 9, 10, 12, 13, 15, 16, 17 and so on. Starting from 15 we get all the consecutive numbers.
The numbers that are not represented in the above sequence are 2, 3, 5, 6, 8, 11 and 14. Can we divide an L-shape into such numbers of tiles? Benoît Jubin reminded me that there is an L-reptile with six pieces.
Consequently, we can add 5 more pieces to any L-irreptile. Thus, there exists an L-irreptile made out of 11 (1+5+5) and out of 14 (1+8+5) pieces. The numbers that are left are 2, 3, 5 and 8.
While I was discussing L-irreptiles with fans of sequences, David Wilson suggested a conjecture.
David Wilson's conjecture. If there is an L-irreptile, there is a corresponding square-irreptile with similarly-sized pieces.
If this conjecture is true, then we can see that L-irreptiles with 2, 3 or 5 pieces can't exist as corresponding square-irreptiles do not exist.
For example, to prove that 2 or 3 square-irreptiles can't exist, you need to notice that each corner of the square we are trying to tile should belong to a different small tile.
The question of the existence of an 8-irreptile of the L-shape is more interesting and challenging. The square 8-irreptile exists. If you can prove that the L-shape 8-irreptile doesn't exist, then you will automatically prove that the converse to Wilson's conjecture is not true.
Only at MIT. Room 4-231.
Let n coins weighing 1, 2, … n be given. Baron Münchhausen knows which coin weighs how much, but his audience does not. Define a(n) to be the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.In the paper Baron Münchhausen's Sequence, three of us completely described the Baron's sequence. In particular, we proved that a(n) ≤ 2. Here we would like to outline another proof idea, which is interesting in part because it touches the Riemann hypothesis.
We denote the total weight of coins in some set A as |A|.
Lemma. Numbers n that can be represented as Ti + Tj + Tk = 3n, where i ≤ j < k, such that there is a subset A of coins from j + 1 to k such that n = Tj + |A|, can be done in two weighings.
Proof. Suppose Ti + Tj + Tk = 3n and there is a subset A of coins from j + 1 to k such that n = Tj + |A|. We propose the two weighings
[1…j] + A = n
and
[1…i] + B = n + A,
where B is the complement of A in {j + 1, j + 2, … , k}.
If we sum up twice the first weighing with the second weighing we get
3[1…i] + 2[(i + 1)…j] + 2A + B = 3n + A.
In other words, three times the weight of the coins that were on the left side in both weighings, plus twice the weight of the coins that were on the left side in only the first weighing, plus the weight of the coins that were moved from the left cup to the right cup plus the weight of the coins on the left cup in only the second weighing equals three times the weight of the coin on the right cup in both weighings. Hence three times the weight of the coin on the right cup in both weighings can't be less than the weight of the k other coins that participated plus the weight of the j coins that were on the left cup in the first weighing and weren't moved to the right cup, plus the weight of the i coins that were one the left cup in both the first and the second weighing. But because Ti + Tj + Tk = 3n, then 3n is the smallest possible weight of any set of i plus j plus k coins, the coin on the right cup in both weighings has to be the n-coin.
We checked that any number up to 600,000 except 20 can be represented so as to satisfy the Lemma. To show how to solve 20 coins in two weighings is easy, and, as usual, is left as an exercise for the reader. Next, we want to look at the following lemma.
Lemma. Given a set of consecutive numbers {(j + 1), … , k}, if k > 2j + 2, then it is possible to find a subset in the set that sums up to any number in the range from j + 1 to (j + k + 1)(k – j)/2 – j – 1.
We won't prove the lemma, but it means that if k is about twice larger than j, then we have a lot of flexibility for building our set A in the weighing above. For moderately large n (where 600000 >> "moderately large"), it is not hard to prove that this flexibility is sufficient.
Now the question becomes: can we find such a decomposition into triangular numbers? It is enough to find a representation Ti + Tj + Tk = 3n, where Tk is at least 81% of 3n.
We know that decompositions into triangular numbers are associated with decompositions into squares. Namely, if Ti + Tj + Tk = 3n, then (2i + 1)2 + (2j + 1)2 + (2k + 1)2 = 24n + 3. If the largest square is at least 81% of 24n + 3, then the largest triangular number in the decomposition of 3n is at least 81%.
There is a theorem (W. Duke, Hyperbolic distribution problems and half-integral weight Maass forms, in Inventiones Math 92 (1988) p.73-90) that states that in the limit the decompositions of numbers into three squares are equidistributed. That is, if we take some region on the unit sphere x2 + y2 + z2 = 1 (for example, the region |z| > 0.8) and view decompositions of 24n + 3 into squares as points on the sphere x2 + y2 + z2 = 24n + 3, then, as n grows, decompositions whose projections fall into our chosen region are guaranteed to appear.
This theorem is great, because it tells us that for large enough n we will always be able to find a decomposition of 24n + 3 into triangle numbers where one of the triangle numbers will be much bigger than the others, and it will be possible to prove the weight of the n coin in two weighings. Unfortunately, this summary, as stated, does not tell us how large that n needs to be. So we need some exact estimates.
The number of decompositions of m into sums of three squares is about the square root of m. More precisely, it is possible to compute a number N, such that for any number m > N, with at most one exception, the number of decompositions is at least Cm1/2−1/30, where C is a known constant.
The more specific statement of Duke's theorem is that if the number of solutions to the quadratic x2 + y2 + z2 = 24n + 3 is large, for a computable value of "large", then the solutions are equidistributed. More precisely, let us denote 3n by m and fix an area Ω on the unit sphere. Then the number of solutions (x, y, z) such that the unit vector (x, y, z)/|(x, y, z)| belongs to Ω is
1/(4π) Ωh(8m+3) + E(m),
where h(8m+3) is the total number of solutions of x2 + y2 + z2 = 24n + 3, and E(m) is an error term, which starting from some number satisfies the inequality: E(m) ≤ 1000m1/2-1/7.
That's pretty good, because combining these two lets us, at least in principle, actually calculate an N such that for all n > N except maybe one a(n) = 2. After that we hoped to write a program to exhaustively search smaller numbers by computer.
This situation is still somewhat annoying, because that possible exception must then be propagated into the proof, and if we are not careful, possibly into the final theorem. ("No matter how many coins the Baron has, he can prove the weight of one in at most two weighings, except maybe one number of coins, and we don't know which...") This is where the Riemann Hypothesis comes in. If the Riemann Hypothesis is true, then that exception isn't there, and all is sunlight and flowers.
The beauty of the Baron's puzzle is such that we actually do not need the Riemann hypothesis. As we can use unbalanced weighings, it is enough to find a good decomposition for one out of the four numbers 3n, 3n-1, 3n-2, or 3n-3.
Instead of finding all these exact estimates we found a different elementary proof of our theorem. But we are excited that methods that are used in very advanced number theory can be used to solve a simple math problem that can be described to middle school children.
It would be great if someone decided to finish this proof.
I am used to thinking that a "woman in numbers" means a female number theorist. But not anymore. I just discovered drawings by Svetlana Bogatyr. From now on the expression a "woman in numbers" will convey an additional meaning to me.
I am grateful to Svetlana for permitting me to post several of her drawings. The "Mature Woman" is on the left. "Eurydice", "Girl in Scarf" and "Holland Woman " are below.
Enjoy.
I just invented a two-player game. To start, you have an empty n by n board. When it's your turn you must write an integer between 1 and n into an empty cell on the board. Your integer has to differ from the integers that are already present in the same row or column. If you finish filling up the board, you will get a Latin square and the game will be a tie. The person who doesn't have a move loses. What is the best strategy?
Let's see what happens if n is 2. The first player puts any number in one of the four corners of the 2 by 2 board. The second player wins by placing a different number in the opposite corner.
I played this game with my son Sergei Bernstein on a 3 by 3 board. We discovered that the first player can always win. Since this game is so much fun, I'll leave it to the reader to play it and to find the winning strategy for the first player.
Can you analyze bigger boards? Remember that this game has many symmetries. You can permute rows and columns. Also, you can permute numbers.
While we were playing Sergei invented two theorems.
Sergei's theorem 1. If n is odd the first player can guarantee a tie.
Proof. In the first move the first player writes (n+1)/2 in the center cell. If the second player puts number x in any cell the first player puts number n+1−x into the cell that is rotationally symmetric to the second player's cell with respect to the center. With this strategy the first player will always have a legal move.
Sergei's theorem 2. If n is even the second player can guarantee a tie.
Proof. If the first player puts number x in any cell the second player puts number n+1−x into the cell that is vertically symmetric to the first player's cell with respect to the vertical line of symmetry of the board. With this strategy the second player will always have a legal move.
As you play the game, let me know if you develop any theorems of your own.
Suppose you meet a friend who you know for sure has two children, and he says: "I have a son born on Tuesday." What is the probability that the second child of this man is also a son?
People argue about this problem a lot. Although I've discussed similar problems in the past, this particular problem has several interesting twists. See if you can identify them.
First, let us agree on some basic assumptions:
Now let us consider the first scenario. A father of two children is picked at random. He is instructed to choose a child by flipping a coin. Then he has to provide information about the chosen child in the following format: "I have a son/daughter born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun." If his statement is, "I have a son born on Tuesday," what is the probability that the second child is also a son?
The probability that a father of two daughters will make such a statement is zero. The probability that a father of differently-gendered children will produce such a statement is 1/14. Indeed, with a probability of 1/2 the son is chosen over the daughter and with a probability of 1/7 Tuesday is the birthday.
The probability that a father of two sons will make this statement is 1/7. Among the fathers with two children, there are twice as many who have a son and a daughter than fathers who have two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 1/2 for the second child to also be a son.
Now let us consider the second scenario. A father of two children is picked at random. If he has two daughters he is sent home and another one picked at random until a father is found who has at least one son. If he has one son, he is instructed to provide information on his son's day of birth. If he has two sons, he has to choose one at random. His statement will be, "I have a son born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun." If his statement is, "I have a son born on Tuesday," what is the probability that the second child is also a son?
The probability that a father of differently-gendered children will produce such a statement is 1/7. If he has two sons, the probability will likewise be 1/7. Among the fathers with two children, twice as many have a son and a daughter as have two sons. Plugging these numbers into the formula for calculating the conditional probability gives us a probability of 1/3 for the second child to also be a son.
Now let us consider the third scenario. A father of two children is picked at random. If he doesn't have a son who is born on Tuesday, he is sent home and another is picked at random until one who has a son that was born on Tuesday is found. He is instructed to tell you, "I have a son born on Tuesday." What is the probability that the second child is also a son?
The probability that a father of two daughters will have a son born on Tuesday is zero. The probability that a father of differently-gendered children will have a son who is born on Tuesday is 1/7. The probability that a father of two sons will have a son born on Tuesday is 13/49. Among the fathers with two children, twice as many have a son and a daughter than two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 13/27 for the second child to also be a son.
Now let's go back to the original problem. Suppose you meet your friend who you know has two children and he tells you, "I have a son born on Tuesday." What is the probability that the second child is also a son?
What puzzles me is that I've never run into a similar problem about daughters or mothers. I've discussed this math problem about these probabilities with many people many times. But I keep stumbling upon men who passionately defend their wrong solution. When I dig into why their solution is wrong, it appears that they implicitly assume that if a man has a daughter and a son, he won't bother talking about his daughter's birthday at all.
I've seen this so often that I wonder if this is a mathematical mistake or a reflection of their bias.
How to solve the original problem? The problem is under-defined. The solution depends on the reason the father only mentions one child, or the Tuesday.
The funny part of this story is that I, Tanya Khovanova, have two children. And the following statement is true: "I have a son born on Tuesday." What is the probability that my second child is a son?
How many different months' lengths are possible?
For "simplicity" let's stick to the Gregorian calendar.
Lennart Green is an amazing magician who performs card tricks. He is so good that the judges at the competition of the International Federation of Magic Societies didn't believe his tricks. They assumed that he used the help of stooges, and unfairly disqualified him. At the next competition he used a judge to assist him and won first place in the cards category.
I saw his performance twice. Both times he brought a woman to the stage, but each time it was a different woman. It was clear that he talked to each woman before the performance, presumably asking her permission. Furthermore, during his performances, both of the women looked slightly bored, implying that it might be not their first time. My first impression was that the women were a part of the act. I was fooled just as the judges had been fooled.
What can I say? Lennart Green isn't skilled at picking up the right women. Watch his performance at TED, and remember that he proved that the assistants were clueless.
When the Abel Prize was announced in 2001, I got very excited and started wondering who would be the first person to get it. I asked my friends and colleagues who they thought was the greatest mathematician alive. I got the same answer from every person I asked: Alexander Grothendieck. Well, Alexander Grothendieck is not the easiest kind of person to give a prize to, since he rejected the mathematical community and lives in seclusion.
Years later I told this story to my friend Ingrid Daubechies. She pointed out to me that my spontaneous poll was extremely biased. Indeed, I was asking only Russian mathematicians living abroad who belonged to "Gelfand's school." Even so, the unanimity of those responses continues to amaze me.
Now several years have passed and it does not seem that Alexander Grothendieck will be awarded the Prize. Sadly, my advisor Israel Gelfand died without getting the Prize either. I am sure I am biased with respect to Gelfand. He was extremely famous in Soviet Russia, although less well-known outside, which may have affected the decision of the Abel's committee.
I decided to assign some non-subjective numbers to the fame of Gelfand and Grothendieck. On Pi Day, March 14, 2010, I checked the number of Google hits for these two men. All the Google hits in the rest of this essay were obtained on the same day, using only the full names inside quotation marks.
Google hits do not give us a scientific measurement. If the name is very common, the results will be inflated because they will include hits on other people. On the other hand, if a person has different spellings of their name, the results may be diminished. Also, people who worked in countries with a different alphabet are at a big disadvantage. I tried the Google hits for the complete Russian spelling of Gelfand: "Израиль Моисеевич Гельфанд" and got an impressive 137,000.
Now I want to compare these numbers to the Abel Prize winners' hits. Here we have another problem. As soon as a person gets a prize, s/he becomes more famous and the number of hits increases. It would be interesting to collect the hits before the prize winner is announced and then to compare that number to the results after the prize announcement and see how much it increases. For this endeavor, the researcher needs to know who the winner is in advance or to collect the data for all the likely candidates.
John Thompson is way beyond everyone else's range because he shares his name with a famous basketball coach. But my point is that Gelfand and Grothendieck could have been perfect additions to this list.
I have this fun book at home written by Clifford Pickover and titled Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning
The most puzzling thing about this list is that there is no overlap with the Abel Prize winners. Here is the list with the corresponding Google hits.
Since there are other great mathematicians with a lot of hits, I started trying random names. In the list below, I didn't include mathematicians who had someone else appear on the first results page of my search. For example, there exists a film director named Richard Stanley. So here are my relatively "clean" results.
If prizes were awarded by hits, even when the search is polluted by other people with the same name, then the first five to receive them would have been:
If we had included other languages, then Gelfand might have made the top five with his 48,000 English-language hits plus 137,000 Russian hits.
This may not be the most scientific way to select the greatest living mathematician. That's why I'm asking you to tell me, in the comments section, who you would vote for.
I got this problem from my friend, a middle-school math teacher, Tatyana Finkelstein.
We have N coins that look identical, but we know that exactly one of them is fake. The genuine coins all weight the same. The fake coin is either lighter or heavier than a real coin. We also have a balance scale.
Unlike in classical math problems where you need to find the fake coin, in this problem your task is to figure out whether the fake coin is heavier or lighter than a real coin. Your challenge is that you are only permitted to use the scale twice. Find all numbers N for which this can be done.
I would like to add an extra twist to the problem above. It is conceivable that there might be several different strategies for finding the direction in which the weight of the fake coin deviates from the real coins. In this case it is better to choose a strategy that can redeem as many coins as possible — that is, to identify the maximum number of coins as real.
The number of coins you identify as real depends on the outcomes of your weighings. Then what is the precise definition of the best strategy?
Let us call a strategy k-redeem if after the weighings you are guaranteed to demonstrate that k coins are real, but you are not guaranteed to demonstrate that k+1 coins are real. Your task is to analyze two-weighing strategies and choose the most profitable one — the strategy that guarantees to redeem the largest possible number of coins, that is, a k-redeem strategy for the largest k.
Sara was born in Boston on February 29, 2008 at 11:00 am. Her parents were quite upset that their calendar-challenged daughter would only be able to celebrate her birthday once in four years. Luckily, science can help Sara's parents. How? Sara can celebrate her birthday every year at the moment when the Earth passes the same point on its orbit around the Sun as when Sara was born.
Assuming that Sara lives her entire life in Boston and that the daylight savings time is not moved earlier into February, your task is to calculate the schedule of Sara's birthday celebrations for 100 years starting from her birth. To simplify your homework, you can approximate one year as 365 days and 6 hours.
Joseph DeVincentis heard my prayers and created an index for MIT mystery hunt puzzles. He created it not because I requested it, but rather because he was on the writing team this year and they needed it. Anyway, finally there is an index.
I have to warn you, though, that this index was created for people who have already solved the puzzles, so the index contains hints for many of the problems and, on rare occasions, solutions.
Now I will do the math index for this year, and I promise that I will avoid big hints.
One fine day in January 2010, John H. Conway shared with me his recipe for success.
1. Work at several problems at a time. If you only work on one problem and get stuck, you might get depressed. It is nice to have an easier back-up problem. The back-up problem will work as an anti-depressant and will allow you to go back to your difficult problem in a better mood. John told me that for him the best approach is to juggle six problems at a time.
2. Pick your problems with specific goals in mind. The problems you work on shouldn't be picked at random. They should balance each other. Here is the list of projects he suggests you have:
3. Enjoy your life. Important problems should never interfere with having fun. When John Conway referred to having fun, I thought that he was only talking about mathematics. On second thought, I'm not so sure.
* * *
Birthdays are beneficial for your health. A new breakthrough statistical study unequivocally proved that the more birthdays one has the longer one lives.
* * *
We know through Erdös that "a mathematician is a device for turning coffee into theorems". It thus follows by duality that a comathematician is a device for turning cotheorems into ffee.
* * *
- What do you do when you see a beautiful girl?
- I download her.
* * *
Programmers wear red T-shirts to match the color of their eyes.
* * *
We invented the decimal system, because humans have ten fingers on their hands; and 32-bit computers, because humans have 32 teeth in their mouths.
* * *
A general shows off a new tank and boasts:
- You see a tank supplied with the most modern computer technology.
- What is the speed of its computer?
- The same as the speed of the tank, of course.
A sultan decides to check how wise his two wise men are. The sultan chooses a cell on a chessboard and shows it to the first wise man. In addition, each cell on the chessboard either contains a rock or is empty. The first wise man has to decide whether to remove one rock or to add one rock to an empty cell. Next, the second wise man must look at the board and guess which cell was chosen by the sultan. The two wise men are permitted to agree on the strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?
If you are stuck, there are many approaches to try. You can attempt to solve the puzzle for a board of size 1 by 2, or for a board of size 1 by 3. Some might find it easier to solve a version in which you are allowed to have a multiple number of rocks on a cell, and the first wise man is permitted to add a rock to a cell that already contains rocks.
This year I am again on the organizing committee of the Women and Mathematics program at Princeton's Institute for Advanced Study. Our subject is "p-adic Langlands Program." It is a fashionable, advanced and very influential program connecting number theory and representation theory.
We invite undergraduate students, graduate students and post-docs to apply. In 2009-2010 the Institute has been running a special year in Analytic Number Theory. That has brought many number theorists to the institute already, so there will be a lot of people to talk to.
Last year I promised to hold a math party during the program. But I had to cancel it due to a scheduling conflict with George Hart's ZomeTool Workshop. I am planning a party this year. Either way, we'll have fun.
If you want to learn about the Langlands program, to spent time on the beautiful grounds of the Institute, to eat in one of the best cafeterias around, and to make new friends with other women interested in number theory, then please apply. The application deadline is February 20.
Suppose you want to increase your chances of winning the lottery jackpot by pooling money with a group of coworkers. There are several issues you should keep in mind.
When you pool the money and you hit the jackpot, the money has to be split. If you bought 10,000 tickets and the jackpot that you win is $100 million, then each ticket is entitled to a mere $10,000. Your chances of hitting the jackpot in the first place are 1 in 17,500 and you're not going to get rich off what you win.
Perhaps you'd be satisfied with a small profit. However, as I calculated in my previous piece on the subject, even if you include the jackpot in the calculation of the expected return, the Mega Millions game never had, and probably never will have a positive return.
Despite this fact, people continue to pool money in the hopes of winning big. However, there are more problems in doing this than just its non-profitability.
Consider a scenario. Your coworkers collected $1,000 to buy 1,000 lottery tickets. You give the money to Jerry who buys the tickets. Jerry can go to a store and buy 1,005 tickets. After the lottery he checks the tickets, takes the best five for himself and comes back to work with 1,000 disappointing tickets.
It is more likely that Jerry is cheating or that he will lose the tickets than it is that your group will win the jackpot. But there is a probabilistic way to check Jerry's integrity. According to the odds, every 40th ticket in Mega Millions wins something. Out of 1,000 tickets that Jerry bought, you should have about 25 that win something. If Jerry systematically brings back tickets that win less often than expected, you should replace Jerry with someone else.
There are methods to protect your group against cheating. For example, you can ask another person to join Jerry in purchasing the tickets, which they then seal in an envelope that they both sign.
Alternatively, you yourself could be the person responsible for buying 1,000 tickets. How would you protect yourself from suspicion of cheating? The same way as I mentioned above: bring along some witnesses and have everyone sign the sealed envelope.
The most reliable way to prevent Jerry from cheating is to have him write down all the ticket numbers and send this information to everyone before the drawing. This way he can't replace one ticket with another. But this is a lot of work for tickets that are usually worth less than the money you collected to buy them.
But there are other kinds of dangers if you use this supposedly reliable method. If you bought a lot of tickets the probability of winning a big payoff increases. Suppose Jerry publicly locks the envelope in a desk drawer in his office. If one ticket wins $10,000, and everyone knows all the ticket combinations, suddenly Jerry's desk drawer becomes a very unsafe place to keep the tickets.
Scams are not your only worry. You shouldn't buy the same combination twice — whether picking randomly or not. You really do not want to waste a ticket and end up sharing the jackpot with yourself.
You cannot change the odds of hitting the jackpot, but you can change the odds of sharing it with others. Indeed, there are people who do not buy random combinations, but rather pick their favorite numbers, like birthdays. You can reduce the probability of sharing the jackpot if you choose the combinations for your tickets wisely, by picking numbers that other people are unlikely to pick.
Still want to try the lottery? If you feel a need to throw your money away, instead of buying lottery tickets, feel free to donate to this blog.
In one of my previous pieces, I discussed returns on the Mega Millions lottery game, assuming that you buy a small number of tickets. In such a case winning the jackpot has zero probability. So I argued that if you want to estimate the profitability of the lottery as an investment, you have to remove the jackpot money from the calculation.
Today I will discuss what the formal expected return is. That is, I will include the jackpot money in the calculation. Since I argued against including the jackpot in my last article, you might wonder why I've then turned around to look into this.
I think this mathematical exercise will be fun. Besides, on a practical note, it is useful to know when the formal expected return is more than 100%, because then it might make sense to pool money with other people. Keep in mind though that if you want a chance to hit the jackpot, the total number of tickets you buy must be really big. For example, even if you manage to pool $10,000 for tickets, your probability of winning the jackpot in Mega Millions is only one in 17,500 — still minuscule.
If you buy only one ticket, you'll lose. If you manage to pool a lot of money and the probability of the jackpot becomes noticeable, that is, non-zero, could the jackpot be large enough that the lottery becomes a good investment?
For this calculation, I'm still assuming that you buy a relatively small number of tickets. If you buy millions of tickets the calculation is slightly different, and I will write about that later.
You might think that when the jackpot is bigger than the odds, it makes sense to play. I am discussing the Mega Millions game, where the odds of winning the jackpot are one in 175 million. So if the jackpot is more than $175 million, then it is profitable to play. Right?
Wrong. As I mentioned in my previous piece, after reducing for taxes, you get about 16% of your money back through smaller payouts. Hence, you need to recover the other 84% through the jackpot. So the jackpot should be more than 175*.84 = 147 million dollars. This sounds even better. Right?
Wrong. No one receives the jackpot. Winners can chose to immediately receive the lump sum, which equals the money lottery organizers have actually set aside for it. Alternatively, the lottery organizers can invest the lump sum and give winners a yearly distribution over many years, the total of which will equal the jackpot.
Suppose for simplicity the lump sum is half of the jackpot. That means we need the jackpot to be $294 million ($147 x 2). Right?
Oops. As usual, we forgot about taxes. To exacerbate your pain, I have to add that the winnings are taxable. Suppose you have to pay 30% from the jackpot. That means the jackpot needs to be $424 ($294/0.7) million in order to justify pooling money. OK?
We haven't seen jackpots that big yet. But neither have we finished the calculation. There is a probability that you might have to share the jackpot with other winners. To calculate this probability, we need to calculate the number of tickets sold. That means, your expected return depends not only on the size of the jackpot, but also on the number of these tickets.
But even if you know the number of tickets sold, we cannot calculate the expected returns precisely because people don't always buy tickets with random combinations, but often pick their own numbers.
When the jackpot is large people start buying tons of tickets, so we can expect that many of them buy quick-picks. Let us assume for now that the vast majority of people do not choose their own numbers, but buy tickets at random. Suppose 200 million tickets were sold. That is a very big number. Last time that many tickets were sold was when the jackpot was $390 million in March 2007. By the way, that was the largest jackpot ever.
In order to finish the calculation, we need to establish the probability of several winners, given that 200 million random tickets were sold:
| Number of winners | Probability |
|---|---|
| No winner | 0.3204 |
| One winner | 0.3647 |
| Two winners | 0.2075 |
| Three winners | 0.0787 |
| Four winners | 0.0224 |
| Five winners | 0.0051 |
| Six winners | 0.0010 |
From here we can calculate the adjustment coefficient, that is, the proportion of money you are expected to get from the jackpot given that there are 200 million players in the game. The coefficient is calculated from the table above as (0.3647 + 1/2*0.2075 + 1/3*0.0787 +1/4*0.0224 + 1/5*0.0051 + 1/6*0.0010)/(1 - 0.3204), and is equal to 0.7379. We need to divide our previous figure of $424 million by the adjustment coefficient. The result is $575 million.
Given that a $390 million jackpot attracted more than $200 million in tickets, we can expect that the $575 million jackpot will make people completely crazy and attract even more money. So I do not anticipate that the Mega Millions game will ever have a positive formal expected gain. My conclusion is that not only is there no financial sense in buying a single lottery ticket, but also none in pooling money.
Of course, you can buy tickets for non-financial reasons, like pumping up your adrenaline. In any case, I showed you the method to calculate your expected return, or, more appropriately, your expected loss.
Here is a fun math activity I use with my students, after I teach them to play the game of set. To other teachers — feel free to clone this idea.
First, I ask the students if they know what a magic square is. They usually do know that a magic square is a three-by-three square of distinct digits, so that every row, column and diagonal has the same sum. Then I ask them what a magic set square might be. Often they guess correctly that it is a three-by-three square made of set cards, so that every row, column and diagonal form a set. Once that's established, I have them build magic set squares.
While they're building them, I ask a lot of questions, from how many cards there should be in the deck to how many different sets there are.
Once the squares are built, I ask them what a magic set cube might be. Their next task is to use their magic set squares as the bottom layer in building magic set cubes. In order to see all the cards in the cube, I instruct them to arrange the layers (bottom, middle and top) side-by-side.
As they're working on their cubes, I continue quizzing them. How many main diagonals does a cube have? Once they confirm that the answer is four, I ask them to show me those diagonals in their magic set cubes and check that they are sets. I might also ask them how many different magic set squares should be inside a magic cube. This is a theoretical math question they need to answer before finding them in their own model. Next they need to identify the different sets that form lines inside their cubes.
At this point, some students guess my next request: to construct a magic set hypercube.
After students build their hypercubes, they never want to destroy them. They like comparing the different hypercubes and often take photos of them. If there's still time left, I can continue in several directions. For example, they can count the main diagonals of the hypercube and find them in their models. Alternatively, they can find a "no set" — the largest possible set of cards inside a magic set hypercube that doesn't contain a set.
Math is usually about thinking, but this is one activity the students can do with their hands. And that adds another layer of magic.
I promised to discuss how to improve the accuracy of your guessing at AMC 10/12, or other tests for that matter. There are two types of guessing. First, meta-guessing is when you do not look at the problem, but rather guess from just looking at the choices. Second, in the one I refer to as an educated-guess you do look at the problem. Instead of completely solving it, you try to deduce some information from the problem that will help you eliminate some of the choices. In this essay, I discuss both methods.
But first let me emphasize that solving problems is a more important skill than meta-guessing from a list of choices. Solving problems not only teaches you to think mathematically, but also increases your brain power. Spending time improving your meta-guessing skills can help you at multiple-choice tests and may give you insight into how test designers think, but this will not increase your math knowledge in the long run.
On the other hand, educated-guessing is a very useful skill to obtain. Not only can it improve your score during a test, the same methods can be applied to speed up the process of re-checking your answers before handing in the test. This skill will also come in handy when you start your research. Some problems in research are so difficult that even minor progress in estimating or describing your answer is beneficial.
Before discussing particular methods, let me remind you that AMC 10/12 is a multiple-choice competition with five choices for each question. The correct answer brings you 6 points. A wrong answer brings you 0 points, and not answering brings you 1.5 points. So if you randomly guess one of the five choices, your expected average score is 1.2 points, which is 0.3 less than your score for an unanswered question. Thus guessing is unprofitable on average.
However, if you can eliminate one choice, your expected average score becomes 1.5 points. In this case guessing doesn't bring you points on average, but it does create some randomness in your results. For strategic reasons, you might prefer guessing, as I discussed in my earlier piece.
If you can eliminate two wrong choices, then guessing becomes profitable. A random guess out of three possibilities brings you 2 points, a better result than 1.5 points for an unanswered question. Even more, if you can eliminate three choices, then guessing will increase your score by 3 points on average.
Now that we've covered the benefits of excluding choices before guessing, I would like to discuss how to exclude choices by just looking at them. Let us take one of the problems from the 2002 AMC10B. Here are the choices: (-2,1), (-1,2), (1,-2), (2,-1), (4,4). The pair (4,4) is a clear outlier. I suggest that an outlier can't be a correct choice. If (4,4) were the correct answer, then it would have been enough, instead of solving the problem, to use some intermediate arguments to choose it. For example, if you can argue that both numbers in the answer must be at least 2, or must be positive or be even, then you can get the correct answer without solving the problem. Any problem for which you can easily pick the correct answer without solving it is an unacceptably poor problem design. Thus, (4,4) can't be the correct answer, and should be eliminated during guessing.
Let us look at a 2002 AMC10A problem with the following choices: 4/9, 2/3, 5/6, 3/2, 9/4. Test designers want to create choices that are plausible. They try to anticipate possible mistakes. In this set of choices, we can deduce that one of the mistakes that they anticipate is that students will confuse a number with its inverse. In this case 5/6 can't be the correct answer. Otherwise, 6/5 would have been included as a choice. In another similar example from the 2000 AMC10 with choices -2, -1/2, 1/3, 1/2, 2, the designers probably hope that students will confuse numbers with their inverses and negations. Hence, we can exclude 1/3.
Sometimes the outlier might hint at the correct answer. Suppose you have the following list of choices: 2, 1/2π, π, 2π, 4π. The number 2 is an outlier here. Probably, the problem designers were contemplating that students might forget to multiply by π. In this case the likely correct answer would be 2π, because only from this answer can you get 2 by forgetting to multiply by π.
As an exercise, try to eliminate the wrong choices from the following set from a problem given at 2000 AMC10: 1/(2m+1), m, 1-m, 1/4m, 1/8m2.
AMC designers know all of these guessing tricks, so they attempt to confuse the competitors from time to time by going against common sense. For example, in a 2002 AMC10A problem the choices were: -5, -10/3, -7/3, 5/3, 5. I would argue that -7/3 is a clear outlier because all the others are divisible by 5. Furthermore, there is no point in including so many answers with 3 in the denominator unless there is a 3 in the denominator of the correct answer. So I would suggest that one of -10/3 and 5/3 must be the answer. My choice would be 5/3, as there is a choice of 5 which I would assume is there for students who forgot to divide by 3. As I said the designers are smart and the actual answer is -10/3. They would have tricked me on this problem.
One of the best ways to design a multiple choice question is to have an arithmetic progression as a list of choices. There is no good way to eliminate some choices from 112, 113, 114, 115, 116. Unfortunately for people who want to get an advantage by guessing, many of the problems at AMC have an arithmetic progression as their choices.
Now that we've seen the methods of meta-guessing, let's look at how to make an educated guess. Let us look at problem 1 in 2003 AMC10A.
What is the difference between the sum of the first 2003 even counting numbers and the sum of the first 2003 odd counting numbers?
Without calculations we know that the answer must be odd. Thus, we can immediately exclude three out of five choices from the given choices of 0, 1, 2, 2003, 4006. Parity consideration is a powerful tool in eliminating wrong answers. Almost always you can decide the parity of the answer much faster than you can calculate the answer. Similar to using parity, you can use divisibility by other numbers to have a fast elimination. Here is a problem from 2000 AMC10:
Mrs. Walter gave an exam in a mathematics class of five students. She entered the scores in random order into a spreadsheet, which recalculated the class average after each score was entered. Mrs. Walter noticed that after each score was entered, the average was always an integer. The scores (listed in ascending order) were 71, 76, 80, 82, and 91. What was the last score Mrs. Walter entered?
The first four numbers entered must be divisible by 4. The total of the given numbers is divisible by 4. Hence, the last number must also be divisible by 4. This reasoning eliminates three out of five choices.
Another powerful method is a rough estimate. Let us look at the next problem in 2003 AMC10A.
Members of the Rockham Soccer League buy socks and T-shirts. Socks cost $4 per pair and each T-shirt costs $5 more than a pair of socks. Each member needs one pair of socks and a shirt for home games and another pair of socks and a shirt for away games. If the total cost is $2366, how many members are in the League?
If we notice that the cost per person is more than $25, we can conclude that there are less than a hundred members in the League. Given the choices of 77, 91, 143, 182, and 286, we immediately can eliminate three of them.
Another method is to use any partial knowledge that you may have. Consider this problem from 2003 AMC10A:
Pat is to select six cookies from a tray containing only chocolate chip, oatmeal, and peanut butter cookies. There are at least six of each of these three kinds of cookies on the tray. How many different assortments of six cookies can be selected?
You might remember that there is a formula for this. Even if you do not remember the exact formula, you might still have a vague memory that the answer must be a binomial coefficient that somehow uses the number of cookies and the number of flavors. Looking at the choices — 22, 25, 27, 28, 29 — you can see that the only choice that appears in the first 10 rows of the Pascal's triangle is 28. So you should go with 28.
It is easy to talk about easy problems; let us see what we can do about difficult ones. Consider the last problem on 2003 AMC10A:
Let n be a 5-digit number, and let q and r be the quotient and the remainder, respectively, when n is divided by 100. For how many values of n is q+r divisible by 11?
The choices are 8180, 8181, 8182, 9000, 9090. They can be naturally split into two groups: three choices below 9000 and the rest. By my rules of removing outliers the group of numbers below 9000 seems the more promising group. But I would like to discuss how to approximate the answer. There is no reason to believe that there is much correlation between remainders by 100 and divisibility by 11. There is a total of 90,000 5-digit numbers; among those numbers, approximately 90,000/11 = 8182 is divisible by 11, so we should go with the group of answers close to 8182.
Another way of thinking about this problem is the following. There are 900 different quotients by 100 to which we add numbers between 0 and 99. Thus for every quotient our sums are a set of 100 consecutive numbers. Out of 100 consecutive numbers usually 9, and rarely 10, are divisible by 11. Hence, the answer has to be less than 9000.
Sometimes methods you use for guessing can bring you the answer. Here is a problem from 2001 AMC12:
What is the product of all odd positive integers less than 10000? (A) 10000!/5000!2, (B) 10000!/25000, (C) 9999!/25000, (D) 10000!/(250005000!), (E) 5000!/25000.
For a rough estimate, I would take a prime number and see in what power it belongs to the answer. It's simplest to consider a prime number p that is slightly below 5000. Then p should appear as a factor in the product of all odd positive integers below 10000 exactly once. Now let us look at the choices. Number p appears in 5000! once and in 10000! twice (as p and 2p). Hence, it appears in (A) zero times, and twice each in (B) and (C). We also can rule out (E) as the product of odd numbers below 10000 must be divisible by primes between 5000 and 10000, but 5000! doesn't contain such primes. Thus the answer must be (D).
The method I just described won't produce the formula. But the ideas in this method allow you to eliminate all the choices except the right one. Moreover, this method provides you with a sanity check after you derive the formula. It also helps to build your mathematical intuition.
I hope that you will find my essays about AMC useful. And good luck on February 9!
I teach students to solve math problems by appreciating the big picture, or by noticing the problem's inner symmetries, or through a deep understanding of the problem. In the long run, one thing leads to another: such training structures their minds so that they are better at understanding mathematics and, as a consequence, they perform well at math competitions.
That is why, when AMC is still far away, I do not give my students a lot of AMC problems; rather, I pick problems that contain useful ideas. When I do give AMC problems, I remove the multiple choices, so they understand the problems completely, instead of looking for shortcuts. For example, this problem from AHSME 1999 is a useful problem with or without choices.
What is the largest number of acute angles that a hexagon can have?
As AMC approaches, we start discussing how to solve problems given multiple choices. Training students for AMC is noticeably different from teaching mathematics. For example, some problems are very specific to AMC. They might not even exist without choices. Consider this problem from the 2001 AMC12:
A polynomial of degree four with leading coefficient 1 and integer coefficients has two zeros, both of which are integers. Which of the following can also be a zero of the polynomial?
Here we really need the choices in order to pick one complex number, such that its real part is an integer or a half integer and, in addition, the product of the number with its conjugate produces an integer.
Sometimes the choices distract from solving the problem. For example, in the following problem from the 2005 AMC12, having choices might tempt students to try to eliminate them one by one:
The sum of four two-digit numbers is 221. None of the eight digits is 0 and no two of them are same. Which of the following is not included among the eight digits?
Without the choices, students might start considering divisibility by 9 right away.
On some occasions, the choices given for the problems at AMC make the problem more interesting. Here is an example from the 200o AMC10:
Two different prime numbers between 4 and 18 are chosen. When their sum is subtracted from their product, which of the following numbers could be obtained?
The choices are 21, 60, 119, 180 and 231. We can immediately see that the answer must be odd. Because the span of the three remaining choices is so wide, we suspect that we can eliminate the smallest and the largest. Trying for 5 and 7 — the two smallest primes in the range — we can eliminate 21. Similarly, checking the two largest primes in the range, we can eliminate 231. This leaves us with the answer: 119. If the choices were different, we might have lost the interplay between the solution and the list of choices. Then, solving the problem would have been slower and more boring. There are ten pairs of prime numbers to check. And we would need on average to check five of them until we stumbled on the correct choice.
In other cases having multiple choices makes the problem more boring and less educational. Here is another problem from the same competition.
Two non-zero real numbers, a and b, satisfy ab = a – b. Find a possible value of a/b + b/a – ab.
Solving this problem without choices can teach students some clever tricks that people use when playing with expressions. Indeed, when we collect a/b + b/a into one fraction (a2 + b2)/ab, we might remember that a2 + b2 is very close to (a – b)2, and see from here that a/b + b/a – 2 is (a – b)2/ab, which, given the initial condition, equals ab. Thus, we can get the answer: 2.
On the other hand, if you look at the multiple choices first: -2, -1/2, 1/3, 1/2, 2, you might correctly assume that the answer is a number. Thus, the fastest way to solve it is to find an example. If a = 1, then b must be 1/2, and the answer must be 2. This solution doesn't teach us anything new or interesting.
My next example from the 2002 AMC10 is similar to the previous one. The difference is that the solution with multiple choices is even more boring, while the solution without these choices is more interesting and beautiful.
Let a, b, and c be real numbers such that a – 7b + 8c = 4 and 8a + 4b – c = 7. Then a2 – b2 + c2 is: 0, 1, 4, 7, or 8.
Given the choices, we see that the answer is a number. Hence we need to find any solution for the system or equations: a – 7b + 8c = 4 and 8a + 4b – c = 7. For example, if we let c = 0, we have two linear equations and two variables a and b that can be solved by a straightforward computation. Then we plug the solution into a2 – b2 + c2.
Without knowing that the result is a number, we need to look at the symmetries of our two initial equations. We might discover a new rule:
If we have two expressions ax + by and bx – ay, where a and b are switched between variables and there is a change in sign, it is a good idea to square each of them and sum them up, because the result is very simple: (a2 + b2)(x2 + y2).
Hence, in our initial problem we need to move the term with b in our two linear equations to the right; then square them and sum up the results. This way we may get a very simple expression. And indeed, this trick leads to a solution and this solution provides insight into working with algebraic expressions.
This is the perfect problem to linger over, assuming you're not in the middle of a timed competition. It might make you wonder for which parameters this problem works. You might discover a new theorem that allows you to create a very similar problem from any number that can be represented as a sum of two non-trivial squares in two different ways.
To prepare my students for AMC I need to teach them tricks that are not useful at USAMO, or in mathematics in general for that matter. Many tricks distract from new ideas or from understanding the problem. All they give us is speed.
This bothers me, but to pacify myself, I keep in mind that most of my students will not become mathematicians and it might be useful in their lives to be able to make split-second decisions among a small number of choices.
However, it seems like Americans have the opposite problem: we make quick decisions without thinking. I'm concerned that training for multiple choice tests and AMC competitions aggravates this problem.
What object is missing?
Should you try to guess an answer to a multiple-choice problem during a test? How many problems should you try to guess? I will talk about the art of boosting your guessing accuracy in a later essay. Now I would like to discuss whether it makes sense to pick a random answer for a problem at AMC 10.
Let me remind you that each of the 25 problems on the AMC 10 test provides five choices. A correct answer brings you 6 points, a wrong answer 0 points and not answering at all gives you 1.5 points. So guessing makes the expected average per problem to be 1.2 points. That is, on average you lose 0.3 points when guessing. However, if you are lucky, guessing will gain you 4.5 points per problem, and if you are unlucky, it will lose you 1.5 points per problem.
So we see that on average guessing is unprofitable. But there are situations in which you have nothing to lose if you get a smaller score and a lot to gain if you get a better score. Usually the goal of a competitor at AMC 10 is to get to AIME. For that to happen, you need to get 120 points or be in the highest one percentile of all competitors. This rule complicates my calculations. So I decided to simplify it and say that your goal is to get 120 points and then see what mathematical results I can get out of that simplification.
First, suppose you are so accurate that you never make mistakes. If you have solved 20 problems, then your score without guessing is 127.5. If you start guessing and guess wrongly for all of the last five questions, you still have your desired 120 points. In this instance it doesn't matter whether you guess or not.
Suppose on the other hand that you are still accurate, but less powerful. You have only solved 15 problems, so your score without guessing is 105. Now you must be strategic. Your only chance to get to your goal of 120 points is to guess. Suppose you randomly guess the answers for the 10 problems you didn't solve. To make it to 120, you need to guess correctly at least five out of the ten remaining problems. The probability of doing so is 3%. Here is a table of your probability of making 120 points if you solve correctly n problems and guess the other problems.
| n | Probability |
|---|---|
| 20 | 1.0 |
| 19 | 0.74 |
| 18 | 0.42 |
| 17 | 0.20 |
| 16 | 0.09 |
| 15 | 0.03 |
| 14 | 0.01 |
| 13 | 0.004 |
| 12 | 0.001 |
We can see that if you solved a small number of problems, then the probability of getting 120 points is minuscule; but as the number of problems you solved increases, so does the probability of getting 120 points by guessing.
The interesting part is that if you have solved 19 problems, you are guaranteed to get to AIME without guessing. On the other hand, if you start guessing and all your guesses are wrong, you will not pass the 120 mark. The probability of having all six problems wrong is a not insignificant 26%. In conclusion, if you are an accurate solver and want to have 120 points, it is beneficial to guess the remaining problems if you solved fewer than 19 problems. It doesn't matter much if you solved fewer than 10 problems or more than 19. But you shouldn't guess if you solved exactly 19.
If you are not 100% accurate things get more complicated and more interesting. To decide about guessing, it is crucial to have a good estimate of how many mistakes you usually make. Let's say that you usually have two problems wrong per AMC test. Suppose you gave answers to 20 problems at AMC. What's next? Let us estimate your score. Out of your 20 answers you are expected to get 18*6 points for them plus 5*1.5 points for the problems you didn't answer. Your expected score is 115.5. You are almost there. You definitely should guess. But does it matter how many questions you are trying to guess?
The correct answer to one question increases your score by 4.5 with probability 0.2, and the wrong answer decreases your score by 1.5 with probability 0.8. One increase by 4.5 is enough for you goal of 120 points. So if you guess one question, with probability 0.2, you get 120 points. If you guess two questions, then your outcome is as follows: you increase your score by 9 points with probability 0.04; you increase your score by 3 points with probability 0.32; and you decrease your score by 3 points with probability 0.64. As you need at least a 4.5 increase in points, it is not enough to guess one question out of two. You actually need to guess correctly on both of them. The probability of this happening is 0.04. It is interesting, but you have a much greater chance to get to your goal if you guess just one question than if you guess two. Overall, here is the table of probabilities to get to 120 points where m is the number of questions you are guessing.
| m | Probability |
|---|---|
| 0 | 0 |
| 1 | 0.20 |
| 2 | 0.04 |
| 3 | 0.10 |
| 4 | 0.18 |
| 5 | 0.26 |
Your best chances are to guess all the remaining questions.
By the end of the test you know how many questions you answered, but you don't know how many errors you made. The table below tells you what you need in order to get 120 points. Here is how you read the table: The number of problems you solved is in the first column. If you are sure that the number of mistakes is not more than the number in the second column, you can relax as you made at least 120 points. The last column gives the score.
| Answered problems | Mistakes you can afford | Score |
|---|---|---|
| 19 | 0 | 123.0 |
| 20 | 1 | 121.5 |
| 21 | 2 | 120.0 |
| 22 | 2 | 124.5 |
| 23 | 3 | 123.0 |
| 24 | 4 | 121.5 |
| 25 | 5 | 120.0 |
If the number of mistakes you made is one more than in the corresponding row of the table, you should start guessing in order to try to get 120 points. Keep in mind that there is a risk: if you are not sure how many problems you solved already and start guessing, you might ruin your achievement of 120 points.
In the next table I show how many questions you can guess without the risk of going below 120 points. The word "all" means that it is safe to guess all the remaining questions.
| Answered problems | Mistakes you can afford | Score | Non-risky guesses |
|---|---|---|---|
| 19 | 0 | 123.0 | 2 |
| 20 | 1 | 121.5 | 1 |
| 21 | 2 | 120.0 | 0 |
| 22 | 2 | 124.5 | all |
| 23 | 3 | 123.0 | all |
| 24 | 4 | 121.5 | all |
You can see that if your goal is to get 120 points, your dividing line is answering 22 questions. If you solved 22 questions or more, there is no risk in guessing. Namely, if you have already achieved more than 120 points, guessing will not take you below that. But if you made more errors than are in the table, then guessing might be beneficial. Hence, you should always guess in this case — you have nothing to lose.
Now I would like to show you my calculations for a situation in which you are close to 120 points and need to determine the optimum number of questions to guess. The first column is the number of answered questions. The second column is the number of mistakes. The third column is your expected score without guessing. The fourth column is the optimum number of questions you should guess. And the last column lists your chances to get 120 points if you guess the number of questions in the fourth column.
| Answered problems | Mistakes | Score | Questions to guess | Probability of success |
|---|---|---|---|---|
| 17 | 0 | 114.0 | 8 | 0.20 |
| 18 | 0 | 118.5 | 7 | 0.42 |
| 18 | 1 | 112.5 | 7 | 0.15 |
| 19 | 1 | 117.0 | 2 | 0.36 |
| 19 | 2 | 111.0 | 6 | 0.10 |
| 20 | 2 | 115.5 | 5 | 0.26 |
| 21 | 3 | 114.0 | 4 | 0.18 |
| 22 | 3 | 118.5 | 3 | 0.49 |
| 22 | 4 | 112.5 | 3 | 0.10 |
| 23 | 4 | 117.0 | 2 | 0.36 |
| 23 | 5 | 111.0 | 2 | 0.04 |
| 24 | 5 | 115.5 | 1 | 0.20 |
You can see that almost always if you are behind your goal, you should try to guess all of the remaining questions, with one exception: if you answered 19 questions and one of them is wrong. In this case you should guess exactly two questions — not all that remain.
Keep in mind that all these calculations are very interesting, but don't necessarily apply directly to AMC 10, because I simplified assumptions about your goals. It may not be directly applicable, but I hope I have expanded your perspective about how you can use math to help you understand how better to succeed at math tests and how to design your strategy.
I plan to teach you how to guess more profitably, and this skill will also advance your perspective.
Lottery is a tax on people bad at math.
In this article I calculate how bad the lottery is as an investment, using Mega Millions as an example. To play the game, a player pays $1.00 and picks five numbers from 1 to 56 (white balls) and one additional number from 1 to 46 (the Mega Ball number, a yellow ball).
During the drawing, five white balls out of 56 are picked randomly, and, likewise, one yellow ball out of 46 is also picked independently at random. The winnings depend on how many numbers out of the ones that a player picks coincide with the numbers on the balls that have been drawn.
So what is your expected gain if you buy a ticket? We know that only half of the money goes to payouts. Can you conclude that your return is 50%?
The answer is no. The mathematical expectation of every game is different. It depends on the jackpot and the number of players. The more players, the bigger is the probability that the jackpot will be split.
Every Mega Millions playslip has odds printed on the back side. The odds of hitting the jackpot are 1 in 175,711,536. This number is easy to calculate: it is (56 choose 5) times 46.
How much is 175,711,536? Let's try a comparison. The government estimates that in the US we have 1.3 deaths per 100 million vehicle miles. If you drive one mile to buy a ticket and one mile back, your probability to die is 2.6/100,000,000. The probability of dying in a car accident while you drive one mile to buy a lottery ticket is five times higher than the probability of winning the jackpot.
Suppose you buy 100 tickets twice a week. That is, you spend $10,000 a year. You will need to live for 1,000 years in order to make your chances of winning the jackpot be one out of 10. For all practical purposes, the chance of winning the jackpot are zero.
As the probability of winning the jackpot is zero, we do not need to include it in our estimate of the expected return. If you count all other payouts then you are likely to get back 18 cents for every dollar you invest. You are guaranteed to lose 82% of your money. If you spend $1000 a year on lottery tickets, on average you will lose $820 every year.
If you do not buy a lot of tickets your probability of a big win is close to zero. For example, the probability of winning $250,000 (that is guessing all white balls, and not guessing a yellow ball) by buying one ticket is about 1 in 4 million. The probability of winning $10,000 — the next largest win — is close to 1 in 700,000. If we say that you have no chance at these winnings anyway, then your expected return is even less: it is 10 cents per every dollar you invest.
You might ask what happens if we pool our money together. When a lot of tickets are bought then the probability of winning the jackpot stops being zero. I will write about this topic later. For now this is what I would like you to remember. From every dollar ticket:
I am not at all trying to persuade you not to buy tickets. Lottery tickets have some entertainment value: they allow you to briefly dream about what you would do with those millions of dollars. But I am trying to persuade you not to buy lottery as an investment and not to put more hope into it than it deserves. If you treat lottery tickets as tickets to a movie that is played in your head, you will never buy more than one ticket at a time.
That is it. I advise you not to buy more than one ticket at a time. One ticket will allow you to dream about the expression on your sister's face when she sees your new $5,000,000 mansion, but will not destroy your finances.
Should you allocate time for checking your answers during important tests? I will use AMC 10/12 as an example, but you can adjust the calculations for any other test.
AMC 10/12 is a math competition that asks 25 multiple-choice questions that you need to solve in 75 minutes. You get 6 points for a correct answer, 1.5 points for an unanswered question and 0 points for a wrong answer.
Whether or not to take time to check your answers depends on you and the situation. If you finished your test and have some time left over, then surely you should use the extra time for checking your answers. If you only have three minutes left and your next problems are too complex to be dealt with in that time, then it is logical to use these moments to check back.
Sometimes, though, it isn't worth it to check your answers. If you haven't finished the test, but are a super-accurate person and never make mistakes, then it is better to continue working on the next problem than to waste time checking your correct answers. Also, if you rarely catch your own mistakes anyway, it doesn't make sense to check.
But things are not usually so clear. By the end of the test, most people need to make a decision: continue working through the problems or use the final moments to check the answers? How can you best decide if you should allocate time for checking and, if so, how much time?
The problems in AMC tests increase in difficulty. I suggest that each time you take the test or practice for AMC, take note of two things. How long did it take you to solve the test's last problem and what is the level of your accuracy for it. Suppose you know that at the end of the AMC test you can solve a problem in about 10 minutes and it is correct about 90% of the time. That means that investing the last ten minutes in solving the next problem will give you on average 5.4 points. If you remember that a blank answer gives you 1.5 points, you should realize that solving the last problem increases your score by 3.9 points. If you are very accurate, your score can increase more, but not more than 4.5 points.
Try conducting the following experiment. Take an AMC test from a past year. Do it for 65 minutes — the time of the test minus the time you need for that last problem. Then spend the last 10 minutes checking and correcting your answers. Now let us calculate how profitable that would be. Compare the scores you would have gotten without your corrections and with your corrections. If checking increases your score by more than 3.9 points, it is more profitable to check than to solve the next problem. If you do not make errors when you're trying to make corrections, the rule of thumb is that correcting one mistake is better than solving one problem. Indeed, your score increases by 6 points if you correct a mistake, and by not more than 4.5 points if you solve the next problem.
On all tests that punish wrong answers, correcting an error produces more points than solving a new question.
If you find that checking is profitable, but you can't check all the problems in ten minutes, you should consider allocating more time. Keep in mind, though, that you should adjust the sample calculation above for the last two problems. Remember, the next to the last problem is generally easier than the last problem. So if it takes you ten minutes to solve the last problem in the test, it most probably will take you less than twenty minutes to solve the last two. Also, since the difficulty increases throughout the test, the accuracy of the second to last problem might be better than the accuracy of the last problem. In addition, the first ten minutes that you check may be more productive than the next ten minutes of checking. So if you wonder if you should forgo the last two problems in order to check your earlier work, you have to redo the experiment anew, measuring both how long it takes you to solve those two problems and the benefits of checking.
This discussion can potentially help you to increase your score. However, there are other strategic considerations to weigh when deciding whether or not to check your work. For example, if the number of mistakes in your tests varies and sometimes you are 100% accurate and you are one problem away from your goal to get to AIME, it is more profitable to go for the last problem and hope for the best. I will discuss the strategic considerations for AMC some other time.
This essay is written especially for high school and undergrad math lovers who enjoy problem solving and who plan to major in mathematics. One of the authors, Tanya, often received this advice when she was an undergraduate in Russia: "Problem solving is child's play. You'll have to change your attitude if you plan to succeed in research."
Perhaps that's why some famous problem solvers, even those who won gold medals at IMO, became not-so-famous mathematicians. To help you avoid that fate, we'll discuss the ways in which research is unlike problem solving.
Yes and no. There are many mathematicians who continue problem solving as their form of research. Remember Paul Erdos who used to suggest a lot of problems and even offered money rewards for solutions. Many mathematicians solve problems posed by other people. You might consider Andrew Wiles as the ultimate math problem solver: he proved Fermat's last theorem, which had been open for 400 years. Though he could not have done it without the many theories that had already been generated in the search to find the elusive proof.
You can become a mathematician and continue to look around you for problems to solve. Even though this is still problem solving, the problems will be very different from competition problems, and you will still need to adjust to this type of research.
So, what is the difference between problems that mathematicians solve during competition and the problems they tackle for their research?
Expected answer. In competition problem solving you know there is a solution. Often you know the answer, but you just need to prove it. In research there is no guarantee. You do not know which way it will go. For this reason finding counter-examples and proving that some ideas are wrong is a positive contribution, for it can eliminate some possibilities. So one adjustment is that you might start valuing negative answers.
Difficulty level. Competition problems are designed to be solved in one hour, so you are expected to generate an idea in just minutes. In research the problem might drag on for years, because it is far more difficult. If you get used to the instant gratification of competition problem solving, you might find the lengthy work of research frustrating. It's very important to adjust your expectations so that you won't drop a problem prematurely. You need to measure progress in small intermediate steps and learn to appreciate this different rhythm.
Motivation. Although you miss the euphoria of finding quick solutions, you get a different kind of reward with research. Because no one knows the answer in advance, when you solve the problem, you are the first to do so. You have opened up a new truth.
Time limits. In competitions you have a time limit for every problem. In research you set your time limits yourself. That allows you to put a problem aside and come back later if necessary. In a sense you can think about several problems at the same time.
Your passion. You can choose your problems yourself. Research is much more rewarding if you follow your heart. In competitions you have to spend time on problems you might not like. Here you have an option to choose and pick only the problems that appeal to you. Thus, you become more motivated and as a result more successful.
After solving problems posed by other people, the next step is to pose math problems yourself. As we mentioned before, in research you do not always have a strictly-defined problem. It is a significant adjustment to move from solving already-defined problems to posing the problems yourself.
Generalizations. Often you can generalize from an existing problem to more general cases. For example, if you see a problem for n=3, you can wonder what happens for any n, or for any prime n.
Being on the lookout. Sometimes a situation puzzles you, but you can't formulate a specific problem around that situation. For example, why do most of the terms in the sequence end in 9? Is there a reason for that? Or, you might find that a formula from your integrable systems seminar is similar to a formula from your representation theory class. This might lead you to the essential research question: "What is going on?" You always need to be on the lookout for the right questions.
Value. When you create your own research problems it is crucial to always ask yourself: Is the problem I am creating important? What is the value of this problem? There is no a good reason to create random generalizations of random problems. If the problem you found interests you very much, that is the first sign that it might interest other people; nonetheless, you should still ask yourself how this problem will help advance mathematics.
There are other things to do than solve problems. There are many mathematicians who work differently, who don't solve problems or don't only solve problems. Here are some of the many options mathematicians have:
Building structures. You may not be interested in calculating the answer to a question, but rather in building a new structure or a new theory.
Advancing the language. When you invent new definitions and new notations, you will help to simplify a math language so that the new language will allow you to prove your results and other peoples' results faster and clearer.
Unification. Sometimes you notice two results in two different areas of mathematics with some kind of similarity. Explaining why these results are the same might create a new understanding of things. It is great to unify two different areas of mathematics.
Explaining. Very often proofs are not enough. Why is something true? What's the reason and what's the explanation? It is good to ask yourself a "why" question from time to time, such as, "Why is this proof working?" When you find an answer, it might become easier to understand what to do next and how to generalize your proof.
Directions. Many mathematicians are valued not for the problems they solve or suggest, but for ideas and directions they propose. Finding a new direction for research can generate unexpected opportunities and create tons of math problems on the way. It can be valuable to come up with good conjectures, even if you have no hope of solving them yourself. Two example of this are the Weil conjectures (eventually proved by Deligne) and the Langlands program, which is still incomplete but which has generated a huge amount of important research.
Vision. What is the most general thing that can be proved by this technique? What kinds of improvements and refinements are there? It is good to step back from the problem you solved and meta-think about it.
As you can see, problem solving is just the beginning of all that mathematics can offer you. Mathematicians find these other options very rewarding, so it's worth your while to try these varied aspects of mathematical work to see if you have a taste for other things. If you don't venture beyond problem solving you might miss the full beauty of mathematics.
I could no longer resist: I added a section of physics jokes to my math jokes collection:
* * *
A hydrogen atom says to the bartender, "Hey buddy, have you seen an electron around here? I seem to have lost mine."
"Are you sure you lost it?" the bartender asks.
And the hydrogen atom answers, "I'm positive!"
* * *
Heisenberg gets stopped on the motorway by the police.
Cop: "Do you know how fast you were going sir?"
Heisenberg: "No, but I know exactly where I am."
* * *
A photon checks into a hotel. The bellhop asks him, "Can I help you with your luggage?"
To which the photon replies, "I don't have any. I'm traveling light."
My recent entry, where I asked you to choose the odd one out among these images
was extremely popular. It was republished all around the world and brought my blog as much traffic in one day as I used to get in a month. Not only did I read the many comments I received, I also followed up on other peoples' blogs who reprinted my puzzle — at least those that were in either Russian or English. I also got private emails and had many conversations in person about it. The diversity of answers surprised me, so I would like to share them with you.
As I've said before, I do not think there is a correct answer to this type of question, but I was disappointed by some of the answers. For example, those who simply said, "The green one is the odd one out," made me feel that either they hadn't read the question or hadn't thought about it very much. It's a shame that these people spent more time sharing their opinion with the world than thinking about the problem in the first place.
I wouldn't mind someone arguing that the green one is the odd one out, but in this case an explanation is in order. Many people did offer explanations. Some told me that we perceive the color difference stronger than all other parameters I used, and the green figure pops out of the picture more than anything else. In fact, I personally perceive color difference the strongest among all the parameters, but since there are people who are color blind, I would disregard my feelings for color as being subjective.
You can create a whole research project out of this puzzle. For example, you can run an experiment: Ask the question, but flash the images above very fast, so there is no time for analysis — only time to guess. This allows us to check which figure is the first one that people perceive as different. Or you can vary the width of the frame and see how the perception changes.
Color was not the only parameter among those I chose — shape, color, size and the existence of a frame — that people thought was more prominent. My readers weighed these parameters unequally, so each argued the primary importance of the parameter they most emphasized. For example, one of my friends argued that:
The second figure should be the odd one out as, first, it is the only one without a frame, and, second, it is the only one comprised of one color rather than two. So it differs by two features, as others differ only by one feature.
A figure having one color is the consequence of not having a frame, so this particular friend of mine inflated the importance of not having a frame.
However, I can interpret any feature as two features. For example, I can say that the circle is the odd one out because not only is it a different figure, but it also doesn't have any angles. Similarly, the last one is the smallest one and the border width is in a different proportion to its diameter.
On a lighter side, there were many funny answers to the puzzle:
For the which-is-the-odd-one-out questions, the designer of the question is usually expecting a particular answer. So here's the answer I expected:
There is only one green figure. Wait a minute, there is only one circle. Hmm, there is only one without a frame and there's only one small figure. I see! The first one is the only figure that is not the odd one, that doesn't have a special property, so the first must be the odd one out. This is cool!
And the majority of the answers were exactly as I expected.
Since this is a philosophical problem, some of the responses took it to a different level. One interesting answer went like this:
All right, the last four figures have special features; the first figure is special because it is normal. Hence, every figure is special and there are no odd ones here.
I like this answer as the author of it equated regular features with a meta-feature, and it is a valid choice. This answer prompted me to write another blog entry with a picture where I purposefully tried to not have an odd one out:
Though I wrote that the purpose of this second set of images is to show an example where there is no odd one out, my commentators still argued about which one was the odd one out here.
Finally, I would like to quote Will's comment to my first set of images:
The prevailing opinion is that the first is least unique and is therefore the oddest. But it is the mean and the others are one deviation from it. Can the mean be the statistical anomaly?
And Cedric replied to Will:
Yes, I think the mean can be a statistical anomaly. The average person has roughly one testicle and one ovary. But a person with these characteristics would certainly be an anomaly.
I started my blog about two year ago. I have written about 200 entries. According to my traffic reports, these have been the top ten most popular entries:
My most popular category was Math Humor.
Israel Gelfand's memorial is being held at Rutgers on December 6, 2009. I was invited as Gelfand's student.
My relationship with Gelfand was complicated: sometimes it was very painful and sometimes it was very rewarding. I was planning to attend the memorial to help me forget the pain and to acknowledge the good parts.
I believe that my relationship with Gelfand was utterly unique. You see, I was married three times, and all three times to students of Gelfand.
Now that I know that I can't make it to the memorial, I can't stop wondering how many single male students of Gelfand will be there.
I've translated two problems from the 2009 Moscow Math Olympiad. In both of them our characters are genetically engineered octopuses. The ones with an even number of arms always tell the truth; the ones with an odd number of arms always lie. In the first problem (for sixth graders) four octopuses had a chat:
- "I have 8 arms," the green octopus bragged to the blue one. "You have only 6!"
- "It is I who has 8 arms," countered the blue octopus. "You have only 7!"
- "The blue one really has 8 arms," the red octopus said, confirming the blue one's claim. He went on to boast, "I have 9 arms!"
- "None of you have 8 arms," interjected the striped octopus. "Only I have 8 arms!"
Who has exactly 8 arms?
Not only do octopuses lie or tell the truth according to the parity of the number of their arms, it turns out that the underwater world is so discriminatory that only octopuses with six, seven or eight arms are allowed to serve Neptune. In the next problem (for seventh graders), four octopuses who worked as guards at Neptune's palace were conversing:
- The blue one said, "All together we have 28 arms."
- The green one said, "All together we have 27 arms."
- The yellow one said, "All together we have 26 arms."
- The red one said, "All together we have 25 arms."
How many arms does each of them have?
My students enjoyed the octopuses, so I decided to invent some octopus problems of my own. In the first problem, the guards from the night shift at Neptune's palace were bored, and they started to argue:
- The magenta one said, "All together we have 31 arms."
- The cyan one said, "No, we do not."
- The brown one said, "The beige one has six arms."
- The beige one said, "You, brown, are lying."
Who is lying and who is telling the truth?
In the next problem the last shift of guards at the palace has nothing better to do than count their arms:
- The pink one said, "Gray and I have 15 arms together."
- The gray one said, "Lavender and I have 14 arms together."
- The lavender one said, "Turquoise and I have 14 arms together."
- The turquoise one said, "Pink and I have 15 arms together."
What number of arms does each one have?
An ancient Russian joke:
Patient: Doctor, is there a medicine I can use to prevent my girlfriends from become pregnant?
Doctor: Kefir.
Patient: Should I drink it before or after sex?
Doctor: Instead of.
I have a more pleasurable suggestion than drinking kefir: date postmenopausal women. There are many other reasons why men enjoy dating older women, but since my blog is about mathematics, I would like to dig into some relevant numbers.
We know that boys are born more often than girls, and men die earlier than women. Somewhere around age 30 the proportion in population switches from more boys to more girls. And it gets more skewed with age. So there's a deficit of older men. In addition, a big part of the population is married, making the disproportions in singles group more pronounced. So I decided to look at the numbers to see how misshaped the dating scene is.
This 2008 data comes from the U.S. government census website's table "Marital Status of the Population by Sex and Age: 2008. (Numbers in thousands. Civilian non-institutionalized population.)" To calculate the number of singles, I summed up the widowed, divorced and never married columns.
| Age Group | Single Male | Single Female | Ratio M/F |
|---|---|---|---|
| Total | 44,707 | 51,293 | 0.87 |
| 15 to 17 years | 6,729 | 6,513 | 1.03 |
| 18 to 24 years | 13,074 | 11,848 | 1.10 |
| 25 to 29 years | 6,639 | 5,224 | 1.27 |
| 30 to 34 years | 3,901 | 3,343 | 1.17 |
| 35 to 39 years | 3,354 | 2,965 | 1.13 |
| 40 to 44 years | 3,410 | 3,270 | 1.04 |
| 45 to 49 years | 3,476 | 3,591 | 0.97 |
| 50 to 54 years | 2,979 | 3,385 | 0.88 |
| 55 to 59 years | 2,309 | 3,123 | 0.74 |
| 60 to 64 years | 1,552 | 2,746 | 0.57 |
| 65 to 69 years | 1,082 | 2,423 | 0.47 |
| 70 to 74 years | 787 | 2,162 | 0.36 |
| 75 to 79 years | 790 | 2,391 | 0.33 |
| 80 to 84 years | 685 | 2,430 | 0.28 |
| 85 years and over | 669 | 2,391 | 0.28 |
These data alone cannot explain the dating situation. For example, I have no way of knowing what proportion of each gender isn't interested in dating the opposite sex, or even in dating altogether. But the trend is quite clear: the proportion of men in younger categories is much higher. That implies that there is less competition for older women. So those young men who are open to dating much older women might have more options and those options might be more interesting.
I just turned 50 and plan to return to dating again. Looking at the data I see that there are 11 million single men older than me and 34 million who are younger than me. If I were to pick a single man randomly, I am three times more likely to end up with a younger man.
Supposedly we live in a free society, where people can do what they want as long as they do not harm anyone else. Still our society often disapproves of women dating much younger men. Consider this definition from Wikipedia:
"Cougar — a woman over 40 who sexually pursues a much younger men."
This derogatory term portrays such women as predatory. Not only is there nothing wrong with women dating younger men, but it makes no sense for older women to ignore the imbalance of the dating scene and be closed to relationships with much younger men. After all, the demographics are also affected by the fact that women live longer, probably because of their healthy life style, non-risky behavior and positive attitude to life.
Can someone explain to me again why sane, healthy, non-risky women with positive attitudes to life are called "cougars"?
The first episode of Numb3rs: Season Six
Suppose you are in a prison and the guard says to you, "You will be hanged tomorrow at noon and it will be a surprise." You presume that you can't be surprised since they already told you, so there is a contradiction in what they've said. Therefore, you conclude that they can't hang you and you relax. Next day at noon the guard comes for you, to take you to be hanged, and you are utterly surprised. Oops.
What I do not like about this paradox is that it assumes that you do not know about the paradox. I, on the other hand, imagine that you, my reader, are logical and intelligent. So the moment the guard tells you that you will be hanged tomorrow at noon and it will be a surprise, you realize that the situation depends on what you decide to believe in now. If you decide that you won't be hanged tomorrow, then you will have a relatively relaxing day today and you will be caught by surprise tomorrow and die. If you decide that you will die tomorrow, then you will have a nerve-wracking day today, but the guard may release you, to save his honor, since you won't be surprised.
The original hangman's paradox in which the guard tells you that you will be hanged on a weekday the following week and that you will be caught by surprise, also assumes that you are not aware of the paradox. If you are aware of the paradox, you know that usually guards in this paradox come for you on Wednesday, so you can prepare yourself. Actually, to guarantee your survival, if not your feeling of moral superiority, you can daily persuade yourself to belief that you will be hanged at noon the next day. This way, you will never be caught by surprise. If you are a person who can control your own beliefs, you may be able to save your life.
The book An Introduction to Diophantine Equations by Titu Andreescu and Dorin Andrica is targeted at people preparing for USAMO and IMO. It contains a lot of problems on Diophantine equations from math Olympiads used in various math Olympiads all over the world.
The first chapter discusses several methods for solving Diophantine equations: decomposition, using inequalities, using parameters, modular arithmetic, induction, infinite descent, and other miscellaneous ideas. Each sub-chapter starts with a short description of the method, accompanied by several solutions to sample problems. At the end of each sub-chapter there are a plethora of exercise problems.
The second and the third chapters are more theoretical. The former discusses some classical equations and the latter looks at Pell's equation. These two chapters also contain problems, but the bulk of the chapters is devoted to basic theory that is essential to an understanding of Diophantine equations.
For those who are training for the Olympiads, this is an important book to own, not only because there are few other books on the subject, but because it provides so many useful problems.
I've long complained that most training books for math competitions leave out any discussion of how we choose a method by just looking at a problem. Andreescu and Andrica didn't fill that gap with this book.
Perhaps in their next book they will point out clues that indicate that a particular problem might be solved by the parametric method. And explain which types of problems are best solved with induction. Let them challenge students to find those clues in a problem that help us to judge which method might be most promising, instead of randomly trying one method after another. Let me give you a sample problem from the book, which originated at the Balkan Mathematical Olympiad:
Prove that the equation x5 – y2 = 4 has no solutions in integers.
The solution is to take the equation modulo 11, and see that it is impossible.
Is there a reason to start with the modular arithmetic method and not with other methods? If we use modular arithmetic, do we recognize why it's best to start with 11? I'm convinced that this problem has sufficient clues to suggest starting with checking this equation modulo 11.
I wonder if you, my readers, agree with me. If so, can you explain which hints in the problem lead to taking the equation modulo 11? I believe it should be a part of competition training to learn to identify clues that suggest that one direction might be preferable to the others.
I love Harvard-MIT Math Tournaments. I like the mini-events, especially when I learn a new game. I also like the guts round, where I enjoy the adrenaline rush of watching the progress in real time. I also like the fact that I know many of the kids from different teams: my current students, my former students, the members of my club, my Sergei's friends.
The problems for the competitions are designed by undergraduate students at MIT and Harvard. Kudos to them. Still, I was somewhat disappointed with the November 2009 problems. Most problems are variations of standard problems with different parameters. It is not easy to design a problem, but I was hoping for something fresh.
My favorite problem from the HMNT 2009 tournament was in the theme round:
There are five guys named Alan, Bob, Casey, Dan, and Eric. Each one either always tells the truth or always lies. You overhear the following discussion between them:Who are the liars?
- Alan: "All of us are truth-tellers."
- Bob: "No, only Alan and I are truth-tellers."
- Casey: "You are both liars."
- Dan: "If Casey is a truth-teller, then Eric is too."
- Eric: "An odd number of us are liars."
My second favorite problem was in the guts round:
Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous — no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.)
This was the funniest problem:
You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and attacking its weak point for massive damage. You cannot cut off any of its claws until you cut off at least three of its legs, and you cannot attack its weak point until you have cut off all of its claws and legs. In how many ways can you defeat the giant enemy crab? (Note that the legs are distinguishable, as are the claws.)
It is difficult to arrange so many problems for four rounds without mistakes. The error in the following problem is not a typo and it bothers me that no one caught it:
Pick a random digit in the decimal expansion of 1/99999. What is the probability that it is 0?
Hey, there is no uniform distribution on an infinite set of integers: picking a random digit is not defined.
Last month I gave my students a problem from Raymond Smullyan's book The Riddle of Scheherazade
A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. How many of them can each say that it is the same color as another one of Hassan's horses?
Half of my students failed to notice the trick and gave the wrong answer. Recently I gave them the continuation of the problem from the same book:
A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan's horses can talk, how many of them can each say that it is the same color as another one of Hassan's horses?
This time the majority of my students didn't notice the trick. This motivated me to continue playing jokes with them. Unfortunately though, Raymond Smullyan had only two problems about Hassan's horses, so I have to invent the next one myself. Here is what I plan to give my students next time:
A certain sheik named Hassan has eight horses. Four of them are white, three are black, and one is brown. Assuming now that Hassan's horses can talk and always tell the truth, how many of them will say that it is the same color as another one of Hassan's horses?
Feel free to continue the series.
My recent blog puzzle where my readers had to choose the odd one out became extremely popular and was republished in many blogs around the world. Some commentators decided that my posting was a joke and an example where the odd one out didn't exist. I have to disappoint them: as a protest against find-the-odd-one-out questions and to illustrate that sometimes there is no good choice for the odd one out I would have chosen a different picture:
Can you find the odd one out?
Inspired by Michael Huber, who in his new book Mythematics
The day was passing towards sunset when the Company finally caught a long-awaited gleam of water, from which sparkled flickers of sunlight. As they quietly drew nearer, they laid their eyes on the next obstacle — a river that they had to transverse. The Company was footsore and tired and the hobbits were starving. But they couldn't rest yet. They needed to collect materials with which to construct their raft before it became too dark. By nightfall they managed to build a tiny raft, and eagerly started their supper.
They couldn't wait until dawn to build more rafts, for they needed to cross the river now. So while they rested, Aragorn smoked his pipe and began to contrive a plan.
Aragorn was in charge and there were eight of them. The four hobbits — Frodo, Sam, Merry and Pippin — were not very useful in battle. However, the four strong fighters — Aragorn, Gimli, Legolas and Boromir, who were sworn to protect the ring-bearer Frodo — were the best in the land.
The small raft they had built would not hold a lot of weight. Aragorn and Boromir were the heaviest. Gimli was short, but together with his armor he weighed as much as either Aragorn or Boromir. Each one of these three heaviest warriors was close to the raft's maximum capacity, so they had to each be alone on the raft while crossing the river. Among the strong fighters, only Legolas was able to cross the river with a hobbit. The raft could also accommodate two hobbits.
Weight was not Aragorn's only consideration: the current was dangerously fast. All the strong men could row, but among the hobbits, only Sam was strong enough to row against such a swift current.
Aragorn also worried about the orcs, who were roaming on both sides of the river. He didn't want to leave any hobbit(s) alone on a riverside, without the safeguard of a strong fighter. Because he was the ring-bearer, Frodo needed extra protection. Aragorn wanted Frodo to be accompanied by at least two strong men. But lately Boromir had become restless when he was around the ring and Aragorn couldn't count on him to look after Frodo. That is, while on the riverside, Frodo's protection had to come from two out of the three remaining strong men: Aragorn, Legolas and Gimli.
Can you help Aragorn design a plan to cross the river?
In a Turing test a human judge on one end of an interface interacts with either a computer or another human through this interface. If the judge can't differentiate a machine from a human, then the computer is said to pass the test. One big goal of folks working in Artificial Intelligence is to build a computer that, when subjected to this test, is indistinguishable from a human.
However, while some people are working hard trying to build programs that can pass as humans, other people are working hard inventing tests that can differentiate between humans and those programs. Such tests are sometimes called Reverse Turing tests. As computer science progresses, the programs that are pretending to be humans as well as reverse tests are becoming increasingly complex.
For example, banks frequently want to prevent malicious computer programs from trying to log into their customers' accounts. As a nice touch the judges are computers in this case. There are different methods designed to confirm that a human is trying to log in. In one of them a picture of a word, called CAPTCHA is presented on a screen, and the program requires that this word be typed in.
I wanted a CAPTCHA with words "Turing Test" in it for this posting. I looked online trying to find a way to do it. I couldn't. There is a ton of software that can produce random CAPTCHAs from a dictionary but nothing could do a particular word. Finally, rather than looking for software, I found a human, a kind gentlemen named Leonid Grinberg who with some GIMP help manually implemented a self-referencing " symbolizing the race between computers and tests.
As text recognition software becomes better and better, these CAPTCHAs become more and more difficult to read by a human. The last time I tried to login, I was only able to type the right word on my fourth try. Very soon computers will be better than humans at parsing CAPTCHAs. Humans are loosing the race on visual methods like this one.
Here's another example. Some malicious software can recognize and capture email addresses on webpages to use for spam. While we don't want them to recognize email addresses, we do want people to be able to do so. Thus we need a way to present email addresses as a reverse Turing test.
The standard safety recommendation is to avoid writing out the full and exact email address. Here's an example: billgates AT gmail DOT com. Actually, I think computers are so smart nowadays that they can learn this trick. Another idea is to show a picture of your email address instead of using characters. Here we return to the image idea, which most computers can nowadays recognize.
Another idea of how to hide an email address is to give simple clues, which point to characters in the email address. For example, if you have "4" in your address, you might say that the character is the sum of two and two. I already invented a version of my email address in which each letter of my username is an answer to a simple question. Unfortunately, I think that the question answering systems like Start, as well as its huge new competitor Wolfram Alpha, will learn to answer these questions very soon. I can construct more sophisticated questions, but that would require my readers to spend more time to figure it out including going back to school for a calculus class.
So, recently, I've come up with a new idea. I made the description of my email simpler, but the paragraph describing my email didn't contain all the necessary information:
I have an email account with Yahoo. My account name consists of seven lower case letters: five letters of my first name concatenated with the first two letters of my last name.
People who want to contact me can easily find my name in the title of my webpage or in my url, but I hoped it would take the evil computers some time to figure out what to look for, where it's located and how to turn it into an address.
The day after I changed my contact web page, I went to my math coaching work at AMSA. During my break, I wanted to unwind by solving a light up puzzle, but it appeared that the new security system at AMSA forbids Internet access to all gaming sites. Thus, being still wound up I decided to do some work and went to my personal page for some materials. I was blocked again. The software politely informed me that access to personal websites was not permitted either. Oops. If a computer can understand that it is a personal website, it probably can figure out the name of the corresponding person. Oops-Oops-Oops. I am loosing the race against computers again. My recent idea to protect my email address from spam lasted one day until my first reality check.
In my days of competing in math, I met guys who could solve any geometry problem by using coordinates: first they would assign variables to represent coordinates of different points, then they would write and solve a set of equations. It seemed so boring. Besides, this approach doesn't provide us with any new insight into geometry.
I find geometric solutions to geometry problems much more interesting than algebraic solutions. The geometric solutions that use geometric transformations are often the shortest and the most beautiful.
I.M. Yaglom wrote a great trilogy called The Geometric Transformations. The first book of this trilogy
I think geometry is the weakest link for the USA math team. So we have to borrow the best geometry books from other countries. This trilogy was translated from Russian and Russians are known for their strong tradition of excellence in teaching geometry.
Below you can find sample problems from Geometric Transformations 1
Problem 1. Let A be a point outside a circle S. Using only a straightedge, draw the tangents from A to S.
Problem 2. At what point should a bridge be built across a river separating two towns A and B (see figure) in order that the path connecting the towns be as short as possible? The banks of the river are assumed to be parallel straight lines, and the bridge is assumed to be perpendicular to the river.
Problem 3. Suppose you have two lines drawn on a piece of paper. The intersection point A of the two lines is unreachable: it is outside the paper. Using a ruler and a compass, draw a line through a given point M such that, were the paper bigger, point A would belong to the continuation of the line.
I added my favorite webcomics from "Not So Humple Pi" to my collection of funny math pictures.
Suppose you got accepted to the college of your dreams, say MIT. If you are so poor that MIT gives you a full financial package or you are so rich that the cost is not an issue, then you might throw a party. Everyone else, however, needs to wait for the financial package letter from MIT. The dream depends on the willingness and the ability of the parents to pay.
Suppose your father looks at the bill in shock. Then he takes you for a walk and tells you to forget about MIT and go to the state college, as he can't pay the requested amount.
If you know for sure that your father has the money, what is the first question that you should ask him? The first question should be: "Are you still married to my mother?" If you are not completely clueless, you ought to know the answer to this question already. The family status of your parents may be the deciding factor in whether or not you can get your father to pay.
If your parents are divorced, your college expenses might be covered by their divorce agreement. In this case, there would be a legal document designating how your parents need to pay. If your father refuses to pay, your mother can use the divorce agreement to threaten your father with a complaint. The threat might be enough. If it is not, the court will probably force the reluctant father to pay according to the divorce agreement. So if your parents are divorced, it might be a good idea for you to scrutinize their divorce agreement.
Even if your parents' lawyers neglected to include college expenses in the divorce agreement, you might still be able to finance your college education. Your mother, for example, might sue your father for college expenses.
I wonder what happens if the divorce agreement covers your college expenses, but neither parent wants to pay. I'm curious whether or not it is possible for the child to sue the parents based on the agreement he/she is not a party to. If any reader knows the answer, I'd appreciate hearing from you.
If your parents are together, there is no divorce agreement to protect your interests. It seems that legally the situation favors the children of divorced parents. If your parents do not love each other and have stayed in their marriage for your sake, it might be to your financial advantage to persuade them to divorce well before you need to go to college. Do not disregard reminding their lawyers to include college expenses in the agreement.
Israel Gelfand was my scientific adviser from the time I was 15. This is the story of how Gelfand helped me, when at 20 I was an undergrad at Moscow State University. At that time, I was married to Sasha (Alexander) Goncharov, who was also Gelfand's student.
Sasha was more driven by mathematics than I. I had a lot of different interests: I wanted to hang out with friends, go to movies and read books. Sasha only wanted to do mathematics. His only other obsession was with what our colleagues (including me) were doing mathematically. So he was constantly asking me about the math problems I was thinking about.
For example, I was sitting at my side of the desk working, and he asked me to tell him about my problem. A few minutes later, I was forced to interrupt my work to go grocery shopping, because the household chores fell to me. As soon as I returned with bread and milk, Sasha excitedly told me the solution to my problem. It made me feel stupid, as if I should have solved it while I was waiting in the line for bread and milk. That feeling blocked out all the other feelings I should have been noticing, such as frustration and annoyance with Sasha.
Without his interference, I would have happily solved the problem myself. I was about to start my serious research, but I worried that I'd end up as a supplier of new problems for his papers.
You might wonder why I didn't stop sharing my math with Sasha. But at that time, I wasn't very in touch with my feelings and I prided myself on being a logical person. The idea that a husband and wife would discuss their work together seemed logical. Besides, even though I wasn't particularly interested, Sasha was always ready to tell me about his math problems. It seemed important for me to be fair and to reciprocate. So I was stuck in a situation I didn't know how to resolve.
I never confided this issue to any math colleagues. I never mentioned it to Gelfand — mostly because I was too scared of him to initiate any conversation. Besides, Gelfand delegated most of his responsibilities to others, because he was quite famous and busy. For example, all official paperwork related to his adviser role was done by Alexandre Kirillov. With me avoiding Gelfand and Gelfand being busy, we almost never spoke one-on-one.
You can understand my surprise when one day Gelfand approached Sasha and me to have a chat. He told us that we were about to start our own research, and while he permitted me to ask Sasha about what he was doing, he would not allow Sasha to interfere with my research.
Gelfand was a great judge of character. Without anyone telling him, he perceived what was going on in our marriage and gave me an excuse to stop Sasha's prying. It was an appreciated gift.
I am strongly opposed to questions of the type "which is the odd one out" during IQ tests. On the other hand, I do not mind them in different settings, especially when they are fun. Inspired by Martin Gardner, I spent a lot of time drawing this picture, and now I have to share it with the world. So, which is the odd one out?
I love the MIT Mystery Hunt. I like the adrenalin rush when solving problems under pressure. Plus, I like the togetherness of doing problems with other people. During the hunt I usually do not have time to look at all the puzzles: some of them are solved by my teammates while I'm sleeping and others are solved before I get to see them.
I've never tried to go back and check out the puzzles I missed nor the puzzles from the previous hunts, probably because without the goal of winning and without my team, I might find them boring. Often the solving process involves tedious Internet browsing to identify the images of different people or objects. I would only be motivated if the puzzle were related to something I am very interested in, such as Ballroom dancing. But I'm not thrilled at the thought of browsing through all the problems in order to find one that is relevant to the Tango.
In short, I need an index to the puzzles. For example, it would be nice to direct the lovers of square dancing to the Do Sa Do puzzle, or fans of Star Trek to the Alien Species puzzle. I hope that nobody blames me for hinting that those aliens are from Star Trek. I'm convinced that Trekkies who only want to solve Star Trek-related puzzles would immediately recognize them anyway. I do believe that I am not revealing too much by saying that the Facebook puzzle will appeal to the aficionados of the television show "24".
It would be extremely useful to humanity to at least mark the MIT Mystery Hunt puzzles that are self-consistent, and do not require activities. For example, some of the puzzles involve interaction with headquarters, so you can't solve them after the hunt. Some of the puzzles might expire, as for example the puzzle with pictures of different announcements in the infinite corridor.
Unfortunately, such an index doesn't exist, and I do not have the time or expertise to create one myself. But I can fill this void at least partially by presenting a guide to math puzzles from the previous four hunts. I can't promise that my guide is complete, as navigating the MIT Mystery Hunt website is very tiresome.
Before going into the math puzzles, I would like to list Sergei's favorite type of puzzle: Duck Konundrums. The first Duck Konundrum puzzle appeared in 2000. It was created by Dan Katz, which is why his initials are in the title. One really needs to follow the instructions for this puzzle. This is very unusual as traditionally hunt puzzles do not have instructions at all. Do not be relieved: the instructions are really very complicated. The next Duck Konundrum puzzle appeared in 2002 and was considered to be even more amusing. People loved it, and this type of puzzle became a tradition in subsequent hunts. Here is my list of Duck Konundrums:
Many Mystery Hunt puzzles appeal to mathematicians. I have to warn you though. Puzzles often are divided into two stages. In the first stage, you need to solve a puzzle, like solving sudoku, a crossword or finding all the wedding dates of the people in the pictures. The second stage requires you to produce a word or a phrase that is the answer to the puzzle. The second stage might be as simple as listing the people in chronological order of their wedding dates and then taking the first letters of their last names. This second stage could also be quite difficult. Depending on your tastes one stage of the puzzle might be much more rewarding than the other. If you love solving sudokus, you might find it more fun to just stop with that solution, instead of continuing on to the second stage.
2006
2007
2008
2009
It would also be nice to have some ratings for puzzles. I am not sure how to persuade the webmasters of the MIT Mystery Hunt page to do the index and the rating. Feel free to send them an encouraging email.
In the book "Mythematics: Solving the Twelve Labors of Hercules
The problems in Mythematics are quite advanced. They range in topic from algebra, geometry and probability to differential equations and integral calculus. Plus, as a reward for helping Hercules, Huber gives you variations on Sudoku puzzles.
Solving some nice math problems might not be the only reason for people to buy this book. Here are some other reasons:
I like Huber's approach. Future possibilities for more books are endless. Let's write new math problems based on Harry Potter, Batman, the Bible or, maybe, The Joy of Sex
Konstantin Knop sent me the following coins puzzle, which was created by Alexander Shapovalov and first appeared at the Regional round of the all-Russian math Olympiad in 2000.
Baron Münchhausen has 8 identical-looking coins weighing 1, 2, …, 8 grams. The Baron knows which coin is which and wants to demonstrate to his guests that he is right. He plans to conduct one weighing on a balance scale, so that the guests will be convinced about the weight of one of the coins. Can the Baron do this?
This being a sequence-lover blog, we want to create a sequence out of this puzzle. The sequence is the following: Let the Baron initially have n identical-looking coins that weigh exactly 1, 2, …, n grams. Then a(n) is the minimum number of weighings on a balance scale that the Baron needs in order to convince his guests about the weight of one of those coins.
The original puzzle can be restated as asking whether a(8) = 1. The sequence is defined starting from index 1 and the first several terms are easy to calculate: 0, 1, 1, 1, 2, 1, 1, 1. Can you continue this sequence?
Let's look at where ones occur in this sequence:
Theorem. If the weight of a coin can be confirmed with one weighing, then one cup of that weighing must contain all the coins with weights from 1 to some i, and the other cup must contain all the coins with weights from some j to n. Furthermore, either the scale must balance, or the cup containing the 1-gram coin must be lighter.
Proof. What does it mean for the Baron to convince his guests about the weight of some coin with one weighing? From the perspective of the guests, a weighing is a number of coins in one cup, a number of coins in the other cup, and a number of coins not on the scale, together with the result the scale shows (one or the other cup heavier, or both the same weight). For the guests to be convinced of the weight of some particular coin, it must therefore be the case that all possible arrangements of coin weights consistent with that data agree on the weight of the coin in question. Our proof strategy, therefore, is to look for ways to alter a given arrangement of coin weights so as to change the weight given to the coin whose weight is being demonstrated, thus arriving at a contradiction.
First, obviously, the coin whose weight k the Baron is trying to confirm has to be alone in its group: either alone on some cup or the only coin not on the scale. After that we can divide the proof of the theorem into several cases.
Case 1. The coin k is on a cup and the scale is balanced. Then we want to show two things: k = n, and the coins on the other cup weigh 1, 2, …, i grams for some i. For the first part, observe that if k < n, then the coin with weight k+1 must not be on the scale (otherwise it would overbalance coin k). Therefore, we can substitute coin k+1 for coin k, and substitute a coin one gram heavier for the heaviest coin that was on the other cup, and produce thereby a different arrangement with the same observable characteristics but a different weight for the coin the Baron claims has weight k.
To prove the second part, suppose the contrary. Then it is possible to substitute a coin 1 gram lighter for one of the coins on the other cup. Now, if coin k-1 is not on the scale, we can also substitute k-1 for k, and again produce a different arrangement with the same observable characteristics but a different weight for the coin labeled k. On the other hand, if k-1 is on the scale but k-2 is not, then we can substitute k-2 for k-1 and then k-1 for k and the weighing is again unconvincing. Finally, if both k-1 and k-2 are on the scale, and yet they balance k, then k=3 and the theorem holds.
Consequently, k = n = 1 + 2 + … + i is a triangular number.
Case 2. The coin k is on the lighter cup of the scale. Then: first, k = 1, because otherwise we could swap k and the 1-gram coin, making the light cup lighter and the heavy cup heavier or unaffected; second, the 2-gram coin is on the heavy cup and is the only coin on the heavy cup, because otherwise we could swap k with the 2-gram coin and not change the weights by enough to affect the imbalance; and finally n = 2 because otherwise we could change the weighing 1 < 2 into 2 < 3.
Thus the theorem holds, and the only example of this case is k = 1, n = 2.
Case 3. The coin k is on the heavier cup of the scale. Then k = n and the lighter cup consists of some collection of the lightest available coins, by the same argument as Case 1 (but even easier, because there is no need to maintain the balance). Furthermore, k must weigh exactly 1 gram more than the lighter cup, because otherwise, k-1 is not on the lighter cup and can be substituted for k, making the weighing unconvincing.
Consequently, k = n = (1 + 2 + … + i) + 1 is one more than a triangluar number.
Case 4. The coin k is not on a cup and the scale is not balanced. Then, since k must be off the scale by itself, all the other coins must be on one cup or the other. Furthermore, all coins heavier than k must be on the heavier cup, because otherwise we could make the lighter cup even lighter by substituting k for one of those coins. Likewise, all coins lighter than k must be on the lighter cup, because otherwise we could make the heavier cup even heavier by substituting k for one of those coins. So the theorem holds; and furthermore, the cups must again differ in weight by exactly 1 gram, because otherwise we could swap k with either k-1 or k+1 without changing the weights enough to affect the result on the scale.
Consequently, the weight of the lighter cup is k(k-1)/2, the weight of the heavier cup is 1 + k(k-1)/2. Thus the total weight of all the coins is n(n+1)/2 = k2+1. In other words, case 4 is possible iff n is the index of a triangular number that is one greater than a square.
Case 5. The coin k is not on a cup and the scale is balanced. This case is hairier than all the others combined, so we will take it slowly (noting first that all the coins besides k must be on some cup).
Lemma 1. The two coins k-1 and k-2 must be on the same cup, if they exist (that is, if k > 2). Likewise k-2 and k-4; k+1 and k+2; and k+2 and k+4.
Proof. Suppose they're not. Then we can rotate k, k-1, and k-2, that is, put k on the cup with k-1, put k-1 on the cup with k-2, and take k-2 off the scale. This makes both cups heavier by one gram, producing a weighing with the same outward characteristics as the one we started with, but a different coin off the scale. The same argument applies to the other three pairs of coins we are interested in, mutatis mutandis.
Lemma 2. The four coins k-1, k-2, k-3 and k-4 must be on the same cup if they exist (that is, if k ≥ 5).
Proof. By Lemma 1, the three coins k-1, k-2, and k-4 must be on the same cup. Suppose coin k-3 is on the other cup. Then we can swap k-1 with k-3 and k with k-4. Each cup becomes heavier by 2 grams without changing the number of coins present, the balance is maintained, and the Baron's guests are not convinced.
Lemma 3. If coin k-4 exists, that is if k ≥ 5, all coins lighter than k must be on the same cup.
Proof. By Lemma 2, the four coins k-1, k-2, k-3 and k-4 must be on the same cup. Suppose some lighter coin is on the other cup. Call the heaviest such coin c. Then, by choice of c, the coin with weight c+1 is on the same cup as the cluster k-1, &hellip, k-4, and is distinct from coin k-2 (because c is on a different cup from k-3). We can therefore swap c with c+1 and swap k with k-2. This increases the weight on both cups by 1 gram without changing how many coins are on each, but moves k onto the scale. The Baron's guests are again unconvinced.
Lemma 4. The theorem is true for k ≥ 5.
Proof. By Lemma 3, all coins lighter than k must be on the same cup. Further, if a coin with weight k+4 exists, then by the symmetric version of Lemma 3, all coins heavier than k must also be on the same cup. They must be on the other cup from the coins lighter than k because otherwise the scale wouldn't balance, and the theorem is true.
If no coin with weight k+4 exists, that is, if n ≤ k+3, how can the theorem be false? All the coins lighter than k must be on one cup, and their total weight is k(k-1)/2. Further, in order to falsify the theorem, at least one of the coins heavier than k must also be on that same cup. So the minimum weight of that cup is now k(k-1)/2 + k+1. But we only have at most two coins for the other cup, whose total weight is at most k+2 + k+3 = 2k + 5. For the scale to even have a chance of balancing, we must have
k(k-1)/2 + k+1 &le 2k + 5 ⇔ k(k-1)/2 ≤ k + 4 ⇔ k(k-1) ≤ 2k + 8 ⇔ k2 - 3k - 8 ≤ 0.
Finding the largest root of that quadratic we see that k < 5.
So for k ≥ 5, the collection of all coins lighter than k is heavy enough that either one needs all the coins heavier than k to balance them, or there are enough coins heavier than k that the theorem is true by symmetric application of Lemma 3.
Completion of Case 5. It remains to check the case for k < 5. If n > k+3, then coin k+4 exists. If so, all the coins heaver than k must be on the same cup. Furthermore, since k is so small, they will together weigh more than half the available weight, so the scale will be unbalanceable. So k < 5 and n ≤ k+3 &le 7.
For lack of any better creativity, we will tackle the remaining portion of the problem by complete enumeration of the possible cases, except for the one observation that, to balance the scale with just the coin k off it, the total weight of the remaining coins, that is, n(n+1)/2 - k must be even. This observation cuts our remaining work in half. Now to it.
Case 5. Seven Coins. n = 7. Then 5 > k ≥ n - 3 = 4, so k = 4. Then the weight on each cup must be 12. One of the cups must contain the 7 coin, and no cup can contain the 4 coin, so the only two weighings the Baron could try are 7 + 5 = 1 + 2 + 3 + 6, and 7 + 3 + 2 = 1 + 5 + 6. But the first of those is unconvincing because k+1 = 5 is not on the same cup as k+2 = 6, and the second because it has the same shape as 7 + 3 + 1 = 2 + 4 + 5 (leaving out the 6-gram coin instead of the asserted 4-gram coin).
Case 5. Six Coins. n = 6. Then 5 > k ≥ n - 3 = 3, and n(n+1)/2 = 21 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 9. The 6-gram coin has to be on a cup and the 3-gram coin is by presumption out, so the Baron's only chance is the weighing 6 + 2 + 1 = 4 + 5, but that doesn't convince his skeptical guests because it looks too much like the weighing 1 + 3 + 4 = 6 + 2.
Case 5. Five Coins. n = 5. Then 5 > k ≥ n - 3 = 2, and n(n+1)/2 = 15 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 6. The only way to do that is the weighing 5 + 1 = 2 + 4, which does not convince the Baron's guests because it looks too much like 1 + 4 = 2 + 3.
Case 5. Four Coins. n = 4. Then the only way to balance a scale using all but one coin is to put two coins on one cup and one on the other. The only two such weighings that balance are 1 + 2 = 3 and 1 + 3 = 4, but they leave different coins off the scale.
The remaining cases, n < 4, are even easier. That concludes the proof of Case 5.
Consequently, by the argument similar to the one in case 4 we can show that the number of coins in case 5 must be the index of a square triangular number.
This concludes the proof of the theorem.
Now we can describe all possible numbers of coins that allow the Baron to confirm a coin in one weighing, or, in other words, the indices of ones in the sequence a(n). The following list corresponds to the five cases above:
If we have four coins, then the same weighing 1+2 < 4 identifies two coins: the coin that weighs three grams and is not in a cup and the coin weighing four grams that is in a cup. The other case like this is for two coins. Comparing them to each other we can identify each of them. It is clear that there are no other cases like this. Indeed, for the same weighing to identify two different coins, it must be the n-gram on the cup, and the n-1 coin off the scale. From here we can see that n can't be big.
As usual we want to give something to think about to our readers. We have given you the list of sequences describing all the numbers for which the Baron can prove the weight of one coin in one weighing. Does there exist a number greater than four that belongs to two of these sequences? In other words, does there exist a total number of coins such that the Baron can have two different one-weighing proofs for two different coins?
To conclude this essay we would like to note that the puzzle we are discussing is related to the puzzle in one of Tanya's previous posts:
You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?
The latter puzzle appeared at the last round of Moscow math Olympiad in 1991. The author of this problem was Sergey Tokarev.
I would like to tell you a story from my childhood and how I started on my math path.
When I was in elementary and middle school, I was very good with mathematics. Actually, I was by far the best math student in my class and my math teacher didn't know what to do with me. Our algebra book had 2,000 problems and was intended to cover three years of study. But I worked out those problems, one after another, whenever I had a free minute in my math class. As I result, I got way ahead of everyone else.
One day a new boy named Lenya Kostyukov joined our class. He had extraordinarily long eye-lashes that covered his eyes, and all the girls envied him. He was a nice smart kid, but other than his lashes, I didn't notice him very much. After a year or two, he announced that he was leaving our school, because he had been accepted to a math school for gifted children.
"Why is he going to a math school? I am the math star here. Why aren't I going to a math school?" I knew about math schools, and I knew that I was good at math; I just never made the connection. I never felt that I was supposed to apply. Despite enjoying my reputation, I just passively went with the flow. Lenya figuratively kicked me in the butt. If he can, why can't I?
So I applied to the same school on the last permissible day and was accepted. It turned out that I accidentally went to the room where they were giving the test for a grade higher than mine. I passed it with flying colors. My parents, though, were scared of a long commute and didn't really want me to go so far away. They found a different math school closer to home, and used my extraordinary results to convince that school to accept me, even though their application date had passed.
For many years I continued to be a very passive person. Applying to a math school was the single big step I took for myself, but it was a defining step. I am grateful to Lenya for that. Or more likely to his parents, who were actively looking around trying to find the best place for their gifted son, and as a byproduct found a place for me. Once I was on the path of mathematics, I had the guidance of teachers and supervisors, for better or for worse, which allowed me to continue to be passive.
I have described my defining moment to you, but I don't want to leave you in the dark about Lenya's fate. Here's what happened to him.
As I mentioned, Leonid (Lenya's formal name) and I ended up in different math schools, so I lost track of him. Four years later I went to study math at Moscow State University and stumbled upon a guy with very long eye-lashes. We recognized each other immediately and eventually became friends.
He was doing logic and was very good at it. He was recommended for graduate school. But by that time our MSU administration noticed his lashes too. The lashes were obviously very suspicious; they hinted at the existence of non-Russian blood in his veins. As it was the period of brutal anti-semitism at MSU, they didn't allow him to go to graduate school.
Leonid Kostyukov dropped mathematics and became a famous writer.
Here is a strange puzzle that was inspired by the palindrome problem. Suppose you have a sequence of words in some alphabet with the initial term a and all the other terms b: a, b, b, b, b, etc. Suppose this sequence generates palindromes every time you concatenate the first several terms, not counting the first term itself. So, ab, abb, abbb, and so on — are all palindromes. We call words b "papaya" words, when a exists, such that a and b generate the sequence with this palindrome property. Can you describe papayas?
Theorem. The word b is a papaya word if and only if b is a substring of Reverse(b)Reverse(b).
Proof. After we have added b so many times that the initial part a is much smaller than half of the concatenated string, the middle part of the concatenated string would consist of several words copies of the word b. The middle of the reverse string consists of several concatenations of Reverse(b). So the word b must be a substring of Reverse(b)Reverse(b). On the other hand, suppose b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby, and we can choose a = y.
Theorem. Papaya words are either palindromes or concatenations of two palindromes.
Proof. Suppose our word consists of two palindromes cd. Then the reverse of it is dc and its double is dcdc. The word cd is a substring of dcdc, thus according to the first theorem, cd is a papaya word. Let's do the other direction. Suppose the word b is a substring of Reverse(b)Reverse(b). Then Reverse(b)Reverse(b) is of the form xby. Then b = yx, and Reverse(b) = xy, which equals Reverse(x)Reverse(y). From here, Reverse(x) = x and Reverse(y) = y. If x or y has zero length, then our word is a palindrome. QED.
Hey, do you already know why we call these words papayas?
Just for fun we would like to study the structure of papaya words. Any one-character or two-character word is a papaya word, so the patterns are: a, aa, ab. For three-character words there are four patterns: aaa, aab, aba, abb. For four-character words there are 10 patterns: aaaa, aaab, aaba, abaa, aabb, abab, abba, abbb, abac, abcb. In this manner we get the sequence of the number of n-character papaya patterns: 1, 2, 4, 10, 21, 50 etc, which is sequence A165137 in the OEIS. This sequence depends on the number of letters in your alphabet. But the first n terms of these sequences are the same for all alphabets that have at least n letters.
Let us assume that we are working with an infinite alphabet. The complementary sequence would be the number of patterns for non-papaya words. The total number of patterns is described by sequence A000110 — Bell numbers: the number of word structures of length n using an infinite alphabet. So the beginning of this complementary sequence A165610 is: 0, 0, 1, 5, 31, 153, etc. The list of corresponding patterns is abc, aabc, abbc, abcc, abca, abcd, etc.
Historically, we first invented the corresponding sequence for numbers, not for words. We call a number a papaya number if it is a palindrome or a concatenation of two palindromes. If we use numbers instead of words in the problem, we need to carefully look at what happens if we encounter initial zeroes. Let's take the papaya number 2200100, and see if we can find a number a, such that adding 22010 repeatedly to this sequence starting with a will always generate a palindrome. The number a must be 00100. But this is not a number. We have two choices: to say that we are working with strings of digits, or to allow several numbers to start the sequence before we add b repetitively and before getting to palindromes. In the latter case our sequence can start 0, 0, 100, 22010, 22010, and so on.
As we mentioned before, the number of patterns of papaya numbers will start the same as the number of patterns of papaya words. Later the sequence of patterns of numbers A165136 will be smaller than the corresponding sequence for words. As the sequence of Bell numbers is much more famous than the sequence A164864 of patterns of numbers, we expect the papaya patterns sequence corresponding to the infinite alphabet to be more interesting and important than the sequence of papaya patterns for numbers.
Though papaya numbers might be less important than papaya words with an infinite alphabet, they have an advantage in that we can generate more sequences with them. For example we can calculate the number of positive papaya number with n digits, as in the sequence A165135: 9, 90, 252, 1872, 4464, 29250, etc. And we can also calculate the sequence A165611 of n-digit non-papaya numbers: 0, 0, 648, 7128, 85536 etc.
This geometric problem was given to me by Arkady Berenstein:
There are n points on the plane, but not all of them are on one line. Prove that a line exists that passes through exactly two points of this set.
Arkady gave me a beautiful solution to this problem. First, draw a line through each pair of points. Suppose you calculate all the distances from each point to all the lines that the point doesn't belong to. Pick the smallest distance. The corresponding line will be the one with two points. To finish the solution you need to fill in the details. That process is usually left to the reader.
I suspect that there might also be a solution using linear algebra. Can you find one?
I would like to reformulate this problem without using geometry. Suppose there is a set of n elements. Let's call a family of subsets line-like if any two distinct subsets of this family can have as an intersection not more than one element. Then the geometry problem above has a set-theoretical analogue:
You have a set of n elements and a line-like family of subsets of this set such that any two elements of the set belong to a subset from this family, and that the family doesn't contain the whole set. Is it true that there always exists a subset in this family consisting of two elements?
Usually I give such problems as homework for the reader, but this time I decided to change my habit, so I'm including the picture which contains the solution of this problem by my son Alexey Radul.
Conclusion: geometry is important.
I remember this question from my childhood:
Why is the South Pole colder than the North Pole?
Indeed, the average winter temperature at the North Pole of -34°C is the same as the temperature at the South Pole at the beginning and end of its summer. The South Pole is only warmer than the North Pole 40 days per year. So the South Pole is a much, much colder place. According to Wikipedia there are three major reasons for this:
I remember when I was a child my father gave me a completely different explanation.
The Earth's orbit is not a circle, but rather an ellipse. According to Kepler's second law: "A line joining a planet and the sun sweeps out equal areas during equal intervals of time." This means that the earth has a slower angle motion around the aphelion — in its furthest point — than around the perihelion — in its closest point to the Sun. Consequently, the summer is longer than the winter for the North Pole, whereas the opposite is true for the South Pole.
Something in my father's explanation bothered me. Now I understand what: though the summer is longer at the North Pole, it should get less sunshine as the North Pole is further away from the Sun than the South Pole during its summer. So the effects might cancel each other out. In any case, as the earth's orbit is almost circular, the contribution of the shape of the orbit should be minor, compared to the effects of elevation, the water underneath and continentality.
On the other hand, it is possible that my father wasn't talking about the poles, but rather about the difference in hemispheres. I wonder if someone can calculate if there is a difference in the amount of sunlight the poles get due to the fact that the Earth's orbit is not circular. Is the temperature different for the places that are equidistant from the equator, and have similar elevation and continentality, but which are located in different hemispheres?
I remember a funny article explaining why the northern hemisphere has more land. They said that continents drifted into the northern hemisphere because they wanted a nicer climate.
I bought the book "Heard on The Street: Quantitative Questions from Wall Street Job Interviews" by Timothy Falcon Crack
The book has problems in logic, probability, statistics and finance, as well as a very useful chapter of general interview questions. If you're interested in buying this book, I should mention that some questions require calculus and knowledge of financial terms.
I love the author's taste in problems, and here are some sample questions from the book.
Question 2.7: How many degrees (if any) are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?
Question 5.1.14: Welcome to your interview. Sit in this chair. Excuse me while I tie your arms and legs to the chair. Thank you. Now we are going to play "Russian roulette." I have a revolver with six empty chambers. Watch me as I load the weapon with two contiguous rounds (i.e., two bullets side-by-side in the cylindrical barrel). Watch me as I spin the barrel. I am putting the gun against your head. Close your eyes while I pull the trigger. This is your lucky day: you are still alive! Our game differs from regular Russian roulette because I am not going to add any bullets to the barrel before we continue, and I am not going to give you the gun.
My question for you: I am going to shoot at you once more before we talk about your résumé. Do you want me to spin the barrel once more, or should I just shoot?
Question 6.1.16: Tell me something you tried but ended up quitting on.
I can tell you what I would have answered to the last question: I tried smoking, but ended up quitting.
Mathematically we can describe a marriage by a graph. People are vertices and two spouses are connected by an edge.
Mathematical models tend to oversimplify life, so let us assume that a person can only be one of two genders. Therefore, the vertices of a graph are colored in two colors: pink and blue. In this article I explore the graph theory of different types of marriages.
A monogamous couple is represented as a complete K2 graph: two vertices connected by an edge. The graph is bipartite, no matter how you color it. But actually our vertices are already colored from the start. If we are considering traditional marriage, one vertex is pink and the other is blue.
Historically, the second most common type of marriage is polygyny, in which one man has several wives. Less common in history, but a mathematically equivalent type, is polyandry, in which one woman has several husbands. Both these types of marriages emphasize inequality, as husbands and wives have completely different sets of rights.
From a mathematical point of view, polygyny and polyandry are described by star graphs. Star graphs are bipartite graphs and the natural coloring is the one that proves bipartiteness.
The final type of marriage is polygynandry, which refers to a group marriage, where more than one man and more than one woman create a family. Everyone can have sex with everyone else of the other gender. Mathematically this type of marriage corresponds to a complete bipartite graph Kn,m. Actually, in this case I can imagine that a particular pair of people of different genders wouldn't like each other and might not consummate their marriage. So this graph is not necessarily complete.
How can same-sex marriages change the graph theory of marriages? As a graph, a monogamous same-sex marriage is the same bipartite K2 graph as a heterosexual marriage. It will just be less colorful, as both vertices will be of the same color.
But what happens if we add the same-sex idea to polygamous marriages?
Suppose a homosexual man wants to live with several spouses at the same time. What name can we give to a family unit of more than two homosexual men? Homopolygamy? Their marriage graph will be a star graph in which all the vertices are of the same color.
If a man can have several spouses, what about his spouses? Can they form multiple marriages too? If only one person is allowed to engage in several marriages, then we will see inequality within the same gender. If any spouse is allowed to form other marriages, then we will have a situation in which several men are all spouses to each other. So mathematically we will see complete graphs with more than two vertices to represent a marriage. If two people in a group do not like each other and do not want to be married, then the corresponding graph doesn't need to be complete.
By symmetry we can describe a marriage of several women, and mathematically it will be similar to a marriage of several men.
Another interesting aspect is the idea of mixed types of marriages involved in polygamy. Suppose a husband has several wives. Some of them might get bored waiting for his attention, and start spending so much time with each other that they end up developing feelings for each other. Suppose two wives of the same man decide to marry each other. What name would we give to this type of marriage? I am afraid that we do not have enough words to cover all the potential situations.
Suppose we have a heterosexual married couple and the man decides to bring another woman into their house. Thus the transition from a traditional marriage to a polygyny is created. If they got along so well that the first wife decides to marry the second wife, this would require a transition to a new type of marriage. Oh, I see that my essay just went in another direction — how different types of marriages might evolve into each other. For now, I'll leave this for future research.
Talking about different directions. I recently wrote a piece about condoms. Now I have a new generalization for the classic condom puzzle. Suppose we have a mixed-type marriage defined by a graph. Suppose tonight every couple of people corresponding to the edge of this graph wants to have sex with each other. What is the smallest number of condoms they can use? In my condom essay, I didn't define the condom usage for the sex of two women. I will leave it to your imagination and definition.
What follows is the story of a pair of integer sequences, which started life as a Google interview puzzle back in the previous century when VHS video tapes were in use:
Suppose you are buying VHS tapes and want to label them using the stickers that came in the package. You want to number the tapes consecutively starting from 1 and the stickers that come with each package are exactly one of each digit ["0"..."9"]. For your first tape you use only the digit "1", and save all the other digit stickers for later tapes. The next time you will need a digit "1" will be for tape number 10. By this time you will have several unused "1" stickers. What is the next tape number such that after labeling the tape with that number you will not have any "1" stickers remaining?
We can formalize this puzzle in the following way:
Consider a function f which, for a given whole number x, returns the number of times that the digit 1 is needed to write all of the numbers between one and x. For example, f(13) = 6. Notice that f(1) = 1. What is the next largest x such that f(x) = x?
Thus f(x) is the number of "1" stickers needed to label all the tapes up to tape x. When f(x) = x then we have used all of the "1" stickers in labeling the first x tapes.
Let's consider any non-zero digit. In the single and double-digit numbers, there are ten of each digit in the ones column, and ten of each digit in the tens column, so 20 altogether. Early on, the tape number is ahead of the digit count. By the time we get to 20-digit numbers, though, there should be, on average, two of any single non-zero digit per number. Thus, the number of times that any digit is used should eventually catch up with the tape numbers.
Encouraged by assurance of reaching our goal somewhere, we might continue our estimate. In the up-to three-digit numbers there are 300 of each non-zero digit; in the numbers below 10,000 there are 4000; then 50,000, and so on up to 1010, where f(x) and x must (almost) meet. In particular, there are 10,000,000,000 counts for any non-zero digit in the numbers below 10,000,000,000. Hence, were the puzzle asking about any of the digits 2–9, then ten billion could have been an easy answer or, at least a limit on how far we need to search.
Sadly, there is a 1 in the decimal representation of ten billion (and a few zeroes), so we require 1010+1 of the digit "1" to write the numbers [1…1010]. Thus, f(1010) ≠ 1010, so 1010 cannot be the answer to the original puzzle. Thus stymied, Gregory wrote a program to find the solution to the original Google's puzzle. And the answer turned out to be 199,981.
Gregory was overstymied, so he actually wrote a program to solve the puzzle for any non-zero digit. He calculated the beginning of the sequence a(n), where a(n) is the smallest number x > 1 such that the decimal representation of n appears as a substring of the decimal representations of the numbers [1…x] exactly x times.
We already know that a(1) is 199,981. The sequence continues as follows: 199,981, 28,263,827, 372,599,983, 499,999,984, 10,000,000,000, 10,000,000,000, 9,465,000,000, 9,465,000,000, 10,000,000,000, ….
Did you expect this sequence to be increasing? You could have, because smaller numbers tend to contain smaller digits than larger numbers. Then why is the sequence not increasing? As Gregory failed to find a value for the digit 5 below ten billion, he noticed that it's fairly easy to imagine a scenario where you have one less than the number you need, and then the next value has more than you need for equality, and then you equalize again later. In response, Alexey Radul, a friend of one author and a son of the other, suggested a related sequence:
Let a(n) be the smallest number x > 1 such that the decimal representation of n appears as a substring of the decimal representations of the numbers [1…x] more than x times.
The key difference being "more than" rather than "exactly". Starting at 1 then, here are the first nine terms of each sequence:
| n | = | > |
|---|---|---|
| 1 | 199,981 | 199,991 |
| 2 | 28,263,827 | 28,263,828 |
| 3 | 371,599,983 | 371,599,993 |
| 4 | 499,999,984 | 499,999,994 |
| 5 | 10,000,000,000 | 5,555,555,555 |
| 6 | 10,000,000,000 | 6,666,666,666 |
| 7 | 9,465,000,000 | 7,777,777,777 |
| 8 | 9,465,000,000 | 8,888,888,888 |
| 9 | 10,000,000,000 | 9,999,999,999 |
Some of these pairs are interesting in their own right. Notice that 199,991 is ten more than the previously found 199,981. For all the numbers in between, the initial equality holds. Likewise for n=3, each of the numbers between 371,599,983 and 371,599,993 has exactly one three. Hence, the increase in a number by one is the same as the increase in the count of threes. A similar situation holds for n=4.
Gregory has submitted these two new sequences to the Online Encyclopedia of Integer Sequences, as they turned out not to be there yet, and they can be found using the identifiers A163500 for the "=" sequence and A164321 for the ">" sequence. It's not surprising that the values matching this relaxed second condition are more well behaved than those with equality. Do you think the second sequence is always increasing? Wait a minute, let's check that sequence for zero.
In counting zeroes, it is important to remember that we start with one, not zero. In this case the smallest number x such that x is less than or equal to the number of 0s in the decimal representations of [1 … x] is 100,559,404,366. But what is the corresponding number for the "=" sequence? It appears that no such number exists. The challenge of accurately proving it, as they say, is left as an exercise to the reader.
There is no reason that we should be constrained to single digits. The formal statement of the problem provides an obvious generalization, where we consider substrings of each of the numbers [1 … x] rather than digits in those numbers. We should note that we count every occurrence of a substring separately. Thus 11 will be counted twice as a substring of 1113.
We can prove that the "more than" sequence is increasing after the first term. Indeed, for two integers i and j, if i is less than j, then for every occurrence of j, by replacing j with i we get a smaller number with an occurrence of i.
Inspired, Tanya wrote another fancier and faster program to find
values of this sequence for two-digit numbers. Here is the smallest
number x for which the number of "10"s as substrings of the
numbers [1…x] is more than or equal to x. And by a
lucky strike the equality holds. The number is:
109,
The value of a≥(11) might seem like a miracle:
119,
Sadly, a≥(12) is not so pretty:
1,296,624,070,230,872,
We cannot leave off without at least mentioning that the sequence function should next take one more parameter: the base of representation.
We have found only the first few members of these new sequences, and there are many related sequences to be catalogued. We would love to hear tales from your explorations. Enjoy the sequence hunt!
Peter Winkler gave a talk at MIT last fall and, as is customary, the audience was invited to join him for dinner afterwards at a local restaurant. I was eager to dine with Peter because
he is a puzzle collector
Peter is now a columnist at ACM communications. His column is called "Puzzled" and it is featured as part of the section titled "Last Byte." Writing these paragraphs has made me so hungry that I need to go grab something to bite.
Okay, I am back and here is the pizza puzzle.
Alice and Bob ordered a pizza. The pizza is cut into several radial pieces. Both Alice and Bob are greedy and well-mannered at the same time. They each want to get as much pizza as possible for themselves, but they don't want to be obvious about it. They take pieces in turn, starting with Alice. Because they are well-mannered and not obvious, when it is their turn, they only take a piece that is adjacent to the pieces already taken. Throughout the process of consuming this pizza, the untaken pieces are contiguous.
The question is: Is it possible to cut the pizza in such a way that although Alice starts, Bob can guarantee himself more than half?
If you want to think about this puzzle on your own, now would be a good time to pause. Why? Because in the next paragraph, I will give you some hints about how to approach this question.
If the number of pieces is even, then Alice can't lose. She can number the pieces around the circle consecutively, decide whether all the odd pieces or all the even pieces make up a bigger chunk, and then follow the parity.
But what happens if there are an odd number of pieces? Alice has an advantage, for she will get more pieces. But is that enough to guarantee that she will get at least half? Suppose she starts by taking a minuscule piece. Then Bob can number all of the leftover pieces in order and decide if he prefers the even-numbered group or the odd-numbered group. He is in control now, so he can guarantee himself the bigger part of the leftover pieces.
However, that might not be good enough for Bob to win. For example, if there is a very big piece, one that is bigger than half of the pizza, then in the first move Alice wins.
On the other hand, would Alice necessarily win by starting with the biggest piece?
Suppose the biggest piece is significantly less than half. Would Bob have a chance? To his advantage, he does have a lot of control. He can choose the parity of the pieces he wants at the beginning, and he can also switch this parity later, depending on what Alice does. Does he control the situation enough that it would be possible to cut the pizza in his favor?
I have to add that if you can find a solution with N pieces, then you can easily build a solution with N+2 pieces. Suppose you start with a pizza cut into N pieces, such that Bob will win. If you add two adjacent pieces of zero value to this pizza, you will get a pizza cut into N+2 pieces, such that Bob can still win. Indeed, Bob will follow the strategy he used with the N-pieces pizza, except that each time Alice takes one of the new pieces, Bob takes the other.
Can you find a way to cut a pizza so that Bob can guarantee himself more than half?
I wrote a story a while ago about how a clerk at my previous job mistyped my resignation date, substituting January 2007 for my real date, January 2008. As a result, my medical insurance provider decided that I wasn't covered in 2007, and requested that my doctor return the money he had already received.
After several phone calls my medical insurance was reinstated, but I kept receiving bills from my doctor. When I called my insurance, they assured me that everything was fine and that they had paid my doctor. However, my doctor continued to send me bills.
After half a year of phone calls back and forth, someone finally explained to me what was going on. My insurance company had initially requested the money back. The money was never returned to them, because my doctor's office would not pay them a penny until I had paid the doctor first. In my doctor's database, my visits were marked as unpaid.
When the problem was cleared up, the insurance company stopped requesting that the doctor pay them back. But the computer at my doctor's office didn't understand that stop-the-request command. It didn't know what stopping the request meant.
The computers were talking different languages and I was caught in the middle.
My son, Alexey Radul, made his PhD thesis available to the public.
I was amazed at how much he had invested in the thesis. I assumed that the main goal for a dissertation in computer science is to write a ground-breaking code and that the accompanying text is just a formality. However, this is not the case with my son's thesis. I am not fully qualified to appreciate the "ground-breakness" of his code, but his thesis text is just wonderful.
Alexey decided that he wanted to make his thesis accessible to a wide audience. He had to make a lot of choices and decisions while he was designing and coding his prototype, and in his thesis he devoted a lot of effort to explaining this process. He also tried to entertain: I certainly had fun trying to solve an evil sudoku puzzle on page 87, that turned out not to have a unique solution.
In addition to everything else, Alexey is an amazing writer.
I am a proud mother and as such I am biased. So I'll let his thesis speak for itself. Below is the table of contents accompanied by some quotes:
"Revolution is at hand. The revolution everyone talks about is, of course, the parallel hardware revolution; less noticed but maybe more important, a paradigm shift is also brewing in the structure of programming languages. Perhaps spurred by changes in hardware architecture, we are reaching away from the old, strictly time-bound expression-evaluation paradigm that has carried us so far, and looking for new means of expressiveness not constrained by over-rigid notions of computational time."
"Fortunately, there is a common theme in all these efforts to escape temporal tyranny. The commonality is to organize computation as a network of interconnected machines of some kind, each of which is free to run when it pleases, propagating information around the network as proves possible. The consequence of this freedom is that the structure of the aggregate does not impose an order of time. Instead the implementation, be it a constraint solver, or a logic programming system, or a functional reactive system, or what have you is free to attend to each conceptual machine as it pleases, and allow the order of operations to be determined by the needs of the solution of the problem at hand, rather then the structure of the problem's description."
"Every human harbors mutually inconsistent beliefs: an intelligent person may be committed to the scientific method, and yet have a strong attachment to some superstitious or ritual practices. A person may have a strong belief in the sanctity of all human life, yet also believe that capital punishment is sometimes justified. If we were really logicians this kind of inconsistency would be fatal, because were we to simultaneously believe both propositions P and NOT P then we would have to believe all propositions! Somehow we manage to keep inconsistent beliefs from inhibiting all useful thought. Our personal belief systems appear to be locally consistent, in that there are no contradictions apparent. If we observe inconsistencies we do not crash—we chuckle!"
"This is power. By generalizing propagation to deal with arbitrary partial information structures, we are able to use it with structures that encode the state of the search as well as the usual domain information. We are consequently able to invert the flow of control between search and propagation: instead of the search being on top and calling the propagation when it needs it, the propagation is on top, and bits of search happen as contradictions are discovered. Even better, the structures that track the search are independent modules that just compose with the structures that track the domain information."
"A shift such as from evaluation to propagation is transformative. You have followed me, gentle reader, through 137 pages of discussions, examples, implementations, technicalities, consequences and open problems attendant upon that transformation; sit back now and reflect with me, amid figurative pipe smoke, upon the deepest problems of computation, and the new way they can be seen after one's eyes have been transformed."
"The "concurrency problem" is a bogeyman of the field of computer science that has reached the point of being used to frighten children. The problem is usually stated equivalently to "How do we make computer languages that effectively describe concurrent systems?", where "effectively" is taken to mean "without tripping over our own coattails". This problem statement contains a hidden assumption. Indeed, the concurrency itself is not difficult in the least—the problem comes from trying to maintain the illusion that the events of a concurrent system occur in a particular chronological order."
"Time is nature's way of keeping everything from happening at once; space is nature's way of keeping everything from happening in the same place ( with apologies to Woody Allen, Albert Einstein, and John Archibald Wheeler, to whom variations of this quote are variously attributed)."
"I'm meticulous. I like to dot every i and cross every t. The main text had glossed over a number of details in the interest of space and clarity, so those dots and cross-bars are collected here."
You have been warned. You are allowed to read this if you are 17 or over. Otherwise, you can ask your parents to read this to you. Here is a famous old condom puzzle in the version I heard when I was a teenager myself:
A man hires three prostitutes and wants to have sex with all three of them. They all might have different sexually transmitted diseases and they all want to use condoms. Unluckily, they have only two condoms. Plus, they are in the forest and can't buy new condoms. Can the man have sex with all three of the women without danger to any of the four?
Everyone in this problem is so health-conscious, that it might not be such a dirty problem after all. I leave you with the fun challenge of figuring this problem out.
Another fun variation of this problem is when you have two men and two women and two condoms. Every woman wants to have sex with every man. How can they do that?
If you are a teacher and want to use these great puzzles for younger students, you can follow the example of MathWorld and pretend that it's a glove problem between doctors and patients.
Recently my younger son and his MIT friends invented another variation of this problem:
Suppose three gay men all want to have sex with each other and every pair among them wants to do two penetrative sexual acts, switching roles. They want to avoid contaminating each other, and in addition, each man also does not want to cross-contaminate himself from either region to the other. How can they do that using exactly three condoms?
Let me remind you that they plan to perform six sexual acts altogether, meaning that six condoms would be enough. On the other hand, each of them needs two condom surfaces, so they can't do it with less than three condoms. My son showed to me his solution, but I will postpone its publication.
Of course, you can say that this is a glove problem about three surgeons operating on each other.
In addition, you can generalize it to any number of gay men. Here is my solution for four men and four condoms, where letters denote people, numbers denote condoms, and the order of people represents roles: A12D, B32D, C2D, A14C, B34C, D4C, A1B, B3A, C21B, D41B, C23A, D43A.
Can you solve the problem for five or more people?
I used to receive emails requesting link exchanges with other websites. They promised to increase my page rank by creating additional hyperlinks to my pages. I ignored them. If they thought my website was good, why did they need my reciprocity to link to me? Besides, their websites didn't have anything to do with mathematics; they were the sites of dental services or Honda dealers.
I have resisted the temptation so far. The links that I have on my websites are to sites that I recommend. Sometimes I wonder through other people blogrolls and add good links to my blog.
At other times a blog roll exchange happens: I have Google Analytics installed on my sites. From time to time I examine my traffic. When I see a new traffic flow from a particular website, I check that site out. If I like it, I add it to my blogroll.
I wouldn't mind people writing to inform me that they have a link to my website and asking me if I'd like to reciprocate. But this doesn't happen. Instead, strangers write to me offering to put up a link to my website on the condition that I put a link to them. I do not like this imposition.
Recently I received a request for a blog review exchange. I went to that blog and found that all of its postings were reviews of other people's blogs, presumably those who had agreed on this kind of exchange. I checked out several of those other blogs and I didn't find any of them very interesting.
I missed this opportunity to receive that blog review, but on the other hand, if I start linking to random crap, I might lose the respect of my readers.
My previous paragraph reminded me of a Russian joke:
I wonder how a person whose website comes up first in a Google search for "random crap" feels.
Russians assume that such a person will be embarrassed. They do not understand Americans who welcome negative publicity, and purposefully would name their website randomcraponline.com.
I enjoyed a recent discussion on the sequences fans mailing list. David Wilson suggested an idea for hiding email addresses on webpages from bots: change your email slightly and explain how to change it back.
For example, if you want to contact me, you should reverse my login name in the following email address:
hkaynat@yahoo.com
Or, remove all the digits from the following email address:
1ta2nya3kh4@yahoo.com
Here is a palindrome problem by Nazar Agakhanov from the All-Russian Mathematical Olympiad, 1996:
Can the number obtained by writing the numbers from 1 to n, one after another, be a palindrome?
Of course, we should assume that n > 1.
When I give this problem to my friends, they immediately answer, "No, of course not." The reasoning is simple. The last 9 digits of this palindrome should be 987654321 — all different digits. The earliest you can get these digits at the end of your string 1 to n, is when your number n is actually 987654321. By that time your string of digits is really huge. If we take a random number with 2k digits, then the probability of it being a palindrome is 10(-k). There is no reason to think that writing consecutive integers increases the probability of finding a palindrome. So the probability of hitting a palindrome is so low, that you can safely answer, "No, of course not."
After confidently saying "no", my friends usually stop thinking about the problem altogether. Only my friend David Bernstein suggested a simple solution for this problem. You can try to find the proof, but I do not insist that you do. I am about to give you many other fun problems to solve, and you can choose which ones you want to think about.
Naturally, we can replace the sequence of natural numbers in the Agakhanov's problem with any sequence. So, one problem becomes 160,000 different problems when you plug all current sequences from the Online Encyclopedia of Integer Sequences into it.
For some periodic sequences every concatenation you create is a palindrome. For example, for the sequence of all zeroes, every set of the first n terms is a palindrome. More interestingly, you can think of an increasing sequence such that any first n terms comprise a palindrome, as we see in the sequence of repunits: 1, 11, 111, 1111, etc. Can you think of other sequences like this?
For some sequences, not every concatenation you create is a palindrome, but you can obtain an infinite number of palindromes. One example, suggested by Sergei Bernstein, is the sequence a(n) of the last digit of the greatest power of 2 that divides n. Can you think of other sequences like that?
For some sequences only the initial term itself is a palindrome. Beyond that you can't obtain a palindrome by concatenating the first n terms. For a few of those sequences, this fact is easy to prove. Take, for example, the sequence of powers of ten, or the sequence of squares, or the sequence of prime numbers. Can you think of other similar sequences?
There are many sequences that do not produce a palindrome beyond the first term, even if you try many times. I suspect that they do not, in fact, ever produce a palindrome, but I have no clue how to prove that. I have in mind the sequence of the digits of π. Can you suggest other sequences like that?
Instead of solving the initial problem, I gave you a variety of other problems. My last challenge for you is to find other sequences that can replace the sequence of natural numbers in the Agakhanov's problem so that the problem becomes solvable and the solution is interesting.
The PhD program in Russia was limited to exactly three years. My son Alexey was born right after I started it, and I was distracted from my research for quite some time. At that time, my mom, who lived with us, reached her retirement age of 55. Her retirement would have been supported by the government and her pension would have been almost equal to her salary. So I begged my mom to retire and help me with my son Alexey. I couldn't understand why she wouldn't stop working, so I kept pressing.
At the same time, I was frantically trying to find a place for Alexey in a day care center. I finally was successful, but it backfired. Alexey started getting sick all the time. Daycare was overcrowded, with 30 kids to every adult. Workers didn't have time to attend to every kid. Day care workers were so tired that they were relieved when a few kids stayed home sick.
After Alexey was hospitalized for two weeks with severe dysentery, my mother gave up and retired. It was one year before the end of my graduate school. In that year I wrote four papers and my thesis, and I got my PhD.
Now that I am fifty, I understand that my mother really did love her job. Being older and wiser, I recognize what a sacrifice my mother made in retiring in order to look after a grandchild.
Mom, sorry for being so pushy back then and thank you so much for all that you did for us.
This puzzle was brought to me by Leonid Grinberg.
A frog needs to jump across the street. The time is discrete, and at each successive moment the frog considers whether to jump or not. Unfortunately, the frog has crappy eyesight. He knows there are dangerous cars out there, but he can't see them. If a car appears at the same moment that he decides to jump, he will die.
The adversary sends cars, hoping to kill the frog. The adversary knows the frog's algorithm, but can use only a finite number of cars. The frog wants to maximize his chances of survival with his algorithm. The frog is allowed to use a random number generator that the adversary can't predict. Can you suggest an algorithm for the frog to cross the street and survive with a probability of at least 1 − ε?
My guest blogger is Levy Ulanovsky, a maven of physics puzzles. Here is one of his favorite puzzles:
There are n points in 3-dimensional space. Every point is connected to every other point by a wire of resistance R. What is the resistance between any two of these points?
In 2007 Alexander Shapovalov suggested a very interesting coin problem. Here is the kindergarten version:
You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.
You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?
To solve this problem, divide the coins into two piles of 50 so that each pile contains exactly one fake coin. Put the piles in the different cups of the scale. The scale will balance, which means that you can't have the total of exactly one fake coin. Moreover, this proves that each group contains exactly one fake coin. But for any particular coin, the judge won't have a clue whether it is real or fake.
The puzzle is solved, and though you do not reveal any information about a particular coin, you still give out some information. I would like to introduce the notion of a revealing coefficient. The revealing coefficient is a portion of information you reveal, in addition to proving that there are exactly two fake coins. Before you weighed them all, any two coins out of 100 could have been the two fakes, so the number of equally probable possibilities was 100 choose 2, which is 5050. After you've weighed them, it became clear that there was one fake in each pile, so the number of possibilities was reduced to 2500. The revealing coefficient shows the portion by which your possibilities have been reduced. In our case, it is (5050 − 2500)/5050, slightly more than one half.
Now that I've explained the kindergarten version, it's time for you to try the elementary version. This problem is the same as above, except that this time you have 99 coins, instead of 100.
Hopefully you've finished that warm-up problem and we can move on to the original Shapovalov's problem, which was designed for high schoolers.
A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.
You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?
If you are lazy and do not want to solve this problem, but not too lazy to learn Russian, you can find several solutions to this problem in Russian in an essay by Konstantin Knop.
Your challenge is to solve the original Shapovalov puzzle, and for each solution to calculate the revealing coefficient. The best solution will be the one with the smallest revealing coefficient.
My guest blogger is David Wilson, a fellow fan of sequences. It is a nice exercise to understand how this graph works. When you do, you will discover that you can use this graph to calculate the remainders of numbers modulo 7. Back to David Wilson:
I have attached a picture of a graph.
Write down a number n. Start at the small white node at the bottom of the graph. For each digit d in n, follow d black arrows in a succession, and as you move from one digit to the next, follow 1 white arrow.
For example, if n = 325, follow 3 black arrows, then 1 white arrow, then 2 black arrows, then 1 white arrow, and finally 5 black arrows.
If you end up back at the white node, n is divisible by 7.
Nothing earth-shattering, but I was pleased that the graph was planar.
My son Alexey Radul defended his PhD thesis on Propagation Networks on August 4. Here is the abstract.
I propose a shift in the foundations of computation. Modern programming systems are not expressive enough. The traditional image of a single computer that has global effects on a large memory is too restrictive. The propagation paradigm replaces this with computing by networks of local, independent, stateless machines interconnected with stateful storage cells. It offers great flexibility and expressive power, and has therefore been much studied, but has not yet been tamed for general-purpose computation. The novel insight that should finally permit computing with general-purpose propagation is that a cell should not be seen as storing a value, but as accumulating information about a value.
Various forms of the general idea of propagation have been used with great success for various special purposes; perhaps the most immediate example is constraint propagation in constraint satisfaction systems. This success is evidence both that traditional linear computation is not expressive enough, and that propagation is more expressive. These special-purpose systems, however, are all complex and all different, and neither compose well, nor interoperate well, nor generalize well. A foundational layer is missing.
I present the design of a general-purpose propagation system. I illustrate on several examples how the resulting prototype supports arbitrary computation; recovers the expressivity benefits that have been derived from special-purpose propagation systems in a single general-purpose framework, allowing them to compose and interoperate; and offers further expressive power beyond what we have known in the past.
Warning: this essay contains solutions to math problems.
Here is a famous hat puzzle:
A king decides to give 100 of his wise men a test. If together they pass, they can go free. Otherwise, the king will execute all of them. The test goes as follows: the wise men stand in a line one after another, all facing in the same direction. The king puts either a black or a white hat on each wise man. The wise men can only see the colors of the hats in front of them. In any order they want, each one guesses the color of the hat on his own head. Other than that, the wise men cannot speak. To pass, no more than one of them may guess incorrectly. Given that they have time to agree on a strategy beforehand, how can they assure that they will survive?
Instead of discussing the puzzle above, I'd like to look at a different version. It is an infinite variation of the puzzle that my son Sergei brought back from the Canada/USA Mathcamp last year.
The king has a countable number of wise men. The line starts from the left and is infinite in the right direction. The wise men are all facing to the right and they see the infinite tail of the line. Again, the king places either a black or white hat on each head and they can only say one of two words: black or white. Will they be able to devise a strategy beforehand that ensures that not more than one person makes a mistake?
Oh, I forgot to mention: you are allowed to use the axiom of choice.
Here is the solution. You can build an equivalence relation on the possible placements of hats. To be equivalent, two ways of placing the hats should have the same tail. In other words, there is a person such that both hat arrangements to his right are the same. By the axiom of choice you can pick a representative in any equivalence class. The first wise man looks at all the other hats and calculates in how many places the tail differs from the representative of the class they picked. This is a finite number, and by stating one color or the other, he signals the parity of that number. After that, all the wise men say their colors from left to right. Everyone sees the tail and everyone hears the color choices of the people behind. So every wise man can reconstruct the color of his hat with this information. Only the first person may potentially be mistaken.
Many things about this solution bother me. Where is this country that can fit an infinite number of people? What kind of humans can see into infinity? How much time will this procedure take?
Aside from the practical matters, there are mathematical matters that bother me, too. By the axiom of choice you can pick an element in every class. The problem is that all of the wise men have to pick the same element. The axiom of choice claims the existence of a choice function, which picks an element in each set. So the function exists, but can we distribute this function to many wise men? Remember, they need to agree on this function the night before.
We already implicitly assumed that our wise men have a lot of magical abilities. So we can add to those the ability to go through all the possible tails and memorize the representatives for all the tails in one evening.
But still, I am very curious to know what follows from the axiom of choice. Tell me what you think: does the axiom of choice imply that we can distribute the choice function, or do we need a new axiom? In your opinion, will these wise men live?
I do not know why I like the television show America's Got Talent. Sometimes I picture myself on a stage doing what I love to do the most: entertaining people with mathematics. But it wouldn't really work on the stage of America's Got Talent. The audience makes its judgment in the first five seconds of a performance. There is no way I can teach a new math idea in five seconds.
Back to the show. I especially like the auditions. I noticed a strange correlation between what people say before their performance and what happens on the stage. In short, if a person brags that he/she has the greatest talent and that the judges will be blown away, the performance is likely to be pathetic.
My first thought was that the producers were editing it this way in order to boost the drama of the show. Now I wonder if it could be something else. Perhaps people who do not have much talent need to build up their confidence to appear on the show. And, vice versa, people who have talent can afford to be modest.
I didn't see the same correlation when I watched Britain's Got Talent. Could this tendency be a part of our American culture? After all, the message that confidence is all we need to succeed permeates the whole culture.
A pre-stage interview with one of the contestants on the show was especially telling. She said, "I could be the next greatest act in America, because I have the courage, the self-esteem, the confidence, the faith and hope and belief in myself." Talent wasn't mentioned at all.
Yesterday I had a nightmare. I was on the stage of America's Got Talent and Piers Morgan, my favorite judge, was questioning me:
Piers: Do you have a talent people will pay for?
Me: Yes, I do.
Piers: What is it?
Me: I sing so badly people will pay me to stop.
Do you know that numbers have destinies? Well, to have a destiny, a number needs to have a life, or in mathematical terms, destinies are defined with respect to an operation or a function.
I know the term "destiny" from John Conway, the creator of the Game of Life. It would be harmonious to assume that he suggested this term.
Case 1. SOD. Suppose our function is the sum of digits of a number, denoted as SOD. Then the trajectory of a number k is the sequence a(n), such that a(0) = k and a(n+1) = SOD(a(n)).
Two numbers have the same destiny with respect to SOD if the tails of their trajectories coincide. Suppose a(n) and b(n) are two trajectories. Then the numbers a(0) and b(0) on which these trajectories are build have the same destiny if there exist N and M, such that for any j, a(N+j) = b(M+j). In particular, all numbers in the same trajectory a(n) have the same destiny.
In the above example of SOD, any trajectory of a positive integer ends with a one-digit non-zero number repeating many times. It follows that all the natural numbers have 9 different destinies with respect to SOD, which only depend on the remainder of the number modulo 9.
Given an operation, we can build another sequence that is called "the first occurrence of a new destiny". This is the sequence of numbers c(n) such that c(n) is the smallest number with its destiny. For the SOD operation, the sequence of the first occurrences of new destinies is finite and is equal to: 1, 2, 3, 4, 5, 6, 7, 8, 9.
Case 2. The next prime. Let us consider a different example. Let the function f(n) be the next prime after n. Then wherever we start, the tail of the trajectory with respect to the function f(n) is a sequence of consecutive prime numbers. Therefore, with respect to this function all integers have the same destiny.
Case 3. Reverse. Suppose f(n) is a reverse of n. If a number is a palindrome, then its trajectory is a one-cycle consisting of that number. If a number is not a palindrome, then its trajectory is a two-cycle consisting of a number and its reverse. The first appearance of a new destiny is sequence A131058 — a list of numbers n whose reverse is not less than n. In this case, instead of studying destinies, it might be more interesting to study types of destinies. For this operation we have two types: one-cycles for palindromic integers and two-cycles for non-palindromic integers.
Case 4. The sum of proper divisors. For the next example, let f(n) denote the sum of proper divisors. Let's look at the trajectory of 15: it is 15, 9, 4, 3, 1, 0. The sum of proper divisors of zero is not-defined or is equal to infinity, whichever you prefer. So, let us say the trajectory of 15 is finite, and ends with 1, 0. This situation makes the definition of destinies more complicated, but it is appropriate to say that finite sequences have the same destinies if they end with the same number. For our example of sums of proper divisors all finite sequences end with 0. Thus all the numbers whose trajectories are finite have the same destinies. The sequence of new destinies starts 1, 6, 28, 220, …; and we do not know what the next number is because for 276 we do not know the behavior of its trajectory. Even when we know what kind of life the number is living the destinies are not always clear.
Case 5. TITO. The next interesting example is the TITO operation. TITO is an abbreviation of "Turning Inside, Turning Outside". By definition, to calculate TITO(n) you need to reverse the prime factors of n, multiply them back together (with multiplicities) and reverse the result. For example, to calculate TITO(68), we first find prime factors of 68, which are 2, 2 and 17. We reverse them and multiply: 2*2*71 = 284. Then we reverse the result: TITO(68) = 482.
It is easy to see that prime numbers are among the fixed points of the TITO operation. That means all prime numbers have different destinies of the same type: they end with a one-cycle. There are numbers other than prime that have one-cycle destinies. For example, a palindrome that is a product of palindromic primes is a fixed point of the TITO operation. There are other cases too: for example 26 is a fixed point, but is neither prime nor palindromic. There are numbers that have one-cycle destinies, but are not the fixed points of TITO operation themselves. For example, the trajectory of 49 starts with the following sequence: 49, 94, 841, 4648, 8212, 80041, 415003, 282145, 54796, 849667, 3652951, 35429422, 2941879, 27075955, 5275759, 5275759, 5275759. ….
There are numbers that generate two-cycles. For example, 12 and 156. For numbers n that have only palindromic factors, TITO(n) is equal to the reverse of n. If n is not a palindrome and the reverse of n has only palindromic factors, then the trajectory of n is a two-cycle. Not all two-cycles are like that. Take for example 291 which is a product of primes 3 and 97. Thus, TITO(291) is the reverse of 3*79, which is equal to 732. On the other hand, 732 = 2*2*3*61. Hence, TITO(732) = reverse(2*2*3*16) = 291.
There are longer cycles too. Take for example 15, which generates a cycle of length 7: 15, 51, 312, 447, 3282, 744, 213, 15, …. Also, for some numbers we do not know if there is a cycle. The smallest number for which I myself do not know whether the trajectory tends to infinity or collapses into a cycle is 78.
For the TITO operation we might be more interested in types of destinies. Personally, I am interested not only in the types of destinies, but also in sets of numbers that have the same destinies for the same reasons. For example, I am interested in dividing numbers of one-cycle TITO destinies into three groups: primes, palindromes with palindromic primes and other cases.
Case 6. RATS. I kept the RATS operation for dessert as, in my opinion, it is the most interesting operation with respect to destinies. RATS is the abbreviation of Reverse Add Then Sort. For example, to calculate RATS(732) we need to reverse 732 getting 237, then add 732 and 237 together getting 969, then sort the digits. Thus, RATS(732) = 699.
Let's look at the RATS sequence starting with one: 1, 2, 4, 8, 16, 77, 145, 668, 1345, 6677, 13444, 55778, 133345, 666677, 1333444, 5567777, 12333445, 66666677, 133333444, 556667777, 1233334444, 5566667777, 12333334444, 55666667777, 123333334444, 556666667777, …. We can prove that this sequence is infinite, because numbers fall into a repetitive pattern with an increasing number of digits. This is the first such example in this discussion. John Conway calls the destiny of 1 "the creeper". Conway conjectured that RATS destinies are either the creeper or a cycle.
New destinies do not appear too often in this sequence. That is why the sequence of new destinies might be of interest: 1, 3, 9, 29, 69, 2079, 3999, 6999, 10677, 20169, …. This sequence is A161590 in the Online Encyclopedia of Integer Sequences and it needs more terms. The length of the corresponding periods starting from the second term are: 8, 2, 18, 2, 2, 2, 14, which is the sequence A161593.
Destinies are kinda fun.
Decades ago there was a study in Russia that claimed that a woman worked four more hours a day than a man on average. Men and women were equal in Russia and all had the same 40-hours-a-week jobs. Women were not, by and large, housewives, for they worked full-time.
So where did the additional four hours come from? They were devoted to house chores. In Russia, women did everything at home — at a time when life in Russia was much more difficult. For example, my family didn't have a washer, or a dryer or a dish-washing machine. Plus, everything was in deficit, so to buy milk or a sweater, women had to stand in lines, sometimes for hours.
My mother was very bitter because her husband, my father, never helped her. So I always hoped that when I got married, my husband would take on some of the house chores.
When I married Andrey, he was somewhat helpful — better than the average Russian husband. Then, when I was at grad school, we had a baby named Alexey. Andrey convinced me that I had to take over all the child care because only women could get academic maternity leave. It seemed logical and I agreed.
In a year, when the leave was over, I felt that Andrey should take over some of these duties. He refused. He insisted that since I already had published a paper when I was an undergrad, and since he still didn't have his research results for his PhD, that he had to stay focused on his work. I wasn't strong enough to resist.
We signed up for government child care — private care didn't exist — but we were on the waiting list for a couple of years. Almost no one in Russia — certainly not graduate students — could afford a private babysitter. I couldn't really work on my PhD research because between caring for the house and the baby, I never had big chunks of time. The best I could do was to start preparing for my qualifying exams.
Allow me to digress from my main story for a moment to mention my gray notebook. This notebook was our baby diary. Initially I recorded important baby data — like the first time Alexey smiled. But later, as soon as Alexey turned one year old, he became very eloquent; and this notebook became my son's quote book.
One day Andrey and I went out and my mom babysat Alexey, who was two years old. When we returned, my mother recited the following quote from Alexey:
When will Daddy be back from the university and Mommy from the store?
I don't really remember the long hours in stores or the cooking and cleaning. I remember the quote.
My son Alexey taught me to play "The Settlers of Catan
Lesson 1. Trading is beneficial for both traders.
When you agree to exchange your two rocks for one grain, one grain is more valuable to you than two rocks. The opposite is true for your trading partner.
Presumably, the same principle works for the economy. If I buy a sweater at T.J.Maxx for $20, I need the sweater more than $20. And if the store sells this sweater for $20, they are hoping to make some profit, that is, that the sweater cost them less than $20. Supposedly, shopping transactions are profitable for both parties.
Lesson 2. Trading is bad for non-trading players.
This is the consequence of the fact that in "Settlers of Catan" there is only one winner. If something is good for someone, it is bad for everyone else. In real life you do not have to lose if someone wins. With each shopping transaction everyone gains. This is the reason why shopping must be good for the economy.
Lesson 3. Powerful players can persuade other players to trade against their best interests.
Shortly after I moved to the US, I became very aware of my own smell. My smell didn't change with my move from Russia, nor did my sense of smell change. I was just bombarded with deodorant advertisements, and due to the vulnerability of my self-perception, in one year I bought more deodorants than in all my previous 30 years. I have a friend who has an exceptional sense of smell. He told me that people often use much more deodorant and perfume than they need.
Lesson 4. You pay a lot for storage.
In Settlers, if you have more than seven cards and the dice rolls seven, you need to discard half of your hand. So if you have six cards and someone offers you three grains for one sheep, consider the storage price before jumping into this bargain deal.
Once I bought so much discounted toilet paper that it lasted me for months and months. When it was time to move to a different apartment, I had to pay for the largest truck available to fit all my junk.
Lesson 5. It is important to understand the goal of the person you are trading with.
A profitable deal becomes a big mistake when, as a result of the trade, your trading partner builds a settlement right in the spot where you were planning to build.
Similarly, if your doctor prescribes you a medication, it would behoove you to know whether he will reap any profit from it himself.
Lesson 6. If a player is the only receiver of rock in the game he dictates the price.
This is like a monopoly. I needed my last laptop more than the $1,000 I paid for it. But this price included pre-installed Windows, which I didn't want and which I immediately deleted. I was forced to pay extra for Windows because of Microsoft's monopoly.
So, is shopping good for the economy?
What about that skirt I bought and never used and eventually threw away? I wasted $20 on it. But the store didn't gain that $20; they only gained their profit margin, which could have been $5. That means that together we wasted $15.
I do not throw away every piece of clothing I buy, but it is true that we buy more things than we need.
I think that going shopping to help our country get out of an economic crisis is a ridiculous idea. If you are shopping for other reasons than necessity, you do not help anyone and as a group we lose.
My son Alexey wins almost every game of "Settlers of Catan" he plays. So does my friend Mark Shiffer. The main reason is that they both know how to use trading effectively. To me that indicates that there are probably other people out there who know how to effectively sell deodorants, pills, clothing and other junk to us. I suspect that I lose in every shopping transaction, as I am an unskilled trader. If most folks are like me, could it be that shopping is actually bad for the economy?
Many years ago I conducted an experiment. I asked several sets of friends who had written joint math papers what they thought their individual contributions were. I asked them separately, of course. As the result of this experiment I formulated the conjecture:
The total of what joint authors estimate their contributions to be is always more than 100%.
Here is an actual example of answers I received from the two authors of a joint paper.
Author 1: My contribution is 80%. I suggested a breakthrough idea that made this paper possible. He just typed everything.
Author 2: My contribution is 80%. I did all the work. She just suggested a good idea.
You can see how the answers are synchronized. It is clear that both are telling the truth. People just tend to over-value their own input.
In other cases each author thinks that she or he generated the main idea. It doesn't mean that one of them is lying. Very often they are absolutely sincere. Take this example of Alice and Bob, who are working on a paper together. Alice suggests that they might have better progress on their theorem if they consider graphs with symmetries first. Bob is engrossed in his thoughts and doesn't register Alice's suggestion. Next day, he comes up with an idea to add a group action on graphs. He sincerely believes that this was his own idea. It would be hard to know whether this had been provoked by Alice's suggestion, or had come to Bob independently. Alice assumes that they are working on her idea.
When you acknowledge other people's contribution, keep in mind that their perception might be different from yours. If you do not want to hurt other people's feelings, you might consider inflating your gratitude.
The conjecture doesn't apply to single-author papers. First of all, mathematicians never claim their contribution is 110% as non-mathematicians do. In many cases, especially when there are acknowledgements in the paper, it would be illogical to claim 100% contribution. Most mathematicians are logical, so if they are gracious enough to acknowledge the help of others, they are unlikely to claim 100%.
I would be curious to continue the experiment and either prove or disprove my conjecture. I'd appreciate your help. If you want to be part of this experiment, you can provide the following numbers in your comments: your average contribution to your own papers; and also your weighted average contribution to your joint papers.
I always thought that the famous equation
102 + 112 + 122 = 132 + 142
is sort of a miracle, a random fluke. I enjoyed this cute equation, but never really thought about it seriously. Recently, when my son Sergei came home from MOP, he told me that this equation is not a fluke; and I started thinking.
Suppose we want to find five consecutive integers such that the sum of the squares of the first three is equal to the sum of the squares of the last two. Let us denote the middle number by n, which gives us the equation:
(n–2)2 + (n–1)2 + n2 = (n+1)2 + (n+2)2.
After simplification we get a quadratic equation: n2 – 12n = 0, which has two roots, 0 and 12. Plugging n = 0 into the equation above gives us (–2)2 + (–1)2 + 02 = 12 + 22, which doesn't look like a miracle at all, but rather like a trivial identity. If we replace n with 12, we get the original miracle equation.
If you looked at how the simplifications were done, you might realize that this would work not only with five integers, but with any odd number of consecutive integers. Suppose we want to find 2k+1 consecutive integers, such that the sum of the squares of the first k+1 is equal to the sum of the squares of the last k. Let us denote the middle number by n. Then finding those integers is equivalent to solving the equation: n2 = 2k(k+1)n. This provides us with two solutions: the trivial solution 0, and the non-trivial solution n = 2k(k+1).
So our miracle equation becomes a part of the series. The preceding equation is the well-known Pythagorean triple: 32 + 42 = 52. The next equation is 212 + 222 + 232 +242 = 252 + 262 + 272. The middle numbers in the series are triangular numbers multiplied by four.
Actually, do you know that 102 + 112 + 122 = 132 + 142 = 365, the number of days in a year? Perhaps there are miracles or random flukes after all.
My son, Sergei Bernstein, got accepted to MIT through early action. Because the financial costs of studying at MIT worried me, I insisted that Sergei also apply to Princeton and Harvard, as I had heard they give generous financial packages. In the end, Sergei was rejected by Princeton and wait-listed and finally rejected by Harvard. Though many people have been rejected by Princeton and Harvard, not too many of them have won places on US teams for two different international competitions — one in mathematics and the other in linguistics. To be fair, Sergei was accepted by these teams after Princeton had already rejected him. Nonetheless, Sergei has an impressive mathematical resume:
I am trying to analyze why he was rejected and here are my thoughts.
Many people told me of surprising decisions by Ivy League schools this year. The surprises were in both directions: students admitted to Ivy League colleges who didn't feel they had much of a chance and students not admitted that had every right to expect a positive outcome. I should mention that I personally know some very deserving kids who were admitted.
I wonder if there has been a change in the financial demographics of the students Harvard and Princeton have accepted this year. If so, this will be reflected in the data very soon. We will be able to see if the average SAT scores of students go down relative to the population and previous years.
I do not know why Sergei wasn't accepted; perhaps I'm missing something significant. But if it was because of our finances, it would be ironic: Sergei wasn't admitted to Princeton and Harvard for the same reason he applied there.
I recently got a new job — to coordinate math students at RSI (Research Science Institute). RSI provides a one-month research experience based at MIT for high school juniors. The program is highly competitive and kids from all over the world apply for it.
Before the program started, I asked around among mathematicians for advice on how to do a great job with these talented kids. I was surprised by the conflicting opinions on the value of the program. I thought you'd be interested in hearing those opinions, although I confess that I do not remember who said what, or anyone's exact words. I will just repeat the gist of it.
Former participants:
Potential participants:
Grad students, former and potential mentors:
Professors on the program in general:
I asked some math professors to suggest problems for these students:
The 2009 RSI has just begun. We have awesome students, great mentors and quite interesting problems to solve. I am positive we'll prove the negativists wrong.
Let me remind you of a very interesting problem from my posting Oleg Kryzhanovsky's Problems.
You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?
I do not want you to find the weight of each coin; I just want you to say yes if the labels are correct, or no if they are not.
I have given this problem to a lot of people, and not one of them solved it. Some of my students mistakenly thought that they succeeded. For example, they would start by putting the coins labeled 1 and 2 on the left cup of the scale and 3 on the right cup. If these coins balanced, the students assumed that the coins on the left weighed 1 and 2 grams and that the coin on the right weighed 3 grams. But they'd get the same result if they had 1 and 4 on the left, for example, and 5 on the right. I am surprised that no one has solved it yet, as I thought that this problem could be offered to middle-schoolers, since it does not actually require advanced mathematical skills.
If you want to try to solve this problem, pause here, as later in this essay I will be providing a number of hints on how to do it. The problem is fun to solve, so continue reading only if you are sure you're ready to miss out on the pleasure of solving it.
I propose the following sequence a(n). Suppose we have a set of n coins of different weights weighing exactly an integer number of grams from 1 to n. The coins are labeled from 1 to n. The sequence a(n) is the minimum number of weighings we need on a balance scale to confirm that the labels are correct. The original Oleg Kryzhanovsky's problem asks to prove that a(6) = 2. It is easy to see that a(1) = 0, a(2) = 1, a(3) = 2. You will enjoy proving that a(4) = 2 and a(5) = 2.
In general, we can prove that a(n) ≤ n-1. For any k < n, the k-th weighing compares coins labeled k and k+1. If we get the expected result every time, then we can confirm that the weights are increasing according to the labels.
On the other hand, we can prove that a(n) ≥ log3(n). Indeed, suppose we conducted several weighings and confirmed that the labels are correct. To every coin we can assign a sequence of three letters L, R, N, corresponding to where the coin was placed during each weighing — left cup, right cup or no cup. If two coins are assigned the same letters for every weighing, then we can't confirm that the labels on these two coins are accurate. Indeed, if we switch the labels on these two coins, the results of all the weighings will be the same.
My son, Alexey Radul, sent me the proof that a(10) = a(11) = 3. As 3 is the lower bound, we just need to describe the weighings that will work.
Here is the procedure for 10 coins. For the first weighing we put coins labeled 1, 2, 3, and 4 on one side of the scale and the coin labeled 10 on the other. After this weighing, we can divide the coins into three groups (1,2,3,4), (5,6,7,8,9) and (10). We know to which group each coin belongs, but we do not know which coin in the group is which. The second weighing is 1, 5 and 10 on the left, and 8 and 9 on the right. The left side should weigh less than the right side. The only possibility for the left side to weigh less is when the smallest weighing coins from the first and the second group and 10 are on the left, and the two largest weighing coins from the first two groups are on the right. After the second weighing we can divide all coins into groups we know they belong to: (1), (2,3,4), (5), (6,7), (8,9) and (10). The last weighing contains the lowest weighing coin from each non-single-coin group on the left and the largest weighing coin on the right, plus, in order to balance them, the coins whose weights we know. The last weighing is 2+6+8+5 = 4+7+9+1.
Here is Alexey's solution, without explanation, for 11 coins: 1+2+3+4 < 11; 1+2+5+11 = 9+10; 6+9+1+3 = 8 +4+2+5.
Let me denote the n-th triangular number as Tn. Then a(Tn) ≤ a(n) + Tn - n - 1. Proof. The first weighing is 1+2+3 ... +n = Tn. After that we can divide coins into groups, where we know that the labels stay within the group: (1,2,...,n), (n+1,n+2,...,Tn-1), (Tn). We can check the first group in a(n) weighings, the second group in Tn - n - 2 weighings, and we already used one. QED.
Similarly, a(Tn+1) ≤ a(n) + Tn - n.
For non-triangular numbers there are sometimes weighings that divide coins into three groups such that the labels can only be permuted within the same group. For example, with 13 coins, the first weighing could be 1+2+3+4+5+6+7+8 = 11+12+13. After that weighing we can divide all coins into three groups (1,2,3,4,5,6,7,8), (9,10), (11,12,13).
In all the examples so far, each weighing divided all the coins into groups. But this is not necessary. For example, here is Alexey's solution for 9 coins. The first weighing is 1+2+3+4+5 < 7+9. When we have five coins on the left weighing less than two coins on the right, we have several different possibilities of which coins are where. Other than the case above, we can have 1+2+3+4+6 < 8+9 or 1+2+3+4+5 < 8+9. But let's look at the next weighing that Alexey suggests: 1+2+4+7 = 6+8. Or, three coins from the previous weighing's left cup, plus one coin from the previous weighing's right cup equals the sum of the two coins that were left over. This can only be true if the coins in the first weighing were indeed 1+2+3+4+5 on the left and 7+9 on the right. After those two weighings everything divides into groups (1,2,4), (3,5), (6,8), (7) and (9). The last weighing 1+7+9 = 4+5+8, resolves the rest.
To check 7 or 8 coins in three weighings is simpler than the cases for 9, 10, and 11 coins, so I leave it as an exercise. As of today I do not know if it is possible to check 7, 8 or 9 coins in two weighings. Consider this a starred exercise.
I invite you to play with this amusing sequence and calculate some bounds. Also, let me know if you can prove or disprove that this sequence is non-decreasing.
Langton's ant travels on the infinite square grid, colored black and white. At each time step the ant moves one cell forward. The ant's direction changes according to the color of the cell he moves onto. The ant turns 90 degrees left if the cell is white, and 90 degrees right if the cell is black. After that, the cell he is on changes its color to the opposite color.
There is a symmetry of time and space for this ant. If at any point of the ant's travel, someone interferes and reverses the ant's direction in between the cells, the ant and the grid will traverse the steps and stages back to the starting point.
Let's give this ant a life. I mean, let's place him inside the Game of Life invented by John H. Conway. In addition to the Langton's ant's rules, I want the cells to change colors according to the rules of the Game of Life.
Let me remind you of the rules of Conway's Game of Life. We call black cells live cells and white cells dead cells. Black is life and white is death. The cell has eight neighbors — horizontal, vertical, diagonal. At each time step:
So, our ant will be traveling in this dying and reproducing population and correcting nature's mistakes. He revives dead cells and kills live cells.
There is an ambiguity in this ant's life description. The life can happen at two different moments. In the first ant's world, the ant jumps from one cell to the next, and while he is in the air, the cells have time to copulate, give birth and die. Upon landing, the ant changes direction and uses his magic wand to change the life status of its landing cell. In the second ant's world, the ant moves to the destination cell, changes its own direction and the status of the cell and then takes a smoke. All the fun, sex and death happen while he is enjoying his cigarette.
The ant's life has symmetry in a way that is similar to the symmetry of the ant without life. If we reverse the ant's direction back and also switch his life-style from the first to the second or vice versa, then the ant and the grid will go backwards in their states.
The parameters for the Langton's ant were chosen to make the ant's behavior interesting. The parameters of the Game of Life were chosen to make the Game of Life's behavior interesting. To make the ant's life fascinating, we might want to modify the ant's behavior or the Life's rules. The synergy of the ant and the Life might be intriguing only if the ant changes its behavior and the Life changes its rules.
Let's experiment and discover how we need to change the rules in order to make the ant's life interesting.
John H. Conway is teaching me his doomsday algorithm to calculate the day of the week for any day. The first lesson was devoted to 2009. "The 2009's Doomsday is Saturday" is a magic phrase I need to remember.
The doomsday of a particular year is the day of the week on which the last day of February falls. February 28 of 2009 is Saturday, thus 2009's doomsday is Saturday. For leap years it is the day of the week of February 29. We can combine the rules for leap years and non-leap years into one common rule: that the doomsday of a particular year is the day of the week of March 0.
f you know the day of the week of one of the days in 2009, you can theoretically calculate the day of the week of any other day that year. To save yourself time, you can learn by heart all the days of the year that fall on doomsday. That is actually what Conway does, and that is why he is so fast with calculations. The beauty of the algorithm is that the days of the doomsday are almost the same each year. They are the same for all months other than January and February; and in January and February you need to make a small adjustment for a leap year. That gives me hope that after I learn how to calculate days in 2009 I can easily move to any year.
To get us going we do not need to remember all the doomsday days in 2009. It is enough to remember one day for each month. We already know one for February, which works for March too. As there are 28 days in February, January 31 happens on a doomsday. Or January 32 for leap years.
Now we need to choose days for other months that are on doomsday and at the same time are easy to remember. Here is a nice set: 4/4, 6/6, 8/8. 10/10. For even months the days that are the same as the month will work. The reason it works so nicely is that two consecutive months starting with an even-numbered month, excluding February and December, have the sum of days equaling 61. Hence, those two months plus two days are 63, which is divisible by 7.
Remembering one of the doomsdays for every other month might be enough to significantly simplify calculations. But if you want a day for every month, there are additional doomsday days to remember on odd numbered months: 5/9, 9/5, 7/11 and 11/7. These days can be memorized as a mnemonic "9-5 job at 7-11," or, if you prefer, "I do not want to have a 9-5 job at 7-11."
If you throw in March 7, then the rule will fit into a poem John recited to me:
The last of Feb., or of Jan. will do
(Except that in leap years it's Jan. 32).
Then for even months use the month's own day,
And for odd ones add 4, or take it away*.
*According to length or simply remember,
you only subtract for September or November.
Let's see how I calculate the day of the week for my friend's birthday, July 29. The 11th of July falls on the doomsday, hence July 25 must be a doomsday. So we can see that my friend will celebrate on Wednesday this year.
You might ask why I described this trivial example in such detail. The reason is that you might be tempted to subtract 11 from 29, getting 18 and saying that you need to add four days to Saturday. In the method I described the calculation is equivalent, but as a bonus you calculate another day for the doomsday and consequently, you are getting closer to John Conway who remembers all doomsdays.
My homework is the same as your homework: practice calculating the days of the week for 2009.
Visitors to the math department of Princeton University used to stop by John Conway's office. Even if it were closed, they could peek through the window in the door to see the many beautiful, symmetric figures hanging in his office.
The figures, which John Conway had made, were there for 20 years. Just recently John received a letter informing him that his office had been inspected by the State Fire Marshall and that "those things hanging from your ceiling are against the State's fire code and must be taken down." The math department was worried about a possible fine.
So John threw away the "things." I wanted to cry as I watched these huge garbage bags being taken away. I rescued several figures, but that was all that I could fit into my car. For 20 years no one complained, but now the bureaucracy has beat out beauty and mathematics.
This picture is the last view of the "hazardous" office.
On one of my visits to Princeton, I stopped by the math department and, as usual, asked John H. Conway what he was up to. He told me that he was turning numbers inside out. He explained that to perform this procedure on a number you need to reverse every prime factor, multiply the reversed factors back and reverse the result. For example, for 34, which is the product of 2 and 17, we need to reverse 2 and 17 (turning inside), changing them into 2 and 71, multiply back, getting 142, and reversing again (turning outside), leading to the resulting number 241.
He started with a number, turned it inside out, then turned the result inside out, and so on, thus getting an infinite sequence for any number. Every sequence he had calculated up to this point ended with a cycle.
Before I had interrupted him, he was calculating the sequence starting with 78 and it was growing. I suggested that Mathematica could do this calculation faster than John could do in his head. Although that was very rude considering his reputation for speed, John agreed, and we moved to a computer. The computer confirmed that the sequence starting with 78 was growing wildly.
While playing around with this, I became very interested in numbers that are fixed under this turning inside-out operation. First, prime numbers do not change — you just reverse them twice. Second, palindromes with palindromic primes do not change, as every reversal encounters a palindrome to apply itself to. I started to wonder if there are palindromes that are fixed under the turning inside-out procedure, but are not products of palindromic primes.
Here is where John had his revenge. He told me that he would be able to find such a number faster than I could write a program to find it. And he won! He found such a number while I was still trying to debug my program. The number he found was 1226221.
Here is how he beat me. If you have two not-too-big primes that consist of zeroes and ones and that are reversals of each other, their product will be a palindrome. And John is really fast in checking primes for primality. See his lesson in my essay Remember Your Primes.
The next day, when I stumbled on John again, he was doing something else. I asked him about the numbers and he told me that he was no longer interested. Initially he had hoped that every sequence would end in a cycle. The turning inside-out operation doesn't produce much growth in a number. On top of that, prime numbers are stable. That means that if the turning inside-out operation was a random operation with a similar growth pattern, there would have been a very high probability of every sequence eventually hitting a prime. But the operation is not random, as it doesn't change remainders modulo 9. In particular, sequences that start with a composite number divisible by 3 would never hit a prime. Our experiment with 78 discouraged him by showing no hope for a cycle.
I asked him, "Why not do it in binary?" He answered that he had sinned enough playing with a base 10 sequence.
A year later when I next visited Princeton and saw John again, I asked him if he had published or done something with the operation. He had not. He agreed to submit the sequence to the online database, but only if we came up with a name he liked. And we did. We now call this operation TITO (turning inside, turning outside). Please welcome TITO.
When my son Sergei made it to the International Linguistics Olympiad I got very excited. After I calmed down I realized that training for this competition is not easy because it is very difficult to find linguistics puzzles in English. This in turn is because these Olympiads started in the USSR many years ago and were adopted here only recently. So I started translating problems from Russian and designing them myself for my son and his team. For this particular problem I had an ulterior motive. I wanted to remind my son and his team of rare words in English with Greek origins. Here is the problem:
We use many words that have Greek origins, for example: amoral, asymmetric, barometer, chronology, demagogue, dermatology, gynecologist, horoscope, mania, mystic, orthodox, philosophy, photography, polygon, psychology, telegram and telephone. In this puzzle, I assume that you know the meanings of these words. Also, since I am a generous person, I will give you definitions from Answers.com of some additional words derived from Greek. If you do not know these words, you should learn them, as I picked words for this list that gave me at least one million Google results.
In the list below, I picked very rare English words with Greek origins. You can derive the meanings of these words without looking in a dictionary, just by using your knowledge of the Greek words above.
Here are some other words. You do not have enough information in this text to derive their definitions, but you might be able to use your erudition to guess the meaning.
Robert Calderbank and Ingrid Daubechies jointly taught a course called "The Theory of Games" at Princeton University in the spring. When I heard about it I envied the students of Princeton — what a team to learn from!
Here is a glimpse of this course — a problem on Evolutionarily Stable Strategy from their midterm exam with a poem written by Ingrid:
On an island far far away, with wonderful beaches
Lived a star-bellied people of Seuss-imagin'd Sneetches.
Others liked it there too — they loved the beachy smell,
From their boats they would yell "Can we live here as well?"
But it wasn't to be — steadfast was the "No" to the Snootches:
For their name could and would rhyme only with booches …
Until with some Lorxes they came!
These now also enter'd the game;
A momentous change this wrought
As they found, after deep thought.
Can YOU tell me now
How oh yes, how?
In what groupings or factions
Or gaggles and fractions
They all settled down?
Sneetches and Snootches only:
| Sneetches | Snootches | |
| Sneetches | 4 | 3 |
| Snootches | 3 | 2 |
Sneetches and Snootches and Lorxes:
| Sneetches | Snootches | Lorxes | |
| Sneetches | 4 | 3 | 8 |
| Snootches | 3 | 2 | 16 |
| Lorxes | 8 | 16 | -60 |
Find all the ESSes, in both cases.
My guest blogger is a friend and a wordsmith Sue Kelman:
* * *
Rizzo (Ratso to his friends) was my cage mate. We had a nifty pad at Children's Hospital — all we could eat with no scrounging, clean beds, quiet surroundings, and plenty of activity to keep us occupied.
Rizzo's favorite was the maze. Each week he bragged to us about how fast he made it through to the cheese. Larry over in Row-D was always the slowest. All the guys used to razz him about it. No matter how hard he tried, Larry took the wrong turn every time. I think his mother spent some time out at a psych hospital, so maybe they messed with her brain and that affected Larry. Who knows? I suspect that know-it-all visiting researcher from MIT knows what happened to Larry but he's probably keeping it under his hat until he publishes his results in JAMA. Putz!
Okay, so one day, Rizzo just came back from one of those tests where they make us hit a little button when the red and green lights go on. Personally this is my favorite gig because of course there's no running around, but Rizzo likes to throw a monkey wrench into the research data. So every now and then, even when he knows how we should respond, he does just the opposite. I told you, he's one smart rodent.
Rizzo's pretty famous, too. Oh he's not as famous as that talking grey parrot that used to be over at Harvard, but he's been around. For a while he was a top gun — the big performer for a group of genetics guys. He's had his DNA tested more times than Mike Tyson.
Then they lent him out to Hematology where, I swear, the guy's already had 15 blood transfusions. No wonder he's healthy as a horse.
Me, I'm just your average lab rat. I know the drill: wake up, eat a few pellets, perform, eat some more pellets, doze off, and wake up to do it all over again. Not a bad life if you can stay away from those vivisection weirdos. They're like Dr. Mengele all over again.
I'd tell you more but Rizzo's gonna tell us about the time he got out of his cage and made it almost all the way to the Starbucks wagon before they caught him. Great story and he's a real raconteur. None of that Stuart Little crap. We fall over laughing every time we hear it. Gotta go.
Due to the popularity of my previous posting of linguistics puzzles, I've translated some more puzzles from the online book Problems from Linguistics Olympiads 1965-1975. I've kept the same problem number as in the book; and I've used the Unicode encoding for special characters.
Problem 180. Three Tajik sentences in Russian transliteration with their translations are below:
Your task is to assign a meaning to each out of four used Tajik words.
Problem 185. For every sequence of words given below, explain whether it can be used in a grammatically correct English sentence. If it is possible show an example. In the usage there shouldn't be any extra signs between the given words.
Problem 241. In a group of relatives each person is denoted by a lower-case letter and relations by upper-case letters. The relations can be summarized in a table below:
| a | b | c | d | e | f | g | |
| a | — | A | A | B | D | E | E |
| b | A | — | A | E | D | E | E |
| c | F | F | — | G | H | I | I |
| d | H | J | J | — | K | L | L |
| e | B | B | B | N | — | N | N |
| f | O | O | D | L | Q | — | A |
| g | J | J | H | L | K | F | — |
The table should be read as following: if the intersection of the row x and the column y has symbol Z, then x is Z with respect to y. It is known that e is a man.
You task is to find out the meaning of every capital letter in the table (each letter can be represented as one English word).
There is interesting data to show that MIT takes math students more seriously than Harvard and Princeton. By Michael Sipser's suggestion I looked at the Putnam Competition results. Out of the top 74 scorers of 2007, 21 were from MIT, 9 from Harvard and 7 from Princeton. Keep in mind that the total freshman enrollment at MIT is much lower than at Harvard or Princeton. This story repeated itself in 2008: out of top 79 scorers 23 were from MIT, 11 from Harvard and 11 from Princeton.
Ironically, MIT's team didn't win Putnam in those years. MIT's team won the third place after Harvard and Princeton. If you look at the results more closely, you will notice that had MIT arranged teams differently, MIT would have won.
It appears that MIT put their three top scorers from the previous year on their lead team. MIT shouldn't assume that those three continue to be their strongest competitors. Instead they should probably test their students right before the Putnam competition, because if you look at MIT's top individual performers, had they been on a team together, they would have won.
Maybe MIT should rethink its algorithm for creating teams, or maybe we should just wait. As it is obvious that MIT is more serious about math, all top math students may want to go to MIT in coming years. If this happens, the mathematics field will be absolutely dominated by MIT.
Of course you can. Can you do it in Russian? You do not need to know Russian to do it; you just need to solve my puzzle. Below are some numerals written in Russian. You have enough information to write any number from 1 to 99 inclusive in Russian.
If you are too lazy to write all the Russian numerals I requested, try the most difficult ones: 16, 17, 19, 67 and 76.
If you know Russian, then I have a back-up puzzle for you. Do the same thing for French:
And again, if you are lazy, you can concentrate on translating 15, 18, 19, 41, 51, 56, 65, 78 and 99 into French.
I invite my readers to create similar puzzles in all languages.
I recently read an article titled "Think having children will make you happy?" that discusses studies correlating happiness and having children. Some studies show that parents and non-parents have the same level of happiness. But other studies show that non-parents are happier. So, do children make us less happy?
There are two major reasons that kids might make people less happy in a long run. First, children require a lot of resources; they put a strain on our budget, time and careers. As my friend Sue Katz puts it: parental unhappiness could stem from poverty, illness, fighting the educational institutions, feeling stuck in a violent relationship because of the kids — a million things, depending on class and options.
Second, children might not live up to our expectations. Parents often dream that their children will have wonderful careers, be supportive of their parents later in life and most importantly be good people. But in reality, children choose their own careers, not necessarily a path approved by their parents. Plus they might live at a distance or the relationship might be strained. They might even develop completely different values from their parents.
The article claims that on average kids will bring more problems than joy to our lives. Do not rush to cancel unprotected sex with your spouse tonight yet.
My friend Peggy Boning suggested that the study should have separately checked parents who wanted children and parents who didn't. It could be that parents who didn't want children are less happy than parents who wanted them. Which means that if you do not want children, make sure you have protected sex. If you do want children, you might be happier with children than without.
Anyone who has studied statistics knows that correlation doesn't mean causality. An individual who wants to have children might be happier as a result, and at the same time the statistics data may well be true. I'd like to find arguments that can make peace between these two suppositions.
Feel free to add your own ideas.
In Psilvania no one knows English, except for one retired professor Mary Bobs. That is why every year the organizers of the linguistics Olympiad in Psilvania beg Mary to design a puzzle in English. Kids in Psilvania know other languages — which gives individuals an advantage if the puzzle is in those languages. An English puzzle would create a level playing field.
Here is the puzzle that Mary proposed. I'm omitting the Psilvanian text, because the characters do not match anything in Unicode tables.
Professor Bobs provided the following sentences in English, accompanied by their translations into Psilvanian. She called these sentences Raw Materials:
The first task that she required was to translate the following sentences into Psilvanian:
Professor Mary Bobs had quit smoking that very week and she couldn't concentrate. It seems that she may have given more information than is necessary. Is it possible to remove any of the Raw Materials (one or more translated sentences) and keep the puzzle solvable? If so, what is the largest number of Raw Materials you can eliminate? Explain.
Her second task was to translate some sentences from Psilvanian into English, and the answers she hoped the students would calculate were:
For each of the three English sentences above, decide whether the participants of the Olympiad will be capable of getting this particular answer. If for any of these three sentences you suspect that they will not be able to arrive at the correct answer, explain why.
Just out of curiosity I googled two phrases: "male mathematician" and "female mathematician". The results for these phrases on May 3, 2009 were:
Why do you think that female mathematicians are more popular than male mathematicians? I think it is because when people hear the word mathematician, by default they picture a man, so the phrase "male mathematician" is perceived as pleonastic.
I decided to look at some of the 824 sites talking about "male mathematicians". Many web-pages containing the words "male mathematician" are actually pages about female mathematicians, where there is a need to mention a mathematician of the opposite sex. Many other sites are dating pages where a mathematician looks for a partner, and it is wise to start with a description of the sex of the seeker.
Speaking of dating, did I ever mention that I am a female mathematician who was married three times, and all of my spouses were male mathematicians?
One of the best inventions of recent years is toilet seat covers. So whenever I visit a bathroom without seat covers, I curse and make my own out of toilet paper. This is not very effective, as toilet paper doesn't stay nicely in place and it takes a lot of time, when time might be of the essence. Besides it wastes a lot of tissue.
When I come into a toilet and see a lot of long pieces of clean toilet paper lying around, I know that someone else tried to create a seat cover before me.
So here is my idea. Why not make individual packages with folded toilet seat covers, like kleenex packets? When I couldn't find toilet seat covers in my local pharmacy, I started wondering how to patent my idea and dreaming about a lot of money. But before I let myself get too excited, I checked the Internet. My new toilet-seat-covers-to-go were already available. So I bought some. Now, every time I flush them, I watch my potential patent going down the toilet.
I would like to discuss the solution to one of the linguistics puzzles I posted a while ago. Here is problem number 211 from the online book Problems from Linguistics Olympiads 1965-1975:
You are given words in Swahili: mtu, mbuzi, jito, mgeni, jitu and kibuzi. Their translations in a different order are: giant, little goat, guest, goat, person and large river. Make the correspondence.
First, lets say that a giant is a large man. The Swahili translation of "giant" may have elements of Swahili words for a "man" and a "large river". Next we notice that each of these Swahili words naturally divides into two parts. We can put them in a table such that the first part is the same for every row and the second part is the same for every column.
| m-tu | m-buzi | m-geni | |
| ji-tu | ji-to | ||
| ki-buzi |
When I gave this problem to my students, they loved the idea that the word "giant" is comprised of the two words "large" and "man", so they assumed that in Swahili a "guest" would also have a two-part translation, such as a "man who visits." In the list of words we have three different types of "man": man, giant and guest. Once they noticed that "m" appears three times, they concluded that "m" must mean a man. Therefore, the object must be the first part of a Swahili word, while the second part contains its description.
Next, they noted that the first part "ji" appears twice. They decided that "ji" must be a goat and thus "ki" must be a river. All of this gives us sufficient information to derive the translations: "mgeni" a guest, "kibuzi" a large river, "mbuzi" a giant, "mtu" a man, "jitu" a goat and "jito" a little goat.
My students were very proud of themselves, but I was dissatisfied with this solution. Here are the problems I've identified:
I would suggest a different approach. Let's say that the puzzle is about sizes, and we have three objects (man, guest, goat) of normal size, two large objects (giant and large river), and one small object (little goat). That means "m" must mean normal, and the size description is in front. If the first part is the size, then "ki" is small, "ji" large. From here "mgeni" is a guest, "kibuzi" a little goat, "mbuzi" a goat, "mtu" a man, "jitu" a giant, and "jito" is a large river.
I love this puzzle because it teaches us to continue pondering, even after everything seems to fit. If you stumble upon the first solution you need to go back and think some more. Only after you discover the second solution does it become clear that the second one is right.
My son, Alexey Radul, married Rebecca Frankel recently. They had a nerdy wedding. You can judge just how nerdy by this poem written and presented by Gremio (Gregory Marton), the best man:
In this summation, may there be no subtraction;
May you multiply blissfully, and find no division;
May the roots of the power of your love run deep;
May the logs of your joys be exponentially steep;
May you derive greatest pleasure from integrating your lives,
And well past your primes, retain composite rhymes.
This group gathered here, on that lush green field:
May we help you build proofs on the vows you just sealed.
I have a tiny book written by Vladimir Arnold Problems for Kids from 5 to 15. A free online version of this book is available in Russian. The book contains 79 problems, and problem Number 6 criticizes American math education. Here is the translation:
(From an American standardized test) A hypotenuse of a right triangle is 10 inches, and the altitude having the hypotenuse as its base is 6 inches. Find the area of the triangle.
American students solved this problem successfully for 10 years, by providing the "correct" answer: 30 inches squared. However, when Russian students from Moscow tried to solve it, none of them "succeeded". Why?
Arnold has inflated expectations for kids. The book presents the problems according to the increasing order of difficulty, and this suggests that he expects kids under 10 to solve Number 6.
Arnold claimed that every student from Moscow would notice what is wrong with this problem. I can forgive his exaggeration, because I've met such kids. Anyways, I doubt that Arnold ever stumbled upon an average Russian student.
My own fundamental interest is in the state of American math education, so I decided to check his claim concerning American students. I asked my students to calculate the area of the triangle in the above puzzle.
Here are the results of my experiment. Most of them said that the answer is 30. Some of them said that it is 24. In case you're wondering where the 24 is coming from, I can explain. They decided that a right triangle with hypotenuse 10 must have two other legs equal to 8 and 6.
Some of the students got confused, not because they realized that there was a trick, but because they thought the way to calculate the area of the right triangle is to take half the product of its legs. As lengths of legs were not given, they didn't know what to do.
There was one student. Yes, there was one student, who decided that he could calculate the legs of the triangle from the given information and kept wondering why he was getting a negative number under the square root.
You decide for yourself whether there is hope for American math education. Or, if you are a teacher, try running the same experiment yourself. I hope that one day I will hear from you that one of your students, upon reading the problem, immediately said that such a triangle can't exist because the altitude of the right triangle with the hypotenuse as the base can never be bigger than half of the hypotenuse.
A long ago my son Sergei went to the Streamline School Olympiad. Some of the problems were really nice and I asked the organizer, Oleg Kryzhanovsky, where he took the problems from. It seems that he himself supplied all the problems, many of which are his original creations. He told me that he can invent a math Olympiad problem on demand for any level of difficulty on any math topic. No wonder that he is the author of almost all math problems at the Ukraine Olympiad.
The following is a sample of his problems from the Streamline Olympiad. For my own convenience I have chosen problems without figures and equations. Note: I edited some of them.
1998 (8th - 9th grade). Find three numbers such that each of them is a square of the difference of the two others.
1999 (9th - 10th grade). The positive integers 30, 72, and N have a property that the product of any two of them is divisible by the third. What is the smallest possible value of N?
1999 (9th - 10th grade). You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?
1999 (11th - 12th grade). In how many ways can the numbers 1, 2, 3, 4, 5, 6 be ordered such that no two consecutive terms have a sum that is divisible by 2 or 3.
2000 (6th - 7th grade). Let A be the least integer such that the sum of all its digits is equal to 2000. Find the left-most digit of A.
2000 (8th grade). You have six bags with coins that look the same. Each bag has an infinite number of coins and all coins in the same bag weigh the same amount. Coins in different bags weigh 1, 2, 3, 4, 5 and 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times do you need to weigh coins in order to confirm that the labels are correct?
I've been translating a lot of linguistics puzzles lately. Now it is my turn to create a new linguistics puzzle. Here are some English phrases with their Russian translations:
Your task is to translate into Russian the following sentences:
Bonus question. Have you noticed any signs that I am getting tired of linguistics?
I stumbled on a Russian linguistics competition called The Russian Little Bear. Most of the puzzles are Russian-specific; but some of them can be translated. I concentrated on puzzles for grades six through nine and used Unicode for uncoding strange characters.
Problem 1. Here are some Latin words with their English translations:
Pick the line of words from A to E that best translates these phrases into Latin: You are loved, I ask, He invites.
Problem 2. The first astronauts from India (I), Hungary (H), France (F) and Germany (G) were Bertalan Farkas (1), Sigmund Jähn (2), Rakesh Sharma (3) and Jean-Loup Chrétien (4). Match the astronauts to the countries:
Problem 3. You do not need to know Russian to solve this puzzle. It is enough to know the modern Russian alphabet: А, Б, В, Г, Д, Е, Ё, Ж, З, И, Й, К, Л, М, Н, О, П, Р, С, Т, У, Ф, Х, Ц, Ч, Ш, Щ, Ъ, Ы, Ь, Э, Ю. Before XVIII century, numbers in Russian were denoted by letters, for example: ТЛЕ — 335, РМД — 144, ФЛВ — 532.
How was 225 written in old Russian?
(A) ВВФ; (B) ВВЕ; (C) СКЕ; (D) СКФ; (E) ВНФ.
Problem 4. Here are several Turkish words and phrases with their English translations:
Pick the line of words from A to E that best translates these phrases into Turkish: thirty isles, men?
Courtney Gibbons gave me her permission to add her webcomics to my collection of Funny Math Pictures.
Abstruse Goose gave me his permission to add his webcomics to my collection of Funny Math Pictures.
Until the introduction of the Abel prize, the Fields medal was the most prestigious prize in mathematics. The medal has been awarded 48 times and all of the recipients have been men. Can we conclude that women are inferior to men when it comes to very advanced mathematics? I do not think so.
The Fields medal was designed for men; it is very female-unfriendly. It is the prize for outstanding achievement made by people under age 40. Most people start their research after graduate school, meaning that people have 10-15 years to reach this outstanding achievement. If a woman wants to have children and devote some time to them, she needs to do it before she is 40. That puts her at a big disadvantage for winning the medal.
Recently the Abel prize for mathematics was introduced. This is the math equivalent of a Nobel prize and nine people have received the prize, all of them male. The Wolf prize is another famous award: 48 people have received it so far and they too have all been male.
On the grand scale of things, women have only recently had the option of having a career in mathematics. Not so long ago it was considered quite exceptional for a woman to work in mathematics. The number of female mathematicians is increasing, but as this is a new trend, they are younger people. At the same time, Abel prizes and Wolf prizes are given to highly accomplished and not-so-young people. That means the increase in the percentage of women PhDs in mathematics might affect the percentage of females getting the prize, but with a delay of several dozen years.
There are other data covering extreme math ability. I refer to the International Math Olympiad. The ability that is needed to succeed in the IMO is very different from the ability required to succeed in math research. But still they are quite similar. The IMO data is more interesting in the sense that the girls who participate are usually not yet distracted by motherhood. So in some sense, the IMO data better represents potential in women's math ability than medals and prizes.
Each important math medal or prize is given to one person a year on average. So the IMO champion would be the equivalent of the Fields medal or the Wolf prize winner. While no girl was the clear best in any particular year, there were several years when girls tied for the best IMO score with several other kids. For example:
In one of those years, a girl might have been the best, but because the problems were too easy, she didn't have a chance to prove it. Evgenia Malinnikova was an outstanding contender who twice had a perfect score. In 1990, she was one out of four people, and she was younger than two of them, as evidenced by the fact they they were not present in 1991. Only one other person — Vincent Lafforgue — got a perfect score in 1990 and 1991. We can safely conclude that Evgenia was one of two best people in 1990, because she was not yet a high school senior.
This might be a good place to boast about my own ranking as IMO Number Two, but frankly, older rankings are not as good as modern ones. Fewer countries were participating 30 years ago, and China, currently the best team, was not yet competing.
Girls came so close to winning the IMO that there is no doubt in my mind that very soon we will see a girl champion. The Fields medal is likely to take more time.
Due to the popularity of my previous posting of linguistics puzzles, I've translated some more puzzles from the online book Problems from Linguistics Olympiads 1965-1975. All of them are from the phonetics section and I've kept the same problem number as in the book. I've used the Unicode encoding for special characters.
Problem 20. In the table below there are numerals from some Polynesian languages. Note that I couldn't find the proper English translation for one of the languages, so I used transliteration from Russian. The language sounds like "Nukuhiva" in Russian.
| Languages | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Hawaiian | kahi | lua | ha | lima | ono | hiku | walu | ***** | ||
| Māori | tahi | rua | toru | wha | ono | whitu | waru | iwa | ***** | |
| Nukuhiva | tahi | to'u | ha | ono | va'u | ***** | ||||
| Rarotongan | ta'i | 'a | rima | ono | 'itu | varu | iva | ŋa'uru | ||
| Samoan | tasi | lua | lima | ono | fitu | iva | ŋafulu |
Your task is to find the words that should be in the empty cells. Note that wh, ', and ŋ denote special consonants.
Problem 21. Below you will find words in several relative languages. You can group these words into pairs or triples of words with the same origin and the same or a similar meaning.
āk, dagr, bōk, leib, fōtr, waʐʐar, buoh, dæʒ, plōgr, hām, wæter, hleifr, pfluog, eih, heimr, fuoʐ, plōʒ.
Task 1. Divide the words into groups so that the first group has words from the same language, the second group has words from another language and so on.
Task 2. (optional) List your suggestions about the meanings of the words and about the identity of the languages.
Problem 22. These words from the Aliutor language are followed by their translations. The stresses are marked by an apostrophe in front of the stressed vowel.
Your task is to put the stresses in the following words: sawat 'lasso', pantawwi 'fur boots', nəktəqin 'solid', ɣətɣan 'late autumn', nəminəm 'bouillon', nirvəqin 'sharp', pujɣən 'spear', tilmətil 'eagle', wiruwir 'red fish', wintatək 'to help', nəmalqin 'good', jaqjaq 'seagull', jatək 'to come', tavitətkən 'I will work', pintətkən 'he attacks (someone)', tajəsqəŋki 'in the evening'.
Note that the vowel ə is similar to many unstressed syllables in English words, such as the second syllable in the words "taken" and "pencil". This vowel is shorter than other vowels in the Aliutor language.
Last time Sue refinanced her mortgage was six years ago. She received a 15-year fixed loan with 5.5% interest. Her monthly payment is $880, and Sue currently owes $38,000.
Sue is considering refinancing. She has been offered a 5-year fixed loan with 4.25% interest. You can check an online mortgage calculator and see that on a loan of $38,000, her monthly payments will be $700. The closing costs are $1,400. Should Sue refinance?
Seems like a no-brainer. The closing costs will be recovered in less than a year, and then the new mortgage payments will be pleasantly smaller than the old ones. In addition, the new mortgage will last five years instead of the nine years left on the old mortgage.
What is wrong with this solution? What fact about Sue's old mortgage did I wickedly neglect to mention? You need to figure that out before you decide whether Sue should really refinance.
So many people liked the puzzles I posted in Subtraction Problems, Russian Style, that I decided to present a similar collection of multiplication and division puzzles. These two sets of puzzles have one thing in common: kids who go for speed over thinking make mistakes.
Humans have 10 fingers on their hands. How many fingers are there on 10 hands?
This one is from my friend Yulia Elkhimova:
Three horses were galloping at 27 miles per hour. What was the speed of one horse?
Here is a similar invention of mine:
Ten kids from Belmont High School went on a tour of Italy. During the tour they visited 20 museums. How many museums did each kid go to?
Another classic:
How many people are there in two pairs of twins, twice?
Can you add more puzzles to this collection?
Today I have my first invited guest blogger, John Berman. John 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:
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:
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.
My son Sergei brought back the Flip-Flop game from Canada/USA Mathcamp, and now I teach it to my students. This game trains students in the multiplication table for seven and eight. These are the most difficult digits in multiplication. This game is appropriate for small kids who just learned the multiplication table, but it is also fun for older kids and adults.
This is a turn-based game. In its primitive simplification kids stand in a circle and count in turn. But it is more interesting than that. Here's what to say and do on your turn, and how the game determines who is next.
First I need to tell you what to say. On your turn, say the next number by default. However, there are exceptions when you have to say something else. And this something else consists of flips and/or flops.
So what are flips? Flip is related to seven. If a number is divisible by seven or has a digit seven, instead of saying this number, we have to say "flip" with multiplicities. For example, instead of 17 we say "flip" because it contains one digit seven. Instead of 14 we say "flip", because ii is divisible by seven once. Instead of 7 we say "flip-flip", as it is both divisible by seven and has a digit seven. Instead of 49, we say "flip-flip" as 49 is divisible by the square of seven. Instead of 77 we say "flip-flip-flip" as it has two digits seven and is divisible by seven once.
Flop relates to eight the same way as flip relates to seven. Thus, instead of 16 we say "flop" as it is divisible by eight; instead of 18 we say "flop" as it contains the digit eight; and for 48 we say "flop-flop" as it is both divisible by eight and contains the digit eight.
A number can relate to seven and eight at the same time. For example 28 is divisible by seven and contains the digit eight. Instead of 28 we say "flip-flop". The general rule is that all flips are pronounced before all flops. For example, instead of 788 we will say "flip-flop-flop-flop" as it is divisible by eight and contains the digit seven once and the digit eight twice.
The sequence of natural numbers in the flip-flop version starts as the following: 1, 2, 3, 4, 5, 6, flip-flip, flop-flop, 9, 10, 11, 12, 13, flip, 15, flop, flip, flop, 19, 20, flip, 22, 23, flop, 25, 26, flip, flip-flop, 29, 30, 31, flop, 33, 34, flip, 36, flip, flop, 39, flop, 41, flip, 43, 44, 45, 46, flip, flop-flop, flip-flip, 50, 51, 52, 53, 54, 55, flip-flop, flip, flop, 59, 60, 61, 62, flip, flop-flop, 65, 66, flip, flop, 69, flip-flip, flip, flip-flop, flip, flip, flip, flip, flip-flip-flip, flip-flop, flip, flop-flop, flop, flop, flop, flip-flop, flop, flop, flip-flop, flop-flop-flop, flop, 90, flip, 92, 93, 94, 95, flop, flip, flopflip-flip-flop, 99, 100.
So how does the turn change? Everyone stands in a circle and says their number the way explained above. We start clockwise and move to the next number. For every flip we reverse the direction and for every flop we skip a person. That means that if we have two flips, we don't change the direction, while for two flops we skip two people. If we have flips and flops together, for example 28 corresponds to "flip-flop", then first we change the direction and then we skip a person.
On top of that, there is an extra rule for what you do on your turn. If you say something other than a default number, you switch your position from standing to sitting and vice versa. Sometimes I skip this extra feature — not because I am too lazy to exercise, but because I usually conduct this game in a classroom, where all the desks prevent us from fully enjoying such physical activity.
There are two ways to play this game: as a competition or as practice. When we are competing, a person who makes a mistake drops out. If we're just practicing, no one drops out. Sometimes I am particularly generous and allow my kids one mistake before making them drop out after the second mistake. So far we have played up to 100. I am curious to see if we can ever reach 700 and how long we will be able to continue the game after that.
Testing in the US is dominated by multiple-choice questions. Together with the time limit, this encourages students to stop thinking and go for guessing. I recently wrote an essay AMC, AIME, USAMO Contradiction, in which I complained about the lack of proofs in the first two rounds of math competitions.
Is there a way to improve the situation? I grew up in the USSR, where each round of the math competition had the same format: you were given several hours to write proofs for three or four difficult problems. There are two concerns with organizing a competition in this way. First, the Russian system is much more expensive, whereas the US's multiple choice tests can be inexpensively checked by a computer. Second, the Russian system is prone to unfairness. You need many math teachers to check all these papers on the highest level. Some of these teachers might not be fully qualified, and it is difficult to ensure uniform checking. This system can't easily be adopted in the US. I am surprised I haven't heard of lawsuits challenging USAMO results, but if we were to start having proofs at the AMC level with several hundred thousand participants, we would get into lots of trouble.
An interesting compromise was introduced at the Streamline Olympiad. The problems were multiple choice, but students were also requested to write proofs. Students got two points for a correct multiple choice answer, and if the choice was correct the proof was checked. Students could get up to three points for a correct proof. This idea solves two issues. The writing of proofs is rewarded at an early stage and the work of the judges is not as overwhelming as it would have been, had they needed to check every proof. However, there is one problem that I discussed in previous posts that this method doesn't solve: with multiple choice, minor mistakes cost you the whole problem, even though you might have been very close to a solution. If we want to reward thinking more than accuracy, the proof system allows us to give credit for partial solutions.
I can suggest another approach. If the Russians require proofs for all problems and the Americans don't require proofs for any problem, why not compromise and require a proof for one problem out of the set.
But I actually have a bigger idea in mind. I think that current development in artificial intelligence may soon help us to check the proofs with the aid of a computer. Artificial intelligence is still far from ready to validate that a mathematical text a human has produced constitutes a proof. But in this particular case, we have two things working for us. First, we can use humans and computers together. Second, we do not need to check the validity of any random proof; we need to check the validity of a specific proof of a simple problem that we know in advance, thus allowing us to prepare the computers.
Let us assume that we already can convert student handwriting into computer-legible text or that students write directly in LaTeX.
Here is the plan. Suppose for every problem, we create a database of some sample right, wrong and partial solutions with corresponding scores. The computer checks the students' solutions against the given sample. Hopefully, the computer can recognize small typos and deviations that shouldn't change the point value. If the computer encounters a solution that is significantly different from the ones in the sample, it sends the solution to human judges. Humans decide how to score the solution and the solution and its score is added to the sample database.
For this system to work, computers should be smart enough not to send too many solutions to humans. So how many is too many? My estimate is based on the idea that we wouldn't want the budget of AMC to go too much higher than the USAMO budget. Since USAMO has 500 participants, judges check just a few hundred solutions to any particular problem. With several hundred thousand participants in AMC, the computer would have to be able to cluster all the solutions into not more than a few hundred groups. The judges only have to check one solution in each group.
As a bonus, we can create a system where for a given solution that is not in the database, the computer finds the closest solution and highlights the difference, thus simplifying the human's job.
In order to improve math education, we need to add proofs when teaching math. My idea might also work for SATs and for other tests.
Now that there is more money available for education research, would anyone like to explore this?
A stick has two ends. If you cut off one end, how many ends will the stick have left?
This pre-kindergarten math problem was given to me by Maxim Kazarian who lives in Moscow, Russia. That got me thinking about math education in the US. Actually, just about anything can get me thinking about education in our country. One of our math education patterns is to provide simplified templates and to train kids to plug numbers into them without thinking.
Math education should be about thinking. We need to give kids a lot of math problems that do not fit into standard templates, in order to encourage creative thinking. Here is another puzzle from Maxim:
A square has four corners. If we cut one corner off, how many corners will the remaining figure have?
I invite my readers to invent additional problems that sound as if a subtraction by one is needed, when, in fact, it is not. Here is my contribution:
Anna had two sons. One son grew up and moved away. How many sons does Anna have now?
To get to the national swimming championship, you need to win the state running championships.
What? Is that a joke? Perhaps you're having the same reaction. Because this is exactly what is happening with math competitions. The official USA math competition has three rounds: AMC, AIME and USAMO.
AMC is a multiple-choice competition with 25 problems in 75 minutes. To be good at it, you need speed, accuracy and the ability to guess well.
AIME is 3 hours long and has 15 problems. The problems are a different level of difficulty and guessing will not help you. Though AIME is also multiple-choice, unlike AMC where you choose out of 5, in AIME you choose out of 1,000. But you still need speed and accuracy. A small arithmetic mistake will cost you the whole problem.
USAMO is a competition that runs for 9 hours and has 6 problems. The problems are much harder and you have to write proofs. Proofs? What proofs? Where are the proofs coming from? It is like you got to the national swimming championship because you are a great runner, but you do not know how to swim.
As the result of this system of selection, the USA team at the International Math Olympiad has diverse skills: these kids are good at all three types of the math competitions. It is like taking an Olympic triathlon team to the Olympic swimming event.
However, the US loses by selecting in this way. There are many kids who are great mathematicians: they may be good at difficult problems but not that good at speed-racing problems. An arithmetic mistake costs you only one point at IMO, but a whole problem at AIME. There are kids who are deep mathematicians prone to small arithmetic mistakes. They could get a gold medal at IMO, but they can't pass AMC or AIME.
Not only that. As many AMC problems are boring and do not require ideas, AMC might discourage kids from all math competitions at an early stage.
I will write later with my ideas about how to change AMC. Right now I would like to offer a solution to a smaller problem. I am sure that the US math team organizers know many cases in which a non-senior kid does great at USAMO and is potentially a team member for the next year's US IMO team, but, oops, next year he can't pass AMC.
I suggest the following: USAMO participants are allowed to go to next year's AIME no matter what their AMC scores are. USAMO winners are allowed to go to the next year's USAMO no matter what their AIME results are. This way kids who have proved that they are great swimmers do not need to compete in running again.
I have forgotten all the problems from the math Olympiads I participated in, except for one. That problem cost me one point, and as result I didn't get a perfect score. Here is Problem Number 4 from the 1976 IMO:
Determine the greatest number that is the product of some positive integers, and the sum of these integers is 1976.
The solution goes like this. Consider a partition of 1976. If there is an integer x in the partition greater than 5, then replacing it with two integers x-2 and 2 gives a bigger product. Replacing 4 in the partition by 2 and 2 doesn't change the product. On the other hand, if there is 1 in the partition, it is profitable to attach it to any other number: to replace 1 and x by x+1.
That means the maximum-product partition of a number greater than one has to consist only of twos and threes. If we have three twos in the partition, we can replace them by two threes, thus increasing the product. That means that our partition should consist of twos and threes, and the number of twos shouldn't be greater than three.
I lost my point when I made an elementary arithmetic mistake while calculating the remainder of 1976 modulo 3.
Let's generalize this problem for any number n. If we define the maximum product of partitions a(n) as a function of the number n, we get the sequence A000792 in the Encyclopedia of Integer Sequences. This sequence has other interesting definitions, which appear if we add some structure to partitions of n.
For example, we can suppose that our n is not just a number, but it also represents n objects that are being permuted by the symmetric group Sn. In this case, we can associate some Abelian subgroups of the symmetric group with every partition. Namely, we can divide the set of n elements into disjoint subsets of sizes corresponding to our partition and cycle the elements in every subset. The product of these cycles is an Abelian subgroup, the order of which doesn't depend on how exactly we partition or how we cycle. This order is the product of the partition numbers. It appears that we can get all maximal Abelian subgroups of the symmetric group in this manner. Thus the sequence a(n) is the maximum size of the maximal Abelian subgroup in a symmetric group Sn.
We can do something else with our n objects. Suppose they are represented by vertices of a graph. We take any partition of n and divide our graph into groups of vertices according to this partition. Next we connect vertices of the graph that belong to different groups. If we take a vertex from every group, then the corresponding subgraph is a clique. We can see that it is a maximal clique as two vertices from the same group are never connected and we can't add any more vertices. The number of different cliques of this size is the product of the number of elements in every group. We can prove that a(n) is the maximum possible number of maximal cliques in a graph with n vertices.
Even though I can't return to 1976 to correct my stupid mistake, I love this problem and the corresponding sequence.
A new study is out. Dr. Satoshi Kanazawa blogged about his new discovery. He claims that he can explain why many studies show that men have higher intelligence than women. In his posting Why men are more intelligent than women he posits that intelligence is correlated with height. Taller men on average are smarter than shorter men.
He also claims that given the same height, women are more i