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.
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, 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 intelligent than men. As he puts it: "Women who are 5'10'' are on average more intelligent than men who are 5'10''." According to him the only problem women have in the brains department is that they aren't tall enough.
I couldn't find the study itself, only his own announcement. My problem with his study is that, according to Dr. Kanazawa's description, he used data from the National Longitudinal Study of Adolescent Health. If we are talking about adolescents we need to take into account that children grow taller and smarter with age. So any difference in intelligence among the kids of different heights may easily be explained by age. Taller boys may be older and therefore likely to perform better on intelligence tests.
As to intelligence differences between boys and girls of the same height, these girls who are 5'10'' may be from higher grades than boys who are 5'10''.
Some IQ tests are designed to take age into account, but what's totally weird is that a scientist is studying the correlation of intelligence and height, using a population that is in the middle of a physical and mental growth spurt.
As a mathematician, I've been around many people of great intelligence, but I've never perceived bright people as especially tall.
Here is the picture of the USAMO winners for 2007. These are certainly extremely smart kids and I know their heights. The sixth student on the left is my son, Sergei. I personally met all these kids and compared to their peers they are not — except for one boy — especially tall.
How many disjoint letters "O" can you draw on a plane? Clearly, the answer is infinitely many. Now the real question is whether this number can be uncountable. We assume that the letter "O" is just a circle. In this case, if we draw all possible concentric circles, we get an uncountable number of circles. I call letters for which you can build a disjoint uncountable set on the plane stackable letters.
If we do not allow one letter "O" to be drawn inside another, then we can prove that it is not possible to draw more than a countable number of letters "O". Indeed, we can always find a special point inside each letter "O" with both coordinates being rational numbers. As circles do not overlap, no two circles can share the same special point. The set of ordered pairs of rational numbers is countable, thus this set of letters "O" has to be countable.
Now let us move to a more interesting question: how many disjoint letters "T" can you draw on a plane? Let us define the letter "T" as two perpendicular line segments, where the end point of one of the segments is the middle point of the other. Prove that the letter "T" is unstackable.
Can you analyze the whole alphabet for stackability? It doesn't matter which alphabet — you just need to define the drawing of every letter in some reasonable manner.
My real question is, can you define the drawings of English letters in such a way that they are recognizable and the number of stackable letters is maximized? What is the biggest number of letters that you can make stackable?
I brought up this subject to my son Sergei one fine morning. As a result we came up with the following breakfast theorem: Stackable letters are topologically equivalent to a line segment or a circle.
And here is our proof. If the letter in question has a part which is topologically equivalent to "T", then the letter is not stackable, because "T" is not stackable.
Fortunately, or unfortunately, this is not the whole story. The stackability of each letter depends on how you define its shape. There are two groups of letters in the English alphabet that you can make stackable. The first group consists of letters like "V" that can be described as a function on a segment and stacked as a parallel translation of the same letter. The second group, like letter "O", can be described as a function of an angle in polar coordinates, and stacked as a dilation of the same letter.
It is clear that this doesn't cover all cases. For example, a piece of a spiral can be stackable — you stack it by rotating it.
I invite my readers to define two different homeomorphic shapes for the same letter — stackable and unstackable.
I just watched the film Mackenna's Gold for the first time. I would have liked it, if not for the sunrise. It is a treasure-hunting movie with gold lying around in a hidden canyon. The secret entrance to the canyon is revealed by the shadow of a big rock tower at the moment of sunrise.
The problem with this clue is that the azimuth of the sunrise differs depending on the day of the year. For example, at the latitude of Cairo, Tel Aviv or Los Angeles, the sunrise azimuth changes from 116 degrees to 62 degrees as the seasons change. This is more than a 40 degree span!
In any map where directions include a long shadow at sunrise, it should include the day of the year. To be more precise, the trajectory — of a given spot on Earth — around the Sun is not periodic. That means the Sun never rises at the exact same azimuth twice. If we are talking about the approximate azimuth, then the Sun rises in the same region two time periods per year. These periods are mirror reflections of each other, with the winter solstice as their focal point. That means MacKenna and his companions needed to wait for several months for the right moment.
I wonder whether the filmmakers knew about this mistake. I see two possibilities.
The first one is that no one noticed. This is very bad. It confirms that this country is illiterate. In fact, it is worse than that, since you don't really need an education to know that sunrise and sunset happen at different points in the sky depending on the time of year. You just need to look out your window from time to time and pay attention.
The second possibility is that someone noticed, but the filmmakers decided to proceed with it anyway, on the assumption that the audience is too dumb to detect the error. Although there are Internet discussions of goofs in this movie, I was disappointed that I didn't find any complaints about this mistake.
George Lucas borrowed many ideas for the Indiana Jones movies from Mackenna's Gold. In particular, for Raiders of the Lost Ark he borrowed the sunrise mistake without the sunrise itself. In the movie the Sun is supposed to penetrate the crystal in the headpiece of the Staff of Ra and reveal the location of the Well of Souls. To do this, the Staff must be placed in a specific spot in the map room at a certain time of day.
The fact that the poetic idea of a sunrise was removed probably means that they knew that it was a mistake. It was replaced by a non-poetic certain time of day. But they kept the mistake. The Sun doesn't repeat its trajectory every day. Like MacKenna, Indiana Jones would have needed to wait in the map room for several months for the Sun to be in the right spot. George Lucas opted for a fast-paced movie that disregards the laws of physics. The mystery of this movie for me is: Does anyone care?
Romanian Masters in Mathematics might become the most prestigious math competition for high school students. Romania invites teams from the 20 best countries from the previous year's International Math Olympiad. This way they guarantee that all the competitors are extremely strong and they can give more difficult problems than the usual IMO problems.
This year they held their second competition and my son, Sergei Bernstein, was invited to join the USA team. Here is one of the problems:
For a finite set X of positive integers, define ∑(X) as the sum of arctan(1/x) for all elements x in X. Given a finite set S, such that ∑(S) < π/2, prove that there exists a finite set T such that S is a subset of T and ∑(T) = π/2.
The official solution involved a tedious greedy algorithm. My son, Sergei, got an extra point for his unique solution, which was very different from the official one. Here's his solution:
To an integer x we associate a complex number x + i, which in polar coordinates is r(cosθ + i sinθ). Note that θ equals arctan(1/x). That means we can interpret ∑(X) as the angle in the polar form of ∏(x+i) — the product of (x+i) for all x in X.
We are given a set S with elements sj such that ∏(sj+i) has a positive real part, and we need to find other elements tk, such that ∏(sj+i) multiplied by ∏(tk+i) has real part 0.
But we know that the ∏(sj+i) = a + bi, for some integers a and b. I claim that we can always find a positive integer y, so that (a + bi)(y + i) has a smaller real part than a.
Note that ∑(S) < π/2, hence a and b are positive. By an ever so slightly modified version of the division algorithm we can find integers q and r such that b = aq + r, 0 < r ≤ a. Now simply set y equal to q + 1 (which is a positive integer). Then the real part of (a + bi)(y + i) equals ay – b = a – r, and is a non-negative number less than a.
Now we just repeat the process, which obviously has a finite number of steps.
My son's solution wasn't complete. The problem talked about sets of numbers and that implies that the numbers should be distinct. I leave it to my readers to finish this solution for distinct numbers.
This story happened in the summer of 1975. I was 16. Before that, I was naive and brainwashed; by the end of the summer I had grown up. All that summer I was stunned and didn't know what to do as I watched this story unfold.
I was invited to the summer training camp for the International Math Olympiad. There I became friends with a fellow team member Sasha (Alexander) Reznikov. Sasha had dreamed of being a mathematician from chil