Archive for October 2009

Ringamatics

Inspired by Michael Huber, who in his new book Mythematics combines math problems with Greek myths, I invented my first logic puzzle. Unlike Huber, I never had any ambition to help Hercules, but I always wanted to assist Frodo.

The day was passing towards sunset when the Company finally caught a long-awaited gleam of water, from which sparkled flickers of sunlight. As they quietly drew nearer, they laid their eyes on the next obstacle — a river that they had to transverse. The Company was footsore and tired and the hobbits were starving. But they couldn’t rest yet. They needed to collect materials with which to construct their raft before it became too dark. By nightfall they managed to build a tiny raft, and eagerly started their supper.

They couldn’t wait until dawn to build more rafts, for they needed to cross the river now. So while they rested, Aragorn smoked his pipe and began to contrive a plan.

Aragorn was in charge and there were eight of them. The four hobbits — Frodo, Sam, Merry and Pippin — were not very useful in battle. However, the four strong fighters — Aragorn, Gimli, Legolas and Boromir, who were sworn to protect the ring-bearer Frodo — were the best in the land.

The small raft they had built would not hold a lot of weight. Aragorn and Boromir were the heaviest. Gimli was short, but together with his armor he weighed as much as either Aragorn or Boromir. Each one of these three heaviest warriors was close to the raft’s maximum capacity, so they had to each be alone on the raft while crossing the river. Among the strong fighters, only Legolas was able to cross the river with a hobbit. The raft could also accommodate two hobbits.

Weight was not Aragorn’s only consideration: the current was dangerously fast. All the strong men could row, but among the hobbits, only Sam was strong enough to row against such a swift current.

Aragorn also worried about the orcs, who were roaming on both sides of the river. He didn’t want to leave any hobbit(s) alone on a riverside, without the safeguard of a strong fighter. Because he was the ring-bearer, Frodo needed extra protection. Aragorn wanted Frodo to be accompanied by at least two strong men. But lately Boromir had become restless when he was around the ring and Aragorn couldn’t count on him to look after Frodo. That is, while on the riverside, Frodo’s protection had to come from two out of the three remaining strong men: Aragorn, Legolas and Gimli.

Can you help Aragorn design a plan to cross the river?

Turing Tests’ Race

In a Turing test a human judge on one end of an interface interacts with either a computer or another human through this interface. If the judge can’t differentiate a machine from a human, then the computer is said to pass the test. One big goal of folks working in Artificial Intelligence is to build a computer that, when subjected to this test, is indistinguishable from a human.

However, while some people are working hard trying to build programs that can pass as humans, other people are working hard inventing tests that can differentiate between humans and those programs. Such tests are sometimes called Reverse Turing tests. As computer science progresses, the programs that are pretending to be humans as well as reverse tests are becoming increasingly complex.

For example, banks frequently want to prevent malicious computer programs from trying to log into their customers’ accounts. As a nice touch the judges are computers in this case. There are different methods designed to confirm that a human is trying to log in. In one of them a picture of a word, called CAPTCHA is presented on a screen, and the program requires that this word be typed in.

I wanted a CAPTCHA with words “Turing Test” in it for this posting. I looked online trying to find a way to do it. I couldn’t. There is a ton of software that can produce random CAPTCHAs from a dictionary but nothing could do a particular word. Finally, rather than looking for software, I found a human, a kind gentlemen named Leonid Grinberg who with some GIMP help manually implemented a self-referencing ” symbolizing the race between computers and tests.

As text recognition software becomes better and better, these CAPTCHAs become more and more difficult to read by a human. The last time I tried to login, I was only able to type the right word on my fourth try. Very soon computers will be better than humans at parsing CAPTCHAs. Humans are loosing the race on visual methods like this one.

Here’s another example. Some malicious software can recognize and capture email addresses on webpages to use for spam. While we don’t want them to recognize email addresses, we do want people to be able to do so. Thus we need a way to present email addresses as a reverse Turing test.

The standard safety recommendation is to avoid writing out the full and exact email address. Here’s an example: billgates AT gmail DOT com. Actually, I think computers are so smart nowadays that they can learn this trick. Another idea is to show a picture of your email address instead of using characters. Here we return to the image idea, which most computers can nowadays recognize.

Another idea of how to hide an email address is to give simple clues, which point to characters in the email address. For example, if you have “4″ in your address, you might say that the character is the sum of two and two. I already invented a version of my email address in which each letter of my username is an answer to a simple question. Unfortunately, I think that the question answering systems like Start, as well as its huge new competitor Wolfram Alpha, will learn to answer these questions very soon. I can construct more sophisticated questions, but that would require my readers to spend more time to figure it out including going back to school for a calculus class.

So, recently, I’ve come up with a new idea. I made the description of my email simpler, but the paragraph describing my email didn’t contain all the necessary information:

I have an email account with Yahoo. My account name consists of seven lower case letters: five letters of my first name concatenated with the first two letters of my last name.

