Goodbye 29, Hello 42

I’ve been celebrating my 29th birthday for many years. Once, when I was actually 45 and wanted to have a big party, I invited everyone to the 5th anniversary of my 29th birthday.

Last week my son turned 29 and I realized that it is time to drop this beautiful, prime, evil, deficient, lazy-caterer number, that in addition is the largest power of two to have all different digits. No more celebrating 29.

For my next age, I picked 42. Not because it is the smallest abundant odious number, but rather because it is the answer to life, the universe and everything.

Thank you everyone who congratulated me on my birthday two days ago. For your information, from now on I am 42.

Share:Facebooktwitterredditpinterestlinkedinmail

A Math Guide to the MIT Mystery Hunt 2011

As I did for 2010 and for previous years, here are math-related puzzles from the MIT Mystery Hunt 2011.

Two more puzzles deserve a special mention for their nerdiness. My teammates loved them.

Share:Facebooktwitterredditpinterestlinkedinmail

Mutant Sudoku

Mutant SudokuTired of the same old sudoku? Here’s an opportunity to try many variations of it. Thomas Snyder and Wei-Hwa Huang wrote a book called Mutant Sudoku. The authors are both Sudoku champions. I like the book because the authors are trying to bring everyone up to their level, rather than dumbing down their puzzles. So the book is not at all boring as are most Sudoku books.

The book contains about 180 fun puzzles. Look at the variety:

  • Tight Fit Sudoku
  • Extra Space Sudoku
  • Tile Sudoku
  • 3-D Sudoku
  • Outside Sudoku
  • Shape Sudoku
  • Target Sum Sudoku
  • Thermo-Sudoku
  • Consecutive Sudoku
  • Surplus Sudoku
  • Deficit Sudoku
  • Chimeric Sudoku

Wei-Hwa Huang kindly sent me this sample Thermo Sudoku puzzle from the book to use on my blog. The grey areas represent thermometers. Every particular thermometer has to have numbers in increasing order (not necessarily consecutive) starting from the bulb.

Thermal Sudoku

Sudoku Masterpieces

The second book by the same authors Sudoku Masterpieces: Elegant Challenges for Sudoku Lovers, is itself a masterpiece. With about 100 puzzles, there are fewer than in the first book, but there are more types of puzzles. As a consequence, you’ll have less practice for each particular type, but more variety. In addition, as you can see from the cover, the second book is elegantly designed.

I bought both books and immediately started scribbling in the first one. My bad handwriting would seem so out of place in the beautiful second book that I have not even started working in it yet. Maybe I will give it as a gift to someone with better penmanship.

Share:Facebooktwitterredditpinterestlinkedinmail

Two Planes Keep Flying

Two days ago I threw at my readers the following problem:

A plane takes off and goes east at a rate of 350 mph. At the same time, a second plane takes off from the same place and goes west at a rate of 400 mph. When will they be 2000 miles apart?

The purpose of throwing this problem was to discuss the nature of the implicit assumptions that we are asked to make when solving math problems, and the implicit assumptions we teach our children to make when we teach them to solve math problems. This is especially important for problems like this, that are phrased in terms of a situation in the real world. The real world is too complex to model all of; the great power of mathematics is that sufficiently idealized situations are predictable. But which idealizations are appropriate? How does one choose? How does one teach youngsters what to choose?

Before I get to the actual discussion, however, I want to re-throw this problem at my readers, in an effort to highlight what originally jumped out at me as being wrong with it.

Neglecting the effects of altitude, differential wind, acceleration, relativity, measurement error, finite size and non-superimposability of the planes, and the Earth’s deviations from perfect sphericity,

  1. Find how much time it takes them to become 2000 miles apart, assuming that the planes are starting from Boston and the distance is measured as
    1. a straight line in 3-space.
    2. the shortest surface distance.
  2. How far from the closest pole may the starting point be located, so that the answer to the problem is “never”? Solve separately for
    1. the 3D distance.
    2. the shortest surface distance.
  3. What portion of the Earth’s surface do the “never”-locations of the previous question occupy?
    1. under the 3D distance?
    2. under the shortest surface distance?

Hint: The easiest question is 2b.

Share:Facebooktwitterredditpinterestlinkedinmail

Naum Bernstein’s Jokes

My Jewish ex-father-in-law, Naum Bernstein, is 96 years old and is full of life. He has a joke for every situation. In the last decade he wrote several volumes of memoirs in Russian. One of the books was a collection of his favorite jokes and his explanations of them. I decided to retell some of the jokes from his selection.

