9
$\begingroup$

While doing a few math puzzles I noted that you could take any three numbers (integers) and use basic arithmetic operations (Addition, Subtraction, Multiplication and Parentheses only) to obtain a multiple of 10, using each number only once.

Eg.
Using 29, 73, 36: $73+36-29=80$
Using 2, 4, 7: $2*7-4=10$

Is there a proof for this theory in particular, or is there a more general theorem that applies to this? If not, is there a set of three numbers which disproves this theory?


I found a few clues while solving this:

If one of the numbers is a multiple of 5 (call it $x$) then there definitely exists a solution divisible by 10. This one is easily provable as you merely need an even number to multiply with. If any one of the remaining two numbers is even, you can use that to multiply with $x$ to get number divisible by 10. If both numbers are odd then you can add them to get an even number to multiply with $x$.

It would seem as only the units place digits have any bearing on whether it's a multiple of 10 or not. As you could take any of the examples, add or subtract any multiple of 10 from it and do the same operations to still get a multiple of ten. I feel this is also easily provable but I can't think of a way to do it which isn't long-winded.
EDIT: It can be proven as such, let $a,b$ be two integers s.t $a+b|10$
Adding two multiples of 10 ($10m,10n$) to $a$ and $b$ we get $10m+a+10n+b$
Since $a+b|10$ it can be written as $10m+10n+10k$ where $a+b=10k$
Which is divisible by ten
Now let $a,b$ be two integers s.t. $a.b|10$
Adding $10m,10n$ to $a$ and $b$ we get $(10m+a)(10n+b)$
$=100mn+10an+10bm+ab$ or $100mn+10an+10bm+10k$
Which is divisible by ten
Therefore any combination of Addition and Multiplication with the three no.s shouldn't matter.
I realise that could replace 10 with any no. in this proof and it would still work. So we really need to just prove for every single digit no.


I ran a program in python that checked for every combination of single digit no.s, but it didn't find any combination that disproves this.

I'm not sure how this question would be categorised, hence the lack lustre tags.

I'm fairly new to StackExchange. Please forgive me if I've worded this question poorly.

$\endgroup$
  • 1
    $\begingroup$ That's a very nice observation that only the units digit has any bearing, and is essentially the underlying idea of "modular arithmetic." This is an interesting problem, and I'll be fairly surprised if it's true. However, there are $3$ ways to order $a, b, c$, a couple choices of symbols between $a,b$ and $b,c$ and with the ability to use parentheses... very interesting! If we have the three numbers $a, b, c$, are we allowed to order them any way we like? $\endgroup$ – pjs36 Nov 5 '17 at 6:47
  • $\begingroup$ How do you get a multiple of $10$ this way using $1$, $2$, and $4$? $\endgroup$ – alex.jordan Nov 5 '17 at 7:58
  • $\begingroup$ @alex.jordan $2\cdot (4+1)$ $\endgroup$ – Kyle Miller Nov 5 '17 at 7:59
  • $\begingroup$ Oh, I see. I somehow thought only addition and subtraction were in play. Didn't read well. $\endgroup$ – alex.jordan Nov 5 '17 at 8:00
  • 1
    $\begingroup$ @pjs36 From the two examples in the OP, it seems clear that reordering is permitted. $\endgroup$ – Erick Wong Nov 5 '17 at 8:07
10
+200
$\begingroup$

Let's collect some of the useful observations mentioned and implicit in the OP:

  1. Only the residue class of $a,b,c$ mod $10$ matters.
  2. If any of $a,b,c$ is divisible by $5$ then there is a solution.
  3. If any subset of $\{a,b,c\}$ has a solution, then so does $\{a,b,c\}$.

As a consequence of the above, we may assume WLOG that $\{a,b,c\}$ are distinct single digits from $1,2,3,4,6,7,8,9$.

With a little more effort, we can justify that $a$ can be replaced by $-a$, which will let us further restrict to the digits $1,2,3,4$. It's not too hard to be convinced of this by playing around with some examples, but let's give a proper proof by structural induction. More specifically, we will prove:

Proposition: Let $f(x_1,\ldots,x_n)$ be a fully parenthesized expression using each $x_i$ exactly once and only $+,-,*$ operators. Then at least one of $-f$ or $f$ can be written as a similar expression using $-x_1,x_2,\ldots,x_n$ exactly once.