People who want to contact me can easily find my name in the title of my webpage or in my url, but I hoped it would take the evil computers some time to figure out what to look for, where it’s located and how to turn it into an address.

The day after I changed my contact web page, I went to my math coaching work at AMSA. During my break, I wanted to unwind by solving a light up puzzle, but it appeared that the new security system at AMSA forbids Internet access to all gaming sites. Thus, being still wound up I decided to do some work and went to my personal page for some materials. I was blocked again. The software politely informed me that access to personal websites was not permitted either. Oops. If a computer can understand that it is a personal website, it probably can figure out the name of the corresponding person. Oops-Oops-Oops. I am loosing the race against computers again. My recent idea to protect my email address from spam lasted one day until my first reality check.

Geometric Transformations

In my days of competing in math, I met guys who could solve any geometry problem by using coordinates: first they would assign variables to represent coordinates of different points, then they would write and solve a set of equations. It seemed so boring. Besides, this approach doesn’t provide us with any new insight into geometry.

I find geometric solutions to geometry problems much more interesting than algebraic solutions. The geometric solutions that use geometric transformations are often the shortest and the most beautiful.

I.M. Yaglom wrote a great trilogy called The Geometric Transformations. The first book of this trilogy discusses translations, rotations and reflections. The second one — looks at similarity transformations, and the third one talks about affine and projective transformations. A lot of beautiful problems with their solutions are scattered throughout these books. They include all my favorite problems related to transformations.

I think geometry is the weakest link for the USA math team. So we have to borrow the best geometry books from other countries. This trilogy was translated from Russian and Russians are known for their strong tradition of excellence in teaching geometry.

Below you can find sample problems from Geometric Transformations 1, Geometric Transformations 2 and Geometric Transformations 3 — not necessarily in this order.

Problem 1. Let A be a point outside a circle S. Using only a straightedge, draw the tangents from A to S.

Problem 2. At what point should a bridge be built across a river separating two towns A and B (see figure) in order that the path connecting the towns be as short as possible? The banks of the river are assumed to be parallel straight lines, and the bridge is assumed to be perpendicular to the river.

Problem 3. Suppose you have two lines drawn on a piece of paper. The intersection point A of the two lines is unreachable: it is outside the paper. Using a ruler and a compass, draw a line through a given point M such that, were the paper bigger, point A would belong to the continuation of the line.

Not So Humble Pi

I added my favorite webcomics from “Not So Humple Pi” to my collection of funny math pictures.

Suppose you got accepted to the college of your dreams, say MIT. If you are so poor that MIT gives you a full financial package or you are so rich that the cost is not an issue, then you might throw a party. Everyone else, however, needs to wait for the financial package letter from MIT. The dream depends on the willingness and the ability of the parents to pay.

Suppose your father looks at the bill in shock. Then he takes you for a walk and tells you to forget about MIT and go to the state college, as he can’t pay the requested amount.

If you know for sure that your father has the money, what is the first question that you should ask him? The first question should be: “Are you still married to my mother?” If you are not completely clueless, you ought to know the answer to this question already. The family status of your parents may be the deciding factor in whether or not you can get your father to pay.

If your parents are divorced, your college expenses might be covered by their divorce agreement. In this case, there would be a legal document designating how your parents need to pay. If your father refuses to pay, your mother can use the divorce agreement to threaten your father with a complaint. The threat might be enough. If it is not, the court will probably force the reluctant father to pay according to the divorce agreement. So if your parents are divorced, it might be a good idea for you to scrutinize their divorce agreement.

Even if your parents’ lawyers neglected to include college expenses in the divorce agreement, you might still be able to finance your college education. Your mother, for example, might sue your father for college expenses.

I wonder what happens if the divorce agreement covers your college expenses, but neither parent wants to pay. I’m curious whether or not it is possible for the child to sue the parents based on the agreement he/she is not a party to. If any reader knows the answer, I’d appreciate hearing from you.

If your parents are together, there is no divorce agreement to protect your interests. It seems that legally the situation favors the children of divorced parents. If your parents do not love each other and have stayed in their marriage for your sake, it might be to your financial advantage to persuade them to divorce well before you need to go to college. Do not disregard reminding their lawyers to include college expenses in the agreement.

Israel Gelfand was my scientific adviser from the time I was 15. This is the story of how Gelfand helped me, when at 20 I was an undergrad at Moscow State University. At that time, I was married to Sasha (Alexander) Goncharov, who was also Gelfand’s student.

Sasha was more driven by mathematics than I. I had a lot of different interests: I wanted to hang out with friends, go to movies and read books. Sasha only wanted to do mathematics. His only other obsession was with what our colleagues (including me) were doing mathematically. So he was constantly asking me about the math problems I was thinking about.