Arithmetic

An arithmetic teacher calls the student Rabinovich to the blackboard. “It is known that from 1 kilogram of sour cream you can make 200 grams of butter. Imagine, Rabinovich, that your father bought 2 kilograms of sour cream. How much butter can he make?”

“Five hundred grams,” Rabinovich replies.

The teacher frowns, “Rabinovich, you do not know arithmetic!”

Rabinovich answers, “Sir, you do not know my father.”

Billions

An astronomy teacher explains that in the future the Earth will lose its heat energy, continents will collide, and solar radiation will increase. In six billion years life will be extinct. A student looking really scared raises his hand and asks, “In how many years will life become extinct?”

“In about six billion years,” the teacher repeats.

“Whew,” says the student, “you got me so scared. I thought you said six million.”

Soccer Player

Two professors are chatting while watching a soccer game. The first one says, “They say that soccer players have their brains in their legs. So their heads are really empty.”

“Not quite,” the second professor replies. “The player on the right passed my exam yesterday.”

The first professor expresses interest, so the second one elaborates. “As a rule, I ask two questions. If the student gives a correct answer to one of them, he passes.”

“So, what did you ask that guy?”

“My first question was ‘What color are red blood cells?’ He answered ‘Yellow.’ That was an incorrect answer. The second question was ‘How is sulfuric acid produced?’ To this he replied, ‘I do not know,’ which was absolutely true, so he passed.”

Pushkin’s “Eugene Onegin”

A Russian literature teacher asks a pupil, “Who wrote Eugene Onegin?” The pupil gets scared that he is being blamed for something and replies, “No, not me! I swear I didn’t write it!” Everyone laughs. The teacher decides that the pupil disrupted the class on purpose and asks for his father to come by.

The father arrives and after the teacher explains what happened, the father says, “Maybe he is not guilty; maybe he really didn’t write it. I doubt that he is capable of writing anything.”

The teacher is stunned and later tells the whole story in the teachers’ lounge to her colleagues. An astronomy teacher comes home and retells the story to her husband who works for the KGB. The husband comments, “Do not worry, we are on it. Three people already confessed to writing it.”

Death of an Anti-Semite

A hardcore anti-Semite was dying. As he got weaker he made a last request. He wanted to convert to Judaism. Everyone was extremely surprised, but decided not to interfere. After the conversion, his wife summoned the courage to ask him what was going on. “Do you think you were mistaken, hating Jews all your life?”

“No,” he replied happily, “But now with my death, the world will get rid of one more Jew.”

Shaving

An old Jew comes to a Rabbi and asks if he can shave his beard off, because his children think that he is old-fashioned. The Rabbi tells him that by Jewish law he is not allowed to shave. The old man turns to go home when he realizes that the Rabbi himself doesn’t have a beard. He stops and asks, “Dear Rabbi, you just forbade me to shave my beard, but how come you are clean-shaven yourself?”

The Rabbi replies, “I didn’t ask anyone’s permission.”

A Bureaucrat

When Rabinovich came to a bureaucrat with a request, the bureaucrat replied, “Come back tomorrow.” Rabinovich returned the next day and received the same reply. Rabinovich was very persistent and returned day after day.

Finally, the bureaucrat lost his patience and attacked Rabinovich, “This is outrageous! Don’t you understand simple language? I keep telling you to come tomorrow and you keep coming today.”

Bathroom Tissue

The communist committee of a supermarket in the USSR received a lot of complaints about the rudeness of their salespeople. The committee decided to improve the quality of service and provided special training in which salespeople were taught politeness. The training emphasized what to do in case a particular item was unavailable. The salespeople were supposed to politely explain that the item is temporarily unavailable and to offer a substitute.

The next thing one of their salespeople said to a customer was “I am very sorry, we are temporarily out of toilet paper. May I offer some sandpaper?”

13th Floor

There is panic in an apartment on the 13th floor. The wife recognizes the sound of her husband’s approach, even though he was supposed to be on a business trip. The lover asks, “What should I do, honey?”

“What do people do in such cases? Jump out the window!”

“But we are on the 13th floor!”

“This is no time for superstition!”

Smelly Socks

A young man had smelly feet, plus he always forgot to change his socks. His girlfriend got tired of it and asked him to promise that he would always change his socks before coming to see her.

Next visit the young man smelled as bad as ever. Outraged, the girl said, “But you promised to change your socks!”