This is trivial for $n=1$, and for $n=2$ we quickly verify each of the four possible expressions of two variables: $$-(a+b) = (-a)-b,\\-(a-b) = (-a)+b,\\(b-a) = b+(-a),\\-(a*b) = (-a)*b.$$

We can now do a structural induction: suppose $n\ge 3$. By extracting the highest-level operator of $f(x_1,\ldots, x_n)$, we may write $f$ as $h(g_1(\cdots),g_2(\cdots))$, where each of $g_1,g_2,h$ are valid expressions, and the arguments of $g_1, g_2$ partition the set $\{x_1,\ldots,x_n\}$. I've deliberately obscured the arguments because the notation becomes unwieldy, as the idea is better illustrated by a simple example:

If $f(x_1,x_2,x_3,x_4,x_5) = ((x_1 * x_5) + x_2) - (x_3 - x_4)$, then we take $$h(a,b) = a-b,\quad g_1 = (x_1 * x_5) + x_2,\quad g_2 = x_3 - x_4.$$

Note that $h,g_1,g_2$ each take $<n$ arguments so we could apply the inductive hypothesis to any of them as desired. Now, $x_1$ belongs to exactly one of $g_1$ or $g_2$. By adjusting $h$, we can assume WLOG that it belongs to $g_1$. By hypothesis, either $-g_1$ or $g_1$ can be written in terms of $-x_1$ and the remaining arguments of $g_1$. If it is $g_1$ that may be so written, then we are done since $f=h(g_1,g_2)$ can be written in terms of $-x_1,x_2,\ldots,x_n$. Else, apply the induction hypothesis again to $h$ to see that either $f=h(g_1,g_2)$ or $-f=-h(g_1,g_2)$ can be written in terms of $-g_1$ and $g_2$, and thus also in terms of $-x_1,x_2,\ldots,x_n$.

The above proposition lets us freely replace $9$ by $-9$ (which is equivalent to $1$), etc., and so we can narrow down the set $\{a,b,c\}$ to a subset of $\{1,2,3,4\}$. Lucky for us, there's only four such subsets:

$$ (1 + 2 - 3) = 0,\\ (1 + 4)*2 = 10,\\ (1 + 3 -4) = 0,\\ (2+3)*4 = 20.$$

$\endgroup$
  • 2
    $\begingroup$ I was going to write the same thing. I believe this one deserves the bounty. $\endgroup$ – user334639 Nov 5 '17 at 9:00
  • 1
    $\begingroup$ Very nicely done, I probably will award the bounty to this answer (I want to keep the bounty alive to reward the nice question; OP had but a single upvote when I set the bounty). Structural induction isn't something I'm familiar with, so I will admit that it's my least favorite part. I notice that in each of the four ultimate cases, addition is used -- I wonder if we could somehow combine that with factoring out a negative, and avoid structural induction. Probably not. At any rate, very nice! $\endgroup$ – pjs36 Nov 6 '17 at 2:36
  • $\begingroup$ Ah I see you've used $-4,-3,-2,-1,1,2,3,4$ instead of $1,2,3,4,6,7,8,9$ and then used my modulo(10) proof.First time I'm coming across structural induction so the proof is a bit hard to chew. Nevertheless, it's a clever proof. $\endgroup$ – Carlton Banks Nov 6 '17 at 10:02
  • $\begingroup$ @CarltonBanks Thanks, to be fair this is really just an induction on the number of terms (it’s structural in the sense that arithmetic expressions aren’t built up by just “adding one more term”). It is also overkill when we’re dealing with only 3 terms, but you did express an interest in more general principles in the OP. Finally, the induction is only needed for a relatively minor technical point: it justifies that if we can find a $0$ using unary $-$ (which doesn’t appear to be allowed), then we can also find one without any unary $-$. $\endgroup$ – Erick Wong Nov 6 '17 at 18:24
3
$\begingroup$

If you have directly verified this for all triples of one-digit numbers, then you have proved it. Because you only care about an arithmetic combination that makes $0$ mod $10$, so proving it for one-digit numbers proves the greater claim.

Without a direct verification, consider all $10^3$ triples of one-digit numbers. If $0$ is in the triple, then multiplying all three is a multiple of $10$.

