Henry Ernest Dudeney/Puzzles and Curious Problems/112 - Simple Division/Solution

== by : $112$ ==
;Simple Division
== Solution ==
The solution given by is as follows:
=== Solution $1$ ===
There are further solutions:
=== Solution $2$ ===
=== Solution $3$ ===
=== Solution $4$ ===
There may be more.
=== Solution $5$ ===
== Proof ==
This section declares the variables which are to be used during the deduction of the solution to this skeleton puzzle.
Let $D$ denote the divisor.
Let $Q$ denote the quotient.
Let $N$ denote the dividend.
Let $q_1$ to $q_5$ denote the digits of $Q$ which are calculated at each stage of the long division process in turn.
Let $n_1$ to $n_5$ denote the partial dividends which are subject to the $1$st to $5$th division operations respectively.
Let $j_1$ to $j_5$ denote the least significant digits of $n_1$ to $n_5$ as they are brought down from $N$ at each stage of the long division process in turn.
Let $p_1$ to $p_5$ denote the partial products generated by the $1$st to $5$th division operations respectively: $p_k = q_k D$
Let $d_1$ to $d_5$ denote the differences between the partial dividends and partial products: $d_k = n_k - p_k$.
By the mechanics of a long division, we have throughout that:
:$n_k = 10 d_{k - 1} + j_k$
for $k \ge 2$.
Hence we can refer to elements of the structure of this long division as follows:
 **7** --> Q
 ----------- ---
 ****7*)**7******* --> D ) N
 ****** --> p_1
 -------
 *****7* --> n_2
 ******* --> p_2
 -------
 *7**** --> n_3
 *7**** --> p_3
 ------
 ******* --> n_4
 ***7** --> p_4
 -------
 ****** --> n_5
 ****** --> p_5
 ------
First we attempt to bound the divisor $D$.
Note that $n_4$, $p_4$ and $d_4$ are $7$, $6$ and $5$-digit numbers respectively.
Thus the first digit of $p_4$ must be $9$.
Since each of $n_3$, $p_3$ and $d_3$ are $6$-digit numbers, the first digit of $p_3$ cannot be $9$.
Also note that $p_2$ has $7$ digits.
These give:
:$p_2 > p_4 > p_3 = 7 D$
Hence we must have $q_2 = 9$ and $q_4 = 8$.
Therefore:
:$D \le \dfrac {999 \, 799} 8 = 124 \, 974 \tfrac 7 8$
Now we determine the first digit of $p_3$.
If it does not exceed $7$:
:$p_4 = 8 D \le 8 \times \dfrac {780 \, 000} 7 \approx 891 \, 429$
which contradicts the fact that the first digit of $p_4$ must be $9$.
Since the first digit of $p_3$ cannot be $9$, it must be $8$.
This gives:
:$D \ge \dfrac {870 \, 000} 7 = 124 \, 285 \tfrac 5 7$
Since the second to last digit of $D$ is $7$:
:$D \ge 124 \, 370$
:$p_3 = 8 D \ge 8 \times 124 \, 370 = 994 \, 960$
Since the third to last digit of $p_3$ is $7$:
:$p_3 \ge 995 \, 700$
:$D \ge \dfrac {995 \, 700} 8 = 124 \, 462.5$
Since the second to last digit of $D$ is $7$:
:$D \ge 124 \, 470$
:$p_3 \ge 8 \times 124 \, 470 = 995 \, 760$
As $124 \, 475 \times 8 = 995 \, 800$, we will need to check:
:$D = 124 \, 470, 124 \, 471, 124 \, 472, 124 \, 473, 124 \, 474$
All the possible values of $N$ that can be generated by the values of $D$ above are of the form:
:$N = D Q = 124 \, 47x \times y9 \, 78z$
where:
:$0 \le x \le 4$
:$1 \le y \le 7$
:$1 \le z \le 8$
First we check that:
Now notice that:
and we see that none of the products above is within a $1 \, 500 \, 000$ range of a number with $7$ as its third digit.
Thus these values of $D$ are eliminated.
Now we consider $D \ge 124 \, 475$.
Since the third to last digit of $p_3$ is $7$:
:$p_3 \ge 996 \, 700$
:$D \ge \dfrac {996 \, 700} 8 = 124 \, 587.5$
Since the second to last digit of $D$ is $7$:
:$D \ge 124 \, 670$
:$p_3 \ge 8 \times 124 \, 670 = 997 \, 360$
Since the third to last digit of $p_3$ is $7$:
:$p_3 \ge 997 \, 700$
:$D \ge \dfrac {997 \, 700} 8 = 124 \, 712.5$
Since the second to last digit of $D$ is $7$:
:$D \ge 124 \, 770$
:$p_3 \ge 8 \times 124 \, 770 = 998 \, 160$
Since the third to last digit of $p_3$ is $7$:
:$p_3 \ge 998 \, 700$
:$D \ge \dfrac {998 \, 700} 8 = 124 \, 837.5$
Since the second to last digit of $D$ is $7$:
:$D \ge 124 \, 870$
:$p_3 \ge 8 \times 124 \, 870 = 998 \, 960$
Since the third to last digit of $p_3$ is $7$:
:$p_3 \ge 999 \, 700$
:$D \ge \dfrac {999 \, 700} 8 = 124 \, 962.5$
Since the second to last digit of $D$ is $7$:
:$D \ge 124 \, 970$
Thus we just need to check the these remaining values:
:$D = 124 \, 970, 124 \, 971, 124 \, 972, 124 \, 973, 124 \, 974$
These values give:
:$1 \, 124 \, 730 \le p_2 \le 1 \, 124 \, 766$
:$874 \, 790 \le p_3 \le 874 \, 818$
:$999 \, 760 \le p_4 \le 999 \, 792$
With this information, we can fill in parts of the puzzle:
 *978*
 -----------
 12497*)**7*******
 ******
 -------
 *****7*
 11247**
 -------
 *7****
 874***
 -------
 1******
 9997**
 --------
 ******
 ******
 ------