The young man answered, “I did as I promised.”

“I don’t believe you, you smell awful.”

“I was sure you wouldn’t believe me. Good thing I brought my dirty socks with me as proof.”

A Recipe for a Happy Marriage

At the 50th anniversary of a very happy couple, someone asked the husband for their secret. He said that right before the wedding they agreed that the husband would decide all the crucial and very important things, and the wife would be responsible for all minor decisions. “For example,” he continued, “yesterday I decided that the US should withdraw their troops from Iraq, and my wife decided where to buy our vacation house.”

Coffee in Bed

Two long-time girlfriends meet after several years without being in touch. “How are your children?” asks one of them.

The other replies, “My daughter is fine, she married a nice young man, who is providing for her. He also helps her with chores and even brings her coffee in bed every morning.”

“What about your son?”

“It’s a disaster. I don’t know what to do. He married a really lazy woman. Even though she’s not working, she wants him to help her with the chores. Can you imagine that? She even dared to ask him to bring her coffee in bed every morning.”

Debt

Two friends are walking along a street very late at night. Robbers attack them with guns, demanding their wallets. One of the friends asks the robbers, “Can you give me 30 seconds?” The robbers agree. He takes out $100 from his wallet and gives it to his friend, “Remember I owed you $100? I am paying back my debt in front of witnesses.”

Struggle

Life is a struggle. Before lunch with hunger, after lunch with sleepiness.

Window

A mother says to her son, “Please, close the window — it’s cold outside.”

The son replies, “Do you think it will get warmer outside if I close the window?”

Pessimist and Optimist

How are pessimists and optimists different from normal people?

A pessimist uses both a belt and suspenders, an optimist uses neither.

Ads

In a cemetery there is a beautiful monument with a picture of a bald, wrinkled old man. He is smiling, showing his perfect white teeth. His epitaph says:

Here lies Mr. X, who lived more than 100 years, lost his hair, became all wrinkled, but kept his perfect teeth. That is because he always used our company’s toothpaste.

A nearby monument has a picture of an old toothless woman with beautiful, voluminous hair. The inscription explains which brand of shampoo she used.

Many other tombstones with ads are scattered throughout the cemetery. But in the middle there is a huge mausoleum with an inscription reading:

No one is buried here and no one ever will be, because his or her parents used condoms made by our company.

Shower

A Russian man marries an American woman. After a while he writes a letter home.

My wife must be very dirty. She showers every day.

Last

Rabinovich was asked why he didn’t attend the last committee meeting. He replied, “If I knew it was the last, I would certainly have come.”

Share:Facebooktwitterredditpinterestlinkedinmail

Two Planes

I stumbled upon the following problem in Mathematics Teacher v.73 (September 1980):

A plane takes off and goes east at a rate of 350 mph. At the same time, a second plane takes off from the same place and goes west at a rate of 400 mph. When will they be 2000 miles apart?

Ooh, boy!

Question for my readers: explain my reaction.

Share:Facebooktwitterredditpinterestlinkedinmail

Dangers of Auto-payments

I have a leased Toyota Corolla, and I am happily enrolled in AutoCheck payments with Toyota’s Financial Services. So I do not even look at my bills. Once I opened my bill and noticed that the requested payment was twice as high as I expected. I looked closer and the bill had a car tax included in it. I looked even closer and read that:

Your Current Payment Due will be automatically withdrawn from your checking or savings account on the above Payment Due Date or the next banking day.

I decided that everything was taken care of and continued my relaxed life. After several months I checked my bill again, and the car tax was still there. After more careful study of my bill I discovered that Toyota’s “Current Payment Due” doesn’t include my car tax. Obviously they assume that their definition of “Current Payment Due” is crystal clear to everyone.

I got worried about this delayed car tax payment and went online to pay it. I tried to make this payment, but Toyota’s website rejected it. The website informed me that because I am enrolled in AutoCheck, I am not allowed to make separate online payments. I couldn’t believe it: to do so, I would have to de-enroll first!

So I just wrote a check.

In one day my feelings for my Toyota Corolla were turned around. If their financial system is designed so stupidly, what can we say about their car designs? Suddenly the sound of my brakes and the squeak in my steering wheel worry me.

Share:Facebooktwitterredditpinterestlinkedinmail

From a Puzzle to a Magic Trick

A year ago I posted a chessboard puzzle. Recently I stumbled on a September 2008 issue of “Math Horizons” where it was presented as a magic trick.

