This blog has a modern version at http://blog.tanyakhovanova.com/, where you can leave comments. This page contains the copies of recent blog entries. The older copies are here:
If you enjoy this page you can support it by shopping at amazon through this link. Thank you.
* * *
Business plan:
* * *
* * *
A cafe patron ordered a pastry, then changed his mind and replaced it with a cup of coffee. When he finished his coffee, he started leaving without paying. The waiter approached him:
—You didn't pay for coffee!
—But I had it instead of the pastry.
—You didn't pay for the pastry either!
—But I didn't have the pastry.
* * *
At a farmers market stand there is a sign: 1 melon—3 dollars, 3 melons—10 dollars. A client requests one melon and pays 3 dollars, then repeats the procedure two more times. Then he says: "I bought three melons for 9 dollars, while you are trying to sell them for 10 dollars. This is really stupid." The farmer talks to himself: This happens all the time: they buy three melons instead of one, and try to teach me how to make money.
* * *
If the government listens in on my phone conversations, should they be paying half of my phone bill?
* * *
To get to free downloads, please, enter your credit card number.
* * *
The biggest lie of the century, "I have read and agree to the terms of ..."
* * * (submitted by Sam Steingold)
Ignorance: If your poker opponent got lucky cards four times in a row, he must get lousy cards now.
Knowledge: Nope, the deals are independent; prior observations have no bearing on the next deal.
Wisdom: The opponent is cheating; get away from the table now!
I recently posted two geometry problems. Now is the time for solutions:
Problem 1. Is it possible to put positive numbers at the vertices of a triangle so that the sum of two numbers at the ends of each side is equal to the length of the side?
One might guess that the following numbers work: (a+b-c)/2, (b+c-a)/2 and (c+a-b)/2, where a, b, and c are the side lengths. But there exists a geometric solution: Construct the incircle. The tangent points divide each side into two segment, so that the lengths of the segments ending at the same vertex are the same. Assigning this length to the vertex solves the problem. Surprisingly, or not surprisingly, this solution gives the same answer as above.
Problem 2. Prove that it is possible to assign a number to every edge of a tetrahedron so that the sum of the three numbers on the edges of every face is equal to the area of the face.
The problem is under-constrained: there are six sides and four faces. There should be many solutions. But the solution for the first problem suggests a similar idea for the second problem: Construct the inscribed sphere. Connect a tangent point on each face to the three vertices on the same face. This way each face is divided into three triangles. Moreover, the lengths of the segments connecting the tangent points to a vertex are the same. Therefore, two triangles sharing the same edge are congruent and thus have the same area. Assigning this area to each edge solves the problem.
There are many solutions to the second problem. I wonder if for each solution we can find a point on each face, so that the segments connecting these points to vertices divide the faces into three triangles in such a way that triangles sharing an edge are congruent. What would be a geometric meaning of these four points?
I was on the writing team for the 2018 MIT Mystery Hunt. I am pleased that the hunt got very positive reviews from the participants. I spent tons of hours working on the hunt and it is good that folks liked it. I edited and tested a lot of puzzles. Here is my review of these year's puzzles that are math-related.
I already posted an essay about the puzzles I wrote myself. Four of my five puzzles are math-related, so I am including them below for completeness. I will mention the topic of each puzzle unless it is a spoiler.
I start with Nikoli-type puzzles. Four elegant Nikoli-type puzzles were written or cowritten by Denis Auroux. In all of them the rules of the logic are stated at the beginning. That means the logic part doesn't contain a mystery and can be solved directly.
There were several puzzles that were very mathematical.
There were also some math-related or computer-sciency puzzles.
There were also several decryption puzzles:
Here is a famous math problem I never before wrote about:
Puzzle. Five pirates discovered a treasure of 100 gold coins. They decide to split the coins using the following scheme. The most senior pirate proposes how to share the coins, and all the pirates vote for or against it. If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the next most senior pirate making a proposal.
As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins whether he votes for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard. Assuming that all five pirates are intelligent, rational, greedy, and do not wish to die, how will the coins be distributed?
You can find the solution in many places including Wikipedia's Pirate game. The answer is surprising: the most senior pirate gets 98 coins, and the third and the fifth pirates by seniority get one coin each. I always hated this puzzle, but never bothered to think through and figure out why. Now I know.
This puzzle emphasizes the flaws of majority voting. The procedure is purely democratic, but it results in extreme inequality.
That means a democracy needs to have a mechanism to prohibit the president from blatantly benefiting himself. With our current president these mechanisms stopped working. Given that Trump does everything to enrich himself, the pirates puzzle tells us what to expect in the near future.
We, Americans, will lose everything: money, clean air and water, national parks, future climate, health, social security, and so on, while Trump will make money.
I was on the writing team of this year's hunt, which was based on the movie "Inside Out." One of our goals was to create an easy first round to allow small teams to have a full hunt experience. Our first round consisted of 34 puzzles related to five basic emotions: joy, sadness, disgust, fear, and anger. Each emotion had its own meta puzzle. And the round had a meta-meta puzzle and a runaround. As I tend to write easy puzzles, I contributed three puzzles to this emotions round. The puzzles had references to corresponding emotions that were not needed for the solve path. They were inserted there for flavor.
I also wrote another easy puzzle called A Tribute: 2010-2017 (jointly with Justin Melvin, Wesley Graybill, and Robin Diets ). Though the puzzle is easy, it is useful in solving it to be familiar with the MIT mystery hunt. This is why the puzzle didn't fit the first emotions round.
I also wrote a very difficult puzzle called Murder at the Asylum. This is a monstrosity about liars and truth-tellers.
In mathematics one of the most important questions is why. Let us consider a problem:
Problem. A number has three hundred ones and three hundred zeroes. Can it be a square?
The solution goes like this. Consider divisibility of this number by 9. The sum of the digits is 300. That means the number is divisible by 3, but not by 9. Therefore, it can't be a square.
Why do we consider divisibility by 9? The divisibility by 9 is a very powerful tool, but why was it the first thing that came to my mind? The divisibility by 9 doesn't depend on the order of the digits. Whenever I see a problem where the question talks about digits that can be in any order, the first tool to use is the divisibility by 9.
The why question, is very important in mathematics. But it is also very important in life. It took me many years to start asking why people did this or that. I remember my mom was visiting me in the US. Every time I came back from work, she complained that she was tired. Why? Because she did the laundry in the bath tub. She wouldn't use my washing machine, because she didn't have such a thing in Russia. I promised her that I'd do the laundry myself when there was a sufficient pile. However, she insisted that the dirty clothes annoyed her. I would point that my water bill went up. And so on.
We argued like this every day. We were both frustrated. Then I asked myself why. Why does she do the laundry? The answer was there. She wanted to be helpful. I calmed down and stopped arguing with her. I sucked it up and paid the water bills. Her time with me turned into the most harmonious visit we ever had. Unfortunately, it was the last.
Puzzle. Alice, Bob, and Charlie are at Alice's house. They are going to Bob's house which is 33 miles away. They have a 2-seat scooter which rides at 25 miles per hour with 1 rider on it; or, at 20 miles per hour with 2 riders. Each of the 3 friends walks at 5 miles per hour. How fast can all three of them make it to Bob's house?
* * * (submitted by Sam Steingold)
I can count to 1023 on my 10 fingers. The rudest number is 132.
* * *
I kept forgetting my password, so I changed it to "incorrect". Now, when I make a mistake during login, my computer reminds me: "Your password is incorrect."
* * *
—You promised me 8% interest, and in reality it is 2%.
—2 is 8—to some degree.
* * * (submitted by Sam Steingold)
Quantum entanglement is simple: when you have a pair of socks and you put one of them on your left foot, the other one becomes the "right sock," no matter where it is located in the universe.
* * *
Teacher:
—I keep telling my students that one half can't be larger or smaller than the other. Still the larger half of my class doesn't get it.
This famous trick puzzle is very old:
Puzzle. The professor is watching across a field how the son of the professor's father is fighting with the father of the professor's son. How is this possible?
This puzzle is tricky only because of gender-bias. Most people assume that the professor is male and miss the obvious intended solution, in which a female professor is watching her brother fighting with her husband.
I just gave this problem on a test. Here are other answers that I received.
Years ago people couldn't figure out this puzzle at all. So there has been progress. I was glad that my students suggested so many ideas that work. Nonetheless, many of them revealed their gender-bias by initially assuming that the professor is a man.
I can't wait until this puzzle stops being tricky.
Puzzle. There are five houses of different colors next to each other equally spaced on the same road. In each house lives a man of a different profession.
Who lives in the white house?
Correction Nov 11, 2017. Replaced "the same distance from" with "halfway between" to eliminate the possibility of the plumber living in the yellow house. Thank you to my readers for catching this mistake and to Smylers for suggesting a correction.
Problem. Invent a connected shape made out of squares on the square grid that cannot be cut into dominoes (rectangles with sides 1 and 2), but if you add a domino to the shape then you can cut the new bigger shape.
This problem reminds me of another famous and beautiful domino-covering problem.
Problem. Two opposite corner squares are cut out from the 8 by 8 square board. Can you cover the remaining shape with dominoes?
The solution to the second problem is to color the shape as a chess board and check that the number of black and white squares is not the same.
What is interesting about the first problem is that it passes the color test. It made me wonder: Is there a way to characterize the shapes on a square grid that pass the color test, but still can't be covered in dominoes?
* * *
Don't anthropomorphize computers: They don't like it.
* * *
I do not have dreams any more. What did I do wrong to make them delete my account?
* * *
How to restore justice: Create a folder named Justice. Delete it. Go to the trash bin and click restore.
* * *
An asocial network: When you sign up, you are friends with everyone. Then you send un-friend requests.
I already wrote about two puzzles that Derek Kisman made for the 2013 MIT Mystery Hunt. The first puzzle is now called the Fractal Word Search. It is available on the Hunt website under its name In the Details. I posted one essay about the puzzle and another one describing its solution. The second puzzle, 50/50, is considered one of the most difficult hunt puzzles ever. Unfortunately, the puzzle is not available, but my description of it is.
Today let's look at the third puzzle Derek made for the 2013 Hunt, building on an idea from Tom Yue. This is a non-mathematical crossword puzzle. Derek tends to write multi-layered puzzles: You think you've got the answer, but the answer you've got is actually a hint for the next step.
Often multi-layered puzzles get solvers frustrated, but the previous paragraph is a hint in itself. If you expect the difficulty, you might appreciate the fantastic beauty of this puzzle.
Welcome to Ex Post Facto.
Every time I visit Princeton, or otherwise am in the same city as my friend John Conway, I invite him for lunch or dinner. I have this rule for myself: I invite, I pay. If we are in the same place for several meals we alternate paying. Once John Conway complained that our tradition is not fair to me. From time to time we have an odd number of meals per visit and I end up paying more. I do not trust my memory, so I prefer simplicity. I resisted any change to our tradition. We broke the tradition only once, but that is a story for another day.
Let's discuss the mathematical way of paying for meals. Many people suggest using the Thue-Morse sequence instead of the alternating sequence of taking turns. When you alternate, you use the sequence ABABAB…. If this is the order of paying for things, the sequence gives advantage to the second person. So the suggestion is to take turns taking turns: ABBAABBAABBA…. If you are a nerd like me, you wouldn't stop here. This new rule can also give a potential advantage to one person, so we should take turns taking turns taking turns. Continuing this to infinity we get the Thue-Morse sequence: ABBABAABBAABABBA… The next 2^{n} letters are generated from the first 2^{n} by swapping A and B. Some even call this sequence a fair-share sequence.
Should I go ahead and implement this sequence each time I cross paths with John Conway? Actually, the fairness of this sequence is overrated. I probably have 2 or 3 meals with John per trip. If I pay first every time, this sequence will give me an advantage. It only makes sense to use it if there is a very long stretch of meals. This could happen, for example, if we end up living in the same city. But in this case, the alternating sequence is not so bad either, and is much simpler.
Many people suggest another use for this sequence. Suppose you are divorcing and dividing a huge pile of your possessions. A wrong way to do it is to take turns. First Alice choses a piece she wants, then Bob, then Alice, and so on. Alice has the advantage as the first person to choose. An alternative suggestion I hear in different places, for example from standupmaths, is to use the Thue-Morse sequence. I don't like this suggestion either. If Alice and Bob value their stuff differently, there is a better algorithm, called the Knaster inheritance procedure, that allows each of them to think they are getting more than a half. If both of them have the same value for each piece, then the Thue-Morse sequence might not be good either. Suppose one of the pieces they are dividing is worth more than everything else put together. Then the only reasonable way to take turns is ABBBB….
The beauty of the Thue-Morse sequence is that it works very well if there are a lot of items and their consecutive prices form a power function of a small degree k, such as a square or a cube function. After 2^{k+1} turns made according to this sequence, Alice and Bob will have a tie. You might think that if the sequence of prices doesn't grow very fast, then using the Thue-Morse sequence is okay.
Not so fast. Here is the sequence of prices that I specifically constructed for this purpose: 5,4,4,4,3,3,3,2,2,2,2,1,1,0,0,0. The rule is: every time a turn in the Thue-Morse sequence switches from A to B, the value goes down by 1. Alice gets an extra 1 every time she is in the odd position. This is exactly half of her turns. That is every four turns, she gets an extra 1.
If the prices grow faster than a power, then the sequence doesn't work either. Suppose your pieces have values that form a Fibonacci sequence. Take a look at what happens after seven turns. Alice will have pieces priced F_{n} + F_{n-3} + F_{n-5} + F_{n-6}. Bob will have F_{n-1} + F_{n-2} + F_{n-4}. We see that Alice gets more by F_{n-3}. This value is bigger than the value of all the leftovers together.
I suggest a different way to divide the Fibonacci-priced possessions. If Alice takes the first piece, then Bob should take two next pieces to tie with Alice. So the sequence might be ABBABBABB…. I can combine this idea with flipping turns. So we start with a triple ABB, then switch to BAA. After that we can continue and flip the whole thing: ABBBAABAAABB. Then we flip the whole thing again. And again and again. At the end we get a sequence that I decided to call the Fibonacci fair-share sequence.
I leave you with an exercise. Describe the Tribonacci fair-share sequence.
A while ago I posted my second favorite problem from the 2015 All-Russian Math Olympiad:
Problem. A coin collector has 100 coins that look identical. He knows that 30 of the coins are genuine and 70 fake. He also knows that all the genuine coins weigh the same and all the fake coins have different weights, and every fake coin is heavier than a genuine coin. He doesn't know the exact weights though. He has a balance scale without weights that he can use to compare the weights of two groups with the same number of coins. What is the smallest number of weighings the collector needs to guarantee finding at least one genuine coin?
Now it's solution time. First we show that we can do this in 70 weighings. The strategy is to compare one coin against one coin. If the scale balances, we are lucky and can stop, because that means we have found two real coins. If the scale is unbalanced, the heavier coin is definitely fake and we can remove it from consideration. In the worst case, we will do 70 unbalanced weighings that allow us to remove all the fake coins, and we will find all the real coins.
The more difficult part is to show that 69 weighings do not guarantee finding the real coin. We do it by contradiction. Suppose the weights are such that the real coin weighs 1 gram and the i-th fake coin weighs 100^{i} grams. That means whatever coins we put on the scale, the heaviest pan is the pan that has the fake coin with the largest index among the fake coins on the scale.
Suppose there is a strategy to find a real coin in 69 weighings. Given this strategy, we produce an example designed for this strategy, so that the weighings are consistent, but the collector cannot find a real coin.
For the first weighing we assign the heaviest weight, 100^{70} to one of the coins on the scale and claim that the pan with this coin is heavier. We continue recursively. If a weighing has the coins with assigned weights, we pick the heaviest coin on the pans and claim that the corresponding pan is heavier. If there are no coins with assigned weights on pans, we pick any coin on the pans, assigned the largest available weight to it and claim that the corresponding pan is heavier.
After 69 weighings, not more than 69 coins have assigned weights, while all the weighings are consistent. The rest of the coins can have any of the leftover weights. For example, any of the rest of the coins can weigh 100 grams. That means that there is no coin that is guaranteed to be real.
I stumbled upon a couple of problems that I like while scanning the Russian website of Math Festival in Moscow 2014. The problems are for 7 graders.
Problem. Inside a 5-by-8 rectangle, Bart draws closed paths that follow diagonals of 1-by-2 rectangles. Find the longest possible path.
This problem is really very difficult. The competition organizers offered an extra point for every diagonal on top of 16. The official solution has 24 diagonals, but no proof that it's the longest. I'm not sure anyone knows if it is the longest.
Here is another problem:
Problem. Alice and Bob are playing a game. They start with two numbers: 2014 and 2015. In one move a player can do one of two things:The winner is the person who is the first to get a one-digit number. Assuming that Alice starts, who wins?
- subtract one of the numbers by one of the non-zero digits in any of the two numbers or,
- divide one number by two if the number is even.
The year is 1994. The man on the left is my first husband, Alexander Goncharov. Although we were out of touch for a decade, when I married my third husband, Joseph Bernstein (on the right), Goncharov started visiting us. It wasn't me he was interested in: he wanted to talk mathematics with my husband. I found this situation hilarious, so I took this photo.
But that's not all. My second husband, Andrey Radul, is not in the picture. But all four of us were students of Israel Gelfand. In short, my three ex-husbands and I are mathematical siblings — that is, we are all one big happy mathematical family.
The Best Writing on Mathematics 2016 is out. I am happy that my paper The Pioneering Role of the Sierpinski Gasket is included. The paper is written jointly with my high-school students Eric Nie and Alok Puranik as our PRIMES-2014 project.
At the end of the book there is a short list of notable writings that were considered but didn't make it. The "short" list is actually a dozen pages long. And it includes two more papers of mine:
To continue bragging, I want to mention that my paper A Line of Sages was on the short list for 2015 volume. And my paper Conway's Wizards was included in the 2014 volume.
I like Odd-One-Out puzzles that are ambiguous. That is why I bought the book Which One Doesn't Belong? Look at the cover: which is the odd one out? The book doesn't include answers, but it has nine more examples in each of which there are several possible odd-one-outs.
I married an American citizen and moved to the US in 1990. At the time I was a very patriotic Russian. It took me a year of pain to realize that some of my ideas had been influenced by Soviet propaganda. After I washed away the brainwashing, I fell in love with the US. For 25 years I thought that America was great. Not anymore.
For the last several months I've been worried as never before in my life. I feel paralyzed and sick. To help myself I decided to put my feelings in words.
World War. My mom was 15 when World War II started. The war affected her entire life, as well as the lives of everyone in the USSR. Every now and then my mom would tell me, "You are lucky that you are already 20 and you haven't witnessed a world war." I moved to the US while my mom stayed back in Russia. From time to time I tell myself something like, "I am lucky that halfway through my expected lifetime, I haven't had to live through a world war." It's been more than 70 years since WWII ended. To maintain the peace is a difficult job. Everything needs to be in balance. Trump is disrupting this balance. I am worried sick that my children or grandchildren will have to witness a major war.
The Red Button. I've noticed that, as a true showman, Trump likes misdirecting attention from things that worry him to fantastic plot twists that he invents. What's the best way to make people forget about his tax returns? It's the nuclear button. Dropping a nuclear bomb some place will divert people from thinking about his tax returns. As his plot twists are escalating, is he crazy enough to push the button?
Climate. The year 2014 was the warmest on record. The year 2015 was even warmer. And last year, 2016, was even warmer than that. I remember Vladimir Arnold's class on differential equations. He talked about a painting that had been hanging on a wall for 20 years. Then it unexpectedly fell off. Mathematics can explain how such catastrophic events can happen. I keep thinking about our Earth: melting ice, dead reefs, fish eating plastic, and so much more. My grandchildren might not be able to enjoy beaches and forests the way I did. What if, like the fallen painting, the Earth can spiral out of control and completely deteriorate? But Trump is ignoring the climate issues. Does he care about our grandchildren? I am horrified that Trump's policies will push climate catastrophe beyond the point of no return.
The Truth. Wiretapping is not wiretapping. Phony jobs numbers stopped being phony as soon as Trump decided that he deserved the credit. The news is fake when Trump doesn't like it. Trump is a pathological liar; he assaults the truth. Being a scientist I am in search of truth, and Trump diminishes it. I do not understand why people ignore his lies. Two plus two is four whether you are a democrat, or a republican, or whomever. Facts are facts, alternative facts are lies. I am scared that lies have become acceptable and no one cares about the truth any more.
Russia. I lived in Russia for the first unhappy half of my life, and in the US for the second happy half. I do not want to go back. There is something fishy between Putin and Trump. Whether it is blackmail or money, or both, I do not know the details yet, But Trump is under Putin's influence. Trump didn't win the elections: Putin won. This horrifies me. I do not want to go back to being under Russian rule.
Gender Issues. I grew up in a country where the idea of a good husband was a man who wasn't a drunkard. That wasn't enough for me. I dreamed of a relationship in which there would be an equal division of work, both outside and inside the home. I could not achieve that because in Russian culture both people work full-time and the wife is solely responsible for all the house chores. Moreover, Russia was much poorer than the US: most homes didn't have washing machines; we never heard of disposable diapers; and there were very long lines for milk and other necessities.
The life in USSR was really unfair to women. Most women had a full-time job and several hours of home chores every day. When I moved to the US, I thought I was in paradise. Not only did I have diapers and a washing machine, I was spending a fraction of the time shopping, not to mention that my husband was open to helping me, and didn't mind us paying for the occasional babysitter or cleaner.
For some time I was blind to gender issues in the US because it was so much better. Then I slowly opened my eyes and became aware of the bias. For some years it has felt like gender equity was improving. Now, with a misogynistic president, I feel that the situation might revert to the dark ages. When women are not happy, their children are not happy, and they grow up to be not happy. If the pursuit of happiness is the goal, the life has to be fair to all groups. But Trump insults not only women but also immigrants, Muslims, members of the LGBTQ community, as well as the poor and the sick. The list is so long, that almost everyone is marginalized. This is not a path towards a happy society.
Democracy. Trump attacks the press and attempts to exclude them. Trump has insulted the intelligence community and the courts. He seems to be trying to take more power to the presidency at the expense of the other branches of government. He ignores his conflicts of interest. Trump disregards every rule of democracy and gets away with it. I am horrified that our democracy is dying.
Tax Returns. Trump's tax returns could either exonerate him or prove that he is Putin's puppet. The fact that he is hiding the returns makes me believe that the latter is more probable. Why the Republicans refuse to demand to see his returns is beyond my understanding.
Corruption. Trump does so many unethical things. Most of his decisions as president seem to be governed by Trump trying to get richer. Let us consider his hotel in Azerbaijan—a highly corrupt country. Having lived in a highly corrupt country myself, I know how it works. For example, an Azerbaijani government official who has access to their country's money can make a deal that involves a personal kickback. This means that their government is paying more than necessary for a service or product in order to cover that kickback. This is how national money makes its way into individual pockets. Since all the deals in Azerbaijan are reputed to be like that, I imagine that when Trump built his hotel there, the Trump organization was overpaid in order to cover the bribe to local officials. Will our country become as corrupt as Azerbaijan?
Americans. The biggest shock of the election was that so many people were so gullible and actually voted for Trump. They didn't see that his agenda is focused on his own profit, and that he lies and makes promises he doesn't plan to deliver. It really terrifies me that there are some people who are not gullible but still voted for Trump.
Is there hope?
I recently wrote about my way of playing Nim against a player who doesn't know how to play. If my move starts in an N-position, then I obviously win. If my move starts in a P-position, I would remove one token hoping that more tokens for my opponent means more opportunity for them to make a mistake. But which token to remove? Does it make a difference from which pile I choose?
Consider the position (2,4,6). If I take one token, my opponent has 11 different moves. If I choose one token from the first or the last pile, my opponent needs to get to (1,4,5) not to lose. If I choose one token from the middle pile, my opponent needs to get to (1,3,2) not to lose. But the first possibility is better, because there are more tokens left, which gives me a better chance to have a longer game in case my opponent guesses correctly.
That is the strategy I actually use: I take one token so that the only way for the opponent to win is to take one token too.
This is a good heuristic idea, but to make such a strategy precise we need to know the probability distribution of the moves of my opponent. So let us assume that s/he picks a move uniformly at random. If there are n tokens in a N-position, then there are n − 1 possible moves. At least one of them goes to a P-position. That means my best chance to get on the winning track after the first move is not more than n/(n−1).
If there are 2 or 3 heaps, then the best strategy is to go for the longest game. With this strategy my opponent always has exactly one move to get to a P-position, I win after the first turn with probability n/(n−1). I lose the game with probability 1/(n−1)!!.
Something interesting happens if there are more than three heaps. In this case it is possible to have more than one winning move from a N-position. It is not obvious that I should play the longest game. Consider position (1,3,5,7). If I remove one token, then my opponent has three winning moves to a position with 14 tokens. On the other hand, if I remove 2 tokens from the second or the fourth pile, then my opponent has one good move, though to a position with only 12 tokens. What should I do?
I leave it to my readers to calculate the optimal strategy against a random player starting from position (1,3,5,7).
It is rare when a word equation coincides with a number equation.
Problem. A store sells letter magnets. The same letters cost the same and different letters might not cost the same. The word ONE costs 1 dollar, the word TWO costs 2 dollars, and the word ELEVEN costs 11 dollars. What is the cost of TWELVE?
Alex Bellos wrote a puzzle book Can You Solve My Problems? Ingenious, Perplexing, and Totally Satisfying Math and Logic Puzzles The book contains a mixture of famous puzzles and their solutions. Some of the puzzles are not mathematical in the strictest sense, but still have an appeal for mathematicians. For example, which integer comes up first when you alphabetize all the integers up to a quadrillion?
Recognize the puzzle on that book cover? You're right! That's my Odd One Out puzzle. Doesn't it look great in lights on that billboard in London?
Mine isn't the only terrific puzzle in the book. In fact, one of the puzzles got my special attention as it is related to our current PRIMES polymath project. Here it is:
A Sticky Problem. Dick has a stick. He saws it in two. If the cut is made [uniformly] at random anywhere along the stick, what is the length, on average, of the smaller part?
The beautiful Pascal triangle has been around for many years. Can you say something new about it?
Of course you can. Mathematicians always find new way to look at things. In 2012 RSI student, Kevin Garbe, did some new and cool research related to the triangle. Consider Pascal's triangle modulo 2, see picture which was copied from a stackexchange discussion.
A consecutive block of m digits in one row of the triangle modulo 2 is called an m-block. If you search the triangle you will find that all possible binary strings of length 2 are m-blocks. Will this trend continue? Yes, you can find any possible string of length 3, but it stops there. The blocks you can find are called accessible blocks. So, which blocks of length 4 are not accessible?
There are only two strings that are not accessible: 1101 and 1011. It is not surprising that they are reflections of each other. Pascal's triangle respects mirror symmetry and the answer should be symmetric with respect to reflection.
You can't find these blocks on the picture, but how do we prove that they are not accessible, that is, that you can't ever find them? The following amazing property of the triangle can help. We call a row odd/even, if it corresponds to binomial coefficients of n choose something, where n is an odd/even number. Every odd row has every digit doubled. Moreover, if we take odd rows and replace every double digit with its single self we get back Pascal's triangle. Obviously the two strings 1101 and 1011 can't be parts of odd rows.
What about even rows? The even rows have a similar property: every even-indexed digit is a zero. If you remove these zeros you get back Pascal's triangle. The two strings 1101 and 1011 can't be part of even rows. Therefore, they are not accessible.
The next question is to count the number of inaccessible blocks of a given length: a(n). This and much more was done by Kevin Garbe for his RSI 2012 project. (I was the head mentor of the math projects.) His paper is published on the arxiv. The answer to the question can be found by constructing recurrence relations for odd/even rows. It can be shown that a(2r) = 3a(r) + a(r+1) − 6 and a(2r+1) = 3a(r) + 2a(r+1) − 6. As a result the number of inaccessible blocks of length n is n^{2} − n + 2. I wonder if there exists a direct proof of this formula without considering odd and even rows separately.
This RSI result was so pretty that it became a question at our entrance PRIMES test for the year 2013. In the test we changed the word accessible to admissible, so that it would be more difficult for applicants to find the research. Besides, Garbe's paper wasn't arxived yet.
The pretty picture above is from the stackexchange, where one of our PRIMES applicants tried to solicit help in solving the test question. What a shame.
I picked four problems that I liked from the Moscow Math Olympiad 2016:
Problem 1. Ten people are sitting around a round table. Some of them are knights who always tell the truth, and some of them are knaves who always lie. Two people said, "Both neighbors of mine are knaves." The other eight people said, "Both neighbors of mine are knights." How many knights might be sitting around the round table?
Problem 2. Today at least three members of the English club came to the club. Following the tradition, each member brought their favorite juice in the amount they plan to drink tonight. By the rules of the club, at any moment any three members of the club can sit at a table and drink from their juice bottles on the condition that they drink the same amount of juice. Prove that all the members can finish their juice bottles tonight if and only if no one brings more than the third of the total juice brought to the club.
Problem 3. Three piles of nuts together contain an even number of nuts. One move consists of moving half of the nuts from a pile with an even number of nuts to one of the other two piles. Prove that no matter what the initial position of nuts, it is possible to collect exactly half of all the nuts in one pile.
Problem 4. N people crossed the river starting from the left bank and using one boat. Each time two people rowed a boat to the right bank and one person returned the boat back to the left bank. Before the crossing each person knew one joke that was different from all the other persons' jokes. While there were two people in the boat, each told the other person all the jokes they knew at the time. For any integer k find the smallest N such that it is possible that after the crossing each person knows at least k more jokes in addition to the one they knew at the start.
Spoiler for Problem 2. I want to mention a beautiful solution to problem 2. Let's divide a circle into n arcs proportionate to the amount of juice members have. Let us inscribe an equilateral triangle into the circle. In a general position the vertices of the triangle point to three distinct people. These are the people who should start drinking juices with the same speed. We rotate the triangle to match the drinking speed, and as soon as the triangle switches the arcs, we switch drinking people correspondingly. After 120 degree rotation all the juices will be finished.
I already posted a funny true story that Smullyan told me when I last visited him. Raymond Smullyan died recently at the age of 97 and my mind keeps coming back to this last visit.
The year was 2012 and I was about to drive back to Boston after my talk at Penn State. Smullyan's place in the Catskills was on the way—sort of. I wanted to call him, but I was apprehensive. Raymond Smullyan had a webpage on which his email was invisible. You could find his email address by looking at the source file or by highlighting empty space at the bottom of the page. Making your contact information invisible sends a mixed message.
While this was a little eccentric, it meant that only people who were smart enough to find it, could access his email address. I already knew his email because he had given it to me along with his witty reply to my blog post about our meeting at the Gathering for Gardner in 2010.
In our personal interactions, he always seemed to like me, so I called Raymond and arranged a visit for the next day around lunch time. When I knocked on his door, no one answered, but the door was open, and since Smullyan was expecting me, I walked right in. "Hello? Anyone there? Hello? Hello?" As I wandered around the house, I saw an open bedroom door and inside Smullyan was sleeping. So I sat down in his library and picked up a book.
When he woke up, he was happy to see me, and he was hungry. He told me that he didn't eat at home, so we should go out together for lunch. I was hungry too, so I happily agreed. Then he said that he wanted to drive. I do not have a poker face, so he saw the fear in me. My only other trip with a nonagenarian driver flashed in front of my eyes. The driver had been Roman Totenberg and it had been the scariest drive I have ever experienced.
I said that I wanted to drive myself. Annoyed, Raymond asked me if I was afraid of him taking the wheel. I told him that I have severe motion sickness and always prefer to drive myself. Raymond could see that I was telling the truth. I got the impression that he was actually relieved when he agreed to go in my car.
We went to Selena's Diner. He took out playing cards with which he showed me magic tricks. I showed him some tricks too. This was probably a bad move as he abandoned me to go to the neighboring table to show his magic tricks to a couple of young girls. They were horrified at first"his unruly hair, his over-the-top energy, his ebullient behavior"but between me and the waitress, we quickly reassured them. The girls enjoyed the tricks, and I enjoyed my visit.
Like many people, I was appalled by Trump's immigration ban. On the Internet I found many essays that explained that he did not include in the ban those majority-Muslim countries in which he has business interests. See for example, an article at Forbes with a nice map, and an article at NPR.
Now the countries that are excluded are motivated to continue to support Trump's businesses, and to offer him bribes and good deals in exchange for staying out of the ban. The countries on the list are also motivated to approach Trump and offer him a sweet business deal.
So even if the courts stopped the ban, he has already succeeded in showing every country in the world that to be on his good side requires that they pay up. And China got the hint and granted Trump a trademark he's been seeking for a decade.
Looks like Trump's vision of a great America is a very rich Mr Trump.
I recently posted the following puzzle:
Puzzle. We have 3^{2n} identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.
Here is my son Sergei's solution. Divide the coins into nine groups of equal size and number the groups in ternary: 00, 01, 02, 10, 11, 12, 20, 21, and 22. On each scale we put three groups versus three groups. On the first scale we compare the three groups that start with 1 with the three groups that start with 2. For the second scale we do the same using the last digit instead of the first one, and for the third scale we use the sum of two digits modulo 3. Any pair of scales, if they are assumed to be normal, would point to one out of nine groups as the group containing the fake coin.
If all three pairs of scales agree on one group, then this is the group containing the fake coin. Thus in three weighings, we reduce the number of groups of coins by a factor of nine. If the pairs of scales do not agree, then the random scale produced a wrong weighing and thus can be found out. How do we do that? We have three out of nine groups of coins each of which might contain the fake coin. We compare two of the groups on all three scales. This way we know exactly which group contains the fake coin and, consequently, which scale generated a wrong weighing. If we know the random scale, we can speed up the rest of the process of finding the fake coin. Thus in the worst case we require 3n+3 weighings.
The big idea here is that as soon as the random scale shows a wrong weighing result it can be found out. So in the worst case, the random scale behaves as a normal scale and messes things up at the very end. Sergei's solution can be improved to 3n+1 weighings. Can you do that?
The improved solution is written in a paper Взвешивания на «хитрых весах» (in Russian) by Konstantin Knop, that is published in Математика в школе 2009-2. The paper contains an even stronger solution that provides a better asymptotics.
The first time I visited the US was in 1990 at the invitation of an old friend, Joseph Bernstein. After my arrival Joseph proposed and I accepted, but my essay is not about that.
Joseph reintroduced me to his daughter, Mira, who was then in her late teens. I was struck by Mira's charm. I had never before met teenagers like her. Of course, Joseph got points for that as I was hoping to have a child with him. When I moved to the US I met some other kids who were also incredibly charming. It was too late to take points away from Joseph, but it made me realize what a huge difference there was between Soviet and American teenagers. American teenagers were happier, more relaxed, better mannered, and less cynical than Soviet ones.
My oldest son, Alexey, was born in the USSR and moved to the US when he was eight. One unremarkable day when he was in middle school (Baker public school in Brookline), the principle invited me for a chat. I came to the school very worried. The principal explained to me that there was a kid who was bugging Alexey and Alexey pushed him back with a pencil. While the principal proceeded to explain the dangers of a pencil, I tuned out. I needed all my energy to conceal my happy smile. This was one of the happiest moments of my life in the US. What a great country I live in where the biggest worry of a principal in a middle school is the waving of a pencil! I remembered Alexey's prestigious school in Moscow. They had fights every day that resulted in bloody noses and lost teeth. When I complained to his Russian teacher, she told me that it was not her job to supervise children during big breaks. Plus the children needed to learn to be tough. No wonder American children are happier.
I was wondering if there were any advantages to a Soviet upbringing. For one thing, Soviet kids grow up earlier and are less naive. They are more prepared for harsh realities than those American kids who are privileged.
Naive children grow up into naive adults. Naive adults become naive presidents. I watched with pain as naive Bush ("I looked the man in the eye. I found him to be very straightforward and trustworthy.") and naive Obama (Russian reset) misunderstood and underestimated Putin.
Putin is (and, according to Forbes Magazine, has been for the last four years) the most powerful person in the world. Even though the US kept its distance from Russia, he was able to manipulate us from afar. Now that Trump wants to be close to Putin, the manipulation will be even easier. Putin is better at this game. He will win and we will lose.
May 5 of 1955 can be written as 5/5/55. How many times during the 20th century the date in the format month day and the last two digits of the year can be written with the same digit?
I had a distant relative Alla, who was brought up by a single mother, who died in a car crash when the girl was in her early teens. Alla was becoming a sweet and pleasant teenager; she was taken in by her aunt after the accident. Very soon the aunt started complaining that Alla was turning into a cheater and a thief. The aunt found a therapist for Alla, who explained that Alla was stealing for a reason. Because the world had unfairly stolen her mother, Alla felt entitled to compensation in the form of jewelry, money, and other luxuries.
I was reminded of Alla's story when I was reading The (Honest) Truth About Dishonesty: How We Lie to Everyone—Especially Ourselves by Dan Ariely. Ariely discusses a wide range of reasons why honest people cheat. But to me he neglects to look at the most prominent reason. Often honest people cheat when they feel justified and entitled to do so.
One of Ariely’s experiments went like this. One group was asked to write a text avoiding letters x and z. The other group was asked to write a text avoiding letters a and n. The second task is way more difficult and requires more energy. After the tasks were completed the participants were given a test in which they had a chance to cheat. For this experiment, the participants were compensated financially according to the number of questions they solved. Not surprisingly, the second group cheated more. The book concludes that when people are tired, their guard goes down and they cheat more. I do not argue with this conclusion, but I think another reason also contributes to cheating. Have you ever tried to write a text without using the letters a and n? I did:
I should try it here. But this is so difficult. I give up.
My son, Alexey, was way better than me:
First, God brought forth the sky with the world. The world existed without form. Gloom covered the deep. The Spirit of God hovered over the fluids. Quoth God: let there be light. Thus light existed.
Fun as it is, this is cruel and unusual punishment. The request is more difficult than most people expect at an experiment. It could be that participants cheated not only because their capacity for honesty was depleted, but because they felt entitled to more money because the challenge was so difficult.
In another experiment, the participants received a high-fashion brand of sunglasses before the test. Some of them were told that the sunglasses were a cheap imitation of the luxury brand (when they really were not). This group cheated more than the group who thought that they got a real thing. The book concludes that wearing fake sunglasses makes people feel that they themselves are fake and so they care less about their honor. Unfortunately, the book doesn't explain in detail what was actually promised. It looks like the participants were promised high-fashion sunglasses. In this case, the fake group would have felt deceived and might have felt more justified to cheat.
Dear Dan Ariely: May I suggest the following experiment. Invite people and promise them some money for a 15-minute task. Pay them the promised minimum and give them a test through which they can earn more. Construct it so that they can earn a lot more if they cheat. Then make the non-control group wait for half an hour. If I were in this group, I would have felt that I am owed for the total of 45 minutes—three times more than what I was promised. I do not know if I would cheat or just leave, but I wouldn't be surprised that in this group people would cheat more than in the control group.
If like me, you fancy Raymond Smullyan and his books, then you've heard about knights and knaves. Knights always tell the truth and knaves always lie. In addition to knights and knaves, there are normal people who sometimes tell the truth and sometimes lie. Here is a puzzle.
Puzzle. How, in one sentence, can a normal person prove that they are normal?
We can draw a parallel between people and coins. We can say that knights correspond to real coins, and knaves to fake coins that are lighter than real ones. Inspired by normal people, my coauthor Konstantin Knop invented chameleon coins. Chameleon coins can change their weight and behave like real or fake coins. I just wrote a post about chameleon coins.
Normal people are too unpredictable: they can consistently pretend to be knights or knaves. So logicians invented a simpler type of person, one who switches from telling the truth in one sentence to a lie in the next and then back to the truth. Such people are called alternators. Here is another puzzle:
Puzzle. You meet a person who is one of the three types: a knight, a knave, or an alternator. In two questions, find out which type they are.
Continuing a parallel between people and coins we can define alternator coins: the coins that switch their weight each time they are on the scale from weighing as much as real ones to weighing as much as fake ones. For the purposes of this essay, we assume that the fake coins are lighter than real ones. Unlike the chameleon coin, which might never reveal itself by always pretending to be real, the alternators can always be found. How do you find a single alternator among many real coins? There is a simple strategy: repeat every weighing twice. This strategy allows us to find an alternator among 9 coins in four weighings. Can we do better?
I used the alternator coins as a research project for my PRIMES STEP program where we do math research with students in seventh and eighth grade. The students started the alternator project and immediately discovered the strategy above. The next step is to describe a better strategy. For example, what is the maximum number of coins containing one alternator such that the alternator can always be found in four weighings?
But first we count possible outcomes. Suppose there is a strategy that finds an alternator. In this strategy we can't have two unbalanced weighings in a row. To prove that, let us suppose there was an unbalanced weighing. Then the alternator switches its weight to a real coin and whether or not the alternator is on the scale, the next weighing must balance. The beauty of it is that given a strategy each outcome has to point to a particular coin as an alternator. That means the number of outcomes bounds the total number of coins that can be processed.
Counting the number of possible outcomes that do not have two unbalances in row is a matter of solving a recurrence, which I leave to the readers to find. The result is Jacobshtal numbers: the most beautiful sequence you might never have heard of. For example, the total number of possible outcomes of four weighings is 11. Since each outcome of a strategy needs to point to a coin, the total number of coins that can be processed in four weighings is not more than 11. But 11 is better than 9 in our previous strategy. Can we process 11 coins in four weighings? Yes, we can. I will describe the first part of the strategy.
So we have 11 coins, one of which is an alternator. In the first weighing we compare 5 coins against 5 coins. If the weighing unbalances, the alternator is on a lighter pan. Our problem is reduced to finding the alternator among five coins when we know that it is in the real state. If the weighing balances, then we know that if the alternator is among the coins on the scale it must now be in the light state. For the second weighting, we pick two sets of three coins out of this ten coins and compare them against each other. Notice that 3 is a Jacobsthal number, and 5, the number of coins outside the scale, is also a Jacobsthal number. If the second weighing balances, the alternator must be among 5 coins outside the scale. All but one of these coins are in the light state, and I leave it to the readers to finish the strategy. If the weighing unbalances, we need to find the alternator among 3 coins that are in the real state now. This can be done in two weighings, and again the readers are to the rescue.
It appears that Jacobsthal numbers provide the exact lower bound of the number of coins that can be processed. This is what my middle-schoolers discovered and proved. We wrote a paper on the subject. The strategy in the paper is adaptive. That means it changes depending on the results of the previous weighings. Can we find an oblivious strategy? I will tell you in later posts.
Suppose we have 3^{n} identical-looking coins. One of the coins is fake and lighter than the other coins which all are real. We also have a random scale. That is a scale that at each weighing behaves randomly. Find the fake coin in the smallest number of weighings. Oops! That won't work! It is impossible to find the fake coin. The scale can consistently misbehave in such a way as to blame a specific real coin for being fake.
Let's try something else. Suppose we have two scales: one normal and one random. Find the fake coin.
What am I thinking? The normal scale can point to one coin and the random scale can point to another coin and we are in a "she said, he said" situation which we can't resolve.
Now, in my final try, I'll make it right. We actually have three scales, one of which is random. So here we go, with thanks to my son Sergei for giving me this puzzle:
Puzzle. We have 3^{n} identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.
Let's start with this strategy: repeat every weighing on all three scales and have a majority vote. At least two of the scales will agree, thus pointing to the true result. This way we can use a divide-into-three-equal-groups strategy for one scale to find the fake coin. It will require 3n weighings.
Can we do better? Of course, we can. We can repeat every weighing on two scales. If they agree we do not need the third scale. If they do not agree, one of the scales is random and lying, and we can repeat the weighing on the third scale to "out" the random scale. After we identify one normal scale, the process goes faster. In the worst case we will need 2n + 1 weighings.
Can we do even better? Yes, we can. I will leave it to the readers to find a beautiful solution that is asymptotically better than the previous one.
Update on Dec 24, 2016. The total number of coins should be 3^{2n}, not 3^{n}. We are looking at the worst case scenario, when the random scale is adversarial.
We all have played with problems in which we had real coins and fake (counterfeit) coins. For this post I assume that the fake coins are always lighter than the real coins. My coauthor Konstantin Knop invented a new type of a coin: a chameleon coin. This coin can mimic a fake or a real coin. It can also choose independently which coin to mimic for each weighing on a balance scale.
You cannot find the chameleon coin in a mix with real coins if it does not want to be found, because it can consistently behave as a real coin. Let's add classic fake coins to the mix, the ones that are lighter. Still the task of identifying the chameleons using a balance scale cannot be achieved: the chameleons can pretend to be fake coins. We can't identify the fake coins either, as the chameleons can mess things us up by consistently pretending to be fake.
What we can do is to find a small number of coins some of which are guaranteed to be fake. Consider the simplest setup, when we have one fake coin and one chameleon in our mix of N coins. That is we have N − 2 real coins. Our task now is to find TWO coins, one of which has to be fake. As usual we want to do it in the smallest number of weighings that guarantees that we'll find the two coins. Let me give you a fun problem to solve:
Puzzle. The total number of coins is four. And as above we have one chameleon and one classic fake. In two weighings find two coins so that one of them is guaranteed to be fake.
If you want to learn more, we just wrote a paper titled Chameleon Coins.
* * *
—Honey, we are like two parallel lines.
—Why do you say that?
—The intersection of our life paths was a mistake.
* * *
—Q: Why did the obtuse angle go to the beach?
—A: Because it was over 90 degrees.
* * *
Ancient Roman in a clothing store: How come XL is larger than L?
* * *
—Which is the odd one out: one, three, six, seven?
—Well, three of them are odd ones.
* * *
When I am with you, I solve integrals in my head, so that blood can come back to my brain.
* * *
There are two kinds of people in this world: Those that can extrapolate from incomplete data.
* * *
Seven has the word even in it, which is odd.
I have always wanted to be an honest person and have followed my honor code. Soviet Russia had two honor codes. One code was for dealing with people and the other for dealing with businesses and the government. I remind you that in Soviet Russia, all businesses were owned by the government. The money paid for work didn't have any relation to the work done. The government paid standard salaries and the businesses did whatever. Generally, that meant that they were doing nothing. Meanwhile, the government got its income from selling oil.
All people were being screwed by the government, so they had no motivation to play fair. Just as American workers do, Soviet Russians might use the work copier to make personal copies. The difference was that we didn't feel guilty at ripping off the government. We wouldn't just make a few necessary copies; we would make copies for our friends, our family, for strangers—as many copies as possible.
I moved to the United States in 1990. Several of my friends took time to explain to me the difference between Soviet Russia and the US. One of the friends, let's call her Sarah, was working as staff at Harvard University. She told me the story of a recent visit by a famous Russian professor. After he left, the department received a bill. It appears that the professor, in a short visit, used several months-worth of the department's budget allocation for copying and phone calls. I was impressed, in a good way, by the professor who I assume spent a good deal of his time making a lot of copies of papers unavailable in Russia, presumably not only for himself but also for students and colleagues. On the other hand, it was clearly wrong.
My new friend Sarah told me that in the US money does not come from nowhere, and I should include Harvard University in my honor code for people. Actually, not only Harvard, but also any place of work and the government too. Sarah also told me that since that budget problem, she was asked to talk to every incoming Russian visitor and explain to them how capitalism works. Most Russian visitors were ready to accept the rules. I too was delighted with that. It is much easier to follow one honor code than two.
I was also very happy for my son, Alexey. He was eight when we moved to Boston. Before our move I had a dilemma. Should I tell him that Lenin and Stalin were bad guys and killed millions of people? If I gave him a truthful explanation, I would also have to teach him to lie. Otherwise, if he mentioned this at school or on the street, we would be at risk of going to prison. If I didn't teach him the truth, he might become brainwashed and grow up believing in communism, which would be very, very bad.
I was so lucky that I moved to the US: I didn't have to teach my son to lie.
Centaurs, manticores, and minotaurs roam their planet. Their society is very democratic: any two animals can become sex partners. When two different species mate, their orgasm is so potent that they merge into one creature of the third species. For example, once one centaur and one manticore make love, they are reborn as one minotaur. At the beginning of the year 2016 there were 2016 centaurs, 2017 manticores, and 2018 minotaurs. They mated non-stop and at the end of the year only one creature was left on the planet. Which one?
This is one of those puzzles that I love-hate. I hate it because it is easy to answer this puzzle by inventing a specific mating pattern that ends with one animal. It is possible to get the correct answer without seeing the beauty. I love it because there is beauty in the explanation of why, if the mating ends with one animal, it has to be a specific animal.
The solution is charming, but being a mathematician this problem makes me wonder if ii is always possible to end with one animal. So I add another puzzle.
Describe the sets of parameters for which it is impossible to end up with one creature.
Today I have two new coin puzzles that were inspired by my son, Alexey Radul:
You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have a balance scale which might or might not be faulty. A faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of weighings you need in order to figure out whether the scale is faulty?
If you think about it, this problem is isomorphic to a known problem I wrote about before:
You have N ≥ 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is either lighter than the real ones or heavier than the real ones. You also have a normal balance scale. What is the smallest number of weighings you need in order to figure out whether the fake coin is lighter or heavier?
To make things more interesting let's mix the problems up.
You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have M > 1 identical-looking balance scales. All but one of them are normal and one is faulty. The faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of total weighings needed to figure out which scale is faulty?
The following problem was at a 2016 entrance test for the MIT PRIMES STEP program.
I drew several triangles on a piece of paper. First I showed the paper to Lev and asked him how many triangles there were. Lev said 5 and he was right. Then I showed the paper to Sasha and asked him how many triangles there were. Sasha said 3 and he was right. How many triangles are there on the paper? Explain.
The intended answer was 8: there were 5 triangles on one side of the paper and 3 on the other.
Most of the students didn't think that the paper might be two-sided, but they came up with other inventive ideas. Below are some of their pictures, and I leave it to you to explain why they work. All the students who submitted these pictures got a full credit for this problem on the test.
If you are a high-school student who wants to conduct research in mathematics, you should check out the MIT PRIMES program. If you enjoy solving the problems in our entrance test, that's the first indication that you might want to apply. But to determine if the program is right for you, and you are right for the program, please read the following questions and answers which have been prepared for you by Tanya Khovanova, the PRIMES Head Mentor. (This only addresses applications to PRIMES Math, and only to the research track)
Question: I do not like math competitions. Should I apply?
Answer: Math competitions are completely separate from research in mathematics. If you enjoy thinking about mathematics for long periods of time and are fascinated by our test questions, you should apply.
Question: I am good at math, but I really want to be a doctor. Should I apply?
Answer: No. PRIMES requires a huge time commitment, so math should really be your most significant interest.
Question: I want to get into Harvard, and PRIMES looks good on a resume. Should I apply?
Answer: PRIMES does look good on a resume. But if you are more passionate about, say, climate change than math, what would Harvard's admission committee see? Our experience in the program is that if math isn't your top interest, your math student may not be sufficiently impressive to be accepted at Harvard as a math researcher. At the same time, you will not be accepted as the top climate change student as you didn't invest your time in that. Math research is a hard way to earn points for college. See also, the essay, Thoughts on research by Simon Rubinstein-Salzedo.
Question: My parents want me to apply. Should I apply?
Answer: Your parents will not be accepted to the program. Do not apply if you do not really, really want to.
Question: Your website suggests that I should spend ten hours a week on the PRIMES project. I can only spend five. But I am a genius and faster than other people.
Answer: We already assume that you are a genius and faster than anyone else you know. Five hours a week are not enough for a successful project.
Question: I looked at the past PRIMES projects and nothing excites me as much as my current interest in Pascal's triangle. I doubt I should apply.
Answer: When you start working on a project, you will learn a lot about it. You will understand why, for example, Cherednik algebras are cool. The excitement comes with knowledge and invested time. Not yet being excited about Cherednik algebras is not a good reason not to apply. Besides a lot of exciting mathematics is done between several different fields.
Question: I really want to do nothing else than study Pascal's triangle.
Answer: We try to match our projects to students' interests as much as we can. But we almost never can fulfill a specific request as above. You might get a project related to Young diagrams, which are connected to quantum Pascal's triangle. If this connection doesn't excite you, you shouldn't apply.
Question: I think I will be better positioned for research if I spend five more years studying.
Answer: There is nothing wrong with this approach. For many years the standard was to start research in graduate school. Our program is innovative. At PRIMES we are trying a different model. It may sound scary, but you will learn everything you need to know in order to do your project. If the project is in representation theory, for example, you will only learn what you need—not the whole theory. Our hope is that eventually you will take a course in representation theory and expand your grasp of it and see the bigger picture behind your project. We have a reading track for people like you who reside in Boston area.
Question: I love math, but I am not sure that I want to be a mathematician. Should I apply?
Answer: Many people start loving math early in life and then discover that there are many other things that require a similar kind of brain: computer science, cryptography, finance, and so on. We do not require from our students a commitment to become mathematicians. If you want to try research in math, you should apply. If students decide that they do not want to do research in math after finishing our program, we do not consider that a negative result. One way or another, the experience of PRIMES will help you understand better what you want to do with your life.
Question: I want to get to the International Math Olympiad. I am afraid that the time the research project takes prevents me from preparing for competitions. Should I apply?
Answer: People who are good at Olympiads often have fantastic brain power that helps in research. On the other hand, research requires a different mind set and the transition might be painful. It is possible, but not trivial to succeed in both. It is up to you to decide how you want to spend your time.
Question: I like number theory, but I do not see past PRIMES projects in number theory.
Answer: Doable number theory projects are hard to come by and we have fewer number theory projects than students who want to do number theory. There are many high-school programs that teach number theory including PROMYS and Ross programs. Our applicants like number theory because they were exposed to it. During PRIMES you will be exposed to something else and might like it as much.
Question: I found a local professor to work with on a research project. Should I apply to PRIMES?
Answer: PRIMES requires that you devote 10 hours a week to research for a year. It is unrealistic to do two research projects in parallel. Choose one. Working with someone in person may be better than by Skype at PRIMES. Also, usually our mentors are not professors, but rather graduate students. On the other hand, they are MIT grad students and projects are often suggested by professors. Our program is well structured. We guarantee weekly meetings in the Spring, we give extra help with your paper, and we have a conference. It is up to you to decide.
Alexander Shapovalov is a prolific puzzle writer. He has a special webpage of his river-crossing puzzles (in Russian). Here is one of these puzzles.
Three swindlers have two suitcases each. They approach a river they wish to cross. There is one boat that can carry three objects, where a person or a suitcase counts as one object. No swindler can trust his suitcase to his swindler friends when he is away, but each swindler doesn't mind his suitcases left alone at the river shore. Can they cross the river?
In my paper with Joshua Xiong, Nim Fractals, we produced a bijection between P-positions in the three-pile Nim and a three-branch Ulam-Warburton automaton. We also defined a parent-child relationship on games that is induced by this bijection. Namely, two consecutive P-positions in a longest optimal game of Nim are the ones that correspond to a parent-child pair in the automaton. A cell in the Ulam-Warburton automaton has exactly one parent. That means, if (a,b,c) is a Nim P-position, then exactly one of (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) must be a P-position and a parent of (a,b,c). (See our paper for more details.)
Now I want to explicitly write out the rules of an automaton which will generate the Nim P-positions in 3D.
Let me restrict the evolution of the automaton to the non-negative octant. That is, we consider points (a,b,c) in 3D, where each coordinate is a non-negative integer. We define the neighbors of the point (a,b,c) to be the points that differ from (a,b,c) in two coordinates exactly by 1. So each point strictly inside the octant has 12 neighbors. (There are three ways to choose two coordinates, and after that four ways to choose plus or minus 1 in each of them.
There is a geometric interpretation to this notion of neighborhood. Let us correspond a unit cube to a point with integer coordinates. The center of the cube is located at the given point and the sides are parallel to the axes. Then two points are neighbors if and only if the corresponding cubes share one edge. Now it becomes more visual that a cube has 12 neighbors, as it has 12 edges.
Here is the rule of the automaton. Points never die. We start with the patriarch, (0,0,0), one point being alive. The non-alive point is born inside the non-negative octant if it has exactly 1 alive neighbor that is closer to the patriarch. In other words the point (a,b,c) is born if and only if exactly one out of three points (a − 1,b − 1,c), (a − 1,b,c − 1), and (a,b − 1,c − 1) is alive. It follows that the points that are born at the n-th step has a coordinate sum 2n.
Consider for example the starting growth. At the first step the points (0,1,1), (1,0,1) and (1,1,0) are born. At the next step the points (0,2,2) and (2,0,2) and (2,2,0) are born. while the (1,1,2) will never be born as starting from the second step it has at least two live neighbors: (0,1,1) and (1,0,1) that are closer to the patriarch.
Theorem. In the resulting automaton, the points that are born at step n are exactly the P-positions of Nim with the total of 2n tokens.
Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. Suppose we proved that at step n exactly P-positions with 2n tokens are born. Consider a P-position of Nim: (a,b,c) such that a + b + c = 2n + 2. Remember, that bitwise XOR of a, b, and c is zero. Consider the 2-adic values of a, b, and c (aka the smallest powers of 2 dividing a, b, and c). There should be exactly two out of these three integers that have the smallest 2-adic value. Suppose these are a and b. Then (a − 1,b − 1,c) is a P-position, while (a − 1,b,c − 1) and (a,b − 1,a − 1) are not. That means by the inductive hypothesis (a,b,c) has exactly one alive neighbor. So the position (a,b,c) is born at time n + 1.
Now we need to proof that nothing else is born. For the sake of contradiction suppose that (a,b,c) is the earliest N-position to be born. That means it has a live neighbor that is a P-position closer to the patriarch. WLOG we can assume that this neighbor is (a − 1,b − 1,c).
If a − 1 and b − 1 are both even, then (a,b,c) is a P-position, which is a contradiction. Suppose a − 1 and b − 1 are both odd. Then their binary representations can't have the same number of ones at the end. Otherwise, (a,b,c) is a P-position. That is a and b have different 2-adic values. Suppose a has a smaller 2-adic value, Then, for (a − 1,b − 1,c) to be a P-position a and c has to have the same 2-adic value. That means (a,b − 1,c − 1) is a P-position too. Now suppose a − 1 and b − 1 are of different parities. Without loss of generality suppose a − 1 is odd and b − 1 is even, then c is odd. Then (a − 1,b,c − 1) is a P-position too. Thus we can always find a second neighbor with the same number of tokens. That is, both neighbors are alive at the same time; and the N-position (a,b,c) is never born. □
One might wonder what happens if we relax the automaton rule by removing the constraint on the distance to the patriarch. Suppose a new point is born if it has exactly one neighbor alive. This will be a different automaton. Let us look at the starting growth, up to a permutation of coordinates. At step one, positions (0,1,1) are born. At the next step positions (0,2,2) are born. At the next step positions (0,1,3), (1,2,3) and (0,3,3) are born. We see that (0,1,3) is not a P-positions. What will happen later? Will this N-position mess up the future positions that are born? Actually, this automaton will still contain all the P-positions of Nim.
Theorem. In the new automaton, the points that are born at step n and have total of 2n tokens are exactly the P-positions of Nim with the total of 2n tokens.
Proof. Only the points with an even total can be born. Now we proceed by induction on the total number of tokens. The base case is obvious. The birth of the points that have total of 2n tokens and are born at step n depend only on the points with the total of 2n − 2 tokens that are born at step n − 1. By the inductive hypothesis, those are the P-positions with 2n − 2 tokens. So the points have total of 2n tokens and are born at step n match exactly the first automaton described above. To reiterate, N-positions with 2n tokens are born after P-positions with 2n tokens, so they do not influence the birth of P-positions with 2n + 2 tokens. □
In the game of Nim you have several piles with tokens. Players take turns taking several tokens from one pile. The person who takes the last token wins.
The strategy of this game is well-known. You win if after your move the bitwise XOR of all the tokens in all the piles is 0. Such positions that you want to finish your move with are called P-positions.
I play this game with my students where the initial position has four piles with 1, 3, 5, and 7 tokens each. I invite my students to start the game, and I always win as this is a P-position. Very soon my students start complaining that I go second and want to switch with me. What should I do? My idea is to make the game last long (to have many turns before ending) to increase the chances of my students making a mistake. So what is the longest game of Nim given that it starts in a P-position?
Clearly you can't play slower then taking one token at a time. The beauty of Nim is that such an optimal game starting from a P-position is always possible. I made this claim in several papers of mine, but I can't find where this is proven. One of my papers (with Joshua Xiong) contains an indirect proof by building a bijection to the Ulam-Warburton automaton. But this claim is simple enough, so I want to present a direct proof here. Actually, I will prove a stronger statement.
Theorem. In an optimal game of Nim that starts at a P-position the first player can take one token at each turn so that the second player is forced to take one token too.
Proof. Consider a P-position in a game of Nim. Then find a pile with the lowest 2-adic value. That is the pile such that the power of two in its factorization is the smallest. Suppose this power is k. Notice that there should be at least two piles with this 2-adic value.
The first player should take a token from one of those piles. Then the bitwise heap-sum after the move is 2^{k+1}−1. Then the Nim strategy requires the second player to take tokens from a pile such that its value decreases after bitwise XORing with 2^{k+1}−1. All piles with the 2-adic value more than k will increase after xoring with 2^{k+1}−1. That means the second player has to take tokens from another pile with 2-adic value k. Moreover, the second player is forced to take exactly one token to match the heap-sum. □
In the position (1,3,5,7) all numbers are odd, so I can take one token from any pile for my first move, then the correct move is to take one token from any other pile. My students do not know that; and I usually win even as the first player. Plus, there are four different ways I can start as the first player. This way my students do not get to try several different options with the same move I make. After I win several times as the first player, I convince my students that I win anyway and persuade them to go back to me being the second player. After that I relax and never lose. I am evil.
Replace question marks with letters in the following sequence:
Y, Y, ?, ?, Y, ?, Y, ?, R, R, R, R.
Problem 1. It is true that it is possible to put positive numbers at the vertices of a triangle so that the sum of two numbers at the ends of each side is equal to the length of the side?
This looks like a simple linear algebra question with three variables and three equations. But it has a pretty geometrical solution. What is it?
Problem 2. Prove that it is possible to assign a number to every edge of a tetrahedron so that the sum of the three numbers on the edges of every face is equal to the area of the face.
Again we have six sides and four faces. There should be many solutions. Can you find a geometric one?
Do you know how to cut a cake? I mean, mathematically. There is a whole area of mathematics that studies cake cutting.
Mathematicians usually assume that each person has their own idea of what is the best part of the cake. Suppose three sisters are celebrating the New Year by having a cake. Anna likes only icing, Bella likes only chocolate chips, and Carol likes only pieces of walnuts mixed into the cake. Mathematicians want to cut cakes fairly. But what is fair? Fair is fair, right? Wrong. There are several different notions of fair cake division.
There is a proportionate division. In such a division every sister gets at least one-third of her value of the cake. This seems fair. Let's see an example. Anna gets one third of the icing, Bella gets one third of the chocolate chips, and Carol gets everything else. This is a fair proportionate division. Each of the sisters believes that she got at least one-third of the cake, in their own value. But it doesn't seem quite fair.
There is a stronger notion of fairness. It is called envy-free. In this division each sister gets at least one-third of the cake and, in addition, none of the three sisters would improve their value by swapping pieces. That means, if Anna wants only icing, not only does she get at least one-third of the icing, but also no one else gets more icing than Anna. The previous example of the proportionate division is not envy-free. Carol got two-thirds of the icing, so Anna would want to switch with her.
Let's try a different division. Anna gets one third of the icing, Bella gets the chocolate chips and another third of the icing, and Carol gets all the walnuts and another third of the icing. Formally, this is envy-free cake cutting. But poor Anna. What do you think Anna feels when she sees the smiles of contentment on the faces of her sisters? Whoever invented the name doesn't understand envy. Anna got one-third of the cake by her value, but the other sisters got the whole cake!
Luckily mathematicians understand this conundrum. So they invented another name for a cake division. They call a division equitable if everyone values all the pieces the same. So the division above is envy-free but not equitable. Let's try again. Let's give each sister one-third of all the components of the cake. This division is very good mathematically: it is proportionate, envy free, and equitable. By the way, envy-free division is always proportionate. This division seems fair. But is it a good division?
There is another term here: Pareto-efficient division means that it is impossible to make one person feel better, without making another person feel worse. All divisions above are not Pareto-efficient. Moving some icing from Carol to Anna, doesn't decrease the value for Carol, but increases the value for Anna.
There is an even better way to divide the cake. We can give the icing to Anna, the walnuts to Bella, and the chocolate chips to Carol. This division is proportionate, envy-free, and Pareto-efficient. It is perfect. Mathematicians even have a word for it. They call it a perfect division.
Mathematically this division is perfect. Unfortunately, sisters are not. I know an Anna who would still envy Bella.
Why are manhole covers round? The manhole covers are round because the manholes are round. Duh! But the cute mathematical answer is that the round shapes are better than many other shapes because a round cover can't fall into a round hole. If we assume that the hole is the same shape as the cover but slightly smaller, then it is true that circular covers can't fall into their holes. But there are many other shapes with this property. They are called the shapes of constant width.
Given the width, the shape with the largest area is not surprisingly a circle. The shape with the smallest area and a given constant width is a Reuleaux Triangle. Here is how to draw a Reuleaux triangle. Draw three points that are equidistant from each other at distance d. Then draw three circles of radius d with the centers at given points. The Reuleaux triangle is the intersection of these three circles.
Can we generalize this to 3d? What would be an analogue of a Reuleaux Triangle in 3d? Of course, it is a Reuleaux Tetrahedron: Take four points at the vertices of a regular tetrahedron; take a sphere at each vertex with the radius equal to the edge of the tetrahedron; intersect the four spheres.
Is this a shape of the constant width? Many people mistakenly think that this is the case. Indeed, if you squeeze the Reuleaux tetrahedron between two planes, one of which touches a vertex and another touches the opposite face of the curvy tetrahedron, then the distance between them is equal to d: the radius of the circle. This might give you the impression that this distance is always d. Not so. If you squeeze the Reuleaux tetrahedron between two planes that touch the opposite curvy edges, the distance between these planes will be slightly more than d. To create a shape of constant width you need to shave off the edges a bit.
Theoretically you can shave the same amount off every edge to get to a surface of constant width. But this is not the cool way to do it. The cool way is to shave a bit more but only from one edge of the pair of opposite edges. You can get two different figures this way: one that has three shaved edges forming a triangle, and the other, where three shaved edges share a vertex. These two bodies are called Meissner bodies and they are conjectured to be shapes of the constant width with the smallest volume.
On the picture I have two copies of a pair of Meissner bodies. The two left ones have three edges that share a vertex shaved off. The very left shape gives a top view of this vertex and the solid next to it has its bottom with holes looking forward. The two shapes on the right show the second Meissner body in two different positions.
I recently discovered a TED-Ed video about manhole covers. It falsely claims that the Reuleaux tetrahedron has constant width. I wrote to TED-Ed, to the author, and posted a comment on the discussion page. There was no reaction. They either should remove the video or have an errata page for it. Knowingly keeping a video with an error that is being viewed by thousands of people is irresponsible.
I am running a PRIMES-STEP program for middle school students, where we try to do research in mathematics. In the fall of 2015 we decided to study the following topic in logic.
Suppose there is an island where the following four types of people live:
See if you can solve this simple logic puzzle about people on this island.
It is known that exactly one person stole an expensive painting from an apartment. It is also known that only Alice or Bob could have done it. Here are their statements:
Alice: I am guilty. Bob is a truth-teller.
Bob: I am guilty. Alice stole it. Alice is the same type as me.
Who stole the painting and what types are Alice and Bob?
My students and I discovered a lot of interesting things about these four types of people and wrote a paper: Who Is Guilty?. This paper contains 11 cute logic puzzles designed by each of my 11 students.
I envied my students and decided to create two puzzles of my own. You have already solved the one above, so here is another, more difficult, puzzle:
A bank was robbed and a witness said that there was exactly one person who committed the robbery. Three suspects were apprehended. No one else could have participated in the robbery.
Alice: I am innocent. Bob committed the crime. Bob is a truth-teller.
Bob: I am innocent. Alice is guilty. Carol is a different type than me.
Carol: I am innocent. Alice is guilty.
Who robbed the bank and what types are the suspects?
The following cute puzzle of unknown origins was sent to me by Martina Balagovic and Vincent van der Noort:
A car travels from A to B and back again. When going uphill it goes 56 km an hour, when going downhill it goes 72 km an hour and while driving on flat surface it goes 63 km an hour. Getting from A to B takes 4 hours and getting back (over the same road) takes 4 hours and 40 minutes.
What is the distance between A and B?
I received a book Really Big Numbers by Richard Schwartz for review. I was supposed to write the review a long time ago, but I've been procrastinating. Usually, if I like a book, I write a review very fast. If I hate a book, I do not write a review at all. With this book I developed a love-hate relationship.
Let me start with love. I enjoyed reading the first 80 pages. The pictures are great, and some explanations are very well thought out. Plus, I haven't thought much about really big numbers, so the book helped me understand them. I was impressed with how this book treats very difficult ideas with simple explanations and illuminating images. I was captivated by it.
Now to hate. I had two problems with this book: one pedagogical and the other mathematical.
The pedagogical issue. The beginning of the book is suitable for small children. Most of the book is suitable for advanced middle-schoolers who like mathematics. The last part is very advanced. Is it a good idea to show children a book that looks like a children's book, but which soon becomes totally out of their reach? Richard Schwartz understands it and says many times that pieces of this book might be read several years apart. Several years? What child is ready to wait several years to finish a book? How would children feel about the book and about numbers when no matter how hard they try, they cannot understand the end of the book?
As a reviewer, I can't recommend the full book for kids who are not ready to grasp the notion of the Ackermann function or arrow notation. Even if the child is capable of understanding these ideas, there are mathematical issues that would prevent me from recommending it.
The mathematical issue. Let me start by explaining the notion of plex. We call an n-plex a number that is equal to 10^{n}. For example, 2-plex means 10^{2} which is 100, and 10-plex means 10^{10}. The fun part starts when we plex plexes. The number n-plexplex means 10 to the power n-plex which is 10^{(1010)}. We can continue plexing: n-plexplexplex means 10 to the power n-plexplex. When you are hunting for really big numbers, it is easier to write the number of plexes rather than writing plexes after plexes. Richard Schwartz introduces the following notation to help visualize the whole thing. He puts numbers in a square. Number n in a square means 1-plexed n times. For example, 2 inside a square means 10^{10}. Ten inside a square is 1-plexplexplexplexplexplexplexplexplexplex.
We can start nesting squares. For example, 2 inside a square means 1-plex-plex or 10^{10}. Let's add a square around it: 2 inside two squares means 10^{10} inside a square, which equals 1 plexed 10^{10} times. To denote 10 nested in n squares Richard Schwartz uses the next symbol: n inside a pentagon. For example, 1 inside a pentagon is 10 inside a square. I wrote this number in the previous paragraph: it is 1-plexplexplexplexplexplexplexplexplexplex. Similarly, n inside a hexagon means 10 inside n nested pentagons. We can continue this forever: n inside a k-gon is 10 inside k nested (k-1)-gons.
What bothers me is why a square? Why not a triangle? If we adopt this scheme, what is the meaning of a number in a triangle? Let's try to unravel this. Following Richard Schwartz's notation we get that n inside a square is the same as 10 inside n nested triangles. What do we do n times with 10 to get to 1 plexed n times? 1-plexed n times is 10 plexed n-1 times. There is a disconnect in notation here. For example, 10 in two nested triangles should mean 2 inside a square that is 10^{10}. 10 inside one triangle should mean 1 inside a square which is 10. This doesn't make any sense.
I started googling around and discovered the Steinhaus–Moser notation. In this notation a number n in a triangle means n^{n}. A number n in a square means the number n inside n nested triangles. A number n in a pentagon means the number n inside n nested squares. And so on. This makes total sense to me. If we move down the number of sides, we can say that the number n inside a 2-gon means n times n and the number n inside a 1-gon means n. This is perfect.
Schwartz changed the existing notation in two places. First he made everything about 10. This might not be such a bad idea except his 10 inside a square doesn't equal 10 inside a square in Steinhaus–Moser notation. In Steinhaus–Moser notation 10 inside a square means 10 plexed 10 times. The author removed one of the plexes. He made 10 inside the square to mean 1 plexed 10 times, and as a result it stopped working.
Even though the first 83 pages are delightful and the pictures are terrific, the notation doesn't work. What a pity.
I have solved too many puzzles in my life. When I see a new one, my solution is always the intended one. But my students invent other ideas from time to time and teach me to think creatively. For example, I gave them this puzzle:
Two boys wish to cross a river, but there is a single boat that can take only one boy at a time. The boat cannot return on its own; there are no ropes or similar tricks; yet both boys manage to cross the river. How?
Here is what my inventive students came up with:
And here is my standard solution: They started on different sides of the river.
I gave a talk about thinking inside and outside the box at the Gathering for Gardner conference. I mentioned this puzzle and the inventiveness of my students. After the conference a guy approached me with another answer which is now my favorite:
Consider a triangle with vertices A, B, and C. Let O be its orthocenter. Let's connect O to the vertices. We get six lines: three sides of the triangle and three altitudes. These six lines are pair-wise orthogonal: AO ⊥ BC, BO ⊥ AC, and CO ⊥ AB.
It is easy to see that A is the orthocenter of the triangle OBC, and so on: each vertex is the orthocenter of the triangle formed by the other three. We say that these four points form an orthocentric system.
I heard a talk about this structure at the MOVES 2015 conference by Richard Guy. What I loved in his talk was his call to equality and against discrimination. The point O plays the same role as the other three points. It should be counted. Richard Guy suggested calling this system an orthogonal quadrangle. I am all for equality. This is not a triangle, this is a quadrangle!
I want the world to be a better place. My contribution is teaching people to think. People who think make better decisions, whether they want to buy a house or vote for a president.
When I started my blog, I posted a lot of puzzles. I was passionate about not posting solutions. I do want people to think, not just consume puzzles. Regrettably, I feel a great push to post solutions. My readers ask about the answers, because they are accustomed to the other websites providing them.
I remember I once bought a metal brainteaser that needed untangling. The solution wasn't included. Instead, there was a postcard that I needed to sign and send to get a solution. The text that needed my signature was, "I am an idiot. I can't solve this puzzle." I struggled with the puzzle for a while, but there was no way I would have signed such a postcard, so I solved it. In a long run I am glad that the brainteaser didn't provide a solution.
That was a long time ago. Now I can just go on YouTube, where people post solutions to all possible puzzles.
I am not the only one who tries to encourage people to solve puzzles for themselves. Many Internet puzzle pages do not have solutions on the same page as the puzzle. They have a link to a solution. Although it is easy to access the solution, this separation between the puzzle and its solution is an encouragement to think first.
But the times are changing. My biggest newest disappointment is TED-Ed. They have videos with all my favorite puzzles, where you do not need to click to get to the solution. You need to click to STOP the solution from being fed to you. Their video Can you solve the prisoner hat riddle? uses my favorite hat puzzle. (To my knowledge, this puzzle first appeared at the 23-rd All-Russian Mathematical Olympiad in 1997.) Here is the standard version that I like:
A sultan decides to give 100 of his sages a test. He has the sages stand in line, one behind the other, so that the last person in line can see everyone else. The sultan puts either a black or a white hat on each sage. The sages can only see the colors of the hats on all the people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. Each person who guesses the color wrong will have his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?
The video is beautifully done, but sadly the puzzle is dumbed down in two ways. First, they explicitly say that it is possible for all but one person to guess the color and second, that people should start talking from the back of the line. I remember in the past I would give this puzzle to my students and they would initially estimate that half of the people would die. Their eyes would light up when they realized that it's possible to save way more than half the people. They have another aha! moment when they discover that the sages should start talking from the back to the front. This way each person sees or hears everyone else before announcing their own color. Finally, my students would think about parity, and voilà, they would solve the puzzle.
In the simplified adapted video, there are no longer any discoveries. There is no joy. People consume the solution, without realizing why this puzzle is beautiful and counterintuitive.
Nowadays, I come to class and give a puzzle, but everyone has already heard the puzzle with its solution. How can I train my students to think?
I stumbled upon a TED-Ed video with a frog puzzle:
You're stranded in a rainforest, and you've eaten a poisonous mushroom. To save your life, you need an antidote excreted by a certain species of frog. Unfortunately, only the female of the species produces the antidote. The male and female frogs occur in equal numbers and look identical. There is no way to distinguish between them except that the male has a distinctive croak. To your left you spot a frog on a tree stump. You hear a croak from a clearing in the opposite direction, where you see two frogs. You can't tell which one made the sound. You feel yourself starting to lose consciousness, and you realize that you only have time to run in one direction. Which way should you go: to the clearing and lick both frogs or to the tree stump and lick the stump frog?
My first thought was that male frogs croak to attract female frogs. That means the second frog in the clearing is probably an already-attracted female. The fact that the stump frog is not moving means it is male. I was wrong. This puzzle didn't assume any knowledge of biology. The puzzle assumes that each frog's gender is independent from other frogs. Thus this puzzle is similar to two-children puzzles that I wrote so much about. I not only blogged about this, but also wrote a paper: Martin Gardner's Mistake.
As in two-children puzzles, the solution depends on why the frog croaked. It is easy to make a reasonable model here. Suppose the male frog croaks with probability p. Now the puzzle can be solved.
Consider the stump frog before the croaking:
Consider the two frogs in the clearing before the croaking:
The probabilities corresponding to our outcome—a non-croaking frog on the stump and one croaking frog in the clearing—are in bold. Given that the stump frog is silent, the probability that it's a female is 1/(1-p). Given that one clearing frog croaked, the probability that one of them is a female is p/2 divided by p(1-p)/2. The ratio is the same 1/(1-p). It doesn't matter where you go for the antidote.
The TED-Ed's puzzle makes the same mistake that is common in the two-children puzzles. I don't want to repeat their incorrect solution. The TED-Ed's frog puzzle is wrong.
When I receive a bank statement, I review all the transactions. The problem is my failing memory. I do not remember when and where I last took money from an ATM, and how much. So I decided to create a pattern. I used to take cash in multiples of 100. Probably most people do that. A better idea is to always take the amount that has a fixed remainder modulo 100, but not 0. For example, let's say I take one of the following amounts: 40, 140, 240, or 340. Sometimes I need more money, sometimes less. This set of numbers covers all of my potential situations, but my pattern is that all the numbers end in 40. This way if someone else gets access to my account, they will almost surely take a multiple of 100. I will be able to discover a fraud without remembering the details of my last withdrawal.
In addition, when I first started doing this, I was hoping I wouldn't need to wait until I review my own statement to discover problems. My hope was that if a thief tried to take cash from my account, my bank would notice a change in the pattern and notify me immediately. Now I realize that this was wishful thinking. I doubt that banks are as smart as I am.
One day I should try an experiment. I should go to an ATM I never use and withdraw 200 dollars. I wonder if my bank would notice.
One of my jobs is giving linear algebra recitations at MIT. The most unpleasant aspect of it is dealing with late homework. Students attempt to submit their homework late for lots of different reasons: a sick parent needing help, stress, a performance at Carnegie Hall, a broken printer, flu, and so on. How do I decide which excuse is sufficient, and which is not? I do not want to be a judge! Moreover, my assumption is that people tell the truth. In the case of linear algebra homework, this assumption is unwise. As soon as students discover that I trust everyone, there's a sharp increase in the number of sick parents and broken printers. So I have the choice of being either a naive idiot or a suspicious cynic. I do not like either role.
Our linear algebra course often adopts a brilliant approach: We announce that late homework is not allowed for any reason. To compensate for emergencies, we drop everyone's lowest score. That is, we allow the students to skip one homework out of ten. They are free to use this option for oversleeping the 4 pm deadline. If all their printers work properly and they do not get so sick that they have to skip their homework, they can forgo the last homework. Happily, this relieves me from being a judge.
Or does it? Unfortunately, this policy doesn't completely resolve the problem. Some students continue trying to push their late homework on me, despite the rules. In order to be fair to other students and to follow the rules, I reject all late homework. The students who badger me nonetheless waste my time and drain my emotions. This is very unpleasant.
From the point of view of those students, such behavior makes sense. They have nothing to lose and they might get some points. There is no way to punish a person who tries to hand in homework late and from time to time they stumble onto a soft instructor who accepts the homework against the official rules. Because such behavior is occasionally rewarded, they continue doing it. I believe that wrong behavior shouldn't be rewarded. As a responsible adult, I think it is my duty to counteract the rewards of this behavior. But I do not know how.
What should I do? Maybe I should…
Maybe I should just do number 4 right now and explain what I feel. A student who persists in handing in homework late feels to me that s/he is entitled and is better than everyone else, and shows that s/he doesn't care about the rules and honor. Again, this wastes my time, puts me in a disagreeable position, and reduces my respect for that student.
Earlier I suggested that students don't have anything to lose by such behavior, but in fact, they do pay a price, even though they may not understand that.
I found the following puzzle on a facebook page of Konstantin Knop (in Russian):
Seven astronauts landed on a small spherical asteroid. They wanted to explore it and walked in different directions starting from the same location. All used the same walking algorithm: walk x kilometers forward, turn 90 degrees left and walk another x kilometers, turn 90 degree left again and walk the last x kilometers. The value of x was different for different astronauts and was one of 30, 40, 50, 60, 70, 80, and 90.
All but one astronaut finished in the same location. What was the value of x for the astronaut who finished alone? What is the size of the asteroid?
I've been collecting math jokes for many years. I thought I've seen them all. No. Inventive people continue to create them. I was recently sent a link to a math joke website that features many jokes that are new to me. Here are my favorites:
* * *
With massive loss of generality, let $n=5$.
* * *
How do you prove a cotheorem? Using rollaries.
* * *
$0\to A\to B \to C \to 0$. Exactly.
* * *
Let $\varepsilon\to 0$. There goes the neighborhood!
* * *
Take a positive integer $N$. No, wait, $N$ is too big; take a positive integer $k$.
* * *
Calculus has its limits.
* * *
There is a fine line between a numerator and a denominator.
* * *
There's a marked difference between a ruler and a straightedge.
* * *
Suppose there is no empty set. Then consider the set of all empty sets.
* * *
Q: Why is it an insult to call someone "abelian"?
A: It means they only have a 1-dimensional character, and are self-centered.
* * *
Q: What's a polar bear?
A: A rectangular bear after a coordinate transform.
* * *
A logician rides an elevator. The door opens and someone asks:
—"Are you going up or down?"
—"Yes."
Russians cherish the issues of Kvant, a famous Soviet monthly magazine for high-school students devoted to math and physics. At its peak its circulation was about 300,000, which is unparalleled for a children's science journal. I still have my old childhood issues somewhere in my basement. But one issue is very special: it has a prominent place in my office. I didn't receive it by subscription; I received it as a gift from my brother Misha.
Strictly speaking Misha is not my brother, but rather a half-brother. His full name is Mikhail Khovanov and he is a math professor at Columbia. The signed issue he gave me contains his math problem published in the journal. He invented this problem when he was a 10th grader. Here it is:
In a convex n-gon (n > 4), no three diagonals are concurrent (intersect at the same point). What is the maximum number of the diagonals that can be drawn inside this polygon so that all the parts they divide into are triangles?
He designed other problems while he was in high school. All of them are geometrical in nature. The journal is available online, and a separate document with all the math problems is also available (in Russian). His problems are M1038, M1103, M1108 (above), M1119, M1153, M1204. I like his other problems too. M1153 (below) is the shortest problem on his list: as usual I am guided by my laziness.
What's the greatest number of turns that a rook's Hamiltonian cycle through every cell on an 8 by 8 chessboard can contain?
I wanted to accompany this post with a picture of my brother at the age he was when he invented these problems—about 16. Unfortunately, I don't have a quality picture from that period. I do have a picture that is slightly off: by about ten years.
What are the Ford circles? A picture is worth a thousand words, so here is a picture.
We draw a circle for any rational number p/q between 0 and 1 inclusive. We assume that p/q is the representation of the number in the lowest terms. Then the center of the circle is located at (p/q,1/q) and the radius is 1/q. The number inside a circle is q.
Here's the game. We start with any circle on the picture, except for the two largest circles corresponding to integers 0 and 1. In one move we can switch to a larger circle that touches our circle. The person who ends up at the two largest circles corresponding to integers 0 or 1 loses. Equivalently, the person who ends in the central circle marked "2" wins.
There are other ways to describe moves in this game in terms of rational numbers corresponding to circles, that is, the x-coordinates of their centers. Two circles corresponding to numbers p/q and r/s touch each other iff one of the following equivalent statements is true:
Let me explain the last bullet. Given two rational numbers in their lowest terms a/b and c/d, we generate their mediant as: (a+c)/(b+d). We call the two numbers a/b and c/d the parents of the mediant (a+c)/(b+d). The Stern-Brocot tree starts with two parents 0/1 and 1/1. Then their mediant is inserted between them to create a row: 0/1, 1/2, and 1/1. Then all possible mediants of two consecutive numbers are inserted in a given row to get a new row. The process repeats ad infinitum. The famous theorem states that any rational number between 0 and 1 will appear in the process.
What I like about this game is a simple and beautiful description of P-positions (These are the positions you want to end your move at in order to win.) P-positions are numbers with even denominators in their lowest terms.
In the picture above P-positions are blue, while other positions are red. All circles touched by blue are red. And if we look at the larger neighbors of every red circle, one of them is blue and one is red.
Let's prove that the numbers with even denominators satisfy the conditions for P-positions. First, two circles corresponding to numbers with even denominators can't touch each other. Indeed, the cross-determinant of two such fractions is divisible by 2. Second, each red circle has to touch one blue and one red circle with larger radii. Indeed, the circles with larger radii touching a given circle are exactly the parents of the circle. If the mediant has an odd denominator, then one of the parents must have an even denominator and the other an odd denominator.
Let us start with regular (non-weighted) mediants. Suppose we have two fractions a/b and c/d, the mediant of these two numbers is the wrong way a child might sum these two fractions: (a+c)/(b+d). There is nothing wrong with this childish way of summing, it is just not a sum of two numbers, but rather an operation the result of which is called a mediant. One must be careful: the result doesn't depend on the initial numbers chosen, but on their representations. The way to deal with this is to assume that a/b, c/d, and (a+c)/(b+d) are in their lowest terms.
The numerical value of the mediant is always in between given numbers. This is probably why it is called a mediant.
Suppose you start with two rational numbers 0/1 and 1/1, and insert a mediant between them. If you continue doing it recursively, you can reach any rational number between 0 and 1. This is a well-known property of the mediants. For example, after three rounds of inserting mediants into the initial sequence (0/1, 1/1), we get the sequence: 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1.
The mediants are easy to generalize if we assign weights to initial fractions. Suppose the first fraction has weight m and the second n, then their weighted mediant is (am+cn)/(bm+dn). The simplest generalization happens when the total weight, m+n is 3. In this case, given two rational numbers a/b and c/d, the left mediant is (2a+c)/(2b+d) and the right one is (a+2c)/(b+2d). Obviously the inequality property still holds. If a/b ≤ c/d, then a/b ≤ (2a+c)/(2b+d) ≤ (a+2c)/(b+2d) ≤ c/d.
James Propp suggested the following question for our PRIMES project. Suppose the starting numbers are 0/1 and 1/1. If we recursively insert two weighted mediants in order between two numbers we will get a lot of numbers. For example, after two rounds of inserting weighted mediants into the initial sequence (0/1, 1/1), we get the sequence: 0/1, 1/5, 2/7, 1/3, 4/9, 5/9, 2/3, 5/7, 4/5, 1/1. It is easy to see that new fractions must have an odd denominator. Thus unlike the standard case, not every fraction will appear. The question is: will every rational number between 0 and 1, which in reduced form has an odd denominator appear?
I started working on this project with Dhroova Aiylam when he was a high-school junior. We didn't finish this project during the PRIMES program. But Dhroova finished another project I already wrote about: he analyzed the case of the standard mediants with any starting points. He showed that any rational number in between the starting points appears.
Dhroova became an undergraduate student at MIT and we decided to come back to the initial PRIMES project of weighted mediants. In our paper Stern-Brocot Trees from Weighted Mediants we prove that indeed every fraction with an odd denominator between 0 and 1 appears during the recursive procedure. We also analyzed what happens if we start with any two rational numbers.
My brother, Mikhail Khovanov, has invented a new game: Ringiana. It is now available for iPhone, and soon should be available for Android.
In the starting position you see four multi-colored quadrants of a ring. For example, the first picture shows the starting position of level 33.
You can either swipe or touch between the quadrants. A swipe expands one quadrant into two quadrants and compresses two other quadrants into one. You can swipe clockwise or counterclockwise. The second figure shows the result of the clockwise swipe of the North opening. The NW quadrant that was half-red and half-yellow has expanded into two quadrants. The red piece now occupies the entire NW quadrant and the yellow piece—the entire NE quadrant. Two East quadrants got contracted into one SE quadrant. The former blue NE quadrant became the top blue half of the SE quadrant. The former SE half-blue half-green quadrant became the bottom half of the SE quadrant. In general the quadrant where the swiping movement starts expands in the direction of the swipe and the quadrant where the swiping movements ends together with the next quadrant compresses.
You can also touch an opening between quadrants. In this case the neighboring quadrants exchange places. The third figure shows the result of touching the East opening.
The goal of the game is to reach the final position: have each quadrant in one color. The next image shows the end of this particular level. As you can see the game was finished in 7 moves. In this particular case this is the smallest number of moves possible. To tell you a secret, it wasn't me who finished the game in the smallest number of moves: it was my brother.
There is also a tutorial for this game on youtube.
I was at the 1976 International Mathematics Olympiad as part of the USSR team. There were eight people on the team and I decided to find out what they have achieved in the last 40 years. Here is the picture of our team. From left to right: Sergey Finashin, Yuri Burov, Nikita Netsvetaev, Boris Solomyak, Alexander Goncharov, Tanya Khovanova, Sergei Mironov, our chaperone Z.I. Moiseeva, our team leader A.P. Savin, no clue who this is (probably a translator), Piotr Grinevich.
The list below is ordered by the number of points received at the Olympiad.
Tanya Khovanova, 39 points: a lecturer at MIT. I am interested in a wide range of topics, mostly recreational mathematics and have written 60 papers.
Sergey Finashin, 37 points: a full professor at Middle East Technical University in Turkey, who is interested in topology. He wrote 40+ papers.
Alexander Goncharov, 37 points: a full professor at Yale University. He is the highest achiever on the team. He won the EMS Prize in 1992 and was an Invited Speaker at the 1994 International Congress of Mathematicians. He is interested in geometry, representation theory, and mathematical physics. He published 75 papers in refereed journals.
Nikita Netsvetaev, 34 points: a full professor at Saint-Petersburg University in Russia. He is interested in topology and algebraic geometry and wrote 20 papers.
Boris Solomyak, 31 points: a full professor at Bar-Ilan University. He is interested in fractal geometry and dynamical systems and wrote 90 papers.
Piotr Grinevich, 26 points: a leading scientific researcher at the Landau Institute for Theoretical Physics. He also teaches at Moscow State University. He is interested in integrable systems and wrote 80 papers.
Sergei Mironov, 24 points. Sergey became very ill while he was an undergrad. He stopped doing mathematics.
Yuri Burov, 22 points. Yuri wrote two papers, but quit mathematics after graduate school. He died several years ago from multiple sclerosis.
Six out of eight people on our team became mathematicians. Or more precisely five an a half. I consider myself a mathematician and am grateful for my position at MIT, where I run innovative programs for young mathematicians. But in the research world, a lecturer is a nobody. This makes me sad. I had to take breaks from research in order to raise my two children. And then I had to work in the private sector in order to support them. I was the best on my team and now I am the only one who is not a full professor. If you are looking for an example of how gender affects a career in academia, this is it.
For many years I tried to lose weight using the idea that most appealed to me: intuitive eating. By that I mean that you eat only when you are hungry. Looking back at frustrating years of trying, I wonder what took me so long to realize that this doesn't work.
I am most hungry at the end of a meal. The only time I want to kill people is when they get between me and my future third helping of cheesecake. I never get the same ravenous feeling if I haven't eaten for some time, or have just started eating.
I am least hungry in the morning. I can work on my computer for hours before I even remember that I need to eat.
When my stomach signals that it needs more food, it is always wrong. Recently, I discovered what is right. I am using myfitnesspal app for my phone that counts my calories. From time to time I know that I haven't eaten enough. At these times, I don't experience my hunger in my gut. I feel it in my head: I feel dizzy.
I decided to drop the idea of intuitive eating and outsource the decision of when and what to eat to a higher power: my smart-phone.
After graduating from MIT, my son Sergei joined Two Sigma, a hedge-fund. Last year he came to MIT representing Two Sigma at a career fair. I visited him in his booth. He was just standing there next to himself on the poster.
I should stop worrying about him. If math does not work out, he has a chance at modelling.
I have written ad nauseam about the ambiguity of problems with children. Usually a problem with two children is formulated as follows:
Mr. Smith has two children and at least one of them is a boy. What is the probability that he has two boys?
I don't want to repeat my arguments for why this problem is ambiguous. Today I want to discuss other problematic assumptions about these problems.
Assumption 1: The probability of a child being a boy is 1/2. We know that this is not the case. Usually boys are born more often than girls. In addition to that, when policy interferes, the numbers can change. When China had their one-child policy, 118 boys were born per 100 girls. That makes a probability of a boy 0.54.
Assumption 2: The gender of one child in a family is independent of the gender of the other children. I am not sure where this assumption comes from, but I easily came up with a list of possible influences on this situation.
I would like to discuss how the last bullet point changes the probabilities in two children problems. Let us consider China. Up to now China had a one-child policy with some exceptions. In some cases if the first child was a girl, the family was allowed a second child. For the sake of argument, imagine a county where people are allowed to have a second child only if the first one is a girl. A family with two boys wouldn't exist in this county. Thus the probability of having two boys is zero.
I tried to find the data about the distribution of children by gender in multi-children families. I couldn't find any. I would be curious to know what happens in real life, especially in China.
A long time ago, before anyone ever heard about ultrasound, there was a psychic who could predict the gender of a future child. No one ever filed a complaint against him.
The psychic had a journal in which he wrote the client's name and the gender of the future child. The beauty of the scam was that what he wrote in the journal was the opposite gender that he had predicted. Whenever a client complained that the gender was wrong, he would show the journal and argue that the client had misunderstood.
Happy clients don't return to complain.
Oh, the power of conditional probability! It is useful to understand it to run scams or to expose them.
I've been trying to lose weight for three years. I wasn't very successful, but I always had plan B. I just didn't like it. I started my weight-loss journey at 245 pounds. Driven by my initial enthusiasm, I lost 25 pounds, but then I slowly gained back 20 pounds. That was it. I had to do the difficult thing: plan B.
My plan B was to log all I eat, convert it to nutrition elements, study it, and adjust my eating habits accordingly. I didn't want to do that: it seemed so complicated. I am not good at estimating weights, nor do I know how to convert food to calories and fat. Besides, it all seemed like such a bother.
When I gained back the weight and reached 240 pounds, I didn’t feel I had much choice. At that point my friend Luba showed me how to use the phone app myfitnesspal. I loved it. The app simplified the whole challenge. I bought a small kitchen scale to help me determine food weight, but more often than not, I don't need it. The app has a database of standard foods, as well as a barcode scanner. For example, when I take my favorite cranberry walnut roll that I buy at Trader Joe's, I just scan the barcode and the phone tells me, "Oops. 210 calories." This means I can only eat one a day — not all six as I might have done.
I started using this app on November 16, 2015. It seems to be working. And I made a lot of interesting discoveries.
I am losing weight, but to avoid jinxing it until I achieve a certain target, I don't want to reveal actual numbers.
To be continued…
You are given N coins such that two of them are fake and the other coins are genuine. Real coins weigh the same. Fake coins weigh the same and are lighter than real ones. You need to find both fake coins using a balance scale in the smallest number of weighings.
It is easy to estimate the number of weighings from below using information theory. Given N coins you will have N choose 2 different answers. The number of possible answers has to be not more than 3^{w}, where w is the number of weighings. This generates a trivial information-theoretic bound (ITB) on the number of coins that can be processed in a given number of weighings.
Previous authors used computers to completely analyze small numbers of weighings: from 2 to 5.
My colleagues from Russia, Konstantin Knop and Oleg Polubasov, performed some fantastic programming accompanied with some subtle heuristic and found optimal solutions for up to 10 weighings. For 11 and 12 weighings, the program is not efficient enough to find the optimal solutions: it found some solutions. Surprisingly, for up to 10 weighings, the optimal solutions match the information-theoretic bound (ITB). The results are in the table below. The first row represents the number of weighings w. The second row is the largest number of coins N for which a solution is found. The last row is the information-theoretic bound (ITB) we explained above.
w | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|
N | 22 | 38 | 66 | 115 | 198 | 344 | 585 | 1026 |
ITB | 22 | 38 | 66 | 115 | 198 | 344 | 595 | 1031 |
Their paper, Two counterfeit coins revisited, is available in Russian. Lucky for us, 70 of 73 pages are pseudo-code of solutions for which you do not need any Russian. You just need to understand the pseudo-code. Here is the explanation.
Each line begins with its number. After it they have the weighing in the format 1 10 v 4 5 meaning coins 1 and 10 are weighed versus coins 4 and 5. Each weighing is followed by a colon, after which they describe in order actions for three different outcomes of the weighing: equality, the first pan is lighter, and the second pan is lighter. Each action is one of the following:
The line numbers after => in line L are always 3L+1, 3L+2 and 3L+3. The sym symbol implies that line 3L+3 is omitted as a symmetric version of line 3L+2.
For example, here is their solution for 2 weighings and 4 coins in their pseudo-code. An empty line separates different weighings:
0. 1 v 2 : => 1, => 2, => 3. sym
1. 1 v 3 : - , (1, 2), (3, 4).
2. 3 v 4 : - , (1, 3), - . sym
Another solution for 3 weighings and 7 coins:
0. 1 2 v 3 4 : => 1, => 2, => 3. sym
1. 1 v 2 : => 4, => 5, => 6. sym
2. 1 v 2 : (1, 2), => 8, => 9. sym
4. 5 v 6 : (5, 6), (5, 7), - . sym
5. 3 v 4 : - , (1, 3), - . sym
8. 5 v 6 : (1, 7), (1, 5), - . sym
If you want to see an optimal solution for 10 weighings, look at the paper: the algorithm takes 36 pages.
I recently posted two trick questions.
First question. What is the answer to this question?
The title to this post was the same as the content except for the question mark: What is the Answer to This Question. The title contained the answer: WHAT.
What I like about trick questions is that sometimes people produce alternative answers that are as good as the intended ones. For this problem I like the following answers:
Second question. How many letters are there in the correct answer to this question?
The intended answer was FOUR, as four is the only number in the English language for which the number of letters in its name is equal to the number itself. Many people used variations on the theme and supplied the following answers by writing out numbers in non-canonical ways:
Some people used sentences to express numbers:
Many people pointed out that if the puzzle would be asked in other languages, it would produce completely different answers.
But the majority of my AMSA students took a completely different approach:
This is because there are thirty letters in the phrase the correct answer to this question.
Although I cut most carbs from my diet, I still wasn't losing weight. I started my weight-loss journey three years ago when I was 245 pounds. My initial excitement helped me get to 220, but then I started slowly gaining it back to 235 pounds. A couple of friends of mine who lost a lot of weight explained to me that I didn't actually cut all the carbs from my diet. I eliminated pizza, potatoes, spaghetti, sugar, cookies, soda, and so on. But there are many carbs hidden in some very natural and healthy foods. For example, a banana has 27 grams of carbs.
I love bananas; I can live on bananas alone. But my friends convinced me to cut the bananas, too. I agreed, but in that week I gained five more pounds. I think that every time I remove something from my diet, I end up becoming more relaxed with other food.
Clearly, carbs-cutting doesn't work. I am back to 240 pounds. Time for plan B.
The first Moscow Math Olympiad was conducted in 1935. Today, eighty years later, I decided to check it out. Most of the problems look standard, but some of the stereometry problems look too complicated. I found four problems that I really like: all of them are geometry problems.
Problem 1. The lengths of the sides of a triangle form an arithmetic progression. Prove that the radius of the inscribed circle is one third of one of the heights of the triangle.
Problem 2. A median, bisector, and height all originate from the same vertex of a triangle. You are given the three points that are the intersection points of the aforementioned median, bisector, and height with the circumscribed circle. Construct the triangle.
Problem 3. Find the set of points P on the surface of a cube such that the main diagonal subtends the smallest possible angle if viewed from P. Prove that the main diagonal subtends larger angles if viewed from other points on the surface. [Clarification: the two corners the main diagonal passes through don't count.]
Problem 4. Given three parallel straight lines, construct a square such that three of its vertices belong to these lines.
Each of these problems has a powerful idea that solves it. You can try and solve these problems, but if you want help, the ideas are presented below as hints in a scrambled order.
As a child I felt that society expected me to grow up and be a mother. And only to be a mother. It didn't make any sense to me, because if all that people do is reproduce, how will progress be made? So in my teens I decided that in addition to having children, I need to do something else, something to make the world a better place.
For many years I wasn't too successful in my plan. My children were my priority. I believed that for the first three years they needed a lot of my attention, which they couldn't necessarily get from a nanny. Later, being a single mother was so overwhelming that I didn't have time for other missions.
As my children grew, I felt myself imposing my own ambitions onto them. It wasn't fair to burden my children like that. I was meant to do something with my life other than bring up children. There was no substitute — I had to do it myself.
At that time, I was working at BAE Systems, but I hated my job. Its only purpose was to support my family. So as soon as my youngest son turned 16, I resigned to come back to mathematics. Though mathematics has my full attention now, my children are still my priority. I can afford to do what I love, because it is good for my children too. I am living my own ambitions, and they have the space to live theirs.
I was supposed to write about menopause. I am writing about menopause, just give me a second. I was also raised to believe that the best thing I can do for a man is to give him children. Every time I loved someone I wanted to have a child with that person, or I thought that I was supposed to want to. Now that I can't conceive a child for any potential future husband, I feel relieved. I can't be blamed any more for not having children. I am so happy that my current attempt at mathematics will not be interrupted any more.
I am so glad that I live in an age when women's life expectancy is way past menopause. I might love a man again; I might marry. I am so glad that I have an excuse not to have children. I can do what I want to do. I am free.
* * *
—Mike, here are 10 chocolates. Give half of them to your brother.
—OK. I'll give him three chocolates.
—You can't count?
—I can, but he can't.
* * *
—How is your progress?
—50%.
—Done or left to do?
* * *
—Q: What did Al Gore play on his guitar?
—A: An Algorithm.
* * *
I put my root beer in a square glass. Now it's just beer.
* * *
—Q: Why shouldn't you argue with a decimal?
—A: Decimals always have a point.
* * *
—I am cold.
—Go stay in the corner. It's 90 degrees.
* * *
Arithmetic is the art of counting up to twenty without taking off your shoes.
* * *
I bought a book online "How to implement an Internet scam." Somehow, though, it's been a while, and I still haven’t received it.
* * *
Sex is a pathetic thrill for losers who are not able to take a triple integral.
* * *
Paradox: Less money, more need to count it.
How many letters are there in the correct answer to this question?
What is the answer to this question?
In my paper Nim Fractals written with Joshua Xiong we discovered an interesting graph structure on P-positions of impartial combinatorial games. P-positions are vertices of the graph and two vertices are connected if they are consecutive P-positions in an optimal longest game.
A longest game of Nim is played when exactly one token is removed in each turn. So in Nim two P-positions are connected if it is possible to get from one of them to the other by removing two tokens.
In the paper we discussed the evolution graph of Nim with three piles. The graph has the same structure as three branches of the Ulam-Warburton automaton.
For completeness, I would like to describe the evolution graph of the 2-pile Nim. The P-positions in a 2-pile Nim are pairs (n,n), for any integer n. Two positions (n,n) and (m,m) are connected if and only if m and n differ by 1. The first picture represents this graph.
The Wythoff's game is more interesting. There are two piles of tokens. In one move a player can take any number of tokens from one pile or the same number of tokens from both piles.
The P-positions (n,m) such that n ≤ m start as: (0,0), (1,2), (3,5), (4,7), (6,10) and so on. They can be enumerated using φ: the golden ratio. Namely, n_{k} = ⌊kφ⌋ and m_{k} = ⌊kφ^{2}⌋ = n_{k} + k, where k ≥ 0.
In a longest Wythoff's game the difference between the coordinates decreases by 1. That is, it takes a maximum of 2k steps to end an optimal game starting from position (n_{k},m_{k}). The picture shows the evolution graph.
The interesting part of the picture is the crossover between two "lines". From positions with large coordinates like (6,10) with a difference of 4 you can get to only one position with a difference of 3: (4,7) and not (7,4). But from position (3,5) with a difference of 2 you can get to both positions with a difference of 1: (1,2) and (2,1).
I enjoy doing research in recreational mathematics. The biggest problem is that the probability that something I've done has already been done before is very high. This is partially because of the nature of this area of research. Trying to find new questions that are not buried deep in the abstract means someone else could have stumbled upon the same question. In addition, I like going in different directions: geometry, number theory, probability, combinatorics, and so on. That means I am not an expert in any of the areas. This too increases my probability of doing something that has already been done before.
This is quite unpleasant: to discover that I reinvented the wheel. And I keep reinvented different wheels on a regular basis. When I complain, my mathematician friends give me the same advice over and over:
Find your own niche!
I've been trying to understand what they mean, and finally I got it:
Do something no one else is interested in using methods no one else can understand.
Finding a topic that is not interesting almost guarantees that other people didn't do it before. Developing new complicated methods helps limit the number of followers and prevents the niche from becoming crowded.
Now I know why I see so many boring math papers I can't understand.
To hell with my own niche!
Let me start with a real story that happened a long time ago when I worked with my co-author on a math project. When I told him the idea I came up with, he dismissed it. The next day he came to me very excited with his new idea. He repeated the idea I had proposed the day before.
I said, "I suggested this exact idea to you yesterday." He didn't believe me. Luckily for our relationship, I knew him very well. He was not a person who lied. I remembered how preoccupied he was when I had laid out the idea to him. Now I think that he didn't pay attention to my idea at the time, but it was lodged somewhere in his subconscious and surfaced later. I am sure that he truly believed that the idea was his. (Unfortunately, he didn’t believe me. But this is another story.)
This story made me think about the nature of collaboration and how people can't really separate ownership of the results of a joint project. Let me tell you another story, one that I do not remember happening, although it could have.
I was working on a paper with my co-author on Sharelatex. One day an idea for a lemma came to me that we hadn't discussed before. My co-author lives in a different time zone, so instead of discussing the idea with him, I just added Lemma 3 and its proof to our paper. I was truly proud of my own contribution.
The next day I came up with Lemma 4 while driving back home. It was another completely new direction for our research. When I came home to my laptop, I discovered my Lemma 4 neatly written and proven by my co-author. Is this lemma his? It can't be completely his. It was a natural extension of what we discussed; he just got to a computer before me.
Did you notice in the last story that the situation is symmetric, but my hypothetical feelings are not? In a true collaboration ideas are bounced off each other. Very often people come up with the same idea at the same time, but you can’t ascribe ownership to the first person who speaks. Because of many stories like this, I made a rule for myself: never discuss in public who did what in a joint paper. Just always say "we."
Unfortunately I keep forgetting to teach my PRIMES/RSI students that. The question usually doesn't come up until it is too late, when one of the students in a group project during a presentation says, "I proved Theorem 5." Oops!
Round 1 of Who Wants to Be a Mathematician had the following math problem:
Bob and Jane have three children. Given that one child is their daughter Mary, what is the probability that Bob and Jane have at least two daughters?
In all such problems we usually make some simplifying assumptions. In this case we assume that gender is binary, the probability of a child being a boy is 1/2, and that identical twins do not exist.
In addition to that, every probability problem needs to specify the distribution of events over which the probability is calculated. This problem doesn't specify. This is a mistake and a source of confusion. In most problems like this, the assumption is that something is chosen at random. In this type of problem there are two possibilities: a family is chosen at random or a child is chosen at random. And as usual, different choices produce different answers.
The puzzle above is not well-defined, even though this is from a contest run by the American Mathematical Society!
Here are two well-defined versions corresponding to two choices in randomization:
Bob and Jane is a couple picked randomly from couples with three children and at least one daughter. What is the probability that Bob and Jane have at least two daughters?
Mary is a girl picked randomly from a pool of children from families with three children. What is the probability that Mary's family has at least two daughters?
Now, if you don't mind, I'm going to throw in my own two cents, that is to say, my own two puzzles.
Harvard researchers study the influence of identical twins on other siblings. For this study they invited random couples with three children, where two of the children are identical twins.
- Bob and Jane is a couple picked randomly from couples in the study with at least one daughter. What is the probability that Bob and Jane have at least two daughters?
- Mary is a girl picked randomly from a pool of children participating in the study. What is the probability that Mary's family has at least two daughters?
The puzzle Family Ties was written for the 2013 MIT Mystery Hunt, but it never made it to the hunt. Here's your chance to solve a puzzle no one has seen before. I wrote the puzzle jointly with Adam Hesterberg. The puzzle is below:
Mathematics professor S. Lee studies genealogy and is interested in the origins of life.
I promised to explain my job situation to my readers. I currently have six part-time jobs, which I describe below in the order that I started them.
The job I have had the longest is coaching math for competitions at AMSA Charter School. I started there in the spring of 2008 and I am still teaching there every week. I post my homework assignments on my webpage for other teachers and students to use.
The next longest has been as the Head Mentor at RSI, which I started in the summer of 2009. RSI is a great program where high school students from all over the world come to MIT to do research during summer vacations. It is amazing how much an ambitious student can do during a short five-week period. My first year I saw some great research done, but I was surprised that RSI papers were generally not available online. Beginning in 2012, at my recommendation, our Director Slava Gerovitch now posts the RSI papers at the math department RSI webpage.
As good a program as it is, RSI is too short for a research project. So we decided to develop our own program called PRIMES (Program for Research in Mathematics, Engineering, and Science for High School Students). I am also the Head Mentor in this program. I provide general supervision of all the projects and review conference slides and final papers. In addition to being the Head Mentor, I mentor my own students, which is great fun. I usually have three projects, but if something happens to a project or a mentor, I take it over.
Together with Pavel Etingof, PRIMES Chief Research Advisor, and Slava Gerovitch, PRIMES Director, I wrote an article Mathematical Research in High School: The PRIMES Experience that appeared in Notices.
My job #4, since the fall of 2013, is as a Teaching Assistant for the MIT linear algebra course.
This year I took on two more jobs at MIT. I am the Head Mentor at Mathroots, a summer program for high school students from underrepresented backgrounds. I am also teaching at PRIMES STEP, the program for gifted middle-school students in the Boston area. The goal of the program is to teach students mathematical thinking, have fun, and prepare them for PRIMES.
Overall, I have reached the stage in my career when I do not have time to breath and I still do not make enough money to pay my bills. The good news: my jobs bring me satisfaction. I just hope that I will not be too tired to notice that I am satisfied.
I already wrote about the sliding-window variation of the Secretary Problem. In this variation, after interviewing a candidate for the job, you can pick him or any out of w − 1 candidates directly before him. In this case we say that we have a sliding window of size w. The strategy is to skip the first s candidates, then pick the person who is better than anyone else at the very last moment. I suggested this project to RSI and it was picked up by Abijith Krishnan and his mentor Shan-Yuan Ho. They did a good job that resulted in a paper posted at the arXiv.
In the paper they found a recursive formula for the probability of winning. The formula is very complicated and not explicit. They do not discuss the most interesting question for me: what is the advantage of a sliding window? How much better the probability of winning with the window as opposed to the classical case without the window?
Let us start with a window of size 2, and n applicants. We compare two problems with the same stopping point. Consider the moment after the stopping point when we see a candidate who is better than everyone else before. Suppose this happens in position b. Then in the classic problem we chose this candidate. What is the advantage of a window? When will we be better off with the window? We will be better if the candidate at index b is not the best, and the window allows us to actually reach the best. This depends on where the best secretary is, and what happens in between.
If the best secretary is the next, in position b + 1, then the window gives us an advantage. The probability of that is 1/n. Suppose the best candidate is the one after next, in position b + 2. The window gives us an advantage only if the person in position b + 1 is better than the person in position b. What is the probability of that? It is less than 1/2. From a random person the probability of the next one being better is 1/2. But the person in position b is not random, he is better than random, so the probability of getting a person who is even better decreases and is not more than 1/2. That means the sliding window wins in this case with probability not more than 1/2n.
Similarly, if the best candidate is in position b + k, then the sliding window allows us to win if every candidate between b and b + k is better than the previous one. The probability of the candidate being better at every step is not more than 1/2. That means, the total probability of getting to the candidate in position b + k is 1/2^{k-1}. So our chances to win when the best candidate is at position b + k are not more than 1/2^{k-1}n. Summing everything up we get an advantage that is at least 1/n and not more than 2/n.
The probability of winning in the classical case is very close 1/e. Therefore, the probability of winning in the sliding window case, given that the size of the window is 2, is also close to 1/e.
Let us do the same for a window of any small size w. Suppose the best secretary is in the same window as the stopping candidate and after him, that is, the best candidate is among the next w − 1 people. The probability of this is (w − 1)/n. In this case the sliding window always leads to the best person and gives an advantage over the classical case. When else does the sliding window help? Let us divide the rest of the applicants into chunks of size w − 1. Suppose the best applicant is in the chunk number k. For the sliding window to allow us to get to him, the best candidate in every chunk has to be better than the best one in the previous chunk. The probability of that is not more than 1/2^{k-1}. The probability that we get to this winner is not more that (w-1)/2^{k-1}n. Summing it all up we get that the advantage of the window of size w is between (w − 1)/n and 2(w − 1)/n.
I already wrote about my favorite problem from the 2015 All-Russian Math Olympiad that involved tanks. My second favorite problem is about coins. I do love almost every coin problem.
A coin collector has 100 coins that look identical. He knows that 30 of the coins are genuine and 70 fake. He also knows that all the genuine coins weigh the same and all the fake coins have different weights, and every fake coin is heavier than a genuine coin. He doesn't know the exact weights though. He has a balance scale without weights that he can use to compare the weights of two groups with the same number of coins. What is the smallest number of weighings the collector needs to guarantee finding at least one genuine coin?
My name is Tanya and here's why. When my mom was pregnant, she was discussing the child's name with my father, Gueliy Khovanov. They decided that she could choose a boy's name while he could choose a girl's name. She wanted me to be Andrey in honor of her half-brother who died in World War II. He wanted me to be Tanya in honor of the unrequited love of his life. In an act of incomprehensible generosity, my mother agreed to name me after this woman. My parents were not even married when I was born.
After the decision was made, I was born on my own Name Day. In Russian culture, different names are celebrated on different dates. The a holiday for Tanyas is especially big and it falls on January 25, the day I was born. This serendipity led me to be very attached to my given name.
When I was a child, I believe that my father introduced me to his love, Tanya, although I do not have any clear memory of her. I doubt they were ever actually together. I do remember how my father loved her all his life. Even today I am sure that his love for Tanya brushed off on me, being her namesake.
I especially remember one day, when I was still a kid, my father agonizing about Tanya and calling to offer her help. My mom grimaced when he offered to babysit her children. My parents were divorced by then, and my father showed no interest in babysitting his own children. Now I understand that watching Tanya's children was the least he could do. This was happening in 1968 when the USSR invaded Czechoslovakia, and Tanya's husband, Konstantin Babitsky, was one of the few people in the USSR who risked their lives to openly protest against it. Tanya's life and freedom were also at risk. Offering any help was the right and only call.
Right before my father died of an illness in 1980, he asked me for one last favor: to tell Tanya that he had died. I was 20 years old and didn't have a clue how to find her; I only knew that her name was Tanya Velikanova. She was a famous Soviet human rights activist and dissident. That made it dangerous for me and for the people I might ask for assistance.
I finally asked my father's best friend to do it for me. He said that Tanya was in exile, but promised to pass a message to her. I am not sure he did it and I still feel guilty that I didn't do it myself before she died.
I forgot to tell you how my dad met the love of his life. They met as teenagers at a math Olympiad, where she beat him.
I already wrote how I build a magic SET hypercube with my students. Every time I do it, I can always come up with a new question for my students. This time I decided to flip over two random cards, as in the picture. My students already know that any two cards can be completed to a set. The goal of this activity is to find the third card in the set without trying to figure out what the flipped-over cards are. Where is the third card in the hypercube?
Sometimes my students figure this out without having an explicit rule. Somehow they intuit it before they know it. But after several tries, they discover the rule. What is the rule?
Another set of questions that I ask my students is related to magic SET squares that are formed by 3 by 3 regions in the hypercube. By definition, each magic SET square has every row, column, and diagonal as a set. But there are four more sets inside a magic SET square. We can call them super and sub-diagonal (anti-diagonal) wrap-arounds. Can you prove that every magic SET square has to have these extra four sets? In addition, can you prove that a magic SET square is always uniquely defined by any three cards that do not form a set, and which are put into places that are not supposed to from a set?
I love The Secretary Problem. I first heard about it a long time ago with a different narrative. Then it was a problem about the marriage of a princess:
The king announces that it is time for his only daughter to marry. Shortly thereafter 100 suitors line up in a random order behind the castle walls. Each suitor is invited to the throne room in the presence of the princess and the king. At this point, the princess has to either reject the suitor and send him away, or accept the suitor and marry him. If she doesn't accept anyone from the first 99, she must marry the last one. The princess is very greedy and wants to marry the richest suitor. The moment she sees a suitor, she can estimate his wealth by his clothes and his gifts. What strategy should she use to maximize the probability of marrying the richest person?
The strategy contains two ideas. The first idea is trivial: if the princess looks at a suitor and he is not better than those she saw before, there is no reason to marry him. The second idea is to skip several suitors at the beginning, no matter how rich they might seem. This allows the princess to get a feel for what kinds of suitors are interested in her. Given that we know the strategy, the interesting part now is to find the stopping point: how many suitors exactly does she have to skip? The answer is ⌊N/e⌋. (You might think that this formula is approximate. Surprisingly, it works for almost all small values. I checked the small values and found a discrepancy only for 11 and 30 suitors.)
The problem is called The Secretary Problem, because in one of the set-ups the employer tries to hire a secretary.
In many situations in real life it is a good idea to sample your options. Whether I'm shopping for an apartment or looking for a job, I always remember this problem, which reminds me not to grab the first deal that comes my way.
Mathematically, I try to find variations of the problem that are closer to real life than the classical version. Here's one of the ideas I had: you can always delay hiring a secretary until you have interviewed several candidates. You can't wait too long, as that good secretary you interviewed two weeks ago might have already found a job. And of course the king has a small window of time in which he can run out of the castle and persuade a suitor to come back before he saddles up his horse and rides away.
To make the problem mathematical we should fix the window size as an integer w. When you are interviewing the k-th suitor, you are allowed to go w − 1 suitors back. In other words, the latest you can pick the current suitor is after interviewing w − 1 more people. I call this problem: The Secretary Problem with a Sliding Window.
It is easy to extrapolate the standard strategy to the sliding window problem. There is no reason to pick a suitor who is not the best the princess have seen so far. In addition, if she sees the best person, it is better to wait for the last moment to pick him in case someone better appears. So the strategy should be to skip several people at the beginning and then to pick the best suitor at the last moment he is available.
The difficult part after that is to actually calculate the probabilities and find the stopping point. So I suggested this project to RSI 2015. The project was assigned to Abijith Krishnan under the direction of Dr. Shan-Yuan Ho. Abijith is a brilliant and hard-working student. Not only did he (with the help from his mentor) write a formula for the stopping point and winning probabilities during the short length of RSI, he also resolved the case when the goal is to pick one candidate out of the best two.
If you are interested to see what other RSI students did this year, the abstracts are posted here.
In my paper with Joshua Xiong on Nim Fractals we explained how to build an evolution graph corresponding to an impartial combinatorial game. The vertices of the graph are P-positions. And two vertices are connected if the two corresponding positions are consecutive P-positions in a longest possible optimal game.
What types of graphs do we get? An evolution graph should have at least one sink: these are our terminal P-positions. Also there are no directed loops: the game is finite. In addition, the distance from a vertex to sinks is uniquely defined: the number of directed edges that is needed to move from this vertex to a sink. This number is equal to half of the number of moves in the longest game, starting from the corresponding P-position.
A natural question arises: Can we build a game from a graph? The graph needs to satisfy the properties above. But other than that, can we? We can consider the graph itself as a game. Players can start at a vertex or an edge. From an edge, they can only move to a vertex where this edge ends. From a vertex they can move to any out-edge. The corresponding evolution graph is the graph itself. Vertices correspond to P-positions and edges to N-positions.
There is an equivalent game with a more uniform description. We put a vertex in the middle of every edge in the evolution graph. The new graph becomes bipartite. Players can start at any vertex. A move is allowed from a vertex following an out-edge to the vertex, where this edge ends. Vertices that are in the same part as terminal positions are P-positions. Other vertices are N-positions.
I explained to my AMSA students the idea of meta-solving multiple choice. Sometimes by looking at the choices without knowing what the problem is, it is possible to guess the correct answer. Suppose your choices are 2k, 2, 2/k, 10k, −2k. What is the most probable answer? There are several ideas to consider.
Both these considerations suggest a rule of thumb: the answers that are odd ones out are probably wrong. In the given example (2k, 2, 2/k, 10k, —2k), the second choice is an odd one out because it's the only one that does not contain k. The third choice is an odd one out because it's the only one in which we divide by k. The fourth choice is an odd one out because it's the only one with 10 instead of 2. The last one is an odd one out because of the minus sign. Thus the most probable answer is 2k.
So I explained these ideas to my students and gave them a quiz, in which I took the 2003 AMC 10A test, but only gave them the choices without the problems. I was hoping they would do better than randomly guessing.
Luckily for me, I have six classes in a row doing the same thing, so I can make adjustments as I go along. Looking at the results of the first two groups of students, I discovered that they were worse than random. What was going on?
I took a closer look, and what do you know? Nobody marked the first or the last choice. The answers are in an increasing order, so the first is the smallest and the last is the largest. So these two numbers are odd ones out, in a way.
It is a good idea to consider 189 as an odd one out in the list 1, 2, 4, 5, 189. In many other cases, the fact that the number is either the smallest or largest is insufficient reason to consider it as the odd one out. For example, there is no reason to consider 1 to be an odd one out in the list 1, 2, 3, 4, 5. And the designers of AMC are good: a lot of problems have an arithmetic progression as a list of choices, where none of the numbers are obviously odd ones out.
To correct the situation of worse than random results, I discussed it with my students in my next classes. Problem designers cannot have a tradition in which the first answer is never the correct answer. If such a tradition existed, and people knew about it, that knowledge would help them guess. So the first answer should be correct approximately five times, which is a fifth of the total number of questions (25).
And we came up with a strategy. Use the odd one out method except for arithmetic progressions. Then add the choices to balance out the total number of the first answers, the second answers, etc.
That method worked. In my next four classes my students were better than random.
Professor Bock came to his office at the Math Department of Deys University and discovered that someone had broken in. Luckily he had a lunch scheduled with his friend Detective Radstein. Bock complained to the detective about the break-in and the detective agreed to investigate.
Nothing was stolen from the office. It looked like somebody had just slept on Professor Bock's couch. The couch was bought recently and it was positioned so that it was impossible to see it through the tiny window of the office door, which had been locked. Interestingly, Professor Bock's office was the only one with a couch. The detective concluded that the person who broke in knew about the couch and thus was from the Math Department. In addition, the couch was very narrow and couldn't possibly sleep more than one person.
Investigating crimes at the Math Department of Deys University was very easy. This was due to a fact discovered by Detective Radstein on a previous case: every member of the department was one of three types:
Thus solving a crime at the department is very easy. Detective Radstein just needs to ask every person two questions, "How much is 2+2?" and "Are you guilty?" Only a guilty dodger would answer "4" and dodge. Only a guilty truth-teller would answer "4" and "yes". Only a guilty liar would answer something other than "4" and "no".
Detective Radstein decided to enjoy himself by making this investigation more challenging. He asked everyone only one question "Are you guilty of breaking-in?" These are the first three replies:
—Albert: I did it.
—Bill: Albert didn't do it.
—Connie: Albert did it.
It was amusing how many people knew where Albert slept, but these answers were enough for Detective Radstein to figure out the culprit. After this issue was resolved he asked Professor Bock, "While I am here, what other problems do you have at the department?"
"Well," said the professor, "In fact, I would be grateful if you could help us resolve two more issues. This semester our expenditure for tea increased three times. It is clear someone is stealing tea. It's also clear that this could only be someone who started working at the department this semester. There are two people who fit this description: David and Eve. So Detective Radstein asked each of them, "Are you stealing the tea?" He got the following answers:
—David: Eve steals the tea.
—Eve: Only one person steals the tea.
Having solved the Math Department's tea problem Detective Radstein then asked Professor Bock, "What else?" "Well," said Professor Bock, "one more thing. We have a lot of blackboards around the department. Every day a famous three-letter Russian curse word appears on the blackboards. The handwriting is always the same, so it is one person. Luckily the word starts with XY, so most people assume that this is some math formula. Anyway, I want to look into the eyes of the person who does this. I left the department late yesterday; only Fedor, Grisha and Harry were here. The blackboards were clean. This morning when I opened up the Math Department, the vulgar swearword had been written on the blackboards. I don't suspect someone of sneaking into the department at night to scribble on our blackboards. I am certain it is one of the three people I mentioned."
Once again Detective Radstein asked the suspects whether they did it.
—Fedor: Grisha did it.
—Grisha: Fedor did it.
—Harry: I do not speak Russian.
And again Detective Radstein solved the case. He was surprised that everyone in the department knew what everyone else was doing. Only his friend Professor Bock seemed clueless.
If you were the detective, would you be able to help Professor Bock?
My mom used to tell me "You are born to teach." My mom was a very shy person with no desire to be a teacher. Somehow she ended up teaching chemistry all her life. She also told me that teaching was our family business. All my ancestors were teachers or priests. Given that I lived in the Soviet Union, priesthood was not an option. (Given that I'm a woman, priesthood was not an option anywhere else.)
After my postdocs, I ended up quitting academia and working for industry. As a result, I didn't teach much. Until 2008 my only teaching experience was a course in Discrete Mathematics that I taught at Bar-Ilan University as part of my postdoc. Somehow Bar-Ilan University wanted five people to teach this same course in parallel and wanted me to teach it in Russian to attract fresh Russian immigrants. By the end of my course, I had way more people coming to my class than at the beginning, many of whom had transferred from the other parallel courses.
I had another clue that I was doing a good job. During one of my classes, the door was left open. A guy was walking down the hall, but when he heard me, he stopped. He stood there listening intently until the end of my class.
At the end of 2007 I resigned my industry job to go back to mathematics. I needed some financial support to do so, so my friends tried to arrange a math coach position for me at AMSA (Advanced Math and Sciences Academy Charter School). I had my interview in April, 2008, for a position for the following academic year. My interviewers were skeptical: they had had a series of PhDs who had proven incapable of teaching. I told them that deep down in my heart I knew that I would be a great teacher. And I made them an offer: I will start working in April and work until the end of the school year in June. Hiring me for two months was not a great risk, but gave them a basis on which to decide whether to give me a contract for the following year. I've been working at AMSA ever since.
My class is optional and there are no grades, but most of my students stick with me for all five years. (I teach grades 8 to 12.) My students show that they like me in many ways. I'm especially thrilled when they tell me that I am the best teacher they ever had.
Informally they call my class Tanya Time.
One evening Detective Radstein visited Professor Bock. He was hanging out in the kitchen and overheard a conversation between Professor Bock and his wife. It appeared that Mrs. Bock had discovered that all the cutlets she had prepared for the next day were missing. She asked her husband:
—Did you eat the cutlets?
—I ate soup, the professor replied.
—Oh well, the children were probably very hungry.
Detective Radstein smiled to himself. Many mathematicians have trouble making false statements. Some of them adjust to social situations by learning how to lie while formally telling the truth. Radstein calls them dodgers. Fortunately, dodgers only dodge a question when they are threatened. It was obvious that Professor Bock was such a dodger. He implied that he didn't eat the cutlets, because he had soup for lunch. The detective was ready to bet $10,000 that, in truth, the soup was just an appetizer to Professor Bock's meal of cutlets.
Detective Radstein talked to his friend Professor Bock about this obsession mathematicians have to make true statements. Professor Bock agreed that many mathematicians are like that. In fact, all the faculty members in his department are either dodgers or pathological truth-tellers. Ironically, all other staff members at Professor Bock's math department are liars.
A pathological truth-teller is another term that Detective Radstein uses to describe people who tell the truth no matter what. They never dodge. They answer a question exactly, often disregarding the context and purpose of the question. For example, when someone enters an elevator and asks a pathological truth-teller, "Is this elevator going up or down?" the answer s/he gets is "Yes."
One day Professor Bock asked Detective Radstein for help, following a series of laptop thefts at his department. It was clear that the thefts were committed by someone working at the department and that the criminal acted alone.
Detective Radstein decided that the easiest starting point would be to ask everyone the same question: Did you steal the laptops? If a pathological truth-teller is the perpetrator, s/he would admit to the crime. A dodger would evade the question, but only if they are guilty. A liar is flexible: s/he might either answer the question with a lie or dodge with a lie. These are the first three answers the detective got from members of the department:
—Alice: No, I didn't steal the laptops.
—Bob: Alice stole the laptops.
—Clara: Alice didn't steal the laptops.
Who stole the laptops?
Yesterday I went online to check out the problems at the 2015 All-Russian Math Olympiad. I was stunned to discover a problem about tanks and fighter jets. I have never seen such a militarized problem before. The problem setup tells me something about the mood of people in Russia. It tells me that the mood has changed—alarmingly for the worse.
On the other hand, mathematically it was my favorite problem. So here it is.
The field is a 41 by 41 square made of square cells. A tank is camouflaged and hidden in one of the cells. A pilot flying a fighter jet above knows that the tank is there and wants to destroy it. If there is a tank in a cell, it will be hit by the shot directed at this cell. The pilot also knows that two hits are needed to destroy the tank. The tank will move to a neighboring cell immediately upon being hit, without breaking its camouflage. Other than that, the tank won't move. What is the smallest number of shots required to guarantee that the tank is destroyed?
My post with Kvantik's 2012 problems for middle school was a success. So I scanned the 2013 issues and found 7 more problems that I liked. Here are two cute problems I've seen before:
Problem 1. In the equation 30 − 33 = 3 move one digit to make it correct.
Problem 2. A patient got two pills for his headache and two pills for his cough. He was supposed to use one of each type of pill today and do the same tomorrow. The pills all looked the same. By mistake, the patient mixed up the pills. How should he use them so that he follows the prescription exactly?
Now logic and information-theoretical problems:
Problem 3. One strange boy always tells the truth on Wednesdays and Fridays and always lies on Tuesday. On other days of the week he can lie or tell the truth. He was asked his name seven days in a row. The first six answers in order are Eugene, Boris, Vasiliy, Vasiliy, Pete, Boris. What was his answer on the seventh day?
Problem 4. Ten people are suspected of a crime. It is known that two of them are guilty and eight are innocent. Suspects are shown to a psychic in groups of three. If there is a guilty person in the group the psychic points him out. If there are two guilty people in the group, the psychic points to one of them. If all of them are innocent, the psychic points at one of the three.
- How would you find at least one guilty person in four séances?
- How would you find both criminals in six séances?
Problem 5. There are four balloons: red, blue, green and black. Some of the balloons might be magical. There is also a detector box that can say how many balloons out of the ones put inside are magical. How can you find all the magical balloons using the detector box not more than three times?
I conclude with two miscellaneous problems.
Problem 6. Three runners started their loops at the same time at the same place on the same track. After some time they ended at their starting point together. The fastest runner passed the slowest runner 23 times. Assuming each runner has a constant speed, how many times was one runner passed by another runner in total?
Problem 7. Given a point inside a circular disk, cut the disk into two parts so that you can put them back together into a new disk such that the given point is the center.
I recently posted a set of problems from a Russian magazine for middle school children. Now it's time for solutions.
Problem 1. There are 6 glasses on the table in a row. The first three are empty, and the last three are filled with water. How can you make it so that the empty and full glasses alternate, if you are allowed to touch only one of the glasses? (You can't push one glass with another.)
Solution. Pour the water from the fifth glass to the second glass.
Problem 2. If it is raining at midnight, with what probability will there be sunshine in 144 hours?
Solution. In 144 hours it be midnight. Assuming we are not close to the earth's poles, there will be no sunshine.
Problem 3. How can you fill a cylindrical pan exactly half-full of water?
Solution. Fill it with water, then tilt so that the water slowly runs out until you are about to see the rim of the floor of the pan.
Problem 4. The Jackal always lies; the Lion always tells the truth. The Parrot repeats the previous answer—unless he is the first to answer, in which case he babbles randomly. The Giraffe replies truthfully, but to the previous question directed to him: his first answer he chooses randomly.
The Wise Hedgehog in the fog stumbled upon the Jackal, the Lion, the Parrot, and the Giraffe, although the fog prevented him from seeing them clearly. He decided to figure out the order in which they were standing. After he asked everyone in order, "Are you the Jackal?" he was only able to figure out where the Giraffe was. After that he asked everyone, "Are you the Giraffe?" in the same order, and figured out where the Jackal was. But he still didn't have the full picture. He started the next round of questions, asking everyone, "Are you the Parrot?" After the first one answered "Yes", the Hedgehog understood the order. What is the order?
Solution. On the question "Are you the Jackal?" the Jackal and the Lion have to answer no. The Giraffe has to say "yes." The Parrot could not have said "yes," because in this case the Hedgehog, knowing where Giraffe is, could have figured out where the Parrot is. That means, in the first round there was only one "yes." We also can conclude that the Parrot is not after the Giraffe. On the question "Are you the Giraffe?" the Lion would have said "no," and the Jackal would have said "yes." The argument here is similar to the previous discussion: the Parrot couldn't have said "yes." We also know that the Parrot is not after the Jackal. So the Parrot is either the first or is after the Lion. After the Hedgehog's last question, we know that the Lion can't be the first. That means the Parrot is the first. Which means the previous animal said "yes," implying that the Jackal is the last. So there are two possibilities: The Parrot, the Lion, the Giraffe, the Jackal, or the Parrot, the Giraffe, the Lion, the Jackal. But in the second arrangement, the Hedgehog would have differentiated the Lion from the Parrot before the last question, as the Parrot couldn't have been after the Giraffe. The answer is: the Parrot, the Lion, the Giraffe, the Jackal.
Problem 5. There are 12 cards with the statements "There is exactly one false statement to the left of me," "There are exactly two false statements to the left of me," ..., "There are 12 false statements to the left of me." Pete put the cards in a row from left to right in some order. What is the largest number of statements that might be true?
Solution. Suppose there are more than six statements that are true. That means one of the cards with a number more than six is true, meaning that there are at least 7 false statements. This is a contradiction. Suppose there are 6 true cards. They have to be cards with numbers one through six. In addition, no pair of adjacent cards can both be true. Arranging the cards in the order 7, 1, 8, 2, 9, 3, 10, 4, 11, 5, 12, 6 works. Notice that we can permute the cards with numbers more than 6 and it will still work.
Problem 6. Olga Smirnov has exactly one brother, Mikhail, and one sister, Sveta. How many children are there in the Smirnov family?
Solution. I shouldn't have posted this problem. In Russian it is clear that Olga is a girl and the answer is 3 children. In English this problem might be confusing.
Problem 7. Every next digit of number N is strictly greater than the previous one. What is the sum of the digits of 9N?
Solution. Remember that 9N = 10N − N. That means the i-th digit of 9N is the (i+1)-th digit of N minus the the i-th digit of 9N. The next to last digit of 9N is the last digit of N minus the next to last digit of N minus 1 (because of the carry). The last digit of 9N is 10 minus the last digit of N. Summing this up, the answer is 9.
Problem 8. Nine gnomes stood in the cells of a three-by-three square. The gnomes who were in neighboring cells greeted each other. Then they re-arranged themselves in the square, and greeted each other again. They did this one more time. Prove that there is at least one pair of gnomes who didn't get a chance to greet each other.
Solution. Color the square in checkerboard colors. There are 8 different ways to assign colors to gnomes for the three rounds. That means there are two gnomes who stood on the same colors all three times. They couldn't have greeted each other.
John Conway told me a story about the book Winning Ways for Your Mathematical Plays that he wrote jointly with Elwyn Berlekamp and Richard Guy. The book includes the birthdays of each of the book's three authors. The book has short author bios, each of which mentions that author's birthday. But in addition, each birthday is hidden inside the book.
Elwyn Berlekamp was born on September 6, 1940, and this date is pictured on a tombstone on page 318 of Volume 2. That chapter is about suiciding moves.
John Conway was born on December 26, 1937. The Doomsday algorithm to calculate the day of the week for a given date is discussed on page 903 of Volume 4. Boxing Day in 1937 is chosen as an example. Boxing Day is a British holiday that originated when wealthy people gave gift boxes to servants the day after Christmas. John Conway was born on Boxing Day. Hidden behind this calculation that it was a Sunday, is the fact that it was Conway's day of birth.
Richard Guy was born on September 30, 1916. He often uses his initials RKG for Richard Kenneth Guy. Maybe because of that he got the nickname Archangel. If you look into the index pages of Volumes 3 and 4, you will find an entry for Archangel that refers to pages 9, 30, 1916. Not only are there no mentions of "Archangel " on pages 9 and 30, the book only has 1004 pages.
The trio of Berlecamp, Conway, and Guy will be the topic of an upcoming MOVES (Mathematics Of Various Entertaining Subjects) conference at the Museum of Mathematics.
The last time I visited John Horton Conway, he showed me a book, Genius At Play: The Curious Mind of John Horton Conway by Siobhan Roberts. It had nothing to do with him wanting to brag about the book. Nothing, nothing at all.
He just wanted to show me a picture from the book. While he was browsing this book about himself, I took a photo of him (featured on the left). The picture he was looking for was on page 314. I am reproducing it here (Photo by Michael A. Stecker, courtesy of Stephen D. Miller).
When we finally found the picture, he asked me how many tennis balls were in it. I smelled a trick question right away and didn't bite. I shrugged. It appears that one of the balls at the far corner at the base of the pyramid had rolled away. So there was one less ball than I would have calculated. So, how many balls are there?
Without using a calculator, can you tell how much 75^{2} is? If you are reading my blog, with high probability you know that it is 5625. The last two digits of the square of a number ending in 5 are always 25. So we only need to figure out the first two digits. The first two digits equals 7 times 8, or 56, which is the first digit of the original number (7) multiplied by the next number (8).
I was good at mental arithmetic and saved myself a lot of money back in the Soviet Union. Every time I shopped I calculated all the charges as I stood at the cash register. I knew exactly how much to pay, which saved me from cheating cashiers. To simplify my practice, the shelves were empty, so I was never buying too many items.
When I moved to the US, the situation changed. Salespeople are not trying to cheat, not to mention that they use automatic cash registers. In addition, the US sales taxes are confusing. I remember how I bought three identical chocolate bars and the total was not divisible by 3. So I completely dropped my at-the-cash-registers mental training.
Being able to calculate fast was somewhat useful many years ago. But now there is a calculator on every phone.
John H. Conway is a master of mental calculations. He even invented an algorithm to calculate the day of the week for any day. He taught it to me, and I too can easily calculate that July 29 of 1926 was Thursday. This is not useful any more. If I google "what day of the week is July 29, 1926," the first line in big letters says Thursday.
One day a long time ago I was watching a TV show of a guy performing mental tricks: remembering large numbers, multiplying large numbers, and so on. At the end, to a grand fanfare, he showed his crowned trick. A member from the audience was to write down a 2-digit number, and to raise it to the fifth power using a calculator. The mental guy, once he is told what the fifth power was, struggled with great concentration and announced the original number.
I was so underwhelmed. Anyone knows that the last digit of a number and its fifth power are the same. So he only needs to guess the first digit, which can easily be estimated by the size of the fifth power.
I found the description of this trick online. They recommend memorizing the fifth powers of the numbers from 1 to 9. After that, you do the following. First, listen to the number. Next, the last digit of the number you hear is the same as the last digit of the original number. To figure out the first digit of the original number, remove the last 5 digits of the number you hear. Finally, determine between which fifth powers it fits. This makes sense. Or, you could be lazy and remember only meaningful digits. For example, 39^{5}=90,224,199, and 40^{5}=102,400,000. So if the number is below 100,000,000, then the first digit is less than 4.
You do not have to remember the complete fifth powers of every digit. You just need to remember significant ranges. Here they are:
first digit | range |
---|---|
1 | between 100,000 and 3,000,000 |
2 | between 3,000,000 and 24,000,000 |
3 | between 24,000,000, 100,000,000 |
4 | between 100,000,000 and 300,000,000 |
5 | between 300,000,000 and 750,000,000 |
6 | between 750,000,000 and 1,600,000,000 |
7 | between 1,600,000,000 and 3,200,000,000 |
8 | between 3,200,000,000, and 5,900,000,000 |
9 | above 5,900,000,000 |
Besides, for this trick the guy needed to guess one out of one hundred number. He had a phenomenal memory, so he could easily have remembered one hundred fifth powers. Actually he doesn't need to remember all the numbers, only the differentiated features. On this note, there is a cool thing you can do. You can guess the number before the whole fifth power is announced. One caveat: a 1-digit number x and 10x when taken to the fifth power, both begin with the same long string of digits. So we can advise the audience not to suggest a 1-digit number or a number divisible by 10, as that is too easy (without telling the real reason).
Now we can match a start of the fifth power to its fifth root. Three first digits are almost always enough. Here is the list of starting digits and their match: (104,16), (107,64), (115,41), (116,65), (118,26), (12,66), (130,42), (135,67), (141,17), (143,27), (145,68), (147,43), (156,69), (161,11), (164,44), (17,28), (180,71), (184,45), (188,18), (19,72), (2051,29), (2059,46), (207,73), (221,74), (229,47), (23,75), (247,19), (248,12), (253,76), (254,48), (270,77), (282,49), (286,31), (288,78), (30,79), (33,32), (345,51), (348,81), (370,82), (371,13), (38,52), (391,33), (393,83), (40,21), (4181,53), (4182,84), (44,85), (454,34), (459,54), (470,86), (498,87), (50,55), (51,22), (525,35), (527,88), (53,14), (550,56), (558,89), (601,57), (604,36), (62,91), (64,23), (656,58), (659,92), (693,37), (695,93), (71,59), (73,94), (75,15), (77,95), (792,38), (796,24), (81,96), (84,61), (85,97), (902,39), (903,98), (91,62), (95,99), (97,25), (99,63).
Or, you can come to the mental guy's performance and beat him by shouting out the correct answer before he can even finish receiving the last digit. This would be cool and cruel at the same time.
* * *
Do you know a statistics joke?
Probably, but it's mean!
* * *
Twelve different world statisticians studied Russian roulette. Ten of them proved that it is perfectly safe. The other two scientists were unfortunately not able to join the final discussion.
* * *
A statistician bought a new tool that finds correlations between different fields in databases. Hoping for new discoveries he ran his new tool on his large database and found highly correlated events. These are his discoveries:
* * *
Scientists discovered that the main cause of living 'till old age is an error on the birth certificate.
* * *
Scientists concluded that children do not really use the Internet. This is proven by the fact that the percentage of people saying 'No' when asked 'Are you over 18?' is close to zero.
* * *
— Please, close the window, it is cold outside.
— Do you think it will get warmer, after I close it?
Some of my friends collect volumes of The Best Writing on Mathematics published by Princeton University Press. The first annual volume appeared in 2010. In 2014, one of my papers, Conway's Wizards, was chosen to be included in the volume The Best Writing on Mathematics 2014.
All my life I have hated writing. My worst grades in high school were for writing. I couldn't write in Russian, and I was sure I would never be able to write in English. I was mistaken. I am a better writer than I gave myself credit for being.
Writing in English is easier for me than writing in Russian because when I make a mistake, I have an excuse. As my written English gets better and better, maybe one day I'll get the courage to try writing in Russian.
I would like to use this opportunity to thank Sue Katz, my friend, English teacher, and editor. Sue edits most of my blog essays. Originally I wrote about Conway's wizards on my blog. When I had three essays on the subject I combined them into a paper. Sue edited the essays and the paper. I am honored to be included in this respected volume and I want to share this honor with Sue.
Kvant was a very popular science magazine in Soviet Russia. It was targeted to high-school children and I was a subscriber. Recently I discovered that a new magazine appeared in Russia. It is called Kvantik, which means Little Kvant. It is a science magazine for middle-school children. The previous years' archives are available online in Russian. I looked at 2012, the first publication year, and loved it. Here is the list of the math puzzles that caught my attention.
The first three problems are well known, but I still like them.
Problem 1. There are 6 glasses on the table in a row. The first three are empty, and the last three are filled with water. How can you make it so that the empty and full glasses alternate, if you are allowed to touch only one of the glasses? (You can't push one glass with another.)
Problem 2. If it is raining at midnight, with what probability will there be sunshine in 144 hours?
Problem 3. How can you fill a cylindrical pan exactly half-full of water?
I like logic puzzles, and the next two seem especially cute. I like the Parrot character who repeats the previous answer: very appropriate.
Problem 4. The Jackal always lies; the Lion always tells the truth. The Parrot repeats the previous answer—unless he is the first to answer, in which case he babbles randomly. The Giraffe replies truthfully, but to the previous question directed to him—his first answer he chooses randomly.
The Wise Hedgehog in the fog stumbled upon the Jackal, the Lion, the Parrot, and the Giraffe, although the fog prevented him from seeing them clearly. He decided to figure out the order in which they were standing. After he asked everyone in order, "Are you the Jackal?" he was only able to figure out where the Giraffe was. After that he asked everyone, "Are you the Giraffe?" in the same order, and figured out where the Jackal was. But he still didn't have the full picture. He started the next round of questions, asking everyone, "Are you the Parrot?" After the first one answered "Yes", the Hedgehog understood the order. What is the order?
Problem 5. There are 12 cards with the statements "There is exactly one false statement to the left of me," "There are exactly two false statements to the left of me." ..., "There are 12 false statements to the left of me." Pete put the cards in a row from left to right in some order. What is the largest number of statements that might be true?
The next three problems are a mixture of puzzles.
Problem 6. Olga Smirnov has exactly one brother, Mikhail, and one sister, Sveta. How many children are there in the Smirnov family?
Problem 7. Every next digit of number N is strictly greater than the previous one. What is the sum of the digits of 9N?
Problem 8. Nine gnomes stood in the cells of a three-by-three square. The gnomes who were in neighboring cells greeted each other. Then they re-arranged themselves in the square, and greeted each other again. They did this one more time. Prove that there is at least one pair of gnomes who didn't get a chance to greet each other.
As I told you before I was recently diagnosed with severe sleep apnea. My doctor ordered me to use a CPAP machine&mdasha Continuous Positive Airway Pressure machine&mdashthat blows air into my nose and improves the quality of overnight breathing.
I was elated, hoping for a miracle. I haven't had a good night's sleep in 20 years. I was so looking forward to waking up rested.
When I went to bed, I put on my nose mask and turned on the machine. The mask was uncomfortable. It gave me headaches and I had to sleep on my back which I do not like. It also had this annoying plastic smell. It took me some time to fall asleep, but eventually I did.
To my disappointment I didn't wake up rested; I woke up tired as usual. Still, I decided not to give up and continued trying the machine.
Several days passed and I found myself mopping the kitchen floor. I never ever mop floors. I have my cleaning crew do that. That mopping was my first positive sign. Then my relatives started telling me that my voice had changed and had become more energetic. A week later I invited my son and his family for my weekly family dinner, which I have been canceling every previous week for several months.
A month after I began sleeping with the machine, I started having night dreams, something I forgot even existed. After two months, I would wake up and my first thought would be, "What day is it today?" Prior to using the machine, my first waking thought was, "My alarm clock must be broken. It's impossible that I have to get up now. I feel too weak to stand up."
My machine is very smart. It records the data from my sleep and uploads it to a website, which my doctor and I can access. Instead of the 37 apnea episodes per hour I had during my sleep study, now I have 1 episode per hour. The quality of my life has changed gradually. I am not yet ready to conquer the world, but I have so much more energy. I've even accepted two more job offers, and now I have six part-time jobs. (I'll tell you all about this some other time.)
There have been some side effects. For some reason I gained 10 pounds during the first two weeks of using the machine. And I feel like an elephant. Not because of my heavy frame, but because my nose mask with its pipe looks like a trunk.
But I prefer feeling like an elephant to feeling like a zombie. This indeed was a miracle, though a very slow-acting miracle.
One day you meet your friend Alice enjoying a nice walk with her husband Bob and their son Carl. They are excited to see you and they invite you to their party.
Alice: Please, come to our party on Sunday at our place at 632 Elm St. in Watertown.
Bob: My wife likes exaggerating and multiplies every number she mentions by 2.
Carl: My dad compensates for my mom's exaggerations and divides every number he mentions by 4.
Alice: Our son is not like us at all. He doesn't multiply or divide. He just adds 8 to every number he mentions.
Where is the party?
Since I was a child I prided myself on knowing arithmetic. I knew how to add fractions. I knew that 2/3 plus 1/4 is 11/12. Some kids around me were struggling and often summed it up the wrong way by adding numerators and denominators separately and getting 3/7 as a result.
As I grew older I found more reasons to ignore the wrong way. For example, the result of such addition depends on the representation of a fraction, not on the fraction itself, and this was bad.
Oh well. I was growing older, but not wiser. Now mathematicians study this wrong addition of fractions. They call such a sum a mediant of two rational numbers. To avoid the dependency on the representation of fractions, the fractions are assumed to be in the lowest terms.
Let us start with the sequence of fractions: 0/1 and 1/0. This sequence is called the Stern-Brocot sequence of order 0. The Stern-Brocot sequence of order n is generated from the Stern-Brocot sequence of order n − 1 by inserting mediants between consecutive elements of the sequence. For example, the Stern-Brocot sequence of order 2 is 0/1, 1/2, 1/1, 2/1, 1/0.
Where are the trees promised in the title? We can build a portion of this binary tree out of the sequence of order n in the following manner. First, ignore the starting points 0/1 and 1/0. Then assign a vertex to every number in the sequence. After that, connect every mediant to one of the two numbers it was calculated from. More precisely, if a number first appeared in the i-th sequence, its only parent is the number that first appeared in the sequence i−1.
There is beautiful theorem that states that every non-negative rational number appears in the Stern-Brocot sequences. The proof is related to continued fraction. Suppose a rational number r is represented as a continued fraction [a_{0};a_{1},a_{2},…,a_{k}], where a_{k} is assumed to be greater than 1 for uniqueness. Then this number first appears in the Stern-Brocot tree of order a_{0} + a_{1} + a_{2} + … + a_{k} + 1, and its parent is equal [a_{0};a_{1},a_{2},…,a_{k} − 1].
My PRIMES student, Dhroova Ayilam, was working on a project suggested by Prof. James Propp. The goal was to find out what happens if we start with any two rational numbers in lowest terms. Dhroova proved that as with the classical Stern-Brocot trees, any rational number in a given range appears in the tree. His paper Modified Stern-Brocot Sequences is available at the arXiv.
I was afraid of my advisor Israel Gelfand. He used to place unrealistic demands on me. After each seminar he would ask his students to prove by the next week any open problems mentioned by the speaker. So I got used to ignoring his requests.
He also had an idea that it is good to learn mathematics through problem solving. So he asked different mathematicians to compile a list of math problems that are important for undergraduate students to think through and solve by themselves. I still have several lists of these problems.
Here I would like to post the list by Andrei Zelevinsky. This is my favorite list, partially because it is the shortest one. Andrei was a combinatorialist, and it is surprising that the problems he chose are not combinatorics problems at all. This list was compiled many years ago, but I think it is still useful, just keep in mind that by calculating, he meant calculating by hand.
Problem 1. Let G be a finite group of order |G|. Let H be its subgroup, such that the index (G:H) is the smallest prime factor of |G|. Prove that H is a normal subgroup.
Problem 2. Consider a procedure: Given a polygon in a plane, the next polygon is formed by the centers of its edges. Prove that if we start with a polygon and perform the procedure infinitely many times, the resulting polygon will converge to a point. In the next variation, instead of using the centers of edges to construct the next polygon, use the centers of gravity of k consecutive vertices.
Problem 3. Find numbers a_{n} such that 1 + 1/2 + 1/3 + … + 1/k = ln k + γ + a_{1}/k + … + a_{n}/k^{n} + …
Problem 4. Let x_{1} not equal to zero, and x_{k} = sin x_{k-1}. Find the asymptotic behavior of x_{k}.
Problem 5. Calculate the integral from 0 to 1 of x^{−x} over x with the precision 0.001.
I regret that I ignored Gelfand's request and didn't even try to solve these problems back then.
I didn't have any photo of Andrei, so his widow, Galina, sent me one. This is how I remember him.
I recently had a home sleep study. I was given a small box which I attached to my chest. I also had to attach a thingy to my finger and put small tubes into my nose. It was relatively easy. Now I have my report:
The total time in bed is 468 minutes. Overall AHI is 37 events per hour. The supine AHI is 58 events per hour. The oxygen saturation baseline is 91%. The hypoxemic burden is 58 minutes. The oxygen saturation nadir is 63%. The heart rate ranges from 76-118 beats per minute.
I didn't have a clue what all that meant so I hit the Internet. AHI means Apnea–Hypopnea Index, and a normal score is below 5. Anything above 30 indicates severe sleep apnea. Because mine is 37, I now have my diagnosis. My 63% oxygen saturation scared me the most. Wikipedia says 65% or less means impaired mental function. I do not need mental function when I sleep, but Wikipedia also says that loss of consciousness happens at 55%. What would happen if I lose consciousness while I sleep? Can I die? Will I wake up?
Overall the sleep study was a great thing. Now I know the diagnosis and there are ways to treat it. So I am looking forward to my improved energy and health.
But there was something in this report that would bother any mathematician. As you can see apnea gets worse when people sleep on their backs. (Thanks to this study I learned a new English word: supine means lying on the back.) The apparatus that I had to attach to my chest prevented me from sleeping on my stomach, one of my favorite sleep positions.
This report doesn't say anything about my average AHI when I am not supine. If this average is low, then the solution might be to learn to never sleep on the back. It also means that the oxygen saturation nadir number is not very meaningful. It shows how bad it can be if I am forced to sleep on my back. It doesn't say much about my standard sleep situation.
When I next see my doctor, I hope she'll have answers to all my questions.
This story started when my student asked for an explanation for his grade B in linear algebra. He was slightly above average on every exam and the cut-off for an A was the top 50 percent of the class. I wrote a post in which I asked my readers to explain the situation. Here is my explanation.
The picture below contains histogram for a typical first midterm linear algebra exam.
The spike in the lowest range indicates zeros for those who missed the exam.
The mean is 74.7 and the median 81.5. As you can see the median is 7 points higher than the mean. That means that if a student performs around average on all the exams, s/he is in the bottom half of the class.
But this is not the whole story. In addition to the above, MIT allows students to drop the class after the second midterm. Suppose 30 students with lower grades drop the class; then the recalculated median for the first midterm for the students who finish the course goes up to 85. This is a difference of more than 10 points from the original average.
If this was a statistics class, then I could have told the puzzled student that he deserves that B. Instead I told him that he didn't even have the highest score among those with Bs. Somehow that fact made him feel better.
Here is my new logic puzzle.
I thought of a positive integer that is below 100 and is divisible by 7. In addition to the public knowledge above, I privately tell the units digit of my number to Alice and the tens digit to Bob. Alice and Bob are very logical people, but their conversation might seem strange:
Alice: You do not know Tanya's number.
Bob: I know Tanya's number.
What is my number?
I recently posted a cute puzzle about the emperor and his wizards from 2015 Moscow Math Olympiad. It is time for the solution and two new variations. But first let me repeat the puzzle.
The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.
During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to discover what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.
Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.
Solution: Suppose the emperor knows one good wizard. Then he can create a chain that leads him to an evil wizard, as follows: Suppose Alice is the known good wizard. The emperor chooses some other wizard, say Bob, and asks Alice "Is Bob evil?" (which question Alice, being good, will answer truthfully). If Bob turns out to be evil, the emperor can expel him, and repeat this (starting with Alice) next round. If Bob turns out to be good, the emperor can continue, asking Bob about Carl, etc, until he either reaches an evil wizard or determines that all remaining wizards are good.
The above means that, if the emperor can find a good wizard sacrificing at most one (other) good wizard, the emperor will succeed. Here is one way to do this: Let the emperor pick Anne and ask everyone else whether Anne is good. Suppose at least one wizard, say Bill, says that Anne is good. The emperor expels Bill. If Bill is revealed to be evil, then nothing is lost, and the emperor can try again next round. If Bill is revealed to be good, then the emperor knows for sure that Anne is good and can proceed to expel all the remaining evil wizards with the chain method above. If, on the other hand, no one says that Anne is good, then the emperor expels Anne. If Anne proves evil, the emperor didn't lose anything and can conduct another trial next round. If Anne proves good, then everyone else is evil, and the emperor can expel them all without asking any more questions.
I like the mathematical part of the puzzle, but I hate when innocent people are punished. So I couldn't stop thinking about the puzzle until I found a variation where no good wizard need be expelled (the magic properties of the gate are redundant now, since the emperor only ever sends evil wizards through it):
The setting is the same as before, except the emperor knows how many evil wizards there are. He wants to expel all the evil wizards without expelling a good one. For which numbers of evil wizards can he do that?
In addition, my reader Leo Broukhis couldn't get through my CAPTCHAs to post a comment (I think there's something wrong with the plugin) but sent me a variation of the original puzzle by email:
There is again an emperor with a magic gate plagued with a superfluity of evil wizards, but this time the carnival is not very long, so the emperor does not have the luxury of asking the wizards many questions. In fact, he is restricted to asking all of them the same single question, after which he will conduct a series of expulsions that must rid the empire of evil wizards while expelling at most one good one. The one saving grace to this difficult situation is that the question need not be limited to "Yes" or "No" answers—an unbounded (single) integer is permissible.
My favorite problem at the 2015 Moscow Olympiad was about an emperor and his wizards.
8-10th grade. Designed by I.V. Mitrofanov. The emperor invited 2015 of his wizards to a carnival. Some of the wizards are good and others are evil. The good wizards always tell the truth, whereas the evil ones are free to say anything they want. The wizards know who is who, but the emperor does not.
During the carnival, the emperor asks every wizard a yes-or-no question. Then he expels one of the wizards from his kingdom. The expelled wizard leaves through a magic door, which allows the emperor to realize what kind of wizard s/he was. After that the emperor starts the next round of questions and expels another wizard. He continues the rounds until he decides to stop.
Prove that it is possible to expel all the evil wizards, while expelling not more than one good wizard.
Two other problems at the Olympiad were noteworthy—because no competitor solved them:
11th grade. Designed by O.N. Kosuhin. Prove that it is impossible to put the integers from 1 to 64 (using each integer once) into an 8 by 8 table so that any 2 by 2 square considered as a matrix has a determinant that is equal to 1 or −1.
9th grade. Designed by A.Y. Kanel-Belov. Do there exist two polynomials with integer coefficients such that each of them has a coefficient with absolute value exceeding 2015, but no coefficient of their product has absolute value exceeding 1?
I am scared of that old German gentleman. Forgot his name. Oh, yeah. Alzheimer.
I started to lose my brain processing speed a long time ago. By my estimates I am about 100 times slower than I used to be. From time to time someone gives me a puzzle I remember I solved in 30 seconds years ago, but now it takes me 30 minutes. And it is getting worse. When I moved to my new apartment recently, it took me a year to remember my own phone number.
On the positive side, I feel quite famous, according to one of the signs of success. I am often greeted by people I don't know.
My moment of action came when I was in my basement doing my laundry and couldn't remember how to turn on my washing machine. This is after 10 years of heavily using this damn machine. I started to look for the button to push, but there were no buttons. There were only knobs, and I couldn't find the word "on" anywhere. After struggling with my memory and with those knobs, I pulled out one of the knobs, and the machine started.
I panicked. I am afraid of Alzheimer's Disease. I do not want to become demented. I do not want to forget how to count or to stop recognizing my children. I do not want to become a drain on my children's time, emotions and money.
I had complained about my memory to my doctor before, but the only thing he ever found was anemia. This time I was more insistent. I had an MRI that ruled out tumors. I had more extensive blood tests that confirmed anemia and showed a Vitamin D deficiency. But then he sent me to a neurologist who suggested a sleep study. Finally I got a diagnosis of severe sleep apnea. I am so happy now. I might not have Alzheimer's Disease. In the worst case scenario, I might die in my sleep. In comparison, this doesn't sound so bad.
I want to come back to a middle-school Olympiad problem I posted a while ago.
Streamline School Olympiad 2000 (8th grade). You have six bags of coins that look the same. Each bag has an infinite number of coins and all the coins in the same bag weigh the same amount. Each different bag contains coins of a different weight, ranging from 1 to 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 you need to weigh the coins in order to confirm that the labels are correct?
The answer is unpretentious: one weighing is enough. We can take one 5-gram coin, two 4-gram coins, three 3-gram coins, four 2-gram coins and five 1-gram coins for the total of 35 grams. This number is not divisible by 6, so we can add one more 1-gram coin and weigh all of them against six 6-gram coins. I leave it to the reader to show that this solution works and to extrapolate the solution for any number of bags.
My new challenge is to find a weighing for the above problem using the smallest number of coins. What is the number of coins in such a weighing for a given number of bags?
I manually calculated this number for a small number of bags, but I would like to get a confirmation from my readers. Starting from 6 bags, I don't know the answer. Can you help me?
The 2015 Intel Science Talent Search results are out. This year they divided the prizes into three categories: basic research, global good, and innovation. All three top prizes in basic research were awarded to our PRIMES students:
PRIMES' success in this year's Siemens competition is even more impressive. Unlike Intel, Siemens didn't divide the projects into three groups. We took the first and second overall individual prizes.
PRIMES is the place for high school math research. Congratulations to all our students—and to me (and my colleagues) for a job well done!
I lead recitations for a Linear Algebra class at MIT. Sometimes my students are disappointed with their grades. The grades are based on the final score, which is calculated by the following formula: 15% for homework, 15% for each of the three midterms, and 40% for the final. After all the scores are calculated, we decide on the cutoffs for A, B, and other grades. Last semester, the first cutoff was unusually low. The top 50% got an A.
Some students who were above average on every exam assumed they would get an A, but nonetheless received a B. The average scores for the three midterm exams and for the final exam were made public, so everyone knew where they stood relative to the average.
The average scores for homework are not publicly available, but they didn't have much relevance because everyone was close to 100%. However, a hypothetical person who is slightly above average on everything, including the homework, should not expect an A, even if half the class gets an A. There are two different effects that cause this. Can you figure them out?
One day I received a call on my home line. I do not like calls from strangers, but the guy knew my name. So I started talking to him. I assumed that it was some official business. He told me that their company monitors Internet activities, and that my computer is emitting viruses into the Internet traffic degrading Internet performance. All I need to do is to go to my computer and he will instruct me how to get rid of my viruses.
While he was saying all this, I covered my phone's microphone and made a call to the police from my cell phone. I was hoping the police could trace the call and do something while I kept the line to the guy open. The police told me to hang up. They said there is nothing they can do.
Meanwhile, the guy on the phone kept directing me to my Start button while I kept telling him that I can't find it. After talking to the police, I got so angry that I told the guy that I wasn't actually looking for the Start button, but talking to the police. So the guy asks, "What does the police say?"
These people are laughing at us. They know that the police do nothing. And then continued instructing me about my Start button.
Have you ever solved a CalcuDoku puzzle, or a MathDoku puzzle? Maybe you have, but you do not know it. Many incarnations of this puzzle are published under different names. The MIT's Tech publishes it as TechDoku. What distinguishes this puzzle type from most others is that it is trademarked. The registered name is KenKen. So anyone can invent and publish a KenKen puzzle as long as they do not call it KenKen.
In this variously named puzzle you need to reconstruct a Latin square, where cells of a square are grouped into regions called cages. Each cage has a number and an operation (addition, subtraction, multiplication, division) in the upper-left corner of the cage. The operation applied to the numbers in the cage must result in a given value. For non-commutative operations (subtraction and division), the operation is applied starting from the largest number in the cage.
These are my two NOT KenKen puzzles. I will call them TomToms, the name for this puzzle used by Tom Snyder in his The Art of Puzzle LINK blog. In the TomTom variation, cages without a number in a corner are allowed and the operation might be missing, but it has to be one of the standard four. The first puzzle I call Three Threes and the second is a minimalistic version where only one number without the operation is given.
But my goal today is not to discuss KenKen or its ekasemans. Ekaseman is the reverse of the word namesake. My son Alexey invented the term ekaseman to denote a different name for the same thing. My real goal is to discuss a new type of puzzle that can be called Crypto KenKen. In this puzzle the digits in the corner are encrypted using a substitution cipher: each digit corresponds to its letter. I first saw this puzzle at Tom Snyder's blog, where it is called TomTom (Cipher). I think the crypto version of this puzzle deserves its own name. So I suggest PamPam: it is an encryption of KenKen as well as TomTom. And it would be nice to have a female name for a change.
It is time to report on my weight loss progress. Unfortunately, the report is very boring; I am still stuck at the same weight: 225. What can I do? Let's laugh about it. Here are some jokes on the subject.
* * *
After the holidays I stepped on my scale. After an hour I tried again and had a revelation: tears weigh nothing!
* * *
I am on a miracle diet: I eat everything and hope for a miracle.
* * *
Ideas to lose weight: A glass of water three days before your meal.
* * *
I wanted to lose five pounds by this summer, now I have only ten pounds to lose to reach my goal.
I wrote a paper with my son, Alexey Radul, titled (Not so) Much Ado About Nothing. As the title indicates, nothing is discussed in this paper. It's a silly, humorous paper full of puns about "nothing." We submitted the paper to the arXiv two months ago, and it has been on hold since then.
This reminds me of an earlier paper of mine that the arXiv rejected because it didn't have journal references. (Not so) Much Ado About Nothing is done in proper style. It follows all the formal rules of math papers, and contains references, acknowledgements, an introduction with motivation, and results. However, the results amount to nothing. The fact that this paper is not accepted is a good sign. It means the arXiv doesn't just look at the papers formally; they look at the content as well.
On the other hand, the paper is submitted as a paper in recreational mathematics, and it is humorous, so it could have been accepted, since nothing is more recreational than nothing.
Neither rejection nor acceptance would have surprised me. The only thing I do not understand is why it is on hold. Why hold on to nothing?
I know how to walk. Everyone knows how to walk. Or so I thought. Now I am not sure any more.
I've been taking ballroom dance lessons on and off for many years. But at some point I stopped progressing. I got stuck at the Silver level. I know many steps and am a good follower, but I often lose balance and my steps are short.
Then I met Armin Kappacher, an unusual dance coach for the MIT Ballroom dance team. I would like to share some of his wisdom with you, but Armin doesn't have much presence on the web. He only wrote one article for Dance Archives: A Theoretical and Practical Approach to "Seeing The Ground of a Movement."
Although I've been attending his classes for several years, I haven't been able to understand a word. He might say, "Your right arm is disconnected from your chest center." But what does that mean? Others seemed to understand him, because they greatly improved under his guidance. But I was so out of touch with my body that I couldn't translate his words into something my body could understand. Being a mathematician, I lived my whole life in my brain. I never tried to listen to my body. I was never aware of whether my forehead was relaxed or tensed, or if my pelvic floor was collapsed. I grasped that it was my own fault that I failed to understand Armin. I stuck with his classes.
After three years of group classes, I asked Armin for a private lesson with an emphasis on the basics. He instructed me to take three steps and quickly discovered my issues, which included:
So now I am taking walking classes from Armin. I am slowly starting to feel what Armin means when he says that my pelvic floor is collapsed. I feel better now. Whenever I pay attention to how I am walking, my posture improves. As a result, I feel more confident, my mood approves, and I feel like more oxygen is getting to my brain. My friends have noticed a change. For example, my son Sergei got married recently, and I was sitting under the Chuppah during the ceremony (see photo). Afterwards, several friends told me that I looked like a queen.
I have to give some credit to my earrings. They were too long and were getting caught on my dress. So I was constantly trying to wiggle my head up—using Armin's techniques.
I proudly brought this photo to Armin to show him my queen-like posture. He told me that I look okay above the chest center. But below the chest center my spine is still collapsed. Next time I will take sitting lessons with Armin.
Skyscraper puzzles are one of my favorite puzzles types. Recently I discovered a new cute variation of this puzzle on the website the Art of Puzzles. But first let me remind you what the skyscraper rules are. There is an n by n square grid that needs to be filled as a Latin square: each number from 1 to n appears exactly once in each row and column. The numbers in the grid symbolize the heights of skyscrapers. The numbers outside the grid represent how many skyscrapers are seen in the corresponding columns/row from the direction of the number.
The new puzzle is called Skyscrapers (Sum), and the numbers outside the grid represent the sum of the heights of the skyscrapers you see from this direction. For example, if the row is 216354, then from the left you see 8(=2+6); and from the right you see 15(=4+5+6).
Here's an easy Skyscrapers (Sum) puzzle I designed for practice.
The Art of Puzzles has four Skyscrapers (Sum) puzzles that are more difficult than the one above:
* * *
A button of unknown functionality should be pressed an even number of times.
* * *
When I tell you that I am closer to 30 than to 20, I mean to tell you that I am 42.
* * *
If a car with a student-driver sign gets its windshield wipers turned on, then the car is about to turn.
* * *
I always learn from the mistakes of people who followed my advice.
* * *
A traffic policeman stops a car:
—You're going 70 in a 35 miles-per-hour zone.
—But there are two of us!
* * *
The most popular tweet, "Live your life so that you do not have time for social networks."
I recently wrote a post about the ApSimon's Mints problem:
New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material. Therefore, fake coins weigh the same no matter where they've been minted. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings in order to deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?
The post was accompanied by my paper Attacking ApSimon’s Mints.
Unfortunately, both the post and the paper contain wrong information. They both state that the number of coins as a sequence of the number of mints is 1, 2, 4, 8, 15, 38, 74. This is wrong. I took this data from the sequence A007673 in the OEIS database. The sequence had incorrect data lying dormant for 20 years. I believe that the sequence was generated from the paper of R. K. Guy and R. J. Nowakowsky, ApSimon's Mints Problem, published in Monthly in 1994. To the credit of Guy and Nowakowsky, they never claimed to find the best solution: they just found a solution, thus providing a bound for the sequence. Someone mistook their solution for the optimal one and generated the sequence in the database.
After my post, my readers got interested in the problem and soon discovered the mistake. First Konstantin Knop found a solution for 6 mints with 30 coins and for 7 mints with 72 coins. Konstantin is my long-time collaborator. I trust him so I was sure the sequence was flawed. Then someone located a reference to a paper in Chinese A New Algorithm for ApSimon's Mints Problem. Although none of my readers could find the paper itself nor translate the abstract from Chinese. But judging from the title and the formulae it was clear that they found better bounds than the sequence in the database. My readers got excited and tried to fix the sequence. David Reynolds improved on Konstantin's results with a solution for 6 mints with 29 coins and for 7 mints with 52 coins. David did even better on his next try with 28 and 51 coins correspondingly. He also found a solution with 90 coins for 8 mints. Moreover, his exhaustive search proved that these were the best solutions.
Now the sequence in the database is fixed. It starts 1, 2, 4, 8, 15, 28, 51, 90.
For future generations I would like to support each number of the sequence by an example. I use the set P(Q) to represent the sequence of how many coins are taken from each mint for the first(second) weighing. For one mint, only one coin and one weighing is needed. ApSimon himself calculated the first five values, so they were not in dispute.
There is a solution for nine mints using 193 coins that is not confirmed to be optimal. It was found by David Reynolds: P=(1,2,4,12,5,4,20,39,43) and Q=(0,1,3,3,25,33,34,18,27). In addition, David Reynolds provided a construction that reduces the upper bound for n mints to (3^{(n+1)}−2n−3)/4. The following set of coins work: P=(1,3,7,15,…,2^{n}−1) and Q=(1,4,13,40,…,(3^{n}−1)/2).
Recently I wrote that my blog is under attack by spam comments. Most of the comments were caught by my spam-filter Akismet, the best-known filter for WordPress. I was receiving about 50,000 comments a day and 200 of them were sneaking through this filter. I had to moderate those and delete them. This was an extreme waste of my time. But I can understand that the bots achieved some goal. None of their comments made it to my website, but at least I myself was made aware of opportunities for hair removal in Florida.
The comments crashed my server and I had to install CAPTCHAs. I was happy that the number of comments that I had to moderate went down, but the total number of comments was still so high that my server kept crashing. Now that the comments are blocked from human view, why are they still pouring in? One software package is trying to inform the other software package about weight-loss wonder drugs. I am convinced that Akismet is not interested.
My hosting provider couldn't handle the traffic and asked me to upgrade to a more advanced hosting package. It's annoying that I have to pay a lot of money for these bots' attempts to sell Akismet fake Louis Vuitton bags.
The upgrade was too expensive, so I tried a different solution. I closed comments for older posts. It didn't help. The bad software continued trying to leave comments that can't be left. They especially like my post about Cech cycles, called A Mysterious Bracelet. My weblog tells me that every second someone downloads this page and tries to leave a comment. But no one will ever see these comments. Even Akismet will never know what it is missing: it might have had a chance to make $5,000 a day from home.
I recently posted the following old Olympiad problem:
Prove that you can choose 2^{k} numbers from the set {1, 2, 3, …, 3^{k}−1} in such a way that the chosen set contains no averages of any two of its elements.
Let me show how to find 2^{k} − 1 such numbers. We can pick all the numbers that have 0 or 1 in their ternary representation. Let me prove that this set doesn't contain averages. Summing two such numbers doesn't involve carry, and the sum will contain a 1 in each place where the digits differ. On the other hand, a double of any number in this set doesn't contain ones.
This solution is pretty, but it is not good enough: we need one more number. We can add the number 3^{k}−1. I will leave it to the reader to prove that the largest number in the group whose binary representation consists only of twos can be added without any harm.
There are other ways to solve this problem. It is useful to notice that multiplying a no-average set by a constant or adding a constant to it, doesn't change the no-average property.
If we were allowed to use 0, then the problem would have been solved. As zero doesn't belong to the initial range, we can add zero and shift everything by 1. The resulting sequence is sequence A3278. This sequence is the lexicographically first non-averaging sequence.
Another solution was suggested by devjoe in my livejournal mirror blog site. If we multiply our non-averaging set (the one that doesn't have twos in their ternary representation) by 2, we get a set of all numbers that do not contain ones in their ternary representation. By linearity, such a set doesn't contain averages either. We can add 1 to this set.
The Intel International Science and Engineering Fair announced 2014 Grand Awards. I worked with three out of the top five mathematical award winners. Now I can brag that I've got my finger in more than half of the world's best high-school math research.
To be clear: I wasn't actually mentoring these projects, but I supervised two of the projects and I trained the third student for several years. So I'm proud to list the award-winning papers:
How interesting that each of these three students is from a different part of my present career. It certainly feels that I am in all the right places.
* * *
A mathematical tragedy: two parallel lines fall in love.
* * *
Life is not fair, even among gadgets: the desktop misbehaves, the monitor gets smacked.
* * *
An amazing magic trick! Think of a number, add 5 to it, then subtract 5. The result is the number you thought of!
* * *
—How can you distinguish a mathematician from a physicist?
—Ask for an antonym for the word parallel.
—And?
—A mathematician will answer perpendicular, and a physicist serial.
* * *
—How can you distinguish a physicist from a mathematician?
—Ask the person to walk around a post.
—And?
—A physicist will ask why, and a mathematician clockwise or counter-clockwise?
* * *
—Some bike thief managed to open my combination lock. How could they possibly guess that the combo was the year of the canonization of Saint Dominic by Pope Gregory IX at Rieti, Italy?
—What year was that?
—1234.
* * *
—Hello? Is this the anonymous FBI tip-line?
—Yes, Mr. Benson.
* * *
—My five-year-old son knows the first 20 digits of Pi.
—Wow!
— I use it as the password on my laptop, where I keep all the games.
* * *
I learned three things in school: how to rite and how to count.
I recently published a crypto word search puzzle: a word search puzzle where all the letters are encrypted by a substitution cypher. The answer to such a puzzle is a word or a phrase formed by those decrypted letters that are not in the hidden words.
The puzzle I posted was easy. It can be solved by analyzing the repeated letters in the hidden words. The new puzzle is more difficult. No hidden word has repeated letters.
The hidden words are: FUN, HUNT, SOLVE, STARK, TABLE, THINK.
The puzzle below can be defined as a Crypto Word Search. Guess what needs to be done in this puzzle. The answer is a word.
The hidden words are: DUKE, EYES, RUSE, WORD, WUSS.
The idea of a crypto word search came to me from a beautiful, but devilishly difficult, puzzle In the Details, designed by Derek Kisman. In the Details can be described as a fractal word search; it contains a crypto word search as one of the simpler steps.
Let us call a natural number awesome if it can be represented as a^{b} + b^{a}, where a and b are natural numbers. For example, number 57 is awesome as 57 = 2^{5} + 5^{2}. Is 2014 awesome?
What parking spot number is the car parked in?
John Conway likes playing with the Fibonacci sequence. He invented many new sequences using the following trick. The next number in the sequence is the sum of the two previous number adjusted in some way. Free Fibonacci sequences were invented this way. Here is the recurrence for an n-free Fibonacci sequence: the next number in the sequence is the sum of the previous two numbers divided by the highest possible power of n.
Let us calculate a 2-free Fibonacci sequence starting with 5 and 4: 5, 4, 9, 13, 11, 3, 7, 5, 3, 1, 1, 1, …. I leave it to the reader to show that any 2-free sequence ends with a cycle of length one.
Let us try a 3-free Fibonacci sequence starting with 5 and 6: 5, 6, 11, 17, 28, 5, 11, 16, 1, 17, 2, 19, 7, 26, 11, 37, 16, 53, 23, 76, 11, 29, 40, 23, 7, 10, 17, 1, 2, 1, 1, 2, and so on. We are now in the cycle of length 3. Is this always the case? Not quite. If there is a 1-1-2 cycle there should be a 2-2-4 cycle, or any cycle k-k-2k, where k is coprime with 3. But the question remains: does it always end in a cycle of length 3?
I published a paper Free Fibonacci Sequences with Brandon Avila. We conjecture that a 3-free Fibonacci sequence always ends in a cycle and support this conjecture with a probabilistic argument. We were amused by how the behavior changes when we move to 4-free Fibonacci sequences. It seems that in this case sequences never cycle. We were even more amused when we moved to 5-free Fibonacci sequences and discovered that the behavior changes again.
When n equals 5 there are some sequences that cycle. Can you find the cycles? There are also sequences that grow indefinitely and we do not need a probabilistic argument to prove that. Consider Lucas numbers: 2, 1, 3, 4, 7, 11, and so on. This is a Fibonacci-like sequence that never has a term divisible by 5. Thus Lucas numbers form a 5-free Fibonacci sequence. We made a probabilistic argument that most of the starting terms converge eventually to a Lucas-like sequence that grows indefinitely because there are no terms divisible by 5.
What happens for larger n? We didn't manage to find any cycles there. Would you like to try?
My weight loss progress is progress no more. I am stuck at 225.
I have my morning routine. I wake up and jog to the facilities; then I weigh myself. Why do I do this in this order? Because I do not use an alarm-clock. I depend on my own hydro-alarm that wakes me up every morning very reliably. The downside is that this alarm doesn't have a snooze button. I just have to get up, and get up very fast. So I have to relieve myself first; then I can weigh myself calmly. As a collateral benefit, by availing myself first, I get a slightly better result.
While weighing myself every day, I noticed some patterns. My weight is slightly better if I get a long night of sleep. I guess my availing is more voluminous then.
Another pattern that I noticed is that if I do not eat after 5:00 pm, I do not gain weight and sometimes I lose a bit; if I do eat after 5:00 pm, even a very light dinner, I can gain up to 3 pounds. This becomes a struggle and sometimes hunger wins. So I stick to the plan for three weeks, and then one moment of tiredness and hunger, one dinner, and, boom, I am back where I was.
This is even affecting my social life. I stopped inviting friends and family for dinner and I am tense whenever I visit my friends in the evening.
The surprising thing is that my system worked at the beginning. I keep asking myself what the difference is. I think I was strongly motivated and excited about my weight loss plan. It's impossible to sustain that level of excitement, so I've adopted a new element in my plan. I decided to replace my initial excitement by external motivation. I am now listening to motivational tapes in my car. We'll see.
Whenever I am under stress, I turn to jokes. My recent problems with spam attacks on my blog led me to surf the web for new math jokes. Here are some of my recent translations from Russian.
* * *
Two is the same thing as eight, to some degree.
* * *
A girl to her mathematician boyfriend:
— Let's do something that is forbidden tonight.
— Divide by zero?
* * *
If thoughts converge, they are bounded.
* * *
A mathematician's son:
— Dad, how do I write the number 8?
— That's easy: rotate the infinity symbol by pi over 2.
* * *
My student couldn't take an integral from my book. So he took the book together with all the integrals there.
* * *
Archimedes, Pascal and Newton play hide and seek. Archimedes is the seeker. Pascal hides, but Newton draws a 1-meter square around himself. Archimedes opens his eyes and shouts:
— I see Newton!
— Oh, no! One newton per square meter is the pascal.
* * *
What a pleasure to smoke an e-cigarette after cybersex...
* * *
Russians were the first in the world to create a computer program that passes the Turing test. Scientists tested the program using several Russians with a variety of questions, and each time the program gave the same answer as the people. The reply to every question was, "Go f*ck yourself!"
* * *
There are two types of people: those who know nothing about fractals and those who think that there are two types of people: those who know nothing about fractals and those who think that there are two types people…
My readers noticed that my blog disappeared several times. Here's what's been happening. Spammers were sending tens of thousands of comments a day, which crashed the server several times. My hosting provider doteasy.com couldn't handle it and took down my blog. They asked me to install CAPTCHAs.
Installing CAPTCHAs became a big issue. Since I started my blog in 2008 I've never bothered to update the Wordpress software. As a result, all the CAPTCHA plugins I tried to install wouldn't work. I had no choice but to update Wordpress. After so many years, this would surely not be a simple matter. So I decided to hire someone to help. It took me a month to find Brett Mellor, but finally he updated my Wordpress software.
Updating such an old database starts with a backup. We didn't want to back up all the tens of thousands of spam comments, but we couldn't sort through them, because my hosting provider was blocking the user-friendly access to my blog. We were forced to delete all the new comments. In the process, I've lost some of the legitimate comments as well. I apologize for that. If you do not see your comments, please resubmit.
In addition, we had to re-number all the categories, so the old category links no longer work.
I was paralyzed by all the stress of not only losing access to my blog, but also not knowing how to solve the problem. This prevented me from writing for three months, and for this I apologize as well.
Now my blog is updated and CAPTCHAs are installed. I've gone from 50,000 spam comments per day to 500. However, my hosting provider still complains about unusual activity and spam comments.
Your brilliant suggestions are very welcome.
I always wanted to be a person of the world. I wanted my genes to be a mixture of everything. I was glad that I had a great-grandfather from Poland and a great-great-great-grandmother from France. I was also thrilled when my mom told me that her Asian students think she is one of theirs. So I decided to send my DNA to 23andMe and really see what I have.
To my surprise, my world is not as mixed as I expected: I am 99.5% European. My Asian part is minuscule: 0.2%, out of which only 0.1% is assigned as Yakut. My African part is also 0.2%.
My European part is a mixture of mostly eastern and northern European. I am 2.8% Ashkenazi.
In addition to my genetic profile, 23andMe sent me the list of a thousand of my distant relatives. They also sent me a report about the most common last names among my relatives. The list starts with Cohen and continues with Levine, Levin, Goldberg, and Rubin.
You might be surprised by this list of Jewish names when I am only 2.8% Jewish. But the list is based on people who decided to send their DNA to 23andME and provided their last names. All my Russian relatives remained in Russia. Russia has its own company, I-gene, that provides a similar service, and the two databases are not shared.
Only my distant relatives who moved to the US and who are curious about their ancestry and who are willing to share their last names will appear on this list. So maybe this list is not surprising.
Here is an old Olympiad problem:
Prove that you can choose 2^{k} numbers from the set {1, 2, 3, …, 3^{k}−1} in such a way that the chosen set contains no averages of any two of its elements.
* * *
—Describe yourself in three words.
—Lazy.
* * *
Internet forum:
—Tell me about yourself.
—I am lazy and I like to eat.
—Tell me some more.
—I am tired of typing. I'll go grab a snack.
* * *
—Why do you want to divorce your wife?
—She nags too much. For the last half six month, she's been bugging me everyday to throw away the Christmas tree.
* * *
Yesterday I realized that I'm not the laziest person in the world. I saw my neighbor walking the dog on a leash through his window.
* * *
The list of symptoms of laziness:
1)
This is a variation on an old quiz. Can you answer the last question?
—An airplane carries 500 bricks. One of the bricks falls out. How many bricks are left in the airplane?
—This is easy: 499!
—Correct. Next question. How do you put a giraffe into a refrigerator?
—Open the refrigerator, put in the giraffe, and close the refrigerator door.
—Good, next. How do you put an elephant into a refrigerator?
—Open the refrigerator, take out the giraffe, put in the elephant and close the door.
—Correct. The Lion King is hosting his birthday party. All the animals come to congratulate him—except one. Why?
—The elephant couldn't come because it is in the refrigerator.
—Fantastic, next. A man needs to cross a river inhabited by crocodiles and he doesn't have a boat. What should he do?
—He can just swim: all the crocodiles are attending Lion King's birthday party.
—Amazing! The last question: The man swims across the river, and dies. What happened?
Hugh ApSimon described the following coin puzzle in his book Mathematical Byways in Ayling, Beeling and Ceiling.
New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material: fake coins weigh the same independently of the mint. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings so that you can deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?
I will follow ApSimon's notation. Suppose P_{r} and Q_{r} is the number of coins from the mint r used in the first and the second weighing correspondingly. That is, we are minimizing Σmax(P_{r},Q_{r}). (All my summations are over all the mints. I skip the summation limits because it is difficult to write math in html.) Let us denote by W the weight of the genuine coin and by W(1 + ε) the weight of the fake coin. We do not know ε, except that it is not zero.
Let d_{r} be either 0 or 1, depending on what material the r-th mint uses. Thus, the coin from the r-th mint weighs W(1 + d_{r}ε). We know the results of these two weighings and the weight of the genuine coin. Therefore, we can calculate the following two values: a = ΣP_{r}d_{r}ε and b = ΣQ_{r}d_{r}ε.
It is clear that we need to request at least one coin from each mint and use it in at least one weighing: P_{r} + Q_{r} > 0. If both sums a and b are zero, then all the mints are producing genuine coins. Neither of the two values gives us much information as we do not know ε. We can get rid of ε by dividing a by b.
There are 2^{n} − 1 combinations of possible answers: these are subsets of the set of mints producing fake coins given that there is at least one. Thus we need to select numbers P_{r} and Q_{r}, so that a/b produces 2^{n} − 1 possible answers for different sets of values of d_{r}.
Let us consider cases in which the total number of mints is small. If there is one mint we can take one coin and we won't even need a second weighing. For two mints we need one coin from each mint for a total of 2. For three mints, one coin from each mint is not enough. I leave this statement as an exercise. It is possible to test three mints with four coins: one each from the first and second mints and two from the third mint. The coins from each mint for the first and second weighings are (0,1,2) and (1,1,0) respectively.
To prove that this works we need to calculate (d_{2} + 2d_{3})/(d_{1} + d_{2}) for seven different combinations of d_{r}. I leave this as an exercise.
This puzzle seems to be very difficult. We only know the answer if the number of mints is not more than seven. The corresponding sequence A007673 in the OEIS is: 1, 2, 4, 8, 15, 38, 74. It is possible to give bounds for this sequence, but they are so far apart. The lower bound is n. And the ApSimon's book offers a construction for two weighings were P_{r} = r! and Q_{r} = 1.
You can try to find a better construction, or you can try calculating more terms of the sequence. You can also read more about this problem in my short paper Attacking ApSimon's Mints.
I do not want to leave the readers with the puzzle that might end up being intractable. So I suggest the following easy puzzle. Solve the ApSimon's Mints problem assuming that the weight of the fake coin is known.
I once took an accent reduction course, to modify my Russian accent in English. In the first class the teacher explained that the biggest reason people have strong accents is that they stop learning and trying to improve their speech as soon as they can be understood. I promised myself to never stop learning and to continue working on my accent reduction forever.
Once I was giving a lecture on probability and statistics at the IAP mathematical series. My last slide was about the research on the correlation between masturbation male habits and prostate cancer. Their interpretation of the data had been wrong and a very good example of what not to do.
So I looked directly into the eyes of the course coordinator, who was observing my lecture, and without realizing what I was saying, asked, "Do we have time for masturbation?"
Everyone started laughing and I had to present my slide in order to explain myself.
The news of my double entendre spread. Soon after that I was asked to give a lecture at the Family Weekend at MIT. I wonder if that is why the lecture coordinator asked me not to discuss masturbation as small children might be present.
Luckily that was the only fallout from my blooper. Anyway, I decided to stop working on my accent. When people understand that English is not my first language they forgive more readily my slips of tongue.
* * *
—Honey, have you blocked our computer?
—Yes.
—What's the password?
—Our wedding date.
—%?#!!
* * *
—What's the pin on our card?
—We're on a public chat, honey. Why don't I sms it?
—But I forgot my phone. Please tell me, cupcake!
—Okay. By digit: the second digit of our apartment number, the fourth digit of your phone number, the month of my birthday, and the number of our children.
—Got it. How clever! 8342, right?
* * *
—Where is the report?
—We are stuck. The tech people took our monitor with passwords.
—What!?!
—Our monitor got broken so the techs took it for repair. Our passwords were written on the stand.
Here is a setup that works for the several puzzles that follow it:
The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat—from his inexhaustible supply—on every wizard's head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan's signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide together on a strategy.
I wrote about puzzles with this setup before in my essay The Wizards' Hats. My first request had been to maximize the number of wizards who are guaranteed to survive. It is easy to show that you cannot guarantee more than 50 survivors. Indeed, each wizard will be right with probability 0.5. That means whatever the strategy, the expected number of wizards guessing correctly is 50. My second request had been to maximize the probability that all of them will survive. Again, the counting argument shows that this probability can't be more than 0.5.
Now here are some additional puzzles, including the first two mentioned above, based on the same setup. Suggest a strategy—or prove that it doesn't exist—in which:
As I mentioned, I already wrote about the first two questions. Below are the solutions to those questions. If you haven't seen my post and want to think about it, now is a good time to stop reading.
To guarantee the survival of 50 wizards, designate 50 wizards who will assume that the total number of red hats is odd, and the rest of the wizards will assume that the total number of red hats is even. The total number of red hats is either even or odd, so one of the groups is guaranteed to survive.
To make sure that all of them survive together with probability 0.5, they all need to assume that the total number of red hats is even.
I love making math questions out of the movies. Here is a Mission Impossible III question.
Tom Cruise is cute. He plays Ethan Hunt in Mission Impossible movies. In Mission Impossible III he needs to steal the Rabbit's Foot from a secure skyscraper in Shanghai. He arrives in Shanghai and studies the skyscraper looking out his window. He decides to break in through the roof. And the way to get to the roof is to use a rope and swing across from another, even taller, skyscraper. 1:21 minutes into the movie, Ethan Hunt calculates the length of the rope he will need by using the projection of a skyline on his window, as seen on the first picture.
Explain why the projection is not enough to calculate the length of the rope. What other data does he need for that? Ethan Hunt does request extra data. But he makes one mistake. He uses his pencil as a compass to draw the end of the rope curve, as seen on the second picture. Explain what his mistake is.
I mentor three PRIMES projects. One of them, with Joshua Xiong from Acton-Boxborough Regional High School, is devoted to impartial combinatorial games. We recently found a connection between these games and cellular automata. But first I need to remind you of the rules of Nim.
In the game of Nim there are several piles with counters. Two players take turns choosing a pile and removing several counters from it. A player loses when he or she who doesn't have a turn. Nim is the most famous impartial combinatorial game and its strategy is well known. To win, you need to finish your move in a so called P-position. Nim P-positions are easy to calculate: Bitwise XOR the number of counters in all the piles, and if the result is zero then it's a P-position.
The total number of counters in a P-position is even. So we calculated the sequence a(n): the number of P-positions in the game of Nim with three piles with the total number of counters equal to 2n. As soon as we got the sequence we plugged it into the OEIS, and voilà it was there: The sequence A130665 described the growth of the three branches of the Ulam-Warburton cellular automaton.
The first picture shows the automaton after 6 generations. The automaton consists of cells that never die and it grows like this: start with a square on a square grid. In the next generation the squares that share exactly one side with the living squares are born. At the end remove the Southern branch.
Everything fell into place. We immediately realized that the language of the automata gives us the right words to describe what we know about the game of Nim.
Now we want to describe the automaton related to any impartial combinatorial game. Again, the cells never die and the initial cells correspond to terminal P-positions. People who write programs for calculating P-positions will find a notion of the next generation very natural. Indeed, the program usually starts with the terminal P-positions: they are generation 0. Then we can proceed by induction. Suppose we have found P-positions up to generation i. Denote the positions that are one move away from generation i and earlier as N_{i}. Then the P-positions that do not belong to generation i and earlier and from which all moves belong to N_{i} are the P-positions from generation i + 1.
This description explains the generations, but it doesn't explain who is the parent of a particular P-position. The parent-child relations are depicted as edges on the cellular automaton graph. The parent of position P_{1} from generation i + 1 is a P-position P_{2} in generation i that can be reached from P_{1} in the game.
The parent-child relationship in the game of Nim is especially easy to explain. A P-position P_{1} is a parent of a P-position P_{2} if P_{1} differs from P_{2} in exactly two piles and it has one fewer counter in each of these piles. For example, a P-position (1,3,5,7) has six parents, one of them is (1,3,4,6). In the game with thee piles a P-position always has exactly one parent.
A position in the game of Nim with three piles is naturally depicted as a triple of numbers, that is as a point in 3D. The picture below shows the Nim automaton in 3D at generation 6.
Our paper, Nim Fractals, about sequences enumerating P-positions and describing the automaton connection in more detail is posted at the arXiv:1405.5942. We give a different, but equivalent definition of a parent-child relationship there. A P-position P_{1} is a parent of P_{2} if there exists an optimal game such that P_{1} is achieved from P_{2} in exactly two moves in a game which takes the longest number of possible moves.
There are too many Olympiads. Now there is even a special undergraduate Olympiad in probability, called Kolmogorov Student Olympiad in Probability. It is run by the Department of Probability Theory of Moscow State University. I just discovered this tiny Olympiad, though it has been around for 13 years.
A small portion of the problems are accessible for high school students. These are the problems that I liked. I edited them slightly for clarity.
Second Olympiad. Eight boys and seven girls went to movies and sat in the same row of 15 seats. Assuming that all the 15! permutations of their seating arrangements are equally probable, compute the expected number of pairs of neighbors of different genders. (For example, the seating BBBBBBBGBGGGGGG has three pairs.)
Third Olympiad. One hundred passengers bought assigned tickets for a 100-passenger railroad car. The first 99 passengers to enter the car get seated randomly so that all the 100! possible permutations of their seating arrangements are equally probable. However, the last passenger decides to take his reserved seat. So he arrives at his seat and if it is taken he asks the passenger in his seat to move elsewhere. That passenger does the same thing: she arrives at her own seat and if it is taken, she asks the person to move, and so on. Find the expected number of moved passengers.
Third Olympiad. There are two 6-sided dice with numbers 1 through 6 on their faces. Is it possible to "load" the dice so that when the two dice are thrown the sum of the numbers on the dice are distributed uniformly on the set {2,...,12}? By loading the dice we mean assigning probabilities to each side of the dice. You do not have to "load" both dice the same way.
Sixth Olympiad. There are M green and N red apples in a basket. We take apples out randomly one by one until all the apples left in the basket are red. What is the probability that at the moment we stop the basket is empty?
Seventh Olympiad. Prove that there exists a square matrix A of order 11 such that all its elements are equal to 1 or −1, and det A > 4000.
Twelfth Olympiad. In a segment [0,1] n points are chosen randomly. For every point one of the two directions (left or right) is chosen randomly and independently. At the same moment in time all n points start moving in the chosen direction with speed 1. The collisions of all points are elastic. That means, after two points bump into each other, they start moving in the opposite directions with the same speed of 1. When a point reaches an end of the segment it sticks to it and stops moving. Find the expected time when the last point sticks to the end of the segment.
Thirteenth Olympiad. Students who are trying to solve a problem are seated on one side of an infinite table. The probability that a student can solve the problem independently is 1/2. In addition, each student will be able to peek into the work of his or her right and left neighbor with a probability of 1/4 for each. All these events are independent. Assume that if student X gets a solution by solving or copying, then the students who had been able to peek into the work of student X will also get the solution. Find the probability that student Vasya gets the solution.
The Russian website problems.ru has a big collection of math problems. I use it a lot in my work as a math Olympiad coach. Recently I was giving a statistics lesson. While there was only one statistics problem on the website, it was a good one.
Assume that every person in every country was tested for IQ. A country's IQ rating is the average IQ of the population. We also assume that for the duration of this puzzle no one is born and no one dies.
- A group of citizens of country A emigrated to B. Show that the rating of both countries can go up.
- After that a group of citizens of B (which may include former citizens of A) emigrated to A. Is it possible that the ratings of both countries go up again?
- A group of citizens of A emigrated to B, and a group of citizens of B emigrated to C. As a result, the ratings of each country increased. After that the migration went the opposite way: some citizens of C moved to B, and some citizens from B moved to A. As a result, the ratings of all three counties went up once more. Is this possible? If yes, then how? If no, then why not?
My AMSA students loved the following puzzle from the 2003 Math Kangaroo contest for grades 7-8:
The children A, B, C and D made the following assertions.How many of the children were telling the truth?
- A: B, C and D are girls.
- B: A, C and D are boys.
- C: A and B are lying.
- D: A, B and C are telling the truth.
A) 0 B) 1 C) 2 D) 3 E) Impossible to determine
I was given this puzzle at the last Gathering for Gardner.
Use arithmetic operations to express 6 using three identical digits. For each digit from 0 to 9 find at least one way to express 6.
For example, I can express 6 using three twos in many ways: 2 + 2 + 2, or 2 · 2 + 2, or 2^{2} + 2. But the problem doesn't ask for many ways. One way is enough, but you need to do it for every digit. So nine more cases to go: 0, 1, 3, 4, 5, 6, 7, 8, and 9.
My son, Alexey Radul, is a programmer. He taught me the importance of laziness in programming.
One of his rules:
Not to write the same line of code in the same program twice.
If you need the same line of code in the same program, that means you should either use a loop or outsource the line to a function. This style of coding saves time; it makes programs shorter and more elegant. Such programs are easier to debug and understand.
I remember how I copied and pasted lines of code before he taught me this rule. Then I needed to change parameters and missed some of the lines during changing. Debugging was such a headache.
Mathematicians are way lazier than programmers. Consider the system of two equations: x+2y=3 and 4x+5y=6. There are no repeating lines here. Only letters x and y appear twice. Mathematicians invented the whole subject of linear algebra and matrices so that they would not need to rewrite variables.
Mathematicians are driven by laziness. Once ancient mathematicians first solved a quadratic equation, they didn't want to do it again. So they invented a formula that solves all quadratic equations once and for all.
I try to keep up with tradition. I try to make my theorems as general as possible. When I write my papers, I try to make them short and simple. When I think about mathematics I try to get to the stage where the situation is so clear I can think about it without paper and pencil. I often discover new theorems while I am in bed, about to fall asleep. Sometimes I wake up with a good idea. So I do my job while I sleep.
I love my profession. I get paid for being lazy.
This is one of my favorite jokes:
Three logicians walk into a bar. The waitress asks, "Do you all want beer?"
The first logician answers, "I do not know."
The second logician answers, "I do not know."
The third logician answers, "Yes."
This joke reminds me of hat puzzles. In the joke each logician knows whether or not s/he wants a beer, but doesn't know what the others want to drink. In hat puzzles logicians know the colors of the hats on others’ heads, but not the color of their own hats.
This is a hat puzzle which has the same answers as in the beer joke. Three logicians walk into a bar. They know that the hats were placed on their heads from the set of hats below. The total number of available red hats was three, and the total number of available blue hats was two.
Three logicians walk into a bar. The waitress asks, "Do you know the color of your own hat?'"
The first logician answers, "I do not know."
The second logician answers, "I do not know."
The third logician answers, "Yes."
The puzzle is, what is the color of the third logician's hat?
This process of converting jokes to puzzles reminds me of the Langland's Program, which tries to unite different parts of mathematics. I would like to unite jokes and puzzles. So here I announce my own program:
Tanya's Program: Find a way to convert jokes into puzzles and puzzles into jokes.
Each time I see John Conway he teaches me something new. At the Gathering for Gardner he decided to quiz me on how well I know a regular six-sided die. I said with some pride that the opposite sides sum up to 7. He said, "This is the first level of knowledge." So much for my pride. I immediately realized that the next level would be to know how all the numbers are located relative to each other. I vaguely remembered that in the corner where 1, 2, and 3 meet, the numbers 1, 2, and 3 are arranged in counter-clockwise order.
Here's how John taught me to remember every corner. There are two types of corners. In the first type numbers form an arithmetic progression. John calls such numbers counters. He chose that name so that it would be easy to remember that counters are arranged in counter-clockwise order. The other numbers he calls chaos: their increasing sequence goes clockwise.
Once I grasped that, I relaxed thinking that now I know dice. "What about the third level?" he asked. "What third level?" "Now that you know which number goes on which side, you need to know how the dots are arranged." Luckily, there are only three sides on which the dots are not placed with rotational symmetry: 2, 3, and 6. And they all meet in a corner, which John calls the home corner. The rule is that the diagonals formed by the dots on the sides with 2, 3, and 6, meet in the home corner. You might argue that 6 doesn't have a diagonal. But if you look at 6, you can always connect the dots to form the letters N or Z, depending on the orientation of the die. When you lay the letter N on its side, it becomes the letter Z. Thus they define the same diagonal. This diagonal has to meet the diagonals from 2 and 3 in the corner.
When I came home from the conference I picked up a die and checked that the rules work. There are 8 corners. It is enough to remember one corner of numbers to recover the other numbers by using the opposite sum rule. But it is nice to have a simple rule that allows us to bypass the calculation. Four of the corners have numbers in arithmetic progression: 1:2:3, 1:3:5, 2:4:6, and 4:5:6. They are counters and they are arranged counter-clockwise. The other four corners are: 1:2:4, 1:4:5, 2:3:6, and 3:5:6, and they are arranged clockwise.
I wanted to provide a picture of a die for this post and went online to see if I could grab one. Many of the graphic images of dice, as opposed to photographs, were arranged incorrectly. Clearly these visual artists did not study dice with John Conway.
Then I decided to check my own collection of dice. Most of them are correct. The ones that are incorrect look less professional. Here is the picture. The ones on the right are correct.
I started my Yellow Road a year ago on February 9, 2013, when my weight was 245.2 pounds. My system worked for eight months. I lost 25 pounds. Then I went to two parties in a row and gained four pounds. According to my plan, I was supposed to eat only apples after lunch. It was too difficult to stick to that, and I got off-target. My target weight continued decreasing daily, as per my plan, while I got stuck. The growing difference between my real weight and my target weight was very discouraging, so I lost my momentum.
I decided to reset the target weight and restart the plan. I changed my plan slightly to incorporate the lessons I had learned about myself.
On February 9, 2014, I started my New Yellow Road. I weighed 223.2 pounds. So I reset my target weight to be 223.2 on February 9. Each day my target weight goes down by 0.1 pounds. I weigh myself each morning. If I am within one pound of my target weight, I am in the Yellow zone and I will eat only fruits and vegetables after 5:00 pm. If I am more than one pound over my target weight, I am in the Red Zone and will eat only apples after 5:00 pm. If I am more than one pound below my target weight, I can eat anything.
I want to tell you the story of my "successful" salary negotiation. The year was 2003 and I had a temporary visiting position at Princeton University. I wanted to move to Boston and my friend showed my resume to Alphatech. The interview went well and they offered me a position as Lead Analyst with a salary of $110.000. This was particularly good news considering that the tech job market was very weak in 2003.
At that time, I was working very hard on building my self-esteem. I read lots of books and was in therapy for two years. I decided to practice what I had learned to try to negotiate a bigger paycheck. While speaking to the HR guy on the phone, I was standing up, as I was taught, and projecting my voice firmly with my chest opened up. I could hardly believe it when I heard myself ask for a $10,000 increase.
Despite my wonderful posture, the human resource person refused. However, he remembered that they had forgotten to give me a moving bonus. He asked me about my living conditions. I told him that I lived in a four-bedroom house. I didn't elaborate: it was a tiny four-bedroom house made out of a garage. I made a counter offer: forget the moving bonus, but give me my salary increase as I asked. He agreed.
For the first year, there was no real difference, because the salary increase was equal to the moving bonus. But I was planning to stay with the company for a long time, so by the second year, my clever negotiation would start to pay off. My negotiations were a success. But were they?
Things change. The boss who hired me and appreciated me stopped being my boss. The company was bought by BAE Systems who were not interested in research. To my surprise, I started getting non-glowing performance reviews. Luckily, by that time I had made a lot of friends at work, and one of them not only knew what was going on, but was willing to tell me. My salary was higher than that of other employees in the same position. Salary increases were tied to performance. They wanted to minimize my increases to bring my salary into the range of others at my level. So to justify it, they needed a negative performance review. After one negative review it is difficult to change the trend. A negative review stays on the record and affects the future reputation.
In a long run I am not sure that my salary negotiations were a success.
There is a famous puzzle about three light bulbs, that is sometimes given at interviews.
Suppose that you are standing in a hallway next to three light switches that are all off. There is another room down the hall, where there are three incandescent light bulbs—each light bulb is operated by one of the switches in the hallway. You can't see the light bulbs from the hallway. How would you figure out which switch operates which light bulb, if you can only go to the room with the light bulbs one and only one time?
This puzzle worked much better in the past when we only had incandescent light bulbs and so didn't need to specify the type of bulbs. Unfortunately, the standard solution only works with incandescent bulbs and the word "incandescent" nowadays needs to be stated. But the use of "incandescent" is a big hint. Indeed, incandescent light bulbs generate heat when they are on, so the standard solution is to turn on the first light switch, to keep the second switch off, and to turn the third switch on for five minutes before turning it off. In the room, the light bulb corresponding to the first switch will be lit, and out of the two unlit bulbs, the one corresponding to the third switch will be warm.
It's a cute solution, but there could be so many other approaches:
I invite my readers to invent other methods to solve this problem. Be creative. After all, if I were to interview you for a job, I would be more impressed by a new solution than the one that is all over the Internet.
You arrive at an archipelago of many islands. On each island there are two villages. In one village truth-tellers live, and they always tell the truth. In the other village liars live, and they always lie. The islanders all know each other.
On the first island you stumbled upon three islanders and you ask each of them your question:
How many truth-tellers are there among you?
Here are their answers:
A: One.
B: A is wrong.
C: A and B are from the same village.
Can you determine who is a truth-teller and who is a liar?
This island is called a classic island, where all behave as if they were in a standard logic puzzle. It is a perfectly nice puzzle but B and C didn't answer the question: B ratted on A, and C went on a tangent. When I was younger, I never cared about the motivations of A, B, or C. Their answers are enough to solve the puzzle. But now that I am older, I keep wondering why they would choose these particular answers over other answers. So I invented other islands to impose rules on how the villagers are allowed to answer questions.
Now you travel to the next island that is called a straightforward island, where everyone answers your question exactly. You are in the same situation, and ask the same question, with the following result:
A: One.
B: One.
C: Ten.
Can you determine who is a truth-teller and who is a liar?
Once again we wonder about their motivation. This time C told an obvious lie, an answer that is impossible. Why on earth did he say 10? Isn't the goal of lying to deceive and confuse people? There is nothing confusing in the answer "ten."
Now you come to the third island, which is a straightforward inconspicuous island. To answer your question, a liar wouldn't tell you an obvious lie. For this particular situation, the liar has to choose one of the four answers that are theoretically possible: zero, one, two, or three. You are again in the same situation of asking three people how many truth-tellers are among them, and these are the answers:
A: Two.
B: Zero.
C: One.
Can you determine who is a truth-teller and who is a liar?
When you think about it, a truth-teller cannot answer zero to this question. So although zero is a theoretically possible answer, we can deduce that the person who said it is a liar. If liars are trying to confuse a stranger, and they're smart, they shouldn't answer "zero."
The next island is a straightforward inconspicuous smart island. The liars on this island are smart enough not to answer zero. You are in the same situation again and ask the same question with the following outcome:A: Two.
B: Two.
C: One.
Can you determine who is a truth-teller and who is a liar? You shouldn't be able to. There are three possibilities. There are two truth-tellers (A and B), one truth-teller (C), or zero truth-tellers.
Let us assign probabilities to liars' answers. Assume that liars pick their answers randomly from the subset of wrong answers out of the set: one, two, three. If two of these answers are incorrect, they pick a wrong answer with probability one half. If all three of the answers are incorrect, they pick one of them with probability one-third. Suppose the people you meet are picked at random. Suppose that the probability that a random person is a truth-teller is 1/2. Given the answers above, what is more probable: that there are two truth-tellers, one truth-teller, or zero truth-tellers?A movie passes the Bechdel Test if these three statements about it are true:
Surely there should be a movie where two women talk about the Bechdel test. But I digress.
The Bechdel test website rates famous movies. Currently they have rated 4,683 movies and 56% pass the test. More than half of the movies pass the test. There is hope. Right? Actually they have a separate list of the top 250 famous movies. Only 70 movies, or 28%, from this list pass the test.
My son Alexey suggested the obvious reverse Bechdel test, which is more striking than the Bechdel test. A movie doesn't pass the test if it
I can't think of any movie like that. Can you?
* * *
A Roman walks into a bar, holds up two fingers, and says, "Five beers, please."
* * *
To understand what a recursion is, you must first understand recursion.
* * *
A guy is complaining to his mathematician friend:
— I have a problem. I have difficulty waking up in the morning.
— Logically, counting sheep backwards should help.
* * *
— Can I ask you a question?
— You can, but you have already just done that.
— Darn, what about two questions?
— You can, but that was your second question.
* * *
The Internet ethics committee worked hard to generate a list of words that should never be used on the Internet. The problem is, now they can't post it.
* * *
Quantum entanglement of a pair of socks: As soon as one is designated as the left, the other instantly becomes the right.
The last MIT Mystery Hunt was well-organized. It went smoothly—unlike the hunt that my team designed the year before. Sigh. As I do every year, here is the list of 2014 puzzles related to math.
There were also several puzzles requiring decoding or having a CS flavor.
I want to mention one non-mathematical puzzle.
You visit an island of three towns: Trueton, Lieberg and Alterborough. Folks living in Trueton always tell the truth. Those who live in Lieberg, always lie. People from Alterborough alternate strictly between truth and lie. You meet an islander who says:
Two plus two is five. Also, three plus three is six.
Can you determine which town he is from?
It should be easy. He made two statements: the first one is false, the second is true. So he must be from Alterborough.
But what about "also"? How should we interpret this transition? There are many ways to interpret this "also." On one hand it could mean: In addition to the previous statement I am making another statement. On the other hand it could mean: The previous pause shouldn't be considered as the end of the statement; the whole thing should be interpreted as one statement. Besides this person was speaking not writing. Are we sure that the first period was not meant to be a comma or a semi-colon? If we assume that the quote is one statement, then the speaker might be either a liar or an alternator.
Here is a puzzle for you from the same island:
One night a call came into 911: "Fire, help!" The operator couldn't ID the phone number, so he asked, "Where are you calling from?" "Lieberg." Assuming no one had overnight guests from another town, is there an emergency? If so, where should help be sent? And was it a fire?
Now find the ambiguities.
The MIT Mystery Hunt starts on Friday. My old team—Manic Sages— fell apart after last years' hunt. My new team—Death and Mayhem—started sending us daily practice puzzle to prepare for the hunt.
Today's puzzle was written by Paul Hlebowitsh. As usual, the answer is a word or a phrase.
Puzzle 3: Humans
"After a long day taking care of the animals, it's good to unwind by letting the taps flow."
Tap 1: Sierra Nevada Pale Ale
Tap 2: Lagunitas Pale Ale
Tap 3: 21st Amendment "Brew Free! or Die IPA"
Tap 4: Wachusett Blueberry
Tap 5: Harpoon UFO
Alice, Bob, Carol, Danny, Erica, Fred, and Gregario, the seven children of Noah, went to a local bar before the flood to get drinks. Accounts of night vary, and no one remembers exactly what happened, but some facts have become clear:
Who ordered which drinks and in what order?
I stopped losing weight. My Yellow Road plan stopped working. If you recall I draw a line on the weight/time plane which I call my target weight. If I'm more than one pound above my target weight, then I'm in the red zone and must restrict my evening food to apples. The hour at which the evening starts depends on how many pounds I'm above my target weight.
And now, back to my bump.
First I stopped following the plan exactly. I realized that I didn't need to restrict myself to eating only apples in the evening when I am in the red zone. I can use salad or anything light.
One day I found myself in the red zone weighing two pounds over my target weight. I was invited to dinner that evening. I decided to accept the invitation and skip the plan for one day. At the party the food was so good I couldn't resist it. The next day I was four pounds over my target weight.
My Yellow Road plan requires me in this situation to eat only apples from 2:00pm onward, but I knew that applying this restriction after 6:00pm worked for me. I decided not to torture myself and started to restrict my food only from 6:00pm. The weight didn't go down. Even though I went to bed very hungry for two weeks, it didn't work.
After these two weeks, I started to feel hungry all the time and even began dreaming about food. As a result, my food intake increased. Now I am seven pounds over my target weight. I've reached a plateau. For the last two months I've been stuck at 220 pounds.
There is some good news: I now have a partner on this journey. After I started my program, I received an email from Natalia Grinberg from Germany. She offered to join forces. We send each other weekly updates on our progress and cheer each other along. Natalia's path wasn't smooth from the start, so she tried to supplement her diet with Almased, which is very popular in Europe. Because Natalia likes it, I looked into it. While I am afraid of pills and chemical ingredients, Almased seems to be okay. It contains soy, yogurt, honey, and vitamins. I bought one can. It is expensive and tastes awful. I'll experiment with cinnamon or pepper and see if that helps. Will Almased help me get over the Bump?
I collect geeky jokes. I think I've heard most of them. So I was surprised to stumble upon a website with many new ones: 50 People On 'The Most Intellectual Joke I Know'. These are some of them:
* * *
Q: What does the "B" in Benoit B. Mandelbrot stand for?
A: Benoit B. Mandelbrot.
* * *
Entropy isn't what it used to be.
* * *
There are two types of people in the world: those who can extrapolate from incomplete data sets
* * *
This sentence contains exactly threee erors.
* * *
There's a band called 1023MB. They haven't had any gigs yet.
* * *
A logician's wife is having a baby. The doctor immediately hands the newborn to the dad. His wife asks impatiently, "So, is it a boy or a girl"? The logician replies, "Yes."
* * *
The barman says, "We don't serve time travelers in here."
A time traveler walks into a bar.
* * *
The first rule of Tautology club, is the first rule of Tautology club.
* * *
A woman walks in on her husband, a string theorist, in bed with another woman. He shouts, "I can explain everything!"
* * *
What do you get when you cross a joke with a rhetorical question?
I used to love arXiv. I've long thought that it was one of the best things that happened to mathematics. arXiv makes mathematical research available for free and without delay. Moreover, it is highly respected among mathematicians. For example, Grigori Perelman never submitted his proof of the Poincaré conjecture to any journal: he just posted it on arXiv.
When I came back to mathematics, all my math friends explained to me that I should submit my paper to arXiv on the same day that I submit it to a journal. As my trust in arXiv grew, I started submitting to arXiv first, waiting one week for comments, and then submitting to a journal.
Now it seems that arXiv might not love its contributors as much as they used to. arXiv moderators seem to be getting harsher and harsher. Here is my story.
In June of 2013, I submitted my paper "A Line of Sages" to arXiv. This paper is about a new hat puzzle that appeared at the Tournaments of the Towns in March 2013. The puzzle was available online at the Tournaments of the Towns webpage in Russian. After some thought I decided that it is better to cite the Tournament itself inside the body of the paper, rather than to have a proper reference. Online references in general are not stable, and this particular one was in Russian. Very soon this competition will be translated into English and the puzzle will appear in all standard math competition archives.
arXiv rejected my paper. A moderator complained that I didn't have a bibliography. So I created a bibliography with the link to the puzzle. My paper was rejected again saying that the link wasn't stable. Duh. That's the reason why I didn't put it there from the start. I Goggled the puzzle and I still didn't find any other links.
I argued with my moderator that the standards for papers in recreational mathematics are different from the standards for purely research papers. Short recreational notes do not require two pages of history and background, nor a long list of references. A recreational paper doesn't need to have theorems and lemmas.
Meanwhile, the moderator complained that the paper was "not sufficiently motivated to be interesting to the readership."
I got tired of exchanging emails with this moderator and submitted my paper to The Mathematical Intelligencer, where it was immediately accepted. So I dropped my submission to arXiv.
Now my paper is not available for free on arXiv. But anyone can freely buy it from Springer for $39.95.
I started my life wanting to be a mathematician. At some point I had to quit academia in order to feed my children. And so I went to work in industry for ten years. Now that my children have grown, I am trying to get back to academia. So I am the right person to compare the experience of working in the two sectors. Just remember:
Money. The pay is much better in industry. About twice as high as academia.
Time. I almost never had to work overtime while working in industry. That might not be true for programmers and testers. As a designer, I worked at the beginning of the project stage. Programmers and testers are closer to deadlines, so they have more pressure on them. The industrial job was more practical than conceptual, so I didn't think about it at home. My evenings and weekends were free, so I could relax with my children. In academia I work 24/7. There are 20 mathematical papers that I have started and want to finish. This is a never-ending effort because I need those papers to find my next job. Plus, I want to be a creative teacher, so I spend a lot of time preparing for classes. I do not have time to breath.
Respect. When I was working in industry, some of my co-workers would tell me that I was the smartest person they ever met. In any case, I always felt that my intelligence and my skills were greatly appreciated. In academia, I am surrounded by first-class mathematicians who rarely express respect and mostly to those who supersede them in their own fields.
Social Life. Mathematics is a lonely endeavor. Everyone is engrossed in their own thoughts. There is no urge to chat at the coffee machine. In industry we were working in teams. I knew everyone in my group. I was closer to my co-workers when I worked in industry.
Freedom. In both industry and academia there are bosses who tell you what to do. But while building my university career, a big part of my life is devoted to writing papers. It is not a formal part of my job, but it is a part of the academic life style. And in my papers I have my freedom.
Motivation. In academia, one must be self-motivated.
Rejection. The output of an academic job is published papers. Most journals have high rejection rates. For me, it's not a big problem because from time to time I get fantastic reviews and I usually have multiple papers awaiting review. I have enough self-confidence that if my paper is rejected, I don't blink. I revise it and send it to a different journal. But this is a huge problem for my high school students who submit their first paper and get rejected. It is very discouraging.
Perfectionism. In industry I was working on deadlines. The goal was to deliver by the deadline a project that more or less worked. Time was more important than quality. My inner perfectionist suffered. When I write papers, I decide myself when they are ready for publication.
Impact. When I was working at Telcordia I felt that I was doing something useful. For example, we were building a local number portability feature, the mechanism allowing people to take their phone numbers with them when they moved. I wish Verizon had bought our product. Just a couple of months ago I had to change my phone number when I moved five blocks from Belmont to Watertown. Bad Verizon. But I digress. When I was working at Alphatech/BAE Systems, I was designing proofs of concepts for future combat systems. I oppose war and the implementation was sub-standard. I felt I was wasting my time. Now that I am teaching and writing papers, I feel that I am building a better world. My goal is to help people structure their minds and make better decisions.
Fame. All the documents I wrote in industry were secret. The world would never know about them. Plus, industry owns the copyright and takes all the credit. There is no trace of what I have done; there is no way to show off. People in academia are much more visible and famous.
Happiness. I am much happier now. I do what I love.
* * *
I just received a call from the delivery man working for the store where I ordered a new GPS device. He got lost and asked directions to my house.
* * *
I have two problems: I can't count.
* * *
Do you want to double your cash?
Hold your money in front of a mirror.
* * *
- Doctor, I think I have paranoia.
- Why is that?
- Yesterday I left my computer for ten minutes to go to the bathroom, and when I came back all my browser windows were filled with bathroom tissue ads.
* * *
- Why is your disc drive so noisy?
- It is reading a disc.
- Aloud?
* * *
If only DEAD people understand hexadecimal, how many people understand hexadecimal?
I gave the following puzzle from Raymond Smullyan's book What is the Name of this Book? to my AMSA students.
What happens if an irresistible cannonball hits an immovable post?
This puzzle is known as the Irresistible Force Paradox. The standard answer is that the given conditions are contradictory and the two objects cannot exist at the same time.
My AMSA student gave me a much cuter answer: The post falls in love with the cannonball as it is so irresistible.
It has been a while since I wrote my last essay and my readers have started to worry. Sorry for being out of touch, but let me tell you what is going on in my life.
In September I received an offer from MIT that changes my status there. In exchange for a slight increase in pay, I am now conducting recitations (supplemental seminars) in linear algebra In addition to my previous responsibilities.
My readers will know that just a slight increase in money in exchange for significant demands on my time would not appeal to me. But this offer comes with perks. First, my position at MIT changes from an affiliate to a lecturer, which looks so much better on my CV. Second, it includes benefits, the most important of which is medical insurance.
I lived without insurance for three years. On the bright side, lack of insurance made me conscious of my health. I developed many healthy habits. I read a lot about the treatments for colds and other minor problems that I had. On the other hand, it is a bit scary to be without insurance.
Many people are surprised to hear that I didn't have any insurance: Doesn't Massachusetts require medical insurance for everyone?
The Commonwealth levies a fine on those who do not have insurance. But I was in this middle bracket in which my income was too high for a subsidized plan, and too low to be fined. You see, the fine is dependent on one's income and is pro-rated. So I didn't have to pay it at all.
I got my insurance from MIT in October, but ironically my doctor's waiting list is so long, that my first check-up will not be until January.
Anyway, I sort of have four jobs now. I am coaching students for math competitions at the AMSA charter school six hours a week. I am the head mentor at the RSI summer program where I supervise the math research projects of a dozen high school students. I do the same thing for the PRIMES program, in which I have the additional responsibility of mentoring my own students. And as I mentioned, I am also teaching two recitation groups in linear algebra at MIT.
Teaching linear algebra turned out to be more difficult than I expected. I love linear algebra, but I had to learn the parts of it that are related to applications and engineering. Plus, I didn't know linear algebra in English. And my personality as a perfectionist didn't help because to teach linear algebra up to my standards would have taken more time than I really had.
This semester I barely had time to breathe, and I certainly couldn't concentrate on essay pieces. Now that this semester is almost over, my as yet unwritten essays are popping up in my head. It's nice to be back.
Hooray! My weight is down to two digits in kilograms: below 100. This is a big deal for me. I reached the desired number of digits. In pounds it means I weigh less than 220 and I've lost 25 pounds.
My friends have started to notice. The chubbier ones ask me to tell them about my Yellow Road. And I don't actually know what to reply, because the Yellow Road is not a solution. I took many steps before I approached the Yellow Road. The Yellow Road is, I hope, the end of the road.
The idea of the Yellow Road is simple. If I weigh more than I want, I decrease food. All my skinny friends have always lived that way. The problem is that the rest of us do not know how exactly to reduce food intake and then how to sustain that reduction.
So today, I would like to explain to my friends and my readers what I really think helped me to lose weight.
1. I got desperate. I was ready to do whatever it takes. I was prepared not to ever eat again. If I had to extract my calories from the air, I was prepared to do that. I was ready to be hungry and restrain myself for the rest of my life. In short, I was totally motivated.
2. I fought my sugar addiction. I used to crave sugar. I used to think that sugar helps my brain. But once I looked into it, I realized that I might be wrong. I decided to experiment and cut off my carbohydrates intake significantly. That was the most painful thing I had to do. But after a week of withdrawal symptoms, I felt better and stopped craving foods and sugars as much.
3. I wrote my weight down everyday. Having numbers staring me in the face reminded me what I ate the day before. This moment of reflection allowed me to understand what causes the increase or decrease in my weight. Now I know that some foods provoke my appetite: carbohydrates, dairy, mayonnaise. I eat them in small portions, but I do not start my day with them. It's better to have an increased appetite for a couple of hours in the evening, than for the whole day.
4. I had already changed some bad habits. I tried to build new healthy habits before I started my Yellow Road. These alone didn't help me lose weight, but I think they contribute to my weight loss. I still do the following:
I feel that an internal switch was turned off. I don't feel that hungry anymore. My son thinks that I'm in my hibernating state. I wonder if he is right and I will awake one day as hungry as ever.
My son, Alexey Radul, is gainfully unemployed. While looking for a new job he wrote several essays about his programming ideas. I am a proud and happy mother. While I can't understand his code, I understand his cutting-edge essays. Below are links to the four essays he has posted so far. He is also a superb writer. You do not need to take my word for it. Each link is accompanied by the beginning of the essay.
The successful fox must know more than the sum of what the hedgehogs know, for it must know the connections from one thing to another. This fact is key to the design of computer systems for solving certain kinds of problems. Read more
Automatic differentiation may be one of the best scientific computing techniques you’ve never heard of. If you work with computers and real numbers at the same time, I think you stand to benefit from at least a basic understanding of AD, which I hope this article will provide; Read more
The “Sufficiently Clever Compiler” has become something of a trope in the Lisp community: the mythical beast that promises language and interface designers near-unlimited freedom, and leaves their output in a performance lurch by its non-appearance. A few years ago, I was young enough to join a research project to build one of these things. Neglecting a raft of asterisks, footnotes, and caveats, we ended up making something whose essence is pretty impressive: you pay for abstraction boundaries in compile-time resources, but they end up free at runtime. One prototype was just open-sourced recently, so that makes now a good time to talk about it. Read more
The Cleverness of Compilers essay described the name of the hyperaggressive compilation game in broad, philosophical strokes. Here, I would like to walk through the Mandelbrot example in some detail, so that the interested reader may see one particular way to actually accomplish that level of optimization. Read more
I submitted four papers to the arXiv this Spring. Since then I wrote four more papers:
(with Leigh Marie Braswell) Cookie Monster Devours Naccis. History and Overview arXiv: arXiv 1305.4305.
In 2002, Cookie Monster appeared in The Inquisitive Problem Solver. The hungry monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for Fibonacci, Tribonacci and other nacci sequences.
A Line of Sages.
A new variation of an old hat puzzle, where sages are standing in line one behind the other.
(Jesse Geneson and Jonathan Tidor) Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs. Combinatorics arXiv: arXiv 1307.1169.
We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.
(with Leigh Marie Braswell) On the Cookie Monster Problem. History and Overview arXiv: arXiv 1309.5985.
The Cookie Monster Problem supposes that the Cookie Monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number of a set is the minimum number of moves the Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for jars containing cookies in the Fibonacci, Tribonacci, n-nacci, and Super-n-nacci sequences. We also construct sequences of k jars such that their Cookie Monster numbers are asymptotically rk, where r is any real number between 0 and 1 inclusive.
This is my toast at the Gelfand's Centennial Conference:
I moved to the US twenty years ago, right after I got my Ph.D in mathematics under the supervision of Israel Gelfand. My first conversation with an American mathematician went like this:
The guy asks me, "What do you do?"
I say, "Mathematics."
"No, I mean what is your field?"
I can't understand what he wants, and repeat "Mathematics."
He says, "No, no, I mean, I do differential geometry. What do you do?"
I do not know how to answer him. My teacher, Israel Gelfand, never mentioned that mathematicians divide mathematics into pieces. So I had to repeat, "My field is mathematics."
I got asked this question many times and I couldn't figure out how to give a satisfactory answer, so I quit academia. Well, I quit it not because of the question, but for many other reasons... But answering the question became so much easier when I worked for industry.
A guy asks me, "What do you do?"
I say, "Battle management."
He says, "What?"
I say, "Battle management. I manage battles, in case there is a war." And this is it, he doesn't ask any more questions … ever.
I always knew that industry was not the right place for me. Five years ago, when my children grew up, I realized that it was time to take some risks. So I resigned from my job, and came back to mathematics. But now I know how to answer the question. When someone asks me, What is your field in mathematics? I say, … brag, "I am a student of Israel Gelfand, I just do mathematics."
I would like to drink to the Unity of Mathematics.
Now that my weight loss is under way, I want to build an exercise program.
I already exercise. I am a member of the MIT ballroom dance team and I go to the gym, where I use the machines, swim, and take gentle yoga and Zumba classes.
Doesn't sound bad, right? But the reality is that I went to Zumba class a total of three times last year. I skipped half the dance classes I signed up for because I was too tired to attend. I had sincerely planned to go to them, but they're held in the evenings, when I'm already drooping.
The yoga situation is the worst. I'm scheduled to go to yoga twice a week, but just as it is time to leave for yoga, I get very hungry and cannot resist having a snack. Then I remember that they do not recommend practicing yoga after eating a meal, and voilà—I have found my excuse. I am all set up to exercise five hours a week, but in reality most weeks I do not exercise at all.
How can I motivate myself? I know that with food, if I have gained weight one day, I eat less the next. So if I've missed my goal of exercising one week, do I add those hours to the next week? That's unlikely to actually help, since the problem is that I'm not meeting my exercise goal, period.
Many people suggested that I punish myself. For example, if I do not meet my goal, I should donate money to a cause I do not support. This feels wrong. If I fail, I'll feel doubly guilty. I'll go broke paying for psychotherapy.
I can try to reward myself. But what should the reward be? Should I reward myself with a piece of tiramisu? Since I am trying to persuade myself that sugar is bad, I shouldn't create a situation that makes sugar desirable. So rewarding with food won't work. Should I buy myself something? If I really want it, I will buy it anyway.
I've been thinking about a plan for a long time. Finally I realized that I should find other people to reward me. I do have a lot of friends, and I came up with an idea of how they could help.
The next time I saw my friend Hillary I asked her if she wanted to sponsor my new exercise plan. She said, "I'm in," without even hearing the plan. Hillary is a true friend. This is what she blindly signed up for.
I decided to push myself to exercise five hours a week. Because of weather and health fluctuations, I pledged to spread 20 hours of exercise over four weeks. I will sent Hillary weekly reports of what I do. This is in itself a huge motivating factor. After the four weeks, we will go to lunch together, which is a great reward for me to look forward to. If I succeed with my plan, she pays for lunch. If I fail, I pay.
Once I saw how enthusiastic Hillary was, I lined up four other friends for the next four-week periods. I hope that after several months of exercise, I will learn to enjoy it. Or at least, I will start feeling the benefits and that itself will be a motivating factor.
Hillary liked my plan so much that she designed a similar exercise plan for herself. Now I am looking forward to two lunches with Hillary.
I was driving on Mass Pike, when the cars in front of me stopped abruptly. I hit the brakes and was lucky to escape the situation without a scratch.
Actually, it wasn't just luck. First of all, I always keep a safe distance from the other cars. Second, if I see the brake lights of the car in front of me, I automatically remove my foot from the gas pedal and hold it over the brake pedal until I know what the situation is.
On a highway, if the car in front of me has its brake lights on, usually that means that the driver is adjusting their speed a little bit. So, most of the time I don't have to do anything. Seeing that the car in front of me has its brake lights on is not a good predictor of what will happen next. Only after I see that the distance between me and the car in front of me is decreasing rapidly, do I know to hit my brakes. That means that brake lights alone are not enough information. Differentiating between insignificant speed adjustments and serious braking requires time and can cost lives.
I have a suggestion. Why not create smart brake lights. The car's computer system can recognize the difference in the strength with which the brakes are hit and the lights themselves can reflect that. They can be brighter or a different color or pulsing, depending on the strength of the pressure.
The drivers behind will notice these things before they will notice the decrease in the distance. This idea could save lives.
I recently posted the following coin weighing puzzle invented by Konstantin Knop:
We have N indistinguishable coins. One of them is fake and it is not known whether it is heavier or lighter than all the genuine coins, which weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts one minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?
The author's solution in Russian is available at his blog. Also, two of my readers, David Reynolds and devjoe, solved it correctly.
Here I want to explain the solution for any number of required weighings.
It is easy to see that for n weighings the information theoretical bound is 5^{n}. Indeed, each weighing divides coins into five groups: four pans and the leftover pile. To distinguish between coins, there can't be two coins in the same pile at every weighing.
Suppose we know the faking potential of every coin, that is, each coin is assigned a value: potentially light or potentially heavy. If a potentially light coin is ever determined to be fake, then it must be lighter than a real coin. The same story holds for potentially heavy coins. How many coins with known potential can we process in n weighings?
If all the coins are potentially light then we can find the fake coin out of 5^{n} coins in n weighings. What if there is a mixture of coins? Can we expect the same answer? How much more complicated could it be? Suppose we have five coins: two of them are potentially light and three are potentially heavy. Then on the first scale we compare one potentially light coin with the other such coin. On the other scale we compare one potentially heavy coin against another potentially heavy coin. The fake coin can be determined in one weighing.
The discussion above shows that there is a hope that any mixture of coins with different potential can be resolved. After each weighing, we want the number of coins that are not determined to be real to be reduced by a factor of 5. If one of the weighings on one scale is unbalanced, the potentially light coins on the lighter pan, plus the potentially heavy coins on the heavier pan would contain the fake coin. We do not want this number to be bigger than one-fifth of the total number of coins we are processing. So we divide coins in pairs with the same potential, and from each pair we put the coins on different pans of the same scale. So in one weighing we can divide the group into five equal groups. If there is an odd number of coins with the same potential, then the extra coin doesn't go on the scales.
The only thing that we is left to check is what happens if the number of coins is small. Namely, we need to check what happens when the number of potentially light coins is odd and the number of potentially heavy coins is odd, and the total number of coins is not more than five. In this case the algorithm requires us to put aside the extra coin in each group, but the put-aside pile can't have more than one coin.
After checking small cases, we see that we can't resolve the problem in one weighing when there are 2 coins of different potential, or when the 4 coins are distributed as 1 and 3.
On the other hand, if we have extra coins that are known to be real, then the above cases can be resolved. Hence, any number of coins with known potential greater than four can be resolved in ⌈log_{5}n⌉ weighings.
Now let's go back to the original problem in which we do not know the coins' potential at the start. After a weighing, if both scales balance, then all the coins on the scale are real and the fake coin is in the leftover pile and we do not know its potential. If a scale doesn't balance then the fake coin is in one of its two pans: the lighter pan has coins that are potentially light and the heavier pan has coins that are potentially heavy.
Let's add an additional assumption to the original problem. Suppose we have an unlimited supply of coins that we know to be real. Let u(n) be the maximum number of coins we can process in n weighings if we do not know their potential.
What would be the first weighing? Both scales might be balanced, meaning that the fake coin is in the leftover pile of coins with unknown potential. So we have to leave out not more than u(n−1) coins. On the other hand, exactly one scale might be unbalanced. In this case, all the coins on this scale will get their potential known. The number of these coins can't be more than 5^{n-1}. But this is an odd number, so we can use one extra real coin to make this number even, in order to put the same number of coins in each pan on this scale.
So u(n) = 2 · 5^{n-1} + u(n−1), and u(1) = 3. This gives the answer of (5^{n}+1)/2. Now we need to go back and remember that we got this bound using an additional assumption that we have an unlimited supply of real coins. Looking closer, we do not need our additional supply of real coins to be unlimited; we just need not more than two real coins. The good news is that we will have these extra real coins after the first weighing. The bad news is that for the first weighing we do not have extra real coins at all. So in the first weighing we should put unknown coins against unknown coins, not more than 5^{n-1} on each scale, and as the number on each scale must be even, the best we can do is put 5^{n-1}−1 coins on each scale.
Thus the answer is (5^{n}−3)/2 for n more than 1.
We can generalize this problem to any number of scales used in parallel. Suppose the number of scales is k. Suppose the number of weighings is more than 1, then the following problems can be solved in n weighings:
The methods I described can be used to answer another common question in the same setting: Find the fake coin and say whether it is heavier or lighter. Let us denote by U(n) the number of coins that can be resolved in n weighings when there is an unlimited supply of extra real coins. Then the recurrence for U(n) is the same as the recurrence for u(n): U(n) = 2·5^{n-1} + U(n−1). The only difference is in the initial conditions: U(1) = k. This means that U(n) = ((2k+1)^{n}−1)/2. If we don't have extra real coins then the answer is: U(n) = ((2k+1)^{n}−1)/2 − k.
When we don't need to say whether the fake coin is heavier or lighter, we can add one extra coin to the mix: the coin that doesn't participate in any weighing and is fake if the scales always balance.
I valued my previous analog scale: I brought it from Europe and it showed my weight in kilograms.
I don't remember why, a year ago, I decided to buy a digital scale: after all, my old scale is still functioning. But my new digital scale became an important instrument in my weight loss program.
Now I understand how my old scale and my lazy nature played tricks on my mind. For example, let's say I decide that as soon as I reach one hundred kilograms (220 pounds), I would do something about it. Some time passes, I step on the scale, and it shows 100 kilograms — and maybe more. Is it more or not quite? If I lean to the right, it looks lower. The scale is not precise. So, I step back and adjust the scale at zero a little bit, to make sure it is not more than zero, but it actually could be slightly less. So I have reached my limit, but the scale's imprecision allows me to pretend that there is a chance I am not over 100 kilograms, and thus do not have to do anything. More time passes, the scale shows 103 kilograms. I realize that I have been deceiving myself, but then it is too late for a fast fix that would lower my weight below 100. So I push the limit, and decide to wait until 105 kilograms.
My digital scale erased any ambiguity. The scale, however, has its own doubts. When I stand on it, the display flips between two numbers for a while. One of the numbers means no dinner tonight. But at the end the scale calls it: it spits out the final number with a beep. I had already decided that the scale is the boss. The flipping is irrelevant; the decision is irrevocable. If it means no dinner, so be it.
My new scale prevents inaction. It also allowed me to design my new plan: my Yellow Road. In this plan, my target weight decreases by 0.1 pounds per day. My behavior depends on my real weight with respect to my target weight. A small difference changes my behavior. So precision is essential.
As you can see in the picture the plan continues to work. I've lost 16 pounds since the start of the plan. Actually, I've lost 18 pounds, if I weigh myself without the camera.
I recently posted the following problem from the Moscow Olympiad:
There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.
- Prove that all the people have exactly the same number of acquaintances at this meeting.
- Show that n can be greater than 4.
Here is the proof for the first bullet. Choose a person X. Take a pair of X's acquaintances. These two acquaintances have to share two acquaintances between themselves one of whom is X. In other words, we have described a function from all pairs of X's acquaintances to people who are not X. On the other hand, for every person who is not X, s/he and X share a pair of acquaintances. Hence, there is a bijection between people other than X and all pairs of X's acquaintances. If the number of X's acquaintances is a, and the total number of people is t, then we have shown that (a choose 2) = t−1. As this is true for any X, we see that everyone has the same number of acquaintances. Moreover, this situation can happen only if t−1 is a triangular number.
But wait. There is more work that needs to be done. The smallest triangular number is 1. That means that t might be 2. If there are two people at the meeting, then the condition holds: they have 0 common acquaintances. The next triangular number is 3. So we need to see what would happen if there are four people. In this case, if everyone knows each other, it works. This is why the second bullet asks us to find an example of the situation with more than four people, because four people is too easy.
Let's look at larger triangular numbers. The situation described in the problem might also happen when there are:
The official Olympiad solution suggests the following example for 16 people total. Suppose we put 16 people in a square formation so that everyone knows people in the same row and column. I leave it to the reader to check that every two people share exactly two acquaintances.
Let me prove that there is no solution for a total of seven people. If there were a solution, then each person would have to know four people. My first claim is that the acquaintance graph can't contain a four-clique. Suppose there is a four-clique. Then each person in the clique has to have another acquaintance outside of the clique to make it up to four. In addition, this extra acquaintance can't be shared with anyone in the clique, because the clique contains all the acquaintances that they share. This means we need to have at least four more people.
Next, suppose two people a and b know each other and share an acquaintance c. Any two people in this group of three has to have another shared acquaintance, who is not shared with the third person. That is, there should be another person who is the acquaintance of a and b, a different person who is an acquaintance of a and c, and a third person who is acquainted with b and c. These three extra people are all the acquaintances of a, b, and c. Which means the last person who is not acquainted with a, b, or c, has less than for four acquaintances.
Let's look at a more difficult problem that I offered at the same posting:
There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.
- Prove that all the people have exactly the same number of acquaintances at this meeting.
- Is it possible that n can be greater than 2k?
As in the previous solution, we see that a, the number of acquaintances of a person and t, the total number of people, satisfy the following equation: (a choose k) = (t−1 choose k−1).
For example, if k = 3, the equation becomes (a choose 3) = (t−1 choose 2). This is a question of finding numbers that are both tetrahedral and triangular. They are known and their sequence, A027568, is finite: 0, 1, 10, 120, 1540, 7140. The corresponding number of acquaintances is 3, 5, 10, 22, 36 and the total number of people is 3, 6, 17, 57, 121. The first trivial example involves 3 people who do not know each other. The next example is also simple: it has 6 people and everyone knows everyone else.
What about non-trivial examples? If there are 17 people in the group, then each person has to know 10 people. Does the acquaintance graph exist so that every group of three people share 3 acquaintances?
We see that the problem consists of two different parts. First, we have to solve the equation that equates two binomial coefficients. And second, we need to build the acquaintance graph. Both questions are difficult. We see that for k = 2 we have an infinite number of solutions to the equation with binomial coefficients. For k = 3, that number is finite. What happens with other k? If there are 2k people and they all know each other, then this works. But are there other non-trivial solutions? I am grateful to Henry Cohn for directing me to the works of Singmaster who studied non-trivial repetitions of numbers in Pascal's triangle. In particular, Singmaster showed that the equation (n+1 choose k+1) = (n choose k+2) has infinitely many solutions given by n = F_{2i+2}F_{2i+3}−1 and k = F_{2i}F_{2i+2}−1.
This sequence generates the following non-trivial examples (15 choose 5) = (14 choose 6), (104 choose 39) = (103 choose 40), and so on. That means it might be possible that there is a group of 16 people so that every 6 people share 6 acquaintances. In this situation every person must know everyone else except for one other person. That leads us to the structure of the acquaintance graph: it is a complement to the perfect matching graph. I leave it to my readers to check that the corresponding acquaintance graph doesn't exist. Are there examples of two binomial coefficients that equal each other and that lead to an acquaintance graph that can be built?
Now that I've tackled the solution to this Olympiad problem, I see that I generated more questions than I answered.
Many years ago at Gelfand's seminar in Moscow, USSR, someone pointed out a young girl and told me: "This is Natalia Grinberg. In her year in the math Olympiads, she was the best in the country. She is the next you."
We were never introduced to each other and our paths never crossed until very recently.
Several years ago I became interested in the fate of the girls of the IMO (International Math Olympiad). So, I remembered Natalia and started looking for her. If she was the best in the USSR in her year, she would have been a gold medalist at the IMO. But I couldn't find her in the records! The only Grinberg I found was Darij Grinberg from Germany who went to the IMO three times (2004, 2005, and 2006) and won two silver medals and one gold.
That was clearly not Natalia. I started doubting my memory and forgot about the whole story. Later I met Darij at MIT and someone told me that he was Natalia's son.
I was really excited when I received an email from Natalia commenting on one of my blog posts. We immediately connected, and I asked her about past events.
Natalia participated in the All-Soviet Math Olympiads three times. In 1979 as an 8th grader she won a silver medal, and in 1980 and 1981 she won gold. That indeed was by far the best result in her year. So she was invited to join the IMO team.
That year the IMO was being held in the USA, which made Soviet authorities very nervous. At the very last moment four members of the team did not get permission to travel abroad. Natalia was one of them. The picture below, which Natalia sent to me, was taken during the Soviet training camp before the Olympiad. These four students were not allowed to travel to the IMO: Natalia Grinberg, Taras Malanyuk, Misha Epiktetov, and Lenya Lapshin.
Because of the authorities' paranoia, the Soviet team wasn't full-sized. The team originally contained eight people, but as they rejected four, only six traveled to the USA, including two alternates.
I have written before how at that time the only way for a Jewish student to get to study mathematics at Moscow State University was to get to the IMO. I wrote a story about my friend Sasha Reznikov who trained himself to get to the IMO, but because of some official machinations, still was not accepted at MSU.
Natalia's story surprised me in another way. She didn't get to the IMO, but she was accepted at MSU. It appears that she was accepted at MSU as a member of the IMO team, because that decision was made before her travel documents were rejected.
Natalia became a rare exception to the rule that the only way for a Jewish person to attend MSU was to participate in the IMO. It was a crack in the system. They had to block visas at the last moment, so that people wouldn't have time to make a fuss and do something about it. Natalia slipped through the crack and got to study at the best university in the Soviet Union.
Unfortunately, the world lost another gold IMO girl. Three Soviet team members won gold medals that year. Natalia, being better then all of them, would have also won the gold medal.
I recently published the following coin puzzle:
There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.
My readers, David Reynolds and ext_1973756, wrote to me that I am missing a coin of 4 grams. Indeed, the same puzzle with five coins—1, 2, 3, 4, and 5—is a more natural and a better puzzle.
David Reynolds also suggested to go all the way up to 9 coins:
There are nine silver coins marked 1, 2, 3, 4, 5, 6, 7, 8, and 9. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.
It is impossible to resolve this situation with more than nine coins as two weighings provide nine different answers to differentiate coins. But indeed it is possible to solve this problem for nine coins. It is even possible to suggest a non-adaptive algorithm, that is to describe the weighings before knowing the results.
To find such a strategy we need to satisfy two conditions. First, we have to weigh groups of coins of the same supposed weight, otherwise we do not get any useful information. Second, there shouldn't be any two coins together (in or out of the pan) in both weighings, because it would then be impossible to differentiate between them.
Here is one possible solution of the problem:
David Reynolds also suggested a problem in which we do not know whether the fake coin is heavier or lighter:
There are four silver coins marked 1, 2, 3, and 4. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.
Again, four coins is the best we can do when in addition to find it, we also want to determine if it is heavier or lighter. Indeed, if there were five coins we would have needed to cover ten different answers, which is too many for two weighings.
Here is the solution for four coins:
The two weighings are 1+3=4, and 1+2=3. If the first weighing balances, then the fake coin is 2 and the second weighing shows if it is heavier or lighter than it should be. Similarly, if the second weighing balances, then the fake coin is four and we can see whether it is heavier or lighter than it should be. If the left pan is lighter/heavier for both weighings, then the fake coin is 1 and is lighter/heavier. But if one pan is heavier on the first of two weighings and the other pan is heavier on the second weighing, then the fake coin is 3. In both cases it is easy to determine whether the fake coin is heavier or lighter.
Now David is missing a coin. If we just want to find the fake coin without determining whether it is heavier of lighter, we can do it with five coins:
There are five silver coins marked 1, 2, 3, 4, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.
We can use the same solution as the previous (four coins) problem. If the scale balances both times, then the fake coin is 5. However, in this case we will not know whether the coin is heavier or lighter.
We can't extend this problem to beyond five coins. Suppose we have six coins. We can't use more than three coins in the first weighing. This is because if the scale unbalances, we can't resolve more than three coins in one remaining weighing. Suppose the first weighing balances; then we have at least three leftover coins we know nothing about and one of them is fake. These three coins should be separated for the next weighing. That means one of the coins needs to be on the left pan and one on the right pan. We can add real coins any way we need. But if the second weighing unbalances we do not know if the fake coin is on the left and lighter or on the right and heavier.
Two interesting research results about male homosexuality are intertwined. The first one shows that the probability of homosexuality in a man increases with the number of older brothers. That is, if a boy is the third son in a family, the probability of him being a homosexual is greater than the probability of a first son in a family being homosexual. The second research result shows that the probability of homosexuality increases with the number of children the mother has. So if a woman is fertile and has many children, the probability that each of her sons is a homosexual is greater than the probability that an only child is a homosexual.
Many people conclude from the first result that a woman undergoes hormonal or other changes while being pregnant with boys that influence the probability of future boys being homosexual. Looking at the second result, researchers conclude that homosexuality has a genetic component. Moreover, that component is tied up with the mother's fecundity. The same genes are responsible for both the mother having many children and for her sons being homosexual. This assumption explains why homosexuality is not dying out in the evolution process.
In one of my previous essays I showed that the first results influences the second result. If each next son is homosexual with higher probability, then the more children a mother has the more probable it is that her sons are homosexuals. That means that the second result is a mathematical consequence of the first result. Therefore, the conclusion that the second result implies a genetic component might be wrong. The correlation between homosexuality and fecundity could be the consequence of hormonal changes.
Now let's look at this from the opposite direction. I will show that the first result is the mathematical consequence of the second result: namely, if fertile women are more probable to give birth to homosexuals, then the probability that the second sons are is higher than the probability that the first sons are gay.
For simplicity let's only consider mothers with one or two boys. Suppose the probability of a son of a one-son mother to be a homosexual is p_{1}. Suppose the probability of a son of a two-sons mother to be a homosexual is p_{2}. The data shows that p_{2} is greater than p_{1}. What is the consequence? Suppose the number of mothers with one son is m_{1} and the number of mothers with two sons is m_{2}. Then in the whole population the probability of a boy who is the first son to be gay is (p_{1}m_{1}+p_{2}m_{2})/(m_{1}+m_{2}) and the probability of a boy who is the second son to be gay is p_{2}. It is easy to see that the first probability is smaller than the second one.
Let me create an extreme hypothetical example. Suppose mothers of one son always have straight sons, and mothers of two sons always have gay sons. Now consider a random boy in this hypothetical setting. If he's the second son, he is always gay, while if he is the first son he is not always gay.
We can conclude that if the probability of having homosexual sons depends on fecundity, then the higher numbered children would be gay with higher probability than the first-born. This means that if the genetics argument is true and being a homosexual depends on the mother's fecundity gene, then it would follow mathematically that the probability of homosexuality increases with birth order. The conclusion that homosexuality depends on hormonal changes might not be valid.
So what is first, chicken or egg? Is homosexuality caused by fecundity, while birth order correlation is just the consequence? Or vice versa? Is homosexuality caused by the birth order, while correlation with fecundity is just the consequence?
What do we do when the research results are so interdependent? To untangle them we need to look at the data more carefully. And that is easy to do.
To show that homosexuality depends on the order of birth independently of the mother's fertility, we need to take all the families with two boys (or the same number of boys) and show that in such families the second child is more probable to be homosexual than the first child.
To show the dependence on fertility, without the influence of the birth order, we need to take all first-born sons and show that they are more probable to be homosexuals if their mothers have more children.
It would be really interesting to look at this data.
My new favorite hat puzzle was invented by Konstantin Knop and Alexander Shapovalov. It appeared (in a different wording) in March 2013 at the Tournament of the Towns:
A sultan decides to give 100 of his sages a test. The sages will stand in line, one behind the other, so that the last person in the line sees everyone else. The sultan has 101 hats, each of a different color, and the sages know all the colors. The sultan puts all but one of the hats on the sages. The sages can only see the colors of the hats on people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. They are not allowed to repeat a color that was already announced. Each person who guesses his color wrong will get his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?
I loved it so much that I wrote a paper about it. You can find the solution there.
I particularly like these two problems that I gave my AMSA students for homework:
Athos, Porthos, and Aramis were rewarded with six coins: three gold and three silver. Each got two coins. Athos doesn't know what kind of coins the others got, but he knows his own coins. Ask him one question to which he can answer "Yes," "No," or "I do not know," so that you will be able to figure out his coins.
There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.
We've all been hearing about parallel computing, and now it has turned up in a coin-weighing puzzle invented by Konstantin Knop.
"We have N indistinguishable coins. One of them is fake and it is not known whether it is heavier or lighter, but all genuine coins weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts a minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?"This puzzle reminds me of another coin-weighing problem, where in a similar situation you need to find a fake coin by using one scale with four pans. The answer in this variation would be 5^{5} = 3125. We can divide coins in five groups with the same number of coins and put four groups on the scale. If one of the groups is different (heavier or lighter), then this group contains the fake coin. Otherwise, the leftover group contains the fake coin. This way each weighing reduces the pile with the fake coin by a factor of five.
One scale with four pans gives you more information than two scales with two pans used in parallel. We can conclude that Knop's puzzle should require at least the same number of weighings as the four-pan puzzle for the same number of coins. So we can expect the answer to Knop's puzzle will not be bigger than 3125. But what will it be?
Once when I was working at Telcordia, I received a phone call from my doctor's office. Here is how it went:
— Are you Tanya Khovanova?
— Yes.
— You should come here immediately and redo your blood test ASAP.
— What's going on?
— Your blood count shows that you are dead.
— If I'm dead, then what's the hurry?
Given that I wasn't dead, the conclusion was that there had been a mistake in the test. If there had been a mistake, the probability that something was wrong after the test was the same as it was before the test. There was no hurry.
I started my Yellow Road plan on February 9 when I was 245.2 pounds.
I decided that my first target weight would be my actual weight on February 9: 245.2. Every day this target weight goes down by 0.1 pounds. I weigh myself every morning and compare my actual weight to my target weight. My actions depend on the difference.
My Yellow Zone is plus or minus one pound of my target weight. My Green Zone means I am doing even better: my weight is less than my target weight minus one pound. My Red Zone means that I am not doing so great: my weight is more than my target weight plus a pound.
If I am within the Yellow corridor, I continue building my healthy habits as I have been doing. If I am in the Green Zone, I can afford to digress from healthy habits and indulge myself a bit. If I am in the Red Zone, I have to reduce my evening meals to apples only, which I do not particularly like. The Red Zone has different shades: if I am one pound over my target weight I have to start my apple restrictions after 8:00 pm. If I am two pounds over, then after 6:00 pm, and so on.
Today I am ten pounds lighter. In the process, I have made these discoveries:
Writing down my weight daily is very important. When I look at yesterday's number and today's number, I start thinking about what caused the increase or decrease. Now I have more clarity about which foods are better for me.
I have a better picture of how much I should eat. One day I held a party and I didn't eat much. In fact, I had only one small desert. I didn't feel full and went to bed feeling proud of myself. The next morning I weighed myself and was surprised to find I had gained three pounds. The amount of food I should be eating is much smaller than I expected. I think it may be three times less than what I was used to eating. My plan might not be aggressive enough. Currently when I am in my lightest Red Zone, I have to eat just apples after 8:00 pm. I discovered that I can still gain weight with this regime.
A half-empty stomach is not such a bad feeling. I was so afraid of starting a plan where I might feel hungry. Now I discovered that there are several hours between my first signal that I should eat and real hunger. My first sense that I should eat something might not be actual hunger at all. I do experience a light feeling in my stomach, but now I am starting to learn to enjoy it.
The system works for me. That's the bottom line. For the first time in my life, I found a way to lose weight. All my friends ask me about this system. I explain that this Yellow Road plan is not a panacea. My plan is based on many other things that I did before. If it continues working, I promise to discuss it further: to analyze what exactly works and why.
My next step is to adjust my plan in light of my discoveries. From now on, I'll eat only apples after 8:00 pm—not as an exception, but as a rule.
Here is a problem from the 2012 Moscow Olympiad:
There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.
- Prove that all the people have exactly the same number of common acquaintances at this meeting.
- Show that n can be greater than 4.
My question is: Why 4? I can answer that myself. If in a group of four people any two people share exactly two common acquaintances, then all four people know each other. So in this Olympiad problem, the author wanted students to invent a more intricate example.
Let's take this up a notch and work on a more difficult problem.
There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.
- Prove that all the people have exactly the same number of common acquaintances at this meeting.
- Is it possible that n can be greater than 2k?
I stumbled upon an article, Winners Live Longer, that says:
"When 524 nominees for the Nobel Prize were examined and compared to the actual winners from 1901 to 1950, the winners lived longer by 1.4 years. Why? It seems just having won and knowing you are on top gives you a boost of 1.8% to your life expectancy."
This goes on top of the pile of Bad Conclusions From Statistics. With any kind of awards where people can be nominated several times, winners on average would live longer. The reason is that nominees who die early lose their chance to be nominated again and to win.
I wonder what would happen if we were to compare Fields medal nominees and winners. There is a cut off age of 40 for receiving a Fields medal. If we compare the life span of Fields medal winners and nominees who survived past 40, we might get a better picture of how winning affects life expectancy.
Living a long life increases your chances of getting a Nobel Prize, but doesn't help you get a Fields medal.
I wish I could write four papers in three weeks. The title just means that I submitted four papers to the arXiv in the last three weeks—somehow, after the stress of doing my taxes ended, four of my papers converged to their final state very fast. Here are the papers with their abstracts:
This is the promised solution to the puzzle Integers and Sequences that I posted earlier. The puzzle is attached below.
Today I do not want to discuss the underlying math; I just want to discuss the puzzle structure. I'll assume that you solved all the individual clues and got the following lists of numbers.
Since the title mentions sequences, it is a good idea to plug the numbers into the Online Encyclopedia of Integer Sequences. Here is what you will get:
Your first "aha moment" happens when you notice that the sequences are in alphabetical order and each has exactly one number missing. The alphabetical order is a good sign that you are on the right track; it can also narrow down the possible names of the sequences that you haven't yet identified. Alphabetical order means that you have to figure out the correct order for producing the answer.
Did you notice that some groups above are as long as nine integers and some are as short as four? In puzzles, there is nothing random, so the lengths of the groups should mean something. Your second "aha moment" will come when you realize that, together with the missing number, the number of the integers in each group is the same as the number of letters in the name of the sequence. This means you can get a letter by indexing the index of the missing number into the name of the sequence.
So each group of numbers provides a letter. Now we need to identify the remaining sequences and figure out in which order the groups will produce the word that is the answer.
Let's go back and try to identify the remaining sequences. We already know the number of letters in the name of each sequence, as well as the range within the alphabet. The third sequence might represent a challenge as its numbers are small and there might be many sequences that fit the pattern, but let's try. The results are below with the capitalized letter being the one that is needed for the answer.What is going on? There are two sequences that fit the pattern of the third group and the sequence for the sixth group has many names, two of which fit the profile but produce different letters. Now we get to your third "aha moment": you have already seen some of the sequence names before, because they are in the puzzle. This will allow you to disambiguate the names.
Now that we have all the letters, we need the order. Sequences are mentioned inside the puzzle. You were forced to notice that because you needed the names for disambiguation. Maybe there is something else there. On closer examination, all but one of the sequence names are mentioned. Moreover, with one exception the clues for one sequence mention exactly one other sequence. Once you connect the dots, you'll have your last "aha moment:" the way the sequences are mentioned can provide the order. The first letter G will be from the pentagonal sequence, which was not mentioned. The clues for the pentagonal sequence mention the primeval sequence, which will give the second letter R, and so on.
The answer is GRANTER.
Many old-timers criticized the 2013 MIT Mystery Hunt. They are convinced that a puzzle shouldn't have more than one "aha moment." I like my "aha moments."
*****
*****
*****
*****
*****
*****
*****
Should I eat this piece of cake or not? I will certainly enjoy it very much. What harm will it do? Will this piece increase my weight? Maybe not. The next piece might, but this particular one looks harmless. Even if my weight increases by half a pound, it could be muscle weight. Yes, it probably would be due to muscle weight: I just went out of my house to throw away my garbage and this has to count as exercise.
Do you see the problem? Eating the cake provides an immediate reward, but the punishment is vague and in the far distant future. That is why I got excited when my son Alexey sent me the link to Beeminder, a company that creates an artificial non-vague and not far-in-the-future punishment for eating that piece of cake.
Here is how it works. You give them your target number — in my case my desired weight, but it could be any measurable goal — and the date by which you want to hit it. They draw a yellow path on a weight chart. You must weigh yourself every day. Whenever your weight is above your path, you have to pay real money to the company. Five dollars!
This is a great idea. Suddenly that piece of cake looks threatening. The only problem with using their system is that I have no clue how to lose weight. The company doesn't provide tools to lose weight: it just provides a commitment device. So it is difficult to stick with the weight-loss commitment without having a proven weight-loss plan.
The truth is that my son sent me the link, I laughed, and forgot about it. Besides, if I ever want to pay money for failing in my commitments, I would rather choose the beneficiary myself. Then I realized that I can use the yellow-road idea to try to lose weight while figuring out what works for me. I call my new plan the Adaptive Diet.
Starting from my actual weight on Day One, I drew a line that represents my target weight, assuming a daily decrease of 0.1 pounds. A deviation of one pound from my target weight on my daily weigh-in is what I call my Yellow Zone. When I am in the Yellow, I continue doing what I was doing before: trying to build new, healthier habits.
If I am more than one pound below my target weight, then I have entered what I call the Green Zone. When I am in the Green, I can allow myself to indulge my cravings. However, when I am one pound above my target weight, I call that the dreaded Red Zone. This Zone has different shades of red. If I am between 1 and 2 pounds above my target weight, I have to eat only apples after 8:00pm. If I am 2 to 3 pounds above my target weight, only-apples time starts at 6:00pm. And so on. Every extra pound above my target weight moves the cut-off time by two hours. That means that if I am 7 pounds above my target weight, I would have to eat apples all day long.
The system has to work: I do not like apples.
In skyscraper puzzles you have to put an integer from 1 to n in each cell of a square grid. Integers represent heights of buildings. Every row and column needs to be filled with buildings of different heights and the numbers outside the grid indicate how many buildings you can see from this direction. For example, in the sequence 213645 you can see 3 buildings from the left (2,3,6) and 2 from the right (5,6).
In mathematical terminology we are asked to build a Latin square such that each row is a permutation of length n with a given number of left-to-right and right-to-left-maxima. The following 7 by 7 puzzle is from the Eighth World Puzzle Championship.
Latin squares are notoriously complicated and difficult to understand, so instead of asking about the entire puzzle we discuss the mathematics of a single row. What can you say about a row if you ignore all other info? First of all, let us tell you that the numbers outside have to be between 1 and n. The sum of the left and the right numbers needs to be between 3 and n+1. We leave the proof as an exercise.
Let's continue with the simplest case. Suppose the two numbers are n and 1. In this case, the row is completely defined. There is only one possibility: the buildings should be arranged in the increasing order from the side where we see all of them.
Now we come to the question we are interested in. Given the two outside numbers, how many permutations of the buildings are possible? Suppose the grid size is n and the outside numbers are a and b. Let's denote the total number of permutations by f_{n}(a, b). We will assume that a is on the left and b is on the right.
In a previous example, we showed that f_{n}(n, 1) = 1. And of course we have f_{n}(a, b) = f_{n}(b, a).
Let's discuss a couple of other examples.
First we want to discuss the case when the sum of the border numbers is the smallest — 3. In this case, f_{n}(1, 2) is (n−2)!. Indeed, we need to put the tallest building on the left and the second tallest on the right. After that we can permute the leftover buildings anyway we want.
Secondly we want to discuss the case when the sum of the border numbers is the largest — n+1. In this case f_{n}(a,n+1-a) is (n-1) choose (a-1). Indeed, the position of the tallest building is uniquely defined — it has to take the a-th spot from the left. After that we can pick a set of a-1 buildings that go to the left from the tallest building and the position is uniquely defined by this set.
Before going further let us see what happens if only one of the maxima is given. Let us denote by g_{n}(a) the number of permutations of n buildings so that you can see a buildings from the left. If we put the shortest building on the left then the leftover buildings need to be arrange so that you can see a-1 of them. If the shortest building is not on the left, then it can be in any of the n-1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function g_{n}(a) satisfies the recurrence:
Actually g_{n}(a) is a well-known function. The numbers g_{n}(a) are called unsigned Stirling numbers of the first kind (see http://oeis.org/A132393); not only do they count permutations with a given number of left-to-right (or right-to-left) maxima, but they also count permutations with a given number of cycles, and they appear as the coefficients in the product (x + 1)(x + 2)(x + 3)...(x + n), among other places. (Another pair of exercises.)
We are now equipped to calculate f_{n}(1, b). The tallest building must be on the left, and the rest could be arranged so that, in addition to the tallest building, b-1 more buildings are seen from the right. That is f_{n}(1, b) = g_{n-1}(b-1).
Here is the table of non-zero values of f_{n}(1, b).
b=2 | b=3 | b=4 | b=5 | b=6 | b=7 | |
---|---|---|---|---|---|---|
n=2 | 1 | |||||
n=3 | 1 | 1 | ||||
n=4 | 2 | 3 | 1 | |||
n=5 | 6 | 11 | 6 | 1 | ||
n=6 | 24 | 50 | 35 | 10 | 1 | |
n=7 | 120 | 274 | 225 | 85 | 15 | 1 |
Now we have everything we need to consider the general case. In any permutation of length n, the left-to-right maxima consist of n and all left-to-right maxima that lie to its left; similarly, the right-to-left maxima consist of n and all the right-to-left maxima to its right. We can take any permutation counted by f_{n}(a, b) and split it into two parts: if the value n is in position k + 1 for some 0 ≤ k ≤ n-1, the first k values form a permutation with a - 1 left-to-right maxima and the last n - k - 1 values form a permutation with b - 1 right-to-left maxima, and there are no other restrictions. Thus:
Let's have a table for f_{7}(a,b), of which we already calculated the first row:
b=1 | b=2 | b=3 | b=4 | b=5 | b=6 | b=7 | |
---|---|---|---|---|---|---|---|
a=1 | 0 | 120 | 274 | 225 | 85 | 15 | 1 |
a=2 | 120 | 548 | 675 | 340 | 75 | 6 | 0 |
a=3 | 274 | 675 | 510 | 150 | 15 | 0 | 0 |
a=4 | 225 | 340 | 150 | 20 | 0 | 0 | 0 |
a=5 | 85 | 75 | 15 | 0 | 0 | 0 | 0 |
a=6 | 15 | 6 | 0 | 0 | 0 | 0 | 0 |
a=7 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
We see that the first two rows of the puzzle above correspond to the worst case. If we ignore all other constrains there are 675 ways to fill in each of the first two rows. By the way, the sequence of the number of ways to fill in the most difficult row for n from 1 to 10 is: 1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704. The maximizing pairs (a,b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3).
The actual skyscraper puzzles are designed so that they have a unique solution. It is the interplay between rows and columns that allows to reduce the number of overall solutions to one.
I just compared two searches on Google Trends:
The most personal puzzle that I wrote for the 2013 MIT Mystery Hunt was Integers and Sequences based on my Number Gossip database. I named it after the first lecture that I prepared after I decided to return to mathematics. It is still my most popular lecture.
Many of the clues in this puzzle are standard math problems that are very good for math competition training. Other clues are related to sequences and integer properties.
You might wonder why I often ask for the second largest integer with some property. Isn't the largest one more interesting than the second largest? I do think that the largest number is more interesting, but exactly for this reason the largest number is available on my Number Gossip website and therefore is googleable. For example, my Number Gossip properties for 3000 contain the fact that 3000 is the largest palindrome in Roman numerals. This is why in the puzzle I used a slightly different clue, i.e. "the second largest three-letter palindrome in Roman numerals."
It took me many hours to find non-googleable variations of interesting properties for this puzzle. Unfortunately, its non-googleability evaporated as soon as my solution was posted, right after the hunt. In any case some clues in this puzzle are useful for math competition training, and I plan to use them myself in my classes. The puzzle is attached below. I will post the solution in a couple of weeks.
*****
*****
*****
*****
*****
*****
*****
The ultimate goal of each MIT Mystery Hunt is to find a hidden coin. So it was highly appropriate that our 2013 team created a coin-weighing puzzle (written by Ben Buchwald, Darby Kimball, and Glenn Willen) as a final obstacle to finding the winning coin:
There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.
Actually, it is possible to find the real coin in six weighings. Can you do that?
My weight used to be my most guarded secret. In general, I am a very open person: I'll tell anyone anything about me, unless it involves other people. However, there were two exceptions, both of them numbers, interestingly enough: my age and my weight. The closest I came to revealing my weight was with my sister, because we often discuss our similar health issues. Unfortunately, she knows my age, so the only missing number is my weight. I am so tired of my struggle to lose weight, that I've stopped caring about keeping the number secret. I am ready to tell it to the whole world.
Let me start from the beginning. I grew up in a country and at a time when men liked plump women. I was never thin, and didn't have to worry about my weight like my thin girlfriends did. I'll never forget my high school boyfriend telling me, "Ninety percent of men like fat women, and the other ten percent like very fat women." When in college I weighed 70 kilograms (154 pounds) and I felt fine. I had my first child when I was 23. I gained 20 kilos while I was breastfeeding, reaching 90 kilos (200 pounds). My husband Andrey kept telling me that he liked Rubenesque women. I wasn't even slightly concerned about my weight. When we divorced in 1988, I felt that my world was crushed and I didn't want to go on living. As a result, I lost about 20 pounds.
By 1990 I recovered from my depression, married my next husband, and moved to the US to live with him. The US made me aware of my weight immediately. It didn't help that Andrey remarried a woman who was the opposite of Rubenesque. From this point on, I wanted to lose weight. After my second child was born, I gained 20 kilograms while breastfeeding, just as I had done with the first child. The result was that I weighed about 220 pounds, much more than I wanted.
I started to look around at what capitalist society had to offer. The pharmacy had many products. I tried Slim Fast, which started to kill my appetite immediately. However, I began to get depressed. The depression felt foreign. As a new mother, I had been very happy before using Slim Fast, and there had been no changes in my life other than consuming Slim Fast. I stopped using it and the depression disappeared. To make sure, I did an experiment. I started using Slim Fast again and the depression reappeared within three days. I stopped it and my depression disappeared. I was so desperate to lose weight that I repeated the experiment. But the result was the same. I stopped using it, and never used any slimming supplement since then. But within that whole process, I lost some weight.
I stayed slightly over 200 pounds for several years. The third time (after the divorce and the Slim Fast) that I lost a lot of weight was when I had my heart broken about 15 years ago. Since then I've been slowly gaining weight.
As you can see from my story, I was never able to lose weight when I wanted to. I lost it three times, but I can't and don't want to reproduce those circumstances. I actually do not know how to lose weight. For the past ten years I've been making changes in my eating habits that I hope, cumulatively, would help me lose weight. I do not buy soda or pizza. I significantly cut my consumption of sweets and starches. I eat more fruits and vegetables. I eat half of what I used to eat in a restaurant. I am still gaining weight.
he only thing I haven't tried is to be hungry. I am afraid of being hungry. Also I am scared that if I decide on a plan which might result in my being hungry, I will not be able to stick to it. I don't want to discover that I don't have enough will power. I am scared to be a failure. I hope that by writing and publishing this I'll gain the courage to replace my half-measures with a more drastic plan.
Oh! I forgot to tell you: I weigh 245 pounds.
* * *
Grigori Perelman's theorem: There is no offer you can't refuse.
* * *
A conversation between two Russians:
— Run to the store and fetch a couple bottles of vodka.
— How much is a couple?
— Seven.
* * *
— Is it true that the Windows operating system was copied from a UFO computer that crashed in Roswell?
— All we know for sure is that the UFO that didn't crash had a different operating system.
* * *
I saw our system administrator's shopping list. The first line was tomatoes.zip for ketchup.
I posted the puzzle In the Details two weeks ago. This is the most talked-about puzzle of the 2013 MIT Mystery Hunt. The author Derek Kisman invented this new type of puzzle and it is now called a Fractal Word Search. I anticipate that people will start inventing more puzzles of this type.
Let's discuss the solution. The words in the given list are very non-random: they are related to fractals. How do fractals work in this puzzle? The grid shows many repeating two-by-two blocks. There are exactly 26 different blocks. This suggests that we can replace them by letters and get a grid that is smaller, for it contains one-fourth of the number of letters. How do we choose which letters represent which blocks? We expect to see LEVEL ONE in the first row as well as many other words from the list. This consideration should guide us into the matching between letters and the two-by-two blocks.
The level one grid contains 18 more words from the list. But where are the remaining words? So we have level one, and the initial grid is level two. The substitution rule allows us to replace letters by blocks and move from level one to level two. When we do this again, replacing letters in level two by blocks, we get the level three grid. From there we can continue on to further levels. There are three words from the list on level three and one word on level four. But this is quickly getting out of hand as the size of the grid grows.
Let's step back and think about the next step in the puzzle. Usually in word search puzzles, after you cross out the letters in all the words you find, the remaining letters spell out a message. What would be the analogous procedure in the new setting of the fractal word search? In which of our grids should we cross out letters? I vote for grid number one. First, it is number one, and, second, we can assume that the author is not cruel and put the message into the simplest grid. We can cross-out the letters from words that we find in level one grid. But we also find words in other levels. Which letters in the level one grid should we cross out for the words that we find in other levels? There is a natural way to do this: each letter in a grid came from a letter in the previous level. So we can trace any letter on any level to its parent letter in the level one grid.
We didn't find all the words on the list, but the missing words are buried deep in the fractal and each can have at most three parent letters. I leave to the reader to explain why this is so. Because there are so few extra letters, it is possible to figure out the secret message. This is what my son Sergei and his team Death from Above did. They uncovered the message before finding all the words. The message says: "SUM EACH WORD'S LEVEL. X MARKS SPOT." Oh no! We do need to know each word's level. Or do we? At this point, the extra letters provide locations of the missing words. In addition, if a word on a deep level has three parents, then it has to be a diagonal word passing through a corner of one of the child's squares. So our knowledge of extra letters can help us locate the missing words faster.
Also, the message says that the answer to this puzzle will be on some level in the part of the grid that is a child of X. Luckily, but not surprisingly, there is only one letter X on level one. The child of X might be huge. But we could start looking in the center. Plus, we know from the number of blanks at the end of the puzzle, that the answer is a word of length 8. So Sergei and his team started looking for missing words and the answer in parallel. Then Sergei realized that the answer might be in the shape of X, so they started looking at different levels and found the answer before finding the last word on the list. The answer was hiding in the X shape in the center of the child of X on level 167: HUMPHREY.
H..Y .UE. .RM. H..P
Cambridge Waldo puzzle from the 2013 MIT Mystery Hunt was supposed to be easy. Its goal was to get people out of the building for some fresh air. I made this puzzle jointly with Ben Buchwald, Adam (Pesto) Hesterberg, Yuri Lin, Eric Mannes and Casey McNamara. The puzzle consists of 50 pictures of different locations in Cambridge; one of the above individuals was hiding in each picture. Let me use this opportunity to thank my friends for starring in my puzzle and being inventive while doing it.
The puzzle starts with a group picture of my stars. The caption to the picture gives their names. The fact that they are standing in alphabetical order is a clue.
Out of the 50 pictures, each person appears in exactly ten pictures. If you mark the locations of one person on a map, they look like a letter. For example, below are Ben's locations that form a letter "S". When you put the letters in the alphabetical order by people names you get the answer to the puzzle: SCAMP.
As you can see, you do not need all ten locations to recognize the letter. You might be able to recognize the letter with five locations, or at least significantly reduce possibilities for the letter. Besides, you do not need all the letters to recognize the answer. We thought that this was an easy puzzle.
And, to make it even easier, the order in which we posted the pictures was not completely random. The pictures of one person were in the order one might walk from one location to another. This played two important roles. If you recognize the person but do not recognize the location on the picture, you can make an approximate estimation of the location because it must be on the path between the previous and next locations. If you recognize the location but not the person, you can guess the person by checking whose path it fits better.
It was difficult to hide people, especially when there were no other people around. So we sometimes used props. We only used one prop per person. Here you can see Pesto with his sarongs in plain view. In the other picture (below) he is hiding under a white sarong. Yuri had a bicycle helmet. In one of the pictures, she hid so well that you couldn't see her — but you could see her helmet. Ben had a bear hat. In one of the pictures you can only see a shadow of a person, but this person was clearly wearing a hat with bear ears. Eric didn't have a prop, but my car was eager to make a cameo appearance at the Mystery Hunt, so I hid him in my car in one of the pictures.
As you might guess I made the pictures of different people at different times. So Ben Buchwald was the one who realized that solvers might differentiate people by looking at the data of the picture files. He carefully removed the original time stamps.
Despite our best intentions, our test-solvers decided not to leave their comfy chairs, but rather to use Google-StreetView. We strategically made some of the pictures not Google-StreetViewable, but our test-solvers still didn't leave the comfort of their chairs. They just became more inventive. I do not know all the things they did to solve the puzzle, but I heard about the following methods:
I have yet to understand why this puzzle was difficult for the Mystery Hunt teams.
Here is the solution to the Open Secrets puzzle I published recently. Through my discussion of this solution, you'll also get some insight into how MIT Mystery Hunt puzzles are constructed in general.
I've included the puzzle (below) so that you can follow the solution. The puzzle looks like a bunch of different cipher texts. Even before we started constructing this puzzle, I could easily recognize the second, the seventh, and the last ciphers. The second is the cipher used by Edgar Allan Poe in his story, The Gold-Bug. The seventh cipher is a famous pigpen (Masonic) cipher, and the last is the dancing men cipher from a Sherlock Holmes story. Luckily you do not need to know all the ciphers to solve the puzzle. You can proceed with the ciphers you do know. With some googling and substitution you will translate these three pieces of text into: COLFERR, OAOSIS OF LIFEWATER, and RBOYAL ARCH.
These look like misspelled phrases, each of which has an extra letter. However, there are no typos in good puzzles. Or, more precisely, "typos" are important and often lead to the answer. So now I will retype the deciphered texts with the extra letter in bold: COLFERR, OAOSIS OF LIFEWATER and RBOYAL ARCH. In the first word it is not clear which R should be bold, but we will come back to that later.
At this point you should google the results. You may notice that the "royal arch" leads you to the Masons, who invented the pigpen cipher. From this, you can infer the structure of the ciphers and the connections among them. Indeed, a translation of one cipher refers to another. So you should proceed in trying to figure out what the texts you have already deciphered refer to. Eoin Colfer is the author of the Artemis Fowl series that contains a Gnomish cipher, and Oasis of Lifewater will lead you to Commander Keen video games with their own cipher. When you finish translating all of the ciphers, you get the following list:
The bold letters do not give you any meaningful words. So there is more to this puzzle and you need to keep looking. You will notice that the translations are in alphabetical order. This is a sign of a good puzzle where nothing is random. The alphabetical order means that you need to figure out the meaningful order.
To start, the phrases reference each other, so there is a cyclic order of reference. More importantly, the authors of the puzzle added an extra letter to each phrase. They could have put this letter anywhere in the phrase. As there is nothing random, and the placements are not the same, the index of the bold letter should provide information. If you look closely, you'll see that the bold letters are almost all in different places. If we choose the second R in COLFERR as an extra R, then the bold letter in each text is in a different place. Try to order the phrases so that the bold letters are on the diagonal. You'll see that this order coincides with the reference order, which gives you an extra confirmation that you are on the right track. So, let's order:
Now the extra letters read BOKLORYFH. This is not yet meaningful, but what is this puzzle about? It is about famous substitution ciphers. The first and most famous substitution cipher is the Caesar cipher. So it is a good idea to use the Caesar cipher on the phrase BOKLORYFH. There is another hint in the puzzle that suggests using the Caesar cipher. Namely, there are many ways to clue the dancing men code. It could be Conan Doyle, Sherlock Holmes, and so on. For some reason the authors chose to use the word ELEMENTARY as a hint. Although this is a valid hint, you can't help but wonder why the authors of the puzzle are not consistent with the hints. Again, there is nothing random, and the fact that the clues are under-constrained means there might be a message here. Indeed, the first letters read ROMAN CODE, hinting again at the Caesar shift. So you have to do the shift to arrive at the answer to this puzzle, which is ERNO RUBIK.
The most difficult puzzle I wrote for the MIT Mystery Hunt 2013 was Turnary Reasoning. I can't take credit for the difficulty: I designed the checkers positions; they were expectedly the easiest. Timothy Chow created the chess positions, and Alan Deckelbaum created the MTG positions. As the name of the puzzle suggests, you need to find whose turn it is in each position or, as the flavor text suggests, decide that the position is impossible.
I tried to solve the chess positions myself and was charmed by their beauty. The most difficult one was the first chess puzzle presented below. Find whose turn it is or prove that the position is impossible.
The puzzle titled "50/50" was the most difficult puzzle in MIT Mystery Hunt 2013. It is a puzzle in which information is hidden in the probability distribution of coin flips. I consider it the most difficult puzzle of the hunt because it took the longest time to test-solve and we were not able to solve all four layers of the original puzzle. As a result, one of the layers was removed. I think this puzzle is very important and should be included in statistics books and taught in statistics classes. If I were ever to teach statistics, I would teach this puzzle. By the way, this elaborate monstrosity (meant as a compliment) was designed by Derek Kisman.
I am not sure that the puzzle is working on the MIT server. The puzzle is just a coin flip generator and gives you a bunch of Hs (heads) and Ts (tails). Here is the solution.
When you flip a coin, the first thing to check is the probability of heads. In this puzzle it is fifty percent as expected. Then you might check probabilities of different sequences of length 2 and so on. If you are not lazy, you will reach length 7 and discover something interesting: some strings of length seven are not as probable as expected. The two least probable strings are TTHHTTH and HTHHTTT, with almost the same probability. The two most probable strings are TTHHTTT and HTHHTTH, with the matching probability that is higher than expected. All oddly behaving strings of length 7 can be grouped in chunks of four with the same five flips in the middle. In my example above, the five middle flips are THHTT. Five flips is enough to encode a letter. The probabilities provide the ordering, so you can read a message. In the version I tested it was "TAXINUMBLOCKS." In the current version it is "HARDYNUMBLOCKS." Keep in mind that the message encoded this way has to have all different letters. So some awkwardness is expected. The message hints at number 1729, a famous taxicab number, which is a clue on what to do next in the second step.
What do you do with number 1729? You divide the data in blocks of 1729 and see how the k-th flip in one block correlates with the k-th flip in the next block. As expected, for most of the indices there is no correlation. But some of the indices do have correlation. These indices are close together: not more than 26 flips apart. Which means the differences will spell letters. Also, there is a natural way to find a starting point: the group of indices spans only a third of the block. In the original version the message was: "PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJKHEREHAVEAPIECEOFPIE."
Now I want to discuss the original version, because its solution is not available online. Here is Derek's explanation of what happens in the third step:
So, this punny message is another hint. In fact the sequence of coin flips conceals pieces of the binary representation of Pi*e. These pieces are of length 14 (long enough to stand out if you know where to look, but not long enough to show up as significant similarities if you compare different sessions of flips), always followed by a mismatch. They occur every 1729 flips, immediately after the final position of the 1729-block message. The HERE in the message is intended to suggest looking there, but you can probably also find them (with more effort) if you search for matches with Pi*e's digits.
The 14-flip sequences start near the beginning of the binary representation of Pi*e and continue to occur in order. (ie, every 1729 flips, 14 of them will be taken straight from Pi*e.) However, between sequences, either 1, 3, or 5 digits will be skipped. These lengths are a sequence of Morse code (1=dot, 3=dash, 5=letter break) that repeats endlessly, with two letter breaks in a row to indicate the start:
- .... ..- ..- ..- - ..- -..- ..- ..- ..- .... ..- .... - ..- ..- .... ..- ....
Translated, this gives the message "THUUUTUXUUUHUHTUUHUH".
(Aside: I didn't use Pi or e individually, because one of the first things I expect some teams will try is to compare the sequence of flips with those constants!)
As I said before, we didn't solve the third step. So Derek simplified it. He replaced "PIECEOFPIE" by "BINARYPI", and made it the digits of Pi, rather than of Pi*e. We still couldn't solve it. So he changed the message from the second step to hint directly at the fourth step: "PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJUSTKIDDINGTHUUUTUXUUUHUHTUUHUH." But the binary Pi was still trapped in the coin flipping factory.
Here is Derek’s explanation of the fourth step:
Almost there! This message looks like some sort of flip sequence, because it has several Ts and Hs in there, but what of the Us and Xs? Well, U just stands for "unknown", ie, we don't care what goes there. And there's only one X, so it seems significant!
The final step is to look for every occurrence of this pattern in the sequence. The flips that go where the X is are the final channel of information. You'll find that they repeat in an unvarying pattern (no noise!) with period 323=17*19. There's only one way to arrange this pattern into a rectangular image with a blank border, and it gives the following image:
................. ...X..XXX.XXX.... ...X..X...X.X.... ...X..XXX.XXX.... ...X..X...XX..... ...X..X...X.X.... ...X.....X....... ...X.....X....... ...X....XXX...... ...X.....X....... ...X............. ...X.....XXX...X. ...X....XXXXX.XX. ..X....XX.XXXXX.. .X......XXXXXX... .X...X.XXXXXXXX.. ..XXX...XXXXX.XX. .........XXX...X. .................
The final answer is the French word for fish, POISSON, a word heavily related to statistics!
The answer POISSON didn't fit in the structure of the Hunt. So Derek was assigned a different answer: MOUNTAIN. He changed the picture and it is now available in the official solution to the puzzle. He adjusted his code for coin flips so that the picture of a mountain is hidden there. But the digits of Pi are still trapped in the flips. They are not needed for the solution, but they are still there.
Derek kindly sent to me his C++ program for the latest version of the puzzle. So if the MIT website can't generate the flips, you can do it yourself. And play with them and study this amazing example of the use of statistics in a one-of-a-kind puzzle.
When the MIT Mystery Hunt was about to end, I asked my son Sergei, who was competing with the team "Death from Above," what his favorite puzzle was. I asked the same question to a random guy from team "Palindrome" whom I ran into in the corridor. Surprisingly, out of 150 puzzles they chose the same one as their favorite. They even used similar words to describe it. Calling it a very difficult and awesome puzzle, they both wondered how it was possible to construct such a puzzle.
The puzzle they were referring to is "In the Details" by Derek Kisman, which you can see below.
TWELEVELTWONSHELMUMUOERAIYRANL QAPIUNPIQAYDPEPIRPRPKVOYESOYOR ELRATFDTELDTTFDTBWNLMUTFONYDWJ PIOYJMHAPIHAJMHAAOORRPJMYDANFC MUOZCGTFBWIRYDHIRAIRTFNCUENCUE RPVQUHJMAOHKANJUOYHKJMZKBNZKBN IRONSHOZGOTFUEELTFOEELUEYDOETF HKYDPEVQDNJMBNPIJMKVPIBNANKVJM BWIYNLTFSHHIELTWGOYDONDTYDHIOE AOESORJMPEJUPIQADNANYDHAANJUKV SHDTYDRPBWUEBWIYTWTWTFYDMUELMU PEHAANAJAOBNAOESQAQAJMANRPPIRP ONTWELBWLMSHELTFUEBWBWLMOZEVHI YDQAPIAOGIPEPIJMBNAOAOGIVQUNJU DTCGUEYDRPEVNCIREVIRTWUEUETWON HAUHBNANAJUNZKHKUNHKQABNBNQAYD IRUERAMUTFELTWONTFOEOEEYDTNLYD HKBNOYRPJMPIQAYDJMKVKVHWHAORAN ELGORPNCTFDTYDSHYDELPKTFOZRACG PIDNAJZKJMHAANPEANPIDFJMVQOYUH DTMUWJOETFYDELMUMUGORAONIRDTCG HARPFCKVJMANPIRPRPDNOYYDHKHAUH
BOUNDARY | HENON | LEVY DRAGON | SCALING |
BROWNIAN | HILBERT | LYAPUNOV | SPACE |
CAUCHY | HURRICANE | MANDELBROT | STRANGE |
CURLICUE | ITERATE | NEURON | TAKAGI |
DE RHAM | JULIA | NURNIE | TECTONICS |
DIMENSION | LEIBNIZ | POWER LAW | T-SQUARE |
ESCAPE | LEVEL ONE | RAUZY | WIENER |
HAUSDORFF | LEVEL TWO | RIVER | YO DAWG |
_ _ _ _ _ _ _ _
The puzzle looks like a word search, but I can tell you up-front: you can't find all the words in the grid. You can only find six words there. So there is something else to this puzzle. I will discuss the solution later. Meanwhile I will ask you very pointed questions:
The easiest of the puzzles I made for the MIT Mystery Hunt 2013 was "Something in Common." I collaborated on this puzzle with Daniel Gulotta. Ironically, it was the most time-consuming of my puzzles to design — well over a hundred hours. I can't tell you why it took me so long without revealing hints about the solution, so I will wait until someone solves it.
I received a lot of critique from my editors for suggesting puzzles that were too easy. When, during the test-solve, I realized that this puzzle was one of the easiest in the hunt, I requested permission to make it harder. It would not actually have been difficult to make it harder: I could have just replaced some specific words with more general ones. Unfortunately, we didn't have time for a new test-solve, so the puzzle stayed as it was. That turned out to be lucky.
This puzzle was in the last round. By the time the last round opened, we knew that the hunt was much more difficult than we had anticipated. I was afraid that people were getting angry with difficult puzzles and so I was very happy that I hadn't changed this puzzle. By the time the teams started submitting answers to it, people were exhausted. Manic Sages increased the speed with which options to buy answers to puzzles were released. I was ecstatic that this puzzle was one of the few puzzles in the last round that was solved, not bought with options. Here is the puzzle:
While everyone was discussing which color to paint the room, the counselor was dreaming about a real chocolate sundae. A walk-in walked into the reception in honor of a regular phenomenon visible every four hours or so. The client just wanted to find his dog in order to provide a permanent shortcut to another part of space; instead, he found something else.
The Federation didn't want to buy a lemon, so their lawyer used a spider to type the password. They discovered that the creatures glow in the dark and the perceptive negotiator won the bid. While they were waiting for the results of the shuttle trip, they turned the lights off to hunt them. The bird-like sounds were coming from under the floor. They used alcohol to save the woman's life, which was a big mistake. She refused to be his conscience, instead she used her new untapped power of light to save the world; she already had a job as a counselor.
Their daughter disappeared two months ago, whereas they needed to keep the wounded survivor steady. The African activist was kidnapped by rebels when she was a teenager. While some people were building a boat on the beach, she escaped from her kidnappers. He said that the reward had been withdrawn to eliminate the financial incentive to lie. They needed to perform a blood transfusion, but they didn't have the proper instruments. By his false statement, he removed over-claimers: people lying to get attention. He needed to write vows. They read surprise at the unexpected labor in the woods in the boy's face. It was clear that the boy had never looked into the backpack.
She described horrors she had seen: rape, torture, massacres carried out by child soldiers, the doctor losing his own blood to help the wounded survivor. There was no deception leakage, but she seemed anxious, so the doctor couldn't go and deliver the baby. They needed to find the other girl before noon, and the crushed leg made blood transfusion impractical. His vows were self-referential. He talked about how he couldn't write the vows. While the doctor played 20 questions one man died and another was born. The girl wasn't answering, but the doctor read her micro-expressions. The writer touched her ear and exposed her lies. At the end the doctor suspected murder, and the book was withdrawn.
She took pictures in an abandoned house and jumped off the roof. Two girls came back to investigate. He was surprised by a basket of cookies and a statue that was in the wrong place. A new drug hit the streets making people see things, like old pictures of a woman who looked exactly like her friend. He started seeing his dead father: when people die in the past, they produce energy in the present.
They were the two most powerful people on the planet. For wedding preparations she got a list of 17 DVDs. His partner started hallucinating about her ex. People do not understand time. Naomi's ability caused all this mess: the box left them behind. The only place where she didn't use gloves was her garden. The dinner guests tried her chicken, and, as a consequence, they were stuck looking at each other forever. The drugged cookies were a gift to help resolve their issues. Because of that, she gave him the shorthand transcripts to complete the cycle.
Did she fall asleep while they were discussing the dead boy's name? The price tag was exorbitant for a witness to identify the defendant. The woman would be everything he wanted and needed. She was a security guard chewing gum. The witness changed her testimony: they went to the woods and were water-rafting, rock-climbing, and arrow-shooting. As she was not the first girl he brought to the woods, the jury gave a verdict of "Not Guilty."
The detective was in court, though it wasn't his case. She needed to stop talking and start running. Shit always rolls downhill. Poisoned water made her see things she was not supposed to remember like a shitty orange couch outside. In spite of the background check the client was a psychopath who was moved from uptown to the fucking low-rises. Shoulder to the wheel. Dead witness, mother-fucker.
A little girl was humming about the dark side. The Wicca group was boring, and the new invention was making whooshing sounds. While a laryngitis epidemic took over the town, the noise-eater got turned on by accident.
The princess's scream would kill the monsters, while the monster machine killed its own remote control. She and her future boyfriend discovered each other's secrets. The dark side is waiting.
The experiment in the gay club was very important to him. He was a semi-cute boy-next-door type and his shuttle trip was supposed to be easy. There is more to a guy than cock size, and he was being pulled. He was injected with something and started to understand everyone. They were a bald priestess and a warrior with a very nice butt. They offered you a discount if you bought the butt and the bulge together.
They were approaching a commerce planet in Pennsylvania. They escaped and were standing on the roof of a hospital. She was sending a transmission, while the older man was running his tongue along the young man's spine. The girl tried to protect him, believing his story, but was arrested for contamination. Fuck. He had a baby, two babies. He distracted the guards with a puzzle ring. And while they were painting his black car with a pink derogatory word, they escaped.
He was drinking before operating on his fiancée. What kind of a father kills people? Tonight was the night he would finally sleep, and drinking was the only way for him to stop his hands from shaking. The limo driver kidnapped him while she watched herself die in the mirror. While being sleep-deprived he conducted a test. Nothing was wrong, except he brought the wrong documents to court. The criminal walked, but, unexpectedly, he couldn't feel his leg and couldn't walk anymore. There was a lot of blood and the body was not filtering iodine. He took a picture of the actor falling into a coma with his blood-spatter camera.
His girlfriend wanted to buy a firm mattress to have sex. He preferred to sleep on a water-bed and told the secret of his bloody hobby to his baby. It was not an infection, it was an allergy, so he changed his plan of where to grab the victim. The case was solved because of the bubbles in the glass. He was killing for his son now. The patient was indeed allergic and crashed his car.
The woman died two weeks ago, but her car accident was yesterday. There was so much blood and, for some reason, ice. Jane Doe wasn't the girl's sister. Melting speed and surface tension could help the calculation. They came to pay their respects but the celebration was postponed. They brought personal effects to drop off. If the couple's daughter was like their mother, then they themselves were like their grandparents. The idea to ask the grandmother resulted in a kiss.
Their planet had been on the verge of a golden age, then everything fell apart. She brought some clothes, a toothbrush, shampoo and some other things to the detention center. "Don't let the history repeat itself," the worshiper of the second in command said. She didn't know what the red string was for. The teen's sister told him stories about another galaxy, and the war and the algorithm that might find the dead man's favorite coffee place and, consequently, solve the case. The kidney operation was in a hotel. They didn't expect to see the body, but there it was. She touched the body to reveal emptiness inside. At the end they gathered in his house for dinner as usual. He had to save Courtney's future body before everything blew up and put the red sticker on his license.
After retirement, he came back to an unsolved murder case; he remembered a kiss in flashbacks. He drove to the lake where the accidental drowning happened. He lured everyone involved to the lake, and, after having sex, he told her that he wanted a real marriage. They wanted their child to be born on the new planet. The doctor was one of the suspects. The couple was already in the cabin, and he doubted that he was the one who she really wanted.
The young man was murdered, and everyone thought that the detective was the real target. The man went to look for sneakers during the boxing match. The nosy lady-writer dropped names to persuade the sheriff to look into the cabin. The admiral challenged the chief to join him in the ring. They didn't find the sneakers, and they shouted this to the skies. The lady solved the murder, as usual, while the boxing match became too personal and people started leaving.
The second "instructioned" puzzle is Portals by Palmer Mebane. It is an insanely beautiful and difficult logic puzzle that consists of known puzzle types interconnected to each other through portals. Here Palmer Mebane explains how portals work:
"Each of the ten puzzles corresponds to a color, seen above the grid where the name of the puzzle is written. The grid contains nine square areas, one each of the other nine colors. These are portals that connect the puzzle to one of the other nine, as denoted by the portal color. Each puzzle's rules define which squares of their solution are "black". On the portal squares, the two puzzles must agree on which squares are black and which are not. For instance, if in the red grid the top left square of the blue portal is black, then in the blue grid the top left square of the red portal must also be black, and vice versa."
On the Portals puzzle page you can find the rules for how each individual game is played and how to shade areas. The puzzle requires a lot of attention. It took us a long time to test-solve it. If you make a mistake in one grid it will propagate and will lead to a contradiction in another grid, so it is difficult to correct mistakes. If you do make a mistake, you are not alone: we kept making mistakes during our test-solve. Because of the difficulty of tracing back to the source of the error, we just started anew, but this time making sure that every step was confirmed by two people. Working together in this way, we were able to finish it.
If you do not care about the extraction and the answer, ignore the letter grid in the middle and enjoy the logic of it.
There were a couple of puzzles during the MIT Mystery Hunt that were not so mysterious. Unlike in traditional hunt puzzles, these puzzles were accompanied by instructions. As a result you can dive in and just enjoy solving the logic part of the puzzle without bothering about the final phase, called the extraction, where you need to produce the answer.
The first puzzle with instructions is Random Walk by Jeremy Sawicki. I greatly enjoyed solving it. In each maze, the goal is to find a path from start to finish, moving horizontally and vertically from one square to the next. The numbers indicate how many squares in each row and column the path passes through. There are nine mazes in the puzzle of increasing difficulty. I am copying here two such mazes: the easiest and the toughest. The colored polyomino shapes are needed for the extraction, so you can ignore them here.
Today I have a special treat for you. Here is the first of several puzzles that I plan to present from the 150 that we used in the MIT Mystery Hunt 2013. Keep in mind that although the puzzles have authors, they were the result of a collaboration of all the team members. In many instances editors, test-solvers and fact-checkers suggested good ways to improve the puzzles.
I wrote the puzzle Open Secrets jointly with Rob Speer. The puzzle was in the opening round, which means it is not too difficult. By agreement the answers to the puzzles are words or phrases. I invite my readers to try this puzzle. I will post the explanation in about two weeks.
I dropped my blog for two months. Some of my readers got worried and wrote to ask if I was okay. Thanks for your concern.
I am okay. I was consumed by the MIT Mystery Hunt. My team, Manic Sages, won the hunt a year ago, and as a punishment — oops, I meant as a reward — we got to write the 2013 hunt, instead of competing in it. I myself ended up writing about ten problems for the hunt. This was in addition to test-solving about 150 problems my whole team prepared for the hunt.
I could only think about the hunt. My mind was full of ideas for the hunt so I was afraid to write in my blog about something that I might later want to use for my problems. Or even worse, I was nervous that my blog posts might be unconsciously revealing hunt secrets. Moreover, I didn't want to advertise the fact that I was working on the hunt, thereby drawing people to my blog to scrutinize my interests as they prepared for the hunt.
So I just disappeared.
I apologize; please forgive me.
The father of my son has four children. My son is my only child. How many children do we have in total together?
"I will win the next International Chopin Piano Competition."
No matter how good I am at positive affirmations, that won't work: I do not play piano.
I tried to read books on positive thinking, but they made me mistrust the genre. The idea that you can achieve anything by positive thinking makes no sense. For example:
Positive thinking might actually be harmful. I can invest tons of time into trying to change my natural eye color by using my thoughts, when instead I could just use my money and buy some colored contact lenses. Or, if I think myself rich, I might start spending more money than I have and end up bankrupt.
However, perhaps I should not have totally dismissed the idea of positive thinking. While it does have logical inconsistencies, such as those in my examples above, maybe there are ways in which positive thinking is helpful.
First, we should treat these beliefs not as a guarantee, but probabilistically. For example, if you think that you can win the piano competition, the judges will feel your confidence, and may give you slightly better marks.
Second, positive thinking can work, if we choose our affirmations correctly. I recently discovered that I am deceiving myself into believing that I am hungry when I'm not. I should be able to reverse that. I should be able to persuade myself that I am not hungry when I am.
I decided to start small. I tried to persuade myself that tiramisu doesn't really taste good. Once that seemed to be working, I got more serious. I bought a couple of CDs with affirmations for weight loss.
Unfortunately, they want me to lie down and relax. I do not have time to lie down. I could listen when I am driving or when I am cleaning my kitchen. Hey, does anyone know some good weight-loss affirmations CDs that do not require relaxation?
Last revised October 2013