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…

The things you will learn here are not things you will learn in college, even if you are a math and science major. Remember this: International Math Olympiads do not test advanced knowledge in math; the participants aren’t even allowed to drink beer in most countries. They test for genius. So my plan is to teach you how to become more than a genius – to become open. If I do this right, the world around you and all of its problems will become challenges that you can’t wait to take on. Since this is the beginning of our journey together, I ask only that you bring your curiosity with you; the one that prompted you to ask Why? all the time when you were a kid. Leave everything else behind – your pride, your fears, the expectations of others. If the math gets too advanced at any point, or the concepts too complex, mea culpa. Keep that in mind and let me know in the comments. And if you find that you are lost from the get-go, don’t give up. Ask for clarification every time, even if you don’t know why you are lost – simply write “I am lost…” in the comments. My intended audience is high school students and up, but if you are lost because you have forgotten how to add fractions, for example, I will show you how again and I will refer you to some great online resources, like Khan Academy’s videos on fractions.

When I was in grad school, I spent 4 hours listening to a student who was struggling with a math class because he was uncomfortable with very small numbers (micronumerophobia). Together, we addressed his anxiety and he went on to become one of the top students in the class. In other words, don’t count on me letting go until you get to your Eureka! moment, even if your biggest obstacle is of the I-am-not-smart-enough variety. With time, this feeling will pass and will be replaced by a vibrant clarity of mind. Now, before going any further, go back and read Redemption: Part I. You will see how natural numbers, which encode the universal language of mathematics, are like molecules that are made up of atomic elements (prime numbers) on the periodic table. You will also learn about relatively prime numbers, which correspond to molecules that share no common elements, like $H_2 O$ (water) and $NaCl$ (salt). Finally, you will meet the greatest common divisor, a number whose importance you have to witness in action to appreciate.

Redemption rebooted…

The challenge: Find all pairs of positive integers $a,b \ge 1$ , such that $a^{b^2} = b^a.$

The biggest progress we made so far in solving this problem came from extracting in Part I the greatest common divisor (gcd) from the numbers $a,b$ in the above equation. The new equation became:

$d^{b^2-a} a_1^{b^2} = b_1^a,$

where $d=gcd(a,b)$ and the numbers $a_1 = a/d, \, b_1=b/d$ are relatively prime (i.e. strangers in the night). Looking at the above equation, we decided to break it into three cases (because if the power to which $d$ is raised is negative, the equation must be turned on its head to avoid equating apples to oranges – whole numbers on one side with fractions on the other side):

$b^2 > a,$
$b^2 = a,$ and
$b^2 < a.$

Case 1 was considered already in Part I and led to the equation: $b_1 = d^{db_1^2-1}$ . Now we try different values for $d$ and see what we get. Starting with $d=1$ , we have $b_1 = 1$ (since 1 raised to any power is always 1). And this is precisely the case which yields the solution we already knew: $a=1,b=1$ . Or is it? Remember clarity of mind? Which case are we considering again? Case 1: $b^2 > a$ . In other words, $1^2 > 1$ in this case, so we get a contradiction and $d$ cannot be 1. So we keep going: $d \ge 2$ yields $b_1 = d^{db_1^2-1} \ge 2^{2b_1^2-1},$ and squaring both sides gives: $b_1^2 \ge 2^{2(2b_1^2-1)}$ , which becomes $(2b_1)^2 \ge 2^{(2b_1)^2}$ after a quick rearrangement (ask me how in the comments). And we have reached a very important milestone in your journey: The day you learn about mathematical induction.

Mathematical induction is so important, that I will not even give you the definition here. I will illustrate it by showing you that the inequality $(2b_1)^2 \ge 2^{(2b_1)^2}$ has no solutions in the natural numbers $b_1 \ge 1$ . That’s right. In two lines, I will prove to you that no value of $b_1$ (and there are infinite of them to consider) satisfies both sides of this inequality. We will prove that the inequality should be reversed from $(2b_1)^2 \ge 2^{(2b_1)^2}$ to $(2b_1)^2 < 2^{(2b_1)^2}$ :