So now consider all $9^3$ triples from 1--9. If $5$ is in the triple, then either both of the other numbers are odd and you can multiply $5(\text{odd}+\text{odd})$ to get a multiple of $10$; or at least one of the others is even and you can multiply all three to get a multiple of $10$.

So now consider all $8^3$ triples from 1--4,6--9. If any number appear twice in the triple, the difference is $0$, and that difference times the third number is a multiple of $10$.

So now consider all $\binom{8}{3}$ triples from 1--4,6--9 without repetition. If a number and its complement mod $10$ are both in the triple, then sum those and multiply by the third to get a multiple of $10$.

So now consider all $\binom{4}{3}\cdot2^3$ triples from 1--4,6--9 without repetition where no two numbers sum to $10$. We are down to only $32$ triples to consider, and inspecting them directly is not so bad. First, consider the $16$ triples with two or three members from 1--4.

$$\underline{12}3\ \color{magenta}{\underline{1}2\underline{4}}\ \color{orange}{\underline{1}2\underline{6}}\ \color{blue}{127}\ \underline{13}4\ \color{blue}{136}\ 1\underline{38}\ 1\underline{47}\ \color{magenta}{\underline{14}8}\ \color{magenta}{\underline{23}4}\ \color{magenta}{\underline{23}6}\ 2\underline{39}\ \color{orange}{\underline{2}4\underline{7}}\ \color{orange}{2\underline{49}}\ \color{orange}{\underline{3}4\underline{8}}\ 3\underline{49}$$

Blue sum to $0$ mod $10$.

Magenta have an (underlined) pair that sum to $5$ (or $15$) and the third number is even, so that sum times the third number is a multiple of $10$.

Orange have an (underlined) pair whose difference is $5$ and the third number is even, so that difference times the third number is a multiple of $10$.

The remaining black all have an (underlined) pair that sums to the third (mod $10$) so adding that pair and then subtracting the third makes a multiple of $10$.

Note that if we negate all members of one of these triples, we get the triples with two or more in 6--9. The same operations give a multiple of $10$ since we only ever either add and subtract [with the blue and black], or add/subtract and then multiply by an even number [with magenta and orange]. So we've indirectly checked all $32$ of the lingering cases.

$\endgroup$
  • $\begingroup$ I was hoping to avoid "too many" cases, but this is a pretty modest number of them. And inspecting the final 32 wasn't so bad, at least when they were color-coded :) Would that I could split a bounty, I like all of the answers... $\endgroup$ – pjs36 Nov 6 '17 at 2:40
  • $\begingroup$ @pjs36 Just FYI, your comment somewhere else got me thinking about how the cases could be cut down to just $16$. $\endgroup$ – alex.jordan Nov 6 '17 at 3:04
2
$\begingroup$

Note: This answer has the focus to reduce the number of variants which are to study by consequently using modular arithmetic.

  • $a,b,c\in\mathbb{Z}$

We are looking for multiples of $10$ when doing addition, subtraction and multiplication. Since we have \begin{align*} (a\, \mathrm{mod}\, (10)) + (b\, \mathrm{mod}\, (10)) &\equiv (a+b)\, \mathrm{mod}\, (10) \\ (a\, \mathrm{mod}\, (10)) - (b\, \mathrm{mod}\, (10)) &\equiv (a-b)\, \mathrm{mod}\, (10) \\ (a\, \mathrm{mod}\, (10)) \cdot (b\, \mathrm{mod}\, (10)) &\equiv (a\cdot b)\, \mathrm{mod}\, (10) \\ \end{align*}

it is sufficient to consider $\color{blue}{a,b,c\in\{0,1,2,3,4,5,6,7,8,9\}}$.

  • $a,b,c\in\{0,1,2,3,4,5,6,7,8,9\}$

If two of the three numbers are congruent modulo $10$, let's say $a\equiv b\, \mathrm{mod}\, (10)$ we obtain \begin{align*} \color{blue}{(a-b)\cdot c}\equiv 0\cdot c\color{blue}{\equiv 0\, \mathrm{mod}\, (10)} \end{align*}

and we are done. In the following we may WLOG assume: $a<b<c$

  • $a,b,c\in\{0,1,2,3,4,5,6,7,8,9\},a<b<c$

