The mentors that shape us

Three years and three weeks ago I started my first blog. I wasn’t quite sure what to call it, so I went to John for advice. I had several names in mind, but John quickly zeroed in on one: Quantum Frontiers. The url was available, the name was simple and to the point, it had the word quantum in it, and it was appropriate for a blog that was to provide a vantage point from which the public could view the frontiers of quantum science. But there was a problem; we had no followers and when I first asked John if he would write something for the blog, he had said: I don’t know… I will see…maybe some day… let me think about it. The next day John uploaded More to come, the first real post on Quantum Frontiers after the introductory Hello quantum world! We had agreed on a system in order to keep the quality of the posts above some basic level: we would send each other our posts for editing before we made them public. That way, we could catch any silly typos and have a second pair of eyes do some fact-checking. So, when John sent me his first post, I went to task editing away typos. But the power that comes with being editor-in-chief corrupts. So, when I saw the following sentence in More to come…

I was in awe of Wheeler. Some students thought he sucked.

I immediately changed it to…

I was in awe of Wheeler. Some students thought less of him.

And next, when I saw John write about himself,

Though I’m 59, few students seemed awed. Some thought I sucked. Maybe I did sometimes.

I massaged it into…

Though I’m 59, few students seemed awed. Some thought I was not as good. Maybe I wasn’t sometimes.

When John published the post, I read it again for any typos I might have missed. There were no typos. I felt useful! But when I saw that all mentions of sucked had been restored to their rightful place, I felt like an idiot. John did not fire a strongly-worded email back my way asking for an explanation as to my taking liberties with his own writing. He simply trusted that I would get the message in the comfort of my own awkwardness. It worked beautifully. John had set the tone for Quantum Frontier’s authentic voice with his very first post. It was to be personal, even if the subject matter was as scientifically hardcore as it got.

So when the time came for me to write my first post, I made it personal. I wrote about my time in Los Alamos as a postdoc, working on a problem in mathematical physics that almost broke me. It was Matt Hastings, an intellectual tornado, that helped me through these hard times. As my mentor, he didn’t say things like Well done! Great progress! Good job, Spiro! He said, You can do this. And when I finally did it, when I finally solved that damn problem, Matt came back to me and said: Beyond some typos, I cannot find any mistakes. Good job, Spiro. And it meant the world to me. The sleepless nights, the lonely days up in the Pajarito mountains of New Mexico, the times I had resolved to go work for my younger brother as a waiter in his first restaurant… those were the times that I had come upon a fork on the road and my mentor had helped me choose the path less traveled.

When the time came for me to write my next post, I ended by offering two problems for the readers to solve, with the following text as motivation:

This post is supposed to be an introduction to the insanely beautiful world of problem solving. It is not a world ruled by Kings and Queens. It is a world where commoners like you and me can become masters of their domain and even build an empire.

Doi-Inthananon temple in Chiang Mai, Thailand. A breathtaking city, host of this year’s international math olympiad.

It has been way too long since my last “problem solving” post, so I leave you with a problem from this year’s International Math Olympiad, which took place in gorgeous Chiang Mai, Thailand. FiverThirtyEight‘s recent article about the dominance of the US math olympic team in this year’s competition, gives some context about the degree of difficulty of this problem:

Determine all triples (a, b, c) of positive integers such that each of the numbers: ab-c, bc-a, ca-b is a power of two.

Like Fermat’s Last Theorem, this problem is easy to describe and hard to solve. Only 5 percent of the competitors got full marks on this question, and nearly half (44 percent) got no points at all.

But, on the triumphant U.S. squad, four of the six team members nailed it.

In other words, only 1 in 20 kids in the competition solved this problem correctly and about half of the kids didn’t even know where to begin. For more perspective, each national team is comprised of the top 6 math prodigies in that country. In China, that means 6 out of something like 100 million kids. And only 3-4 of these kids solved the problem.

The coach of the US national team, Po-Shen Loh, a Caltech alum and an associate professor of mathematics at Carnegie Mellon University (give him tenure already) deserves some serious props. If you think this problem is too hard, I have this to say to you: Yes, it is. But, who cares? You can do this.

