About spiros

Spyridon Michalakis does research on quantum many-body physics and topological quantum order at Caltech's Institute for Quantum Information and Matter, where he is also the manager for outreach activities.

Unsolvable

mar-de-plata1

Why go swimming, if you can do math instead inside a room with no windows?

Back in 1997, during my visit to beautiful Mar del Plata in Argentina, I was asked to solve a math problem that I soon realized was close to being unsolvable. The setting was the Banquet for the 38th International Math Olympiad. I was 17 and there was delicious, free food in front of me, so it was pretty impossible to get my attention. Still, the coach of the Romanian team decided to drop by the Greek table to challenge us with the following problem:

Infinite Power: If x^{x^{x^{x^{\dots }}}} = 2, find x.

I was pretty hungry and a bit annoyed at the interruption (it is rude to eat and do math at the same time!), so I looked at the problem for a moment and then challenged him back with this one:

Infiniter Power: If x^{x^{x^{x^{\dots }}}} = 4, find x.

After a few moments, he looked at me with a puzzled look. He knew I had solved his problem within a few seconds, he was annoyed that I had somehow done it in my head and he was even more annoyed that I had challenged him back with a problem that confounded him.

Your mission, if you choose to accept it, is to figure out why the coach of the Romanian IMO team left our table alone for the rest of the competition.

Good luck!

PS: The rest of the Romanian team (the kids) were really cool. In fact, a few years later, I would hang out with a bunch of them at MIT’s Department of Mathematics, or as my older brother put it, The Asylum.

One, two, three, four, five…

As this year comes to a close, people around the world will be counting down the last few seconds of 2012. But, how come we never count up the first few seconds of the new year? What is it about the last few seconds of the year that makes them so special? Maybe it has to do with surviving a Mayan apocalypse, but that was just this year. I guess it always comes down to letting go of the good and of the difficult moments in our past. The champagne helps. Still, I would like to take a moment to pay tribute to the first few seconds of 2013 (the future) with a simple problem and a twist…

back-to-the-future

The question is simple enough:
What is the longest sequence of consecutive numbers, such that each element of the sequence is a power of a prime number?

You will arrive at the answer soon after asking yourself the question: How often is a number divisible by both 2 and 3? The answer is every 6 numbers (since the number in question has to be divisible by 2\cdot3). So, the best one can do is to count the numbers from one to five. That is, if you count 1 as the power of a prime number, then the first five numbers have the incredible property of being the only such sequence of numbers (right?). [Note: Recalling that 1 is not a prime number (see Redemption: Part I, for a hint), we will allow ourselves to use 0 as a valid power to which we may raise a prime number, thus getting 2^0 = 1, which completes the argument.]

Now, here comes the twist…

Challenge: Is there a sequence of 10 consecutive numbers such that none of them is a power of a prime number?

To get the ball rolling, here are the first such sequences with one, two and three elements, respectively: [6], [14,15], [20,21,22].

Super Challenge: Can you find a sequence of 2013 consecutive numbers, such that none of them is a power of a prime number?

Impossible Challenge: Can you solve the first challenge, giving the sequence containing the smallest numbers satisfying the conditions of the problem?

Good luck and enjoy the rest of 2012! Who knows, maybe some genius will solve the above challenges before 2013 rolls around…

Fermat’s Lost Theorem

Pierre Fermat, known for his Last Theorem and for rarely proving any of his claims.


Last week, I posted a series of increasingly difficult challenges in the post One line proof. Today, I would like to spend some time with the second challenge:

Fermat’s Lost Theorem: Show that (x+y)^n = x^m+y^m has only one solution for integers x > y > 0 and m,n > 1.

The truth is, I don’t know how to solve this problem myself. But, I think that we can figure it out together. Below, I will give the solution to the simpler case of y=1 and x > 1. I expect that many of you know the following variant of the problem:

Fermat’s Last Theorem: Show that z^m = x^m + y^m has no solutions for integers z > x > y > 0 and m > 2.

The above theorem was one of the most important unsolved problems in mathematics, until Andrew Wiles presented his proof to the public at a conference in Cambridge in 1993. Then someone pointed out a serious flaw in his proof and the extreme high Wiles was feeling turned into a dark abyss of despair. But being awesome implies that you pick yourself up and run full force towards the wall as if you didn’t get floored the last time you tried breaking through. And so Andy went back to his office and, with a little help from his friend (and former student) Richard Taylor, he fixed the flaw and published the massive proof in the most prestigious journal of mathematics, the Annals of Mathematics, in 1995.
Continue reading

One line proof

It is not often that we come across a problem whose solution can fit in the margins of a notebook. In fact, many of the problems I have worked on in the field of quantum many-body physics require proofs that often exceed 30 pages. And that is without taking into account the several references included as sources for results used as “elementary” tools in the proof (referees love these papers…) So it is natural to think that a proof is a proof, so long as it is correct, and once confirmed by the academic community it is time to move on to something new.

But… sometimes things get interesting. A 30-page proof collapses to a 3-page proof when a different point of view is adopted (see the famous Prime Number Theorem). Below, you will find two problems that may, or may not have a “one-line” proof. The challenge is for you to find the shortest, most elegant proof for each problem:

