Sums and Products, a Generalization

Elsewhere we played with and analyzed an arithmetic puzzle. Given a sequence of numbers, pick any two, say \(A\) and \(B\), randomly and replace the two with the result of \(A\times B + A + B\). Repeat the procedure until only one number remains. Try to predict the final result.

Curiously and unexpectedly (for those who have not thought of the puzzle before) the final number does not depend on the order in which pairs of numbers are selected at each of the steps

Assume at a certain stage of the process we have a sequence \(S\) of integers, \(S = \{A_{1}, A_{2}, \ldots , A_{n}\}\). Let \(P\) stand for the product of all integers present, each increased by \(1\) less \(1\): \(P = (A_{1}+1)(A_{2}+1)\ldots (A_{n}+1) - 1\). When two numbers \(A\) and \(B\) are replaced with \(A\times B + A + B\) the product \(P\) does not change. Indeed, it loses two factors \((A+1)(B+1)\) but gains another one \(A\times B + A + B + 1\). The two are of course equal. It then follows that \(P\) is an invariant quantity that does not change in the course of the game. It could be computed at the very beginning.

James Tanton explained a beautiful and edifying generalization.

Let "\(\circ\)" stand for a binary operation on integers. We are interested in operations that possess two properties, commutativity and associativity.

Commutativity

\(a\circ b = b\circ a\).

Associativity

\((a\circ b)\circ c = a\circ (b\circ c)\).

Common addition and multiplication both have the two properties. But so are many other (and sometimes exotic) operations. For example, let \(a\circ b=\sqrt{a^{2}+b^{2}}\). This is indeed an operation that, for any two numbers, produces a third one. The operation is obviously commutative. Let's check its associativity.

\(\begin{align} (a\circ b)\circ c &= \sqrt{(\sqrt{a^{2}+b^{2}})^{2}+c^{2}} \\ &= \sqrt{a^{2}+b^{2}+c^{2}} \\ &= \sqrt{a^{2}+(\sqrt{b^{2}+c^{2}})^{2}} \\ &= a\circ (b\circ c). \end{align} \)

Consider \(a\circ b = \frac{ab}{a+b}\). This operation is commutative. Let's check associativity:

\( \begin{align} (a\circ b)\circ c &= \frac{ab/(a+b)\cdot c}{ab/(a+b)+ c} \\ &= \frac{abc}{ab+(a+b)c} \\ &= \frac{abc}{ab+bc+ca} \\ &= \frac{abc}{a(b+c)+bc} \\ &= \frac{a\cdot bc/(b+c)}{a + bc/(b+c)} \\ &= a\circ (b\circ c). \end{align} \)

You may want to check whether the operations \(\mbox{log}(10^{a}+10^{b})\), \(\mbox{gcd}(a, b)\), or the beastly \((a+666)(b+666)-666\) have the properties of commutativity and associativity.

To make the importance of the two properties and to show the relevance of the foregone discussion to the puzzle we started with, observe that the operation \(a\circ b=(a+1)(b+1)-1\) is both commutative and associative and defines the puzzle because

\(a\circ b=(a+1)(b+1)-1=a+b+ab\).

What remains is to show that making a substitution of two numbers \(A\) and \(B\) from a given sequence of numbers with the result of \(A\circ B\), for any operation "\(\circ\)" that is both associative and commutative, leads to a unique number that could be determined in advance. Indeed, for a sequence \(A, B, \ldots ,Z\), the result, i.e. the number that remains when the sequence shrinks to a single term, is always the same:

\(A\circ B\circ \ldots \circ Z\)

and does not depend on the specific choices of two numbers at any of the steps. The two properties of associativity and commutativity insure that this is so.


Related material
Read more...

  • 3-Term Arithmetic Progression
  • Aliquot game (An Interactive Gizmo)
  • Euclid's Game (An Interactive Gizmo)
  • Euclid's Game on a Square Grid
  • Sums and Products
  • Sums, Products, and 1-1 Functions
  • Zeros and Nines
  • A Candy Game: Integer Iterations
  • A Candy Game (Change Discharged)
  • Heads and Tails
  • Loop or Halt - An Interactive Gizmo
  • Breaking Chocolate Bars (An Interactive Gizmo)
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    71470998