A puzzle from James Tanton

Michael Lugo Uncategorized March 20, 2012 2 Minutes

James Tanton asks in a series of tweets (which I’ve modified slightly): Write 20 numbers. Erase any two, $a$ and $b$ , and replace with $f(a,b)$ , where some possible choices of $f(a,b)$ are:

$f_1(a,b) = a+b+ab$ (here)
$f_2(a,b) = \sqrt{a^2+b^2}$ (here)
$f_3(a,b) = ab/(a+b)$ (here)
$f_4(a,b) = \log(e^a+e^b)$ (here)

Repeat 19 times, until you get a single number. The final result will be independent of the choices of pairs made. Why?

For example, consider $f(a,b) = a+b+ab$ . And say we start with the numbers 2, 3, 6, 7. Then we could choose to do the replacement as follows. In each case the two bolded numbers are replaced by one.

2, 3, 6, 7 becomes 3, 7, 20
3, 7, 20 becomes 7, 83
7, 83 becomes 671

and so we’re left with 671. Or we could have

2, 3, 6, 7 becomes 2, 7, 27
2, 7, 27 becomes 23, 27
23, 27 becomes 671

and again we’re left with 671. What’s going on here? It’s not immediately apparent, but if you try this starting with lots of small integers, you often get results which are one less than some number with many small factors — in this case, 672. And in fact $672 = (3)(4)(7)(8)$ , which we can rewrite as

$671 + 1 = (2+1)(3+1)(6+1)(7+1).$

We can think of the whole process, starting with $x_1, x_2, \ldots, x_n$ , as computing the product $(x_1+1) (x_2+1) \cdots (x_n+1)$ by combining two factors at a time; of course the order doesn’t matter.

Similarly with the function $f_2$ , if we start with $x_1, x_2, \ldots, x_n$ we end up with $\sqrt{x_1^2 + \cdots + x_n^2}$ . With $f_4$ , we get $\log \left( e^{x_1} + e^{x_2} + \cdots + e^{x_n} \right)$ . The result with $f_3$ is a little harder to see but if we start with $x_1, \ldots, x_n$ we eventually get $1/(x_1^{-1} + \cdots + x_n^{-1})$ . This is a bit easier to see if we realize that $f_3(a,b) = (1/a + 1/b)^{-1}$ ; therefore applying $f_3$ conserves the sum of the reciprocals.

What others are there? Of course there are trivial examples like $f(a,b) = a+b$ and $f(a,b) = ab$ ; iterating these functions will just give the sum or the product of the original numbers. But what other nontrivial examples are there? Can you say what all of them are?

Published by Michael Lugo

View all posts by Michael Lugo

Published March 20, 2012

10 thoughts on “A puzzle from James Tanton”

John Armstrong says:

March 20, 2012 at 7:24 pm

I don’t know if these are all the possibilities, but all your examples are conjugate to multiplication or addition. And of course multiplication is conjugate to addition too!

$ab = exp(ln(a)+ln(b))$

So the question (conjecture?) is: given an associative, binary function $f:\mathbb{R}^2\to\mathbb{R}$ , is it conjugate to addition? That is, is there an invertible $g:\mathbb{R}\to\mathbb{R}$ such that $f(a,b)=g^{-1}(g(a)+g(b))$ ?

Reply
1. Qiaochu Yuan says:
  
  March 21, 2012 at 1:17 pm
  
  This is false for silly reasons; for example, it suffices to exhibit a noncommutative group with the same cardinality as $\mathbb{R}$ and a bijection between them (the group of bijections $\mathbb{N} \to \mathbb{N}$ works). This also doesn’t capture all of the examples; $\frac{ab}{a+b}$ isn’t defined on all of $\mathbb{R}$ but only on, say, the positive reals.
  
  Reply
2. Qiaochu Yuan says:
  
  March 21, 2012 at 1:23 pm
  
  Whoops, that’s not quite right either. You want commutative associative binary functions. They’re clearly not all conjugate because some of them don’t have identities or inverses, but I suppose all of the given examples are conjugate to nice subsemigroups of the reals under addition.
  
  Reply
Brent says:

March 20, 2012 at 7:34 pm

Isn’t it sufficient just to have some $f$ which is commutative and associative?

Reply
Buddha Buck says:

March 20, 2012 at 7:43 pm

The last three have the form $g^{-1}(g(a)~g(b))$, where $g$ is an invertable function and $~$ is a commutative, associative operator. The ultimate value will be $g^{-1}(g(a)~…~g(n))$. I believe any invertable $g$ and commutative, associative operator $~$ would work as well.

In the first case, the same formulation works with $g(n) = n+1$ and $~$ being multiplication.

The “trivial” examples have $g(n)=n$.

Reply
Brent says:

March 20, 2012 at 7:46 pm

To expand on my previous comment a bit: it is clearly necessary for $f$ to be associative (since otherwise we could find $a, b, c$ such that we get a different answer depending on the order in which we choose to apply $f$ ) and commutative (since otherwise we would get different results for some $a,b$ vs $b,a$ ). That it is sufficient follows by noting that we are essentially building a binary tree with elements of the original list at the leaves and applications of $f$ at the internal nodes; if we consider two trees equivalent whenever they are related by a rotation (associativity) or reflection (commutativity) the equivalence classes are bags (i.e. sets with multiplicity), that is, any two trees with the same leaf elements are equivalent.

Reply
anstei says:

March 21, 2012 at 1:04 am

Well, whenever you have a bijective function g, you can construct such an f by defining [tex]f(a,b) = g^{-1}(g(a) + g(b))[/tex] or [tex]f(a,b) = g^{-1}(g(a)\cdot g(b))[/tex]. The choices [tex]g(x)=x+1[/tex], [tex]g(x)=x^2[/tex], [tex]g(x)=x^{-1}[/tex] and [tex]g(x)=\exp(x)[/tex] then give us the examples. (Of course, [tex]x^2[/tex] and [tex]\exp[/tex] are not bijective, but you actually only need that g has preimage on the sum or product of images.)

Reply
Z Le barabel (@zozoped) says:

March 21, 2012 at 2:55 am

I think you also need the binary operation to be commutative.

However, I am not sure the conjoncture of John Armstrong holds : take as an example the “exclusive or (^)”, as a binary operation over the set of all (positive) integers : it fulfills the commutativity and associativity, so achieves the result, but it is not conjugate to addition (or else, since f(a, a) = 0, we should have for all a, 2g(a) = 0.

Reply
Vishal Lama says:

March 23, 2012 at 5:50 pm

Perhaps the following was mentioned in your post implicitly but I would like to point out the role of “invariants” played in all of the problems you mentioned. For example, in the first problem, with a little bit of algebra, we see that we are essentially, looking at the “transformation” $(a,b) \mapsto (a+1)(b+1) - 1$ . Then, it is not hard to see that the “invariant” under the given operation is $(a_1 + 1)(a_2 + 1) \ldots (a_n + 1) - 1$ , with the result that the final answer after 19 iterations will be $(a_1 + 1)(a_2 + 1) \ldots (a_{20} + 1) - 1$ .

Similarly, the invariants become obvious in the other problems under the corresponding operations/transformations. I suppose you were thinking of an “invariant” when you wrote “ $f_3$ conserves the sum of the reciprocals”.

Reply
Blaise Pascal says:

March 26, 2012 at 10:06 am

I think it’s clear from looking at the span of comments that a pointer to how to embed TeX mathematics into comments would be appreciated. I see at least two different nonworking methods of doing so, including mine.

Obviously some people know how to post math, I’d like to, too.

Reply