A unit triangle: A triangle with sides a\le b \le c has area 1. Show that b^2 \ge 2.

Fermat’s Lost Theorem: Show that (x+y)^n = x^m+y^m has only one solution with positive integers x > y > 0 and m,n > 1.

Continue reading

No calculators allowed

During Friday evenings at Caltech, the Institute for Quantum Information and Matter runs a seminar series focusing on research talks geared towards a diverse audience whose common background is quantum mechanics (just that, nothing else…) But, the fun doesn’t end after the 45 minute talks are over. The seminar is followed by a mingling session on the brand new patio of East Bridge, the building where Richard Feynman delivered his famous lectures.

Grigori Perelman. Not a Russian middle-schooler anymore, but still pretty smart.

Last Friday, Aleksander Kubica (pronounced Koobitsa), a Polish graduate student in the Theory group of IQIM and a first prize winner of the 2009 European Union Contest for Young Scientists, decided to test our ingenuity by giving us a problem that Russian middle-schoolers are expected to solve. If you haven’t met any Russian middle-schoolers, well, let’s just say that you should think carefully before accepting a challenge that is geared towards their level of mathematical maturity. What was the challenge?

Problem 1: Show that: \frac{1}{2}\cdot \frac{3}{4}\cdot \frac{5}{6}\cdot \frac{7}{8}\cdot \frac{9}{10}\cdots \frac{99}{100} < \frac{1}{10}.
Continue reading

Redemption: Part II

Last week, a journey began to find the solution to a problem I could not solve as a seventeen year-old boy. That problem became an obsession of mine during the last days of the International Math Olympiad of 1997, the days when I also met the first girl I ever kissed. At the time, I did not have the heart to tell the girl that I had traveled across the Atlantic to compete with the best and brightest and had come up short. I told her that I had solved the problem, but that the page with my answer had been lost. I told my parents the same thing and to everyone at school who would ask me why I did not return with a medal from the Math Olympics. The lie became so powerful that I did not look at that problem again until now. So, you may be wondering why a blog about Quantum Information Science at Caltech includes posts on problems from Math Olympiads. And why I would open the book on the page with that one problem after fifteen years… Continue reading

Redemption: Part I

Back in my last post, I closed with a problem (The Redeemer) from the International Math Olympiad of 1997. Unlike the problem I posted from 1981 (Elementary, my dear Watson), I was actually walking by the time I met The Redeemer. In fact, I was in Mar del Plata, a beautiful seaside beach resort in Argentina, participating in the 38th International Math Olympiad. The Redeemer was Problem 5. I remember clearly the moment I saw it. It looked so simple, so innocent: Find all pairs of positive integers a,b \ge 1, such that a^{(b^2)} = b^a.

I had to solve it. But little did I know…

Continue reading

A promise

During my recent trip back home, I had a chance to talk with friends and family over dinner about the future of Greece. I heard about tales of political corruption and wasted opportunities within Greece, but I noticed also a growing resentment towards the rest of the world, who was mocking us, at best, and was out to get us, at worst. After I had listened for a while to the older generation, I asked them this: “So, what do you plan to do about all this?” They looked at me and an old, wise-looking man said: “There is nothing to be done. If you try to change anything, they will find you and silence you. I tried to change things once…” At this point, the younger generation, some still in high-school, others in college, nodded approvingly. But one young man, a young composer planning to study at the famed Berklee College of Music, was looking at me intently. What was he thinking? Why wasn’t he nodding with the old man? I don’t know. But, it was then that I turned to the old man and said: “There are wise men who see the world as it is. And there are fools who see it as it can be.”
Continue reading

Elementary, my dear Watson

On last week’s “Welcome to the math olympics”, I closed with a problem from the International Math Olympiad of 1981 (a bad year for wine – I would know, I was an avid drinker back then). I would like to take some time to present a solution to this problem, because this is where all the magic happens. What magic? You will see. Here is the problem again:

Problem 6 (IMO 1981, modified): If f(0,y) = y+1, \, f(x+1,0) = f(x,1) and f(x+1,y+1) = f(x, f(x+1,y)), for all non-negative integers x,y, find f(4,2009).

The solution that follows uses solely elementary mathematics. What does that mean? It means that a 15 year-old can figure out the solution, given enough time and an IQ of 300. And, indeed, there are some who can solve this problem in 15 minutes. But, as you will see, it takes clarity of mind that is only attained through relentless effort. Effort to the outside world – to you, it will feel like you are going down the rabbit-hole and you don’t want the journey to end. But you must enter this world with wonder, because it is the world of the imagination – a world where your greatest weapon is your curiosity, prodding your mind to see how far the rabbit-hole goes.
Continue reading

Welcome to the math olympics

It was a beautiful day in the Winter of 1994. I had slept in because it was Saturday, but my older brother, Nikos, was not so lucky. He had just come back from a regional math competition named after the Greek philosopher Θαλής (Thales of Miletus) and he did not look happy. I asked him how he did, but he did not answer; he just reached into his backpack and took out the paper that contained the problems from the competition. Looking back, what I did next defines much of how I approach life since that day: I took the paper and started solving the problems one after the other until I was done. It took me three days – the competition lasted three hours.
Continue reading