When the magician leaves the room, the trickees lay out eight coins in a row deciding which side is turned up according to their whim. They also think of a number between 1 and 8 inclusive. The magician’s assistant then flips exactly one of the coins, before inviting the magician back in. The magician looks at the coins and guesses the number that the trickees thought of.

The magician’s strategy can be derived from the solution to the chessboard puzzle. The assistant numbers the coins from zero to seven from left to right. Then s/he flips the coin so that the parity addition (XORing) of all the numbers corresponding to heads is the number that the magician needs to guess. For this trick to work, the number of coins needs to be a power of 2.

Andrey Zelevinsky posted (in Russian) a cool variation of this trick with two decks of cards.

The magician has two identical card decks and he is out of the room for now. A random person from the audience thinks of a card. Next, the audience chooses several cards from the first deck. Then the assistant adds one card from the second deck to the set of chosen cards, lays them on a table, and then invites the magician back. The magician looks at the cards on the table and guesses the card that was thought of.

Unlike in the coin trick above, the number of cards in the deck doesn’t need to be a power of 2. This flexibility is due to the fact that the magician has two decks of cards, as opposed to one set of coins. Having the second deck is equivalent to the assistant in the coin trick being allowed to flip one or ZERO coins.

Share:Facebooktwitterredditpinterestlinkedinmail

Sergey Markelov’s Best

Nikolay Konstantinov, the creator and the organizer of the Tournament of the Towns, discussed some of his favorite tournament problems in a recent Russian interview. He mentioned two beautiful geometry problems by Sergey Markelov that I particularly loved. The first one is from the 2003 tournament.

An ant is sitting on the corner of a brick. A brick means a solid rectangular parallelepiped. The ant has a math degree and knows the shortest way to crawl to any point on the surface of the brick. Is it true that the farthest point from the ant is the opposite corner?

The other one is from 1995.

There are six pine trees on the shore of a circular lake. A treasure is submerged on the bottom of the lake. The directions to the treasure say that you need to divide the pine trees into two groups of three. Each group forms a triangle, and the treasure is at the midpoint between the two triangles’ orthocenters. Unfortunately, the directions do not explain how exactly to divide the trees into the groups. How many times do you need to dive in order to guarantee finding the treasure?

Share:Facebooktwitterredditpinterestlinkedinmail

On the Perfidy of Negative Numbers

Tanya Khovanova, Alexey Radul

Perfidy is to parity as odious is to odd and evil is to even. As a reminder, odious numbers are numbers with an odd number of ones in their binary expansions. From here you can extrapolate what the evil numbers are and the fact that the perfidy of an integer is the parity of the number of ones in its binary expansion. We live in a terrible world: all numbers are perfidious.

So why are we writing about the perfidy of negative numbers? One would expect it to be a natural extension of the perfidy of positive numbers, but it turns out that the naive way of defining it doesn’t work at all. Is there hope? Could negative numbers be innocent of evil and free of odiousness? Is zero an impenetrable bulwark against perfidy? Not quite, but something interesting does happen to evil as it tries to cross zero. Read on.

To define perfidy for negative numbers, let us study how perfidy behaves for positive numbers. It is easiest to think about the perfidies of power-of-two-sized chunks of non-negative integers at a time. Let us denote by Tn the string of perfidies of the integers from 0 to 2n−1, with evil being zero and odious being 1. So T0 = 0, T1 = 01, T2 = 0110, T3 = 01101001, …. The recurrence relation governing the Tn is Tn+1 = TnTn, where T is the bitwise negation of the string T, and juxtaposition is concatenation. The limit of this as n tends to infinity is the (infinite) sequence of perfidies of non-negative integers. This sequence is called the Thue-Morse sequence: 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,….

So defining the perfidy of negative numbers is equivalent to extending the Thue-Morse sequence to the left. If we are to define “the” perfidy of negative numbers, that definition should preserve most of the properties of the Thue-Morse sequence after extension.

So, let’s see. We asked around, and most people said that the binary expansion of a negative integer should be the binary expansion of its absolute value, but with a minus sign. Defining perfidy as parity of number of ones in this binary expansion corresponds to the following extended Thue-Morse sequence in which we mark values corresponding to negative indices with bold font: … 0, 1, 1, 0, 1, 1, 0, ….

