Henry Ernest Dudeney/Modern Puzzles/66 - Another 37 Division/Solution

== by : $66$ ==
;Another $37$ Division
== Solution ==
The chances are $1$ in $40$ that the number will be divisible by $37$.
== Proof ==
Suppose $n = \sqbrk {abcdefghi}$ is a haphazard arrangement of the $9$ digits divisible by $37$.
Since the sum of digits of $n$ is $45$, which is divisible by $9$:
:$9 \divides n$ by Divisibility by $9$.
By Divisibility by $37$:
:$37 \divides n \iff 37 \divides \paren {\sqbrk {abc} + \sqbrk {def} + \sqbrk {ghi} }$
Thus $\sqbrk {abc} + \sqbrk {def} + \sqbrk {ghi}$ would be divisible by $9$ and $37$, and hence divisible by their product, $333$.
Note that:
Thus $\sqbrk {abc} + \sqbrk {def} + \sqbrk {ghi}$ is one of:
:$999, 1332, 1665, 1998, 2331$
In any case of $\sqbrk {abc} + \sqbrk {def} + \sqbrk {ghi} = \sqbrk {wxyz}$, we have:
For each of the cases above, we determine the possible values of $c_1, c_2$ and find the sets of digits $\set {a, d, g}, \set {b, e, h}, \set {c, f, i}$ that satisfies the relations above.
Also the sum of any three distinct digits cannot exceed $7 + 8 + 9 = 24$ or be less than $1 + 2 + 3 = 6$.
=== Case $1$: $999$ ===
In this case, we have:
:$45 = 9 \paren {c_1 + c_2} + 0 + 9 + 9 + 9$
which leads to:
:$c_1 + c_2 = 2$.
Neither $c_1$ nor $c_2$ could be equal to $2$ since the sum of three distinct digits cannot reach $27$.
Hence:
:$c_1 = c_2 = 1$
:$a + d + g = 8$
:$b + e + h = 18$
:$c + f + i = 19$
For $\set {a, d, g} = \set {1, 2, 5}$, the possibilities for $\set {b, e, h}$ are:
:$\set {3, 6, 9}$
:$\set {3, 7, 8}$
:$\set {4, 6, 8}$
For $\set {a, d, g} = \set {1, 3, 4}$, the possibilities for $\set {b, e, h}$ are:
:$\set {2, 7, 9}$
:$\set {5, 6, 7}$
so there are $5$ total possibilities.
=== Case $2$: $1332$ ===
In this case, we have:
:$45 = 9 \paren {c_1 + c_2} + 10 + 3 + 3 + 2$
which leads to:
:$c_1 + c_2 = 3$.
Neither $c_1$ nor $c_2$ could be equal to $3$ since the sum of three distinct digits cannot exceed $30$.
Hence:
:$\set {c_1, c_2} = \set {1, 2}$
so either:
:$a + d + g = 12$
:$b + e + h = 22$
:$c + f + i = 11$
or:
:$a + d + g = 22$
:$b + e + h = 11$
:$c + f + i = 12$
the difference between these two cases is simply an exchange of place values, so we only need to consider the second case.
For $\set {a, d, g} = \set {5, 8, 9}$, the possibilities for $\set {b, e, h}$ are:
:$\set {1, 3, 7}$
:$\set {1, 4, 6}$
:$\set {2, 3, 6}$
For $\set {a, d, g} = \set {6, 7, 9}$, the possibilities for $\set {b, e, h}$ are:
:$\set {1, 2, 8}$
:$\set {2, 4, 5}$
so there are $5 \times 2 = 10$ total possibilities.
=== Case $3$: $1665$ ===
In this case, we have:
:$45 = 9 \paren {c_1 + c_2} + 10 + 6 + 6 + 5$
which leads to:
:$c_1 + c_2 = 2$.
Since $5$ and $25$ cannot be a sum of distinct digits, we must have $c_1 = 1$.
Thus $c_2 = 1$ as well.
Hence:
:$a + d + g = b + e + h = c + f + i = 15$
The possible sets of three distinct digits that sums to $15$ are:
:$\set {1, 5, 9}$
:$\set {1, 6, 8}$
:$\set {2, 4, 9}$
:$\set {2, 5, 8}$
:$\set {2, 6, 7}$
:$\set {3, 4, 8}$
:$\set {3, 5, 7}$
:$\set {4, 5, 6}$
There is only two groups of digits that satisfies $a + d + g = b + e + h = c + f + i = 15$:
:$\set {\set {a, d, g}, \set {b, e, h}, \set {c, f, i} } = \set {\set {1, 5, 9}, \set {2, 6, 7}, \set {3, 4, 8} }$
:$\set {\set {a, d, g}, \set {b, e, h}, \set {c, f, i} } = \set {\set {1, 6, 8}, \set {2, 4, 9}, \set {3, 5, 7} }$
The three sets of digits can freely swap between themselves.
So there are $2 \times 3! = 12$ total possibilities.
=== Case $4$: $1998$ ===
In this case, we have:
:$45 = 9 \paren {c_1 + c_2} + 10 + 9 + 9 + 8$
which leads to:
:$c_1 + c_2 = 1$.
Hence:
:$\set {c_1, c_2} = \set {0, 1}$
so either:
:$a + d + g = 18$
:$b + e + h = 8$
:$c + f + i = 19$
or:
:$a + d + g = 8$
:$b + e + h = 19$
:$c + f + i = 18$
By our analysis in Case $1$, there are $5 \times 2 = 10$ total possibilities.
=== Case $5$: $2331$ ===
In this case, we have:
:$45 = 9 \paren {c_1 + c_2} + 20 + 3 + 3 + 1$
which leads to:
:$c_1 + c_2 = 2$.
Neither $c_1$ nor $c_2$ could be equal to $0$ since the sum of three distinct digits cannot be less than $4$.
Hence:
:$c_1 = c_2 = 1$
:$a + d + g = 11$
:$b + e + h = 12$
:$c + f + i = 22$
By our analysis in Case $1$, there are $5$ total possibilities.
We see that in all the above cases, there are $42$ total possibilities.
All the digits within those sets can be freely exchanged.
Therefore the number of possibities of $n$ is:
:$42 \times 3! \times 3! \times 3! = 9072$
And thus the probability that a haphazard arrangement of the $9$ digits would be divisible by $37$ is:
:$\dfrac {9072} {9!} = \dfrac 1 {40}$
== Sources ==
* : Solutions: $66$. -- Another $37$ Division
* : Answers: Digital Puzzles: $117$. Another $37$ Division
Category:Henry Ernest Dudeney/Modern Puzzles/Solutions