Test the simplest case: $b_1=1$ yields $2^2 < 2^{(2^2)} = 16$ . Check.
Set $s=(2b_1)^2$ and check that $s+1 < 2^{s+1}$ whenever $s < 2^s$ : $s+1 < 2^s + 1 \le 2^s + 2^s = 2^{s+1}$ , where I used $2^s \ge 1$ , for all $s \ge 0$ .
BAM!

What kind of sorcery is this?!? Well, let’s play it back in slow motion… First, we do a sanity check in Step 1, to make sure we are not about to prove the wrong thing! This is called the base case, which obviously refers to the foundation upon which we will build the rest of our argument. Next comes magic. And like all great magic tricks, the sense of wonder only increases once the truth is revealed. And the trick is simple: If you can show that your guess works for the number $s+1$ , assuming that it works for the number $s$ , then you are done. Because $s+2$ is to $s+1$ , as $s+1$ is to $s$ . Good stuff, right? Right. So, back to the one-liner above: $s < 2^s$ implies $s+1 < 2^s+1$ (just add one on both sides) and $2^s \ge 1$ , for all positive exponents $s$ (check out this Khan Academy video on exponents). The rest follows from $2^s+1 \le 2^s+2^s = 2^1\cdot 2^s = 2^{1+s}$ (again, check out the video on exponent rules). That line of inequalities we just saw is the famous inductive step (up there with the dubstep) and the assumption we made (the guess) that $s < 2^s$ (for some fixed number $s$ ) is the equally famous inductive hypothesis (if you haven’t heard of it, it’s because we run in different circles).

But words are like leaves, and where they most abound, much fruit of sense beneath is rarely found.

So forget about inductive steps and hypotheses and remember only the feeling of satisfaction from realizing that in two lines, we showed that Case 1 is a dud. No numbers $a,b \ge 1$ can satisfy both $b^2 > a$ and $a^{b^2} = b^a$ . And let’s be honest; Case 2 is looking pretty easy. If $b^2=a$ , then the exponent of $d$ is 0 and the equation $d^{b^2-a} a_1^{b^2} = b_1^a$ reduces to $a_1^{b^2} = b_1^a$ . But the numbers $a_1, b_1$ are relatively prime (and as we proved in Part I, so are their powers). Now, how can it be that two molecules with no common atomic elements can be equal? It can’t be! Unless $a_1 = b_1 = 1$ , which yields $a=b=d$ . Is this consistent with $b^2=a$ ? Yes, as long as $d^2=d$ , which implies $d=1$ (since $d\ge 1$ ). Finally, we have a solution: $a=b=1$ ! The obvious solution we already knew about… But in the process, you learned about mathematical induction. And this is up there with learning how to add two numbers.

Life-changing stuff.

What about Case 3: $b^2 < a$ ? All you need to know, you have already been taught in these two parts. So, you’ve got to ask yourself one question: Do I feel lucky? Well, do ya?

5 thoughts on “Redemption: Part II”

shaunmaguire on October 2, 2012 at 9:47 pm said:

Thanks for the incredibly ‘open’ post. Especially the part about lying to the girl and your peers — it takes guts to admit something like that.

As a reference for curious aspiring mathematicians reading this post, I originally learned about induction, the pigeon-hole principle, invariants and other problem solving tricks from Loren C. Larson’s “Problem Solving Through Problems.” It’s a fantastic book that I couldn’t recommend more highly.

Reply ↓
James Graber on October 8, 2012 at 2:49 pm said:

I liked this post. After some work, I think I have a solution to $a^(b^n) =b^a$ for integer n. I will post it or reply by email if you wish. Jim Graber

Reply ↓
- spiros on October 8, 2012 at 3:59 pm said:
  
  Dear James, please post your answer below! You may use $latex … for equations in tex. If you need a reference, Google “latex wordpress”.
  
  Reply ↓
  - James Graber on October 13, 2012 at 10:29 am said:
    
    Sorry to be so late in responding.
    $a^(b^n) = b^a$ for n an integer, although it may not be necessary for n to be an integer. Solution is:
    $a=b^b$
    $b = n+1$
    Examples:
    $4^2=2^4$
    $(27^ (3^2)) = 27^9=3^27$
    $(256 ^(4^3)) = 256^64 = 4^256$
    etc.
    
    Reply ↓
James Graber on October 13, 2012 at 10:39 am said:

Both sides of the equation equal (n+1)^((n+1)^(n+1)).

Reply ↓