One of the major properties of the Thue-Morse sequence is its fractal property: if you replace every zero of the Thue-Morse sequence by 0,1 and every one by 1,0, you will get the Thue-Morse sequence back. Clearly, our new extended sequence doesn’t have this property.

Another set of properties for the Thue-Morse sequence, called avoidance properties, is a long list of patterns that the sequence avoids. For example, the Thue-Morse sequence doesn’t contain any overlapping squares — patterns axaxa, where a is a character and x is a word. But you can see above, our first extension contains it. So this definition is wrong, not just once but twice (and two wrongs only make a right under very unusual circumstances). Perfidy is stymied by the cross-over from zero to minus one. Are negative numbers protected from the ravages of evil? (and odiousness?)

Unfortunately, there are many people, for example John Conway, who inadvertently extend the reach of perfidy by arguing that the binary expansion of a negative integer should be different. Indulge in a flight of fancy and imagine the binary expansion that consists of infinitely many ones to the left: …1111. What happens when you add 1 to it? The carry gets pushed infinitely far away, and you get …000000 — zero. So it is quite reasonable to let …1111 be the binary expansion of −1. Similarly, the string …1110 represents −2, …1101 represents −3, etc. Continuing this we see that the binary expansion of a negative integer −n is the bitwise negation of the binary expansion of n − 1 (including the leading zeros). This is called the Two’s complement representation.

Why is two’s complement a reasonable representation? Suppose you were trying to invent a binary notation for negative numbers, but you wanted to pursue uniformity by not using a minus sign. The problem is that the standard definition of the binary representation allows you to represent only positive numbers. But you can solve this problem with modular arithmetic: modulo any fixed N, every negative number is equivalent to some positive number (by adding enough multiples of N), so you can just represent it by representing that positive number. If you choose N to be a power of two, modding out by it is just truncation of the binary representation. If you let those powers of two tend to infinity, you get the two’s complement representation described above.

Aside: When you are building a computer, uniformity is money, because special cases cost special transistors. The two’s complement idea lets one build arithmetic units that just operate on positive numbers with some number of bits (effectively doing arithmetic modulo 2k), and leave the question of negativeness to the choice of representatives of those equivalence classes.

If we take two’s complement as the binary expansion of negative numbers, how will we define the perfidy? Is the number of ones in the infinite string …1111 corresponding to −1 even or odd?

We can’t answer that question, but we know for every binary expansion of negative numbers the parity of the number of zeroes. Thus we can divide all negative integers in two classes with different perfidy. We just do not know which one is which.

Let us consider two cases. In the first case we consider a negative number odious if the number of zeroes in its binary expansion is odd. The corresponding extended Thue-Morse sequence is: … 0, 1, 1, 0, 0, 1, 1, 0, …. The negative half is the reflection of the classical Thue-Morse sequence. In the second case we consider a negative number odious if the number of zeroes in its binary expansion is even. The corresponding extended Thue-Morse sequence is: … 1, 0, 0, 1, 0, 1, 1, 0, …. The negative half is the bitwise negation of the reflection of the classical Thue-Morse sequence.

Can we say that one of the sequences is better than the other? Both of them respect the fractal property of the classical Thue-Morse sequence. Let us look at the avoidance properties. The avoidance properties are symmetric with respect to switching zeroes with ones and with respect to changing the direction of the sequence. Hence, the negation, the reflection, and the reflection of the negation of the Thue-Morse sequence will continue to respect these properties.

Thus, we only need to check the avoidance properties of the finite subsequences that span both negative and non-negative indices. We claim that for both definitions of perfidy, any finite middle subsequence of the extended Thue-Morse sequence occurs as a subsequence in the classical Thue-Morse sequence. So any avoidance properties that are true for the Thue-Morse sequence will also be true for both extensions.

Indeed, it is easy to show that the strings T2n defined above are palindromes. So for the first definition of perfidy the string in the middle will be a substring of T2nT2n for some large n, and for the second definition a substring of T2nT2n. But the classical Thue-Morse sequence contains the subsequence T2nT2nT2nT2nT2nT2nT2nT2n. So whichever way we extend the Thue-Morse sequence to the left any finite middle part will always be a repetition of a piece in the classical Thue-Morse sequence. Thus, all the avoidance properties will hold.

We see that there are two logical ways to define perfidy for negative integers. There are two clear groups of numbers with the same perfidy, but which is called evil and which odious is interchangeable. So evil doesn’t stop at zero after all, but at least it gets an identity crisis.

Share:Facebooktwitterredditpinterestlinkedinmail