Note that all values that $p_2$ can take contains a digit $7$.
Thus this puzzle cannot be completed unless more $7$'s are used than those given at the start.
Since $n_3 < 980 \, 000$, we have:
:$D \times \sqbrk {78q_5} < 98 \, 000 \, 000$
which gives:
:$\sqbrk {78q_5} < \dfrac {98 \, 000 \, 000} {124 \, 974} \approx 784.2$
This shows that $q_5 \le 4$.
Using the $7$ given in $n_2$, we need to find the pairs of $D$ and $q_5$ such that the sixth digit of the product $D \times \sqbrk {978q_5}$ is $7$.
Going through all $20$ possibities:
:$\begin{array}{r|rrrr}
\times & 9781 & 9782 & 9783 & 9784 \\ \hline
124 \, 970 & 1 \, 222 \, 331 \, 570 & 1 \, 222 \, 456 \, 540 & 1 \, 222 \, 581 \, 510 & 1 \, 222 \, 706 \, 480 \\
124 \, 971 & 1 \, 222 \, 341 \, 351 & 1 \, 222 \, 466 \, 322 & 1 \, 222 \, 591 \, 293 & 1 \, 222 \, 716 \, 264 \\
124 \, 972 & 1 \, 222 \, 351 \, 132 & 1 \, 222 \, 4 \color{red} 76 \, 104 & 1 \, 222 \, 601 \, 076 & 1 \, 222 \, 726 \, 048 \\
124 \, 973 & 1 \, 222 \, 360 \, 913 & 1 \, 222 \, 485 \, 886 & 1 \, 222 \, 610 \, 859 & 1 \, 222 \, 735 \, 832 \\
124 \, 974 & 1 \, 222 \, 3 \color{red} 70 \, 694 & 1 \, 222 \, 495 \, 668 & 1 \, 222 \, 620 \, 642 & 1 \, 222 \, 745 \, 616 \\
\end{array}
$
We see that the only possible pairs are:
:$D = 124 \, 972$ and $q_5 = 2$
:$D = 124 \, 974$ and $q_5 = 1$
== Sources ==
* : Solutions: $112$. -- Simple Division
* : Answers: $149$. Simple Division
Category:Henry Ernest Dudeney/Puzzles and Curious Problems/Solutions
Category:Henry Ernest Dudeney/Puzzles and Curious Problems/112 - Simple Division