A puzzle from James Tanton

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:

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?

Advertisements

10 thoughts on “A puzzle from James Tanton

  1. 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))?

    1. 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.

    2. 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.

  2. 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$.

  3. 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.

  4. 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.)

  5. 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.

  6. 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”.

  7. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s