For example, I was sitting at my side of the desk working, and he asked me to tell him about my problem. A few minutes later, I was forced to interrupt my work to go grocery shopping, because the household chores fell to me. As soon as I returned with bread and milk, Sasha excitedly told me the solution to my problem. It made me feel stupid, as if I should have solved it while I was waiting in the line for bread and milk. That feeling blocked out all the other feelings I should have been noticing, such as frustration and annoyance with Sasha.

Without his interference, I would have happily solved the problem myself. I was about to start my serious research, but I worried that I’d end up as a supplier of new problems for his papers.

You might wonder why I didn’t stop sharing my math with Sasha. But at that time, I wasn’t very in touch with my feelings and I prided myself on being a logical person. The idea that a husband and wife would discuss their work together seemed logical. Besides, even though I wasn’t particularly interested, Sasha was always ready to tell me about his math problems. It seemed important for me to be fair and to reciprocate. So I was stuck in a situation I didn’t know how to resolve.

I never confided this issue to any math colleagues. I never mentioned it to Gelfand — mostly because I was too scared of him to initiate any conversation. Besides, Gelfand delegated most of his responsibilities to others, because he was quite famous and busy. For example, all official paperwork related to his adviser role was done by Alexandre Kirillov. With me avoiding Gelfand and Gelfand being busy, we almost never spoke one-on-one.

You can understand my surprise when one day Gelfand approached Sasha and me to have a chat. He told us that we were about to start our own research, and while he permitted me to ask Sasha about what he was doing, he would not allow Sasha to interfere with my research.

Gelfand was a great judge of character. Without anyone telling him, he perceived what was going on in our marriage and gave me an excuse to stop Sasha’s prying. It was an appreciated gift.

The Odd One Out

I am strongly opposed to questions of the type “which is the odd one out” during IQ tests. On the other hand, I do not mind them in different settings, especially when they are fun. Inspired by Martin Gardner, I spent a lot of time drawing this picture, and now I have to share it with the world. So, which is the odd one out?

A Math Guide to the MIT Mystery Hunt

I love the MIT Mystery Hunt. I like the adrenalin rush when solving problems under pressure. Plus, I like the togetherness of doing problems with other people. During the hunt I usually do not have time to look at all the puzzles: some of them are solved by my teammates while I’m sleeping and others are solved before I get to see them.

I’ve never tried to go back and check out the puzzles I missed nor the puzzles from the previous hunts, probably because without the goal of winning and without my team, I might find them boring. Often the solving process involves tedious Internet browsing to identify the images of different people or objects. I would only be motivated if the puzzle were related to something I am very interested in, such as Ballroom dancing. But I’m not thrilled at the thought of browsing through all the problems in order to find one that is relevant to the Tango.

In short, I need an index to the puzzles. For example, it would be nice to direct the lovers of square dancing to the Do Sa Do puzzle, or fans of Star Trek to the Alien Species puzzle. I hope that nobody blames me for hinting that those aliens are from Star Trek. I’m convinced that Trekkies who only want to solve Star Trek-related puzzles would immediately recognize them anyway. I do believe that I am not revealing too much by saying that the Facebook puzzle will appeal to the aficionados of the television show “24″.

It would be extremely useful to humanity to at least mark the MIT Mystery Hunt puzzles that are self-consistent, and do not require activities. For example, some of the puzzles involve interaction with headquarters, so you can’t solve them after the hunt. Some of the puzzles might expire, as for example the puzzle with pictures of different announcements in the infinite corridor.

Unfortunately, such an index doesn’t exist, and I do not have the time or expertise to create one myself. But I can fill this void at least partially by presenting a guide to math puzzles from the previous four hunts. I can’t promise that my guide is complete, as navigating the MIT Mystery Hunt website is very tiresome.

Before going into the math puzzles, I would like to list Sergei’s favorite type of puzzle: Duck Konundrums. The first Duck Konundrum puzzle appeared in 2000. It was created by Dan Katz, which is why his initials are in the title. One really needs to follow the instructions for this puzzle. This is very unusual as traditionally hunt puzzles do not have instructions at all. Do not be relieved: the instructions are really very complicated. The next Duck Konundrum puzzle appeared in 2002 and was considered to be even more amusing. People loved it, and this type of puzzle became a tradition in subsequent hunts. Here is my list of Duck Konundrums:

Many Mystery Hunt puzzles appeal to mathematicians. I have to warn you though. Puzzles often are divided into two stages. In the first stage, you need to solve a puzzle, like solving sudoku, a crossword or finding all the wedding dates of the people in the pictures. The second stage requires you to produce a word or a phrase that is the answer to the puzzle. The second stage might be as simple as listing the people in chronological order of their wedding dates and then taking the first letters of their last names. This second stage could also be quite difficult. Depending on your tastes one stage of the puzzle might be much more rewarding than the other. If you love solving sudokus, you might find it more fun to just stop with that solution, instead of continuing on to the second stage.

2006

2007

2008

2009

It would also be nice to have some ratings for puzzles. I am not sure how to persuade the webmasters of the MIT Mystery Hunt page to do the index and the rating. Feel free to send them an encouraging email.