Note: I will work out the solution in detail in an upcoming post, unless one of you solves it in the comments section before then!

Update: Solution posted in comments below (in response to Anthony’s comment). Thank you all who posted some of the answers below. The solution is far from trivial, but I still wonder if an elegant solution exists that gives all four triples. Maybe the best solution is geometric? I hope one of you geniuses can figure that out!

12 thoughts on “The mentors that shape us”

Thankfully, most very successful mathematicians and physicists were able to achieve such success without coming close to making one of those teams!

Reply ↓

well lets start with the easiest solution (2,2,2)

Reply ↓

Which may well be the only solution.

Reply ↓

Mark Weitzman on July 24, 2015 at 3:58 pm said:

So here is my probably wrong solution: The three equations are ab-c=2^n, bc-a=2^m, ca-b=2^p. Multiplying each by c,a,b leads to c(c+1)2^n=a(a+1)2^m=b(b+1)2^p. Now i need to prove that the product of consecutive positive integers cannot differ by a power of 2. I f this is correct then a(a+1)=b(b+1=c(c+1) which only has solutions a=b=c (since we are dealing with positive integers). But then a^2-a=2^n or a(a-1)=2^n, n=0 is impossible, n>=1 implies a-1=1 or a=2. This leads to (2,2,2). So if my hypothesis of consecutive positive integers differing by a power of 2 is correct, this would be the only solution, Of course this should be wrong since then the problem is way too easy.

Reply ↓
- dfan on July 24, 2015 at 6:19 pm said:
  
  When I multiply the three equations by c, a, and b, I get abc = c2^n + c^2 = a2^m + a^2 = b2^p + b^2, so c(2^n + c) = a(2^m + a) = b(2^p + b). which is different from your equalities. Where did one of us go wrong?
  
  Reply ↓
  - Mark Weitzman on July 24, 2015 at 6:29 pm said:
    
    You didn’t do anything wrong – I made one of my quick senile old man mistakes. How do you edit or delete a post here?
    
    Reply ↓

Let $ab - c=2^l$ , $bc - a=2^m$ , and $ca-b=2^n$ . On taking the pairwise differences of the equations, we get $(a-b)(c-1) = 2^n - 2^m$ and two similar equations obtained by cyclically permuting $a,b,c$ and $l,m,n$ . This could be written as $[(a-1)-(b-1)](c-1) = 2^n - 2^m$ (and cyclic permutations), which suggests the substitution $a = a' + 1$ , $b = b' + 1$ , and $c = c' + 1$ , so that we have $(a'-b')c' = 2^n - 2^m$ .

Next we take the pairwise sums of the original equations which are $(a+b)(c-1) = 2^n + 2^m$ (and cyclic permutations). In terms of $a', b', c'$ , this becomes $(a'+b'+2)c' = 2^n + 2^m$ . Now I add the equations $(a'-b')c' = 2^n - 2^m$ and $(a'+b'+2)c' = 2^n + 2^m$ to get $(a'+1)c' = 2^n$ . This implies that $a' + 1$ and $c'$ are both powers of $2$ . But by symmetry, we see that $a',b',c', a'+1,b'+1,c'+1$ are all powers of $2$ . This is only possible if $a'=b'=c'=1$ , which is to say $a=b=c=1$ . This therefore is the only solution.

Reply ↓

Arpan Saha on July 25, 2015 at 6:00 am said:

Can’t edit my earlier comment, but I obviously meant $a=b=c=2$ . Also, on second thoughts, the substitution was completely superfluous and could be done without.

Reply ↓
Arpan Saha on July 26, 2015 at 3:13 am said:

I’m sorry. There’s a much more serious error here. The pairwise differences are $(a-b)(c+1) = 2^n-2^m$ . This should have been evident from the fact that you can’t get anything new by adding the sum and difference of two equations.

Reply ↓

hum, I don’t think there is a single solution. (2,2,3) also works.

Reply ↓

anthonyleverrier on July 26, 2015 at 2:36 am said:

(3,5,7) and (2,6,11) also work.

Reply ↓
- spiros on July 28, 2015 at 4:48 pm said:
  
  The solutions have all been given in the comments above (up to permutations): (2,2,2), (2,2,3), (3,5,7) and (2,6,11). The difficult part is showing that there are no other solutions. The proof is a bit long, but the idea is to treat four cases separately. Let $ab-c = 2^m$ , $bc-a=2^n$ and $ca-b=2^r$ and assume $m \le n \le r$ , without loss of generality.
  
  The first case is $n=r$ , which implies that $bc-a = ca-b$ and, hence $(c+1)(b-a) = 0 \rightarrow b=a$ . Setting $b = a$ in the original equations, we get $a^2-c =2^m$ and $a(c-1) = 2^n$ . Solving for $c = a^2-2^m$ and plugging into the previous equation, we get $a(a^2-(2^m+1))=2^n$ . Setting $a=2^k$ , we immediately see that $2^{2k}=1+2^m+2^{n-k}$ , which can only hold if $k=1$ and either $m=0, n=2$ , or $m=1, n=1$ . In the first case, $a=2, b=2, c=3$ , and in the second case, $a=b=c=2$ .
  
  The second case is $m=n$ , but that case gives the same solution (2,2,2) as the previous case (using a similar argument as above). So, we can now assume that $m < n < r$ . At this point, we get two extra solutions, (2,6,11) corresponding to the case of $m=0$ and (3,5,7) corresponding to the case $m \ge 1$ . For the case $m=0$ , we have that $ab = 1+c$ and using equations mentioned above by Arpan (for pairwise addition and difference of equations), we get: $(a-b)ab=2^n(2^{r-n}-1)$ and $(a+b)(ab-2)=2^n(2^{r-n}+1)$. The next step, then is to write $a=2^{k}p_a, b=2^{l}p_b$ , where $p_a,p_b$ are odd, and show that $k=l=1$ (one can show that $k\neq l$ yields a contradiction; moreover, ab and ab-2 cannot both be multiples of 4), and $p_a=3, p_b=1$ , which corresponds to the solution (6,2,11).
  
  The last case is $1 \le m < n < r$ . To solve this case, we use the following equations: $c(a^2-1) = 2^m(2^{r-m}a+1)$ and $a(c^2-1)=2^n(2^{r-n}c+1)$ , which can be derived from $ab-c=2^m$ and $cb-a=2^n$ , after we plug in $b=ac-2^r$ and rearrange terms. In the case that $a$ is even, we have that $c$ is even, which further implies that $a=2^np_a, c=2^mp_c$ . After substitution and rearranging, it becomes clear that $p_a$ divides $1+p_c$ and $p_c$ divides $1+p_a$ . This is only possible is $p_a=p_c=1$ , which yields the equations $2^{2n}-1=2^{r-m+n}+1$ and $2^{2m}-1=2^{r+m-n}+1$ , whose only solution is $m=n=r=1$ , giving us the solution (2,2,2), which we already have. So, the last last case is to assume that both a,c are odd, which implies that $a^2-1=2^mp_a$ , and using the fact that $gcd(a-1,a+1)=2$ , we have $a+1=2^kp_k, a-1=2^{m-k}p_l$ , with $p_a =p_kp_l$ and $k=1$ , or $m=k+1$ . Finally, taking the difference of the two equations, we get $2=2^kp_k-2{m-k}p_l=2$ , which gives $a = 2^{m-1}p_k-1$ , or $a=2^{m-1}p_l+1$ . Similarly, we get $c = 2^{n-1}p_c-1$ , or $c = 2^{n-1}p_c+1$ . Plugging these back into the equations $(a+c)(b-1)=2^m(2^{n-m}+1)$ and $(c-a)(b+1)= 2^m(2^{n-m}-1)$ , we see that $b=2^{m-1}p_b+1$ , or $b=2^{m-1}p_b-1$ (with sign opposite that of a). Substituting into the previous equations, we see that $p_a=p_b=p_c=1$ (otherwise, the left-hand-side is larger than the right-hand-side) and $m=3,n=4,r=5$ , which gives $b=3, a=5, c=7$ .
  
  Reply ↓