If one of them, let's say $a$ is zero we obtain \begin{align*} \color{blue}{a\cdot b\cdot c}&\equiv 0\cdot b\cdot c \color{blue}{\equiv 0\, \mathrm{mod}\, (10)} \end{align*}

and we are done.

  • $a,b,c\in\{1,2,3,4,5,6,7,8,9\}, a<b<c$

If one of them, let's say $a$ is equal to $5$ we consider two cases.

First case: One of $b$ or $c$ is even. Let's assume $b$ is even. It follows \begin{align*} a&\equiv 0\, \mathrm{mod}\, (5)\\ b&\equiv 0\, \mathrm{mod}\, (2)\\ ab&\equiv 0\, \mathrm{mod}\, (10)\\ \end{align*} and we obtain \begin{align*} \color{blue}{a\cdot b\cdot c}&\equiv 0\cdot c \color{blue}{\equiv 0\, \mathrm{mod}\, (10)} \end{align*}

Second case: Both, $b$ and $c$ are odd. It follows from

\begin{align*} b\equiv 1\, \mathrm{mod}\, (2)\\ c\equiv 1\, \mathrm{mod}\, (2)\\ (b+c)\equiv 0\, \mathrm{mod}\, (2)\\ \end{align*}

and we obtain \begin{align*} \color{blue}{a\cdot (b+c)} \color{blue}{\equiv 0\, \mathrm{mod}\, (10)} \end{align*}

  • $a,b,c\in\{1,2,3,4,6,7,8,9\}, a<b<c$

Since

\begin{align*} 1\equiv (1-10)\equiv (-9)\, \mathrm{mod}\, (10)\\ 2\equiv (2-10)\equiv (-8)\, \mathrm{mod}\, (10)\\ 3\equiv (3-10)\equiv (-7)\, \mathrm{mod}\, (10)\\ 4\equiv (4-10)\equiv (-6)\, \mathrm{mod}\, (10)\\ \end{align*}

we can restrict the attention to $\color{blue}{a,b,c\in\{1,2,3,4\},a<b<c}$.

  • $a,b,c\in\{1,2,3,4\}, a<b<c$

This case is already nicely considered in the answer from @ErickWong.

Conclusion: Doing arithmetic with three integers $a,b,c\in\mathbb{Z}$, each of them occurring once and using one or more of the operations addition, subtraction, multiplication and negation ($a \rightarrow -a$) we can always obtain an integer value which is a multiple of $10$.

$\endgroup$
  • 1
    $\begingroup$ This is a nice, thorough answer. Allowing negation is an interesting point. While not explicitly mentioned, I feel like there should be some algebraic trickery that lets us convert negation to addition, subtraction, and multiplication with our same three numbers; e.g., $(-b + a) \cdot c = -(b - a)\cdot c$. Maybe, but maybe it would just serve to introduce more cases, even though it's intuitively clear that negation doesn't really add anything new. $\endgroup$ – pjs36 Nov 6 '17 at 2:48
  • $\begingroup$ @pjs36: Thanks. :-) Allowing negation is a modest way of cheating somewhat. In fact negation $-a=0-a$ is equivalent to add 0 to $\{+,-,\cdot,(,)\}$. To me it is not so clear that it doesn't introduce anything new. Keep in mind that $-(a-b)$ for instance also uses negation. $\endgroup$ – Markus Scheuer Nov 6 '17 at 7:16
  • 1
    $\begingroup$ @pjs36 I agree, this is where I spend most of the effort in my answer and I would love to see a simpler way to prove that negation can always be eliminated :). $\endgroup$ – Erick Wong Nov 6 '17 at 18:27
  • $\begingroup$ @MarkusScheuer It’s fine that $-(a-b)$ uses negation: the point of my argument is that all interior negations can be bubbles up to the exterior. Once we have that, then $a-b$ works just as well as $-(a-b)$ for producing zeroes, so we eliminate negation altogether. $\endgroup$ – Erick Wong Nov 6 '17 at 18:30
  • 1
    $\begingroup$ @ErickWong: Ahh, now I see your point! Good argument. Your're right, of course. :-) (+1) $\endgroup$ – Markus Scheuer Nov 7 '17 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.