4

My niece has shown me a problem for her advanced high school algebra class that I am personally finding fascinating, regarding the proof (or lack thereof) of the commutativity of a particular arbitrarily defined binary operator (basically, a randomly defined operator just for the sake of an interesting homework problem).

(This is not a homework-tag question; as a programmer I am personally interested in this.)

Here is the operator:

Define a # b (a and b are positive integers) such that # is a binary operator that reverses the (decimal) digits of positive integer a, adds the reversed number so obtained to positive integer b, then adds up the (decimal) digits of the result of this addition.

If the result has more than one (decimal) digit, add these digits together to obtain a new result, and repeat until only one digit remains.

(NOTE: I added the final sentence of the above definition after seeing @angryavian's answer, below - the final sentence was not in the original problem, but we noticed that commutativity applies when the final sentence is added to the definition of the operator.)

Putting in a number of various examples has always worked, so that it seems from examples that # is commutative. For example, a = 791, b = 907 results in:

a # b = 791 # 907 -> 197 + 907 = 1104 --> 6

b # a = 907 # 791 -> 709 + 791 = 1500 --> 6

... Other random examples also work, such as a = 1348, b = 26935.

As a programmer, I could write a simple program that creates an iterative loop (involving taking the modulus base 10 until no more digits remain) just to test any combination of numbers. But, proving the commutativity of this operator is another story.

It strikes me as unintuitive that such an arbitrary operator as this would turn out to be commutative, but every combination of numbers we've tried results in the same value when a and b are reversed.

I do not yet have a sense of how to go about actually proving this (assuming it's true).

How would one go about proving that this operator # is commutative? (Assuming that it is, indeed, commutative and that the numbers we've tested aren't just coincidentally commutative.)

Dan Nissenbaum
  • 141

2 Answers2

1

Define $r(n)$ to be the number obtained by reversing the decimal digits of $n$, and define $s(n)$ to be the result of summing the digits of $n$ (then summing the digits of the result if necessary, etc.) until a single digit remains. Then $a\mathop{\#}b = s(r(a)+b)$.

The key fact is that $s(n) = k$ where $1\le k\le 9$ is the unique digit such that $n\equiv k\pmod 9$. This is a standard number theory fact and any number theory textbook will have a proof.

It follows quickly that $s(c+d) \equiv c+d \equiv s(c)+s(d)\pmod 9$, and it is of course obvious that $s(r(n)) = s(n)$. Therefore $$ a\mathop{\#}b = s(r(a)+b) \equiv s(r(a)) + s(b) \equiv s(a) + s(r(b)) \equiv s(r(b)+a) = b\mathop{\#}a \pmod 9, $$ and so $a\mathop{\#}b= b\mathop{\#}a$ since both are single digits.

Greg Martin
  • 78,820
1

[Edit: this answer is for an older version of the question.]

It is not necessarily commutative if the two numbers have different numbers of digits. For example, $91 \# 1=2$ but $1 \# 91=11$. [For another counterexample without one-digit numbers, $103 \# 19 = 5$ but $19 \# 103=14$.]

If the two numbers have the same number of digits (say $a=a_na_{n-1} \cdots a_0$ and $b=b_n b_{n-1} \cdots b_0$), then the first stage of the computation of $a\#b$ will give $$(a_0+b_n)10^n+(a_1+b_{n-1} )10^{n-1}+\cdots + (a_n+b_0)10^0,\tag{1}$$ while the respective sum for $b \# a$ is $$(a_n+b_0)10^n+(a_{n-1}+b_{1} )10^{n-1}+\cdots + (a_0+b_n)10^0\tag{2}.$$

We just need to show that these two numbers (when written in decimal form) will have digits summing to the same number. This is true [even if terms like $a_1+b_{n-1}$ are greater than $9$ and you need to carry!] because you end up summing all the digits. Specifically, I mean that the sum of the digits of the decimal number in (1) is the same as the sums of the digits of all the decimal numbers $a_0+b_n, a_1+b_{n-1},\ldots, a_n+b_0$, and the same for (2).

angryavian
  • 89,882
  • Interesting! Thanks. ...Note that (looking at your answer) continuing to add the digits until a single digit remains may end up being commutative ... in both examples in the first paragraph of your answer, it works (2, 11 -> 2, 2) and (5, 14 -> 5, 5). This wasn't in the original question but it occurs to me now, looking at your answer! – Dan Nissenbaum Sep 22 '14 at 02:09
  • In fact, in my question I did assume that the numbers continue to be added in the final step (this is necessary for my (1348, 26935) example to work). I will modify the question to indicate this. – Dan Nissenbaum Sep 22 '14 at 02:13
  • @DanNissenbaum I think that if you continue adding until only one digit remains, then the only thing that matters is what digits appear in $a$ and $b$. That is, you can arbitrarily permute the digits however you like before adding them together and then continue adding up the digits. For instance, $197+43=240\to 6$ and $917+34 =951\to 15 \to 6$. You can even append zeros if you like: $100907+40300=141207\to 15 \to 6$. – angryavian Sep 22 '14 at 02:16
  • @DanNissenbaum To show this is true, you just need to show that $a # b$ is the same as taking the sum of the digits of $a$ and the digits of $b$ and continuing to sum until one digit remains. [Or in other words, the summing of "reversed" $a$ and $b$ as decimal numbers is irrelevant.] – angryavian Sep 22 '14 at 02:18
  • Actually - I am having a hard time working through the final steps... but I suspect you're right! (As soon as I do work through the final steps I'll mark this as the accepted answer!) – Dan Nissenbaum Sep 22 '14 at 02:21