Henry Ernest Dudeney/Puzzles and Curious Problems/110 - An Absolute Skeleton/Solution/Initial Deductions
Puzzles and Curious Problems by Henry Ernest Dudeney: $110$
- An Absolute Skeleton
- Here is a good skeleton puzzle.
- The only conditions are:
******** ------------ ***)*********** *** --- *** *** ---- **** **** ----- *** *** ---- **** **** ----- **** **** ----- **** **** ----- **** **** ----
Initial Deductions
Declarations
Let $D$ denote the divisor.
Let $Q$ denote the quotient.
Let $N$ denote the dividend.
Let $q_1$ to $q_8$ denote the digits of $Q$ which are calculated at each stage of the long division process in turn.
Let $n_1$ to $n_8$ denote the partial dividends which are subject to the $1$st to $8$th division operations respectively.
Let $j_1$ to $j_8$ denote the least significant digits of $n_1$ to $n_8$ as they are brought down from $N$ at each stage of the long division process in turn.
Let $p_1$ to $p_8$ denote the partial products generated by the $1$st to $8$th division operations respectively: $p_k = q_k D$
Let $d_1$ to $d_8$ 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:
******** --> Q ------------ --- ***)*********** --> D ) N *** --> p_1 --- *** --> n_2 *** --> p_2 ---- **** --> n_3 **** --> p_3 ----- *** --> n_4 *** --> p_4 ---- **** --> n_5 **** --> p_5 ----- **** --> n_6 **** --> p_6 ----- **** --> n_7 **** --> p_7 ----- **** --> n_8 **** --> p_8 ----
It is apparent from the structure of the long division sum presented that no digit of $Q$ may be zero.
We also have, from the additional constraint on $Q$, that:
\(\ds q_7\) | \(=\) | \(\ds q_8 + 2\) | If $2$ be added to the last figure in the quotient it equals the last but one, | |||||||||||
\(\ds q_5\) | \(=\) | \(\ds q_6 + 2\) | and if $2$ be added to the third figure from the end it gives the last figure but $3$ in the quotient. |
This also gives us that:
\(\ds q_5\) | \(\ge\) | \(\ds 3\) | as $q_6 \ne 0$ | |||||||||||
\(\ds q_6\) | \(\le\) | \(\ds 7\) | ||||||||||||
\(\ds q_7\) | \(\ge\) | \(\ds 3\) | as $q_8 \ne 0$ | |||||||||||
\(\ds q_8\) | \(\le\) | \(\ds 7\) |
The rule about repeated digits offers similar constraints on $n_2$ to $n_8$ and $p_1$ to $p_8$, and will be used without further comment in the following.
However, note that this does not apply to $n_1$, which in this context is the first $4$ digits of $N$, which has no constraint on the uniqueness of its digits.
We have:
\(\ds p_1\) | \(\le\) | \(\ds 987\) | ||||||||||||
\(\ds d_1\) | \(\le\) | \(\ds 98\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds n_1\) | \(=\) | \(\ds p_1 + d_1\) | |||||||||||
\(\ds \) | \(\le\) | \(\ds 987 + 98\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1085\) |
This gives us a firm upper bound on $N$, and we can immediately state:
- $(1): \quad 10 \, 000 \, 000 \, 000 \le N \le 10 \, 859 \, 999 \, 999$
Hence also:
\(\ds p_1\) | \(=\) | \(\ds n_1 - d_1\) | ||||||||||||
\(\ds p_1\) | \(\ge\) | \(\ds 1000 - 98\) | the lower bound of $n_1$ minus the upper bound of $d_1$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 902\) |
Thus we have:
- $902 \le p_1 \le 987$
We have that $p_1$, $p_2$ and $p_4$ each have $3$ digits.
But each of $q_1$, $q_2$ and $q_4$ are distinct.
Hence:
\(\ds \max \set {q_1, q_2, q_4}\) | \(\ge\) | \(\ds 3\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \max \set {q_1, q_2, q_4} \times D\) | \(=\) | \(\ds \max \set {p_1, p_2, p_4}\) | |||||||||||
\(\ds \) | \(\le\) | \(\ds 987\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds D\) | \(\le\) | \(\ds \dfrac {987} 3\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds D\) | \(\le\) | \(\ds 329\) |
We have that $p_3$, $p_5$, $p_6$, $p_7$ and $p_8$ each have $4$ digits.
But each of $q_3$, $q_5$, $q_6$, $q_7$ and $q_8$ are distinct.
Hence:
\(\ds \min \set {q_3, q_5, q_6, q_7, q_8}\) | \(\le\) | \(\ds 5\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \min \set {q_3, q_5, q_6, q_7, q_8} \times D\) | \(=\) | \(\ds \min \set {p_3, p_5, p_6, p_7, p_8}\) | |||||||||||
\(\ds \) | \(\ge\) | \(\ds 1023\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds D\) | \(\ge\) | \(\ds \dfrac {1023} 5\) | |||||||||||
\(\text {(3)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds D\) | \(\ge\) | \(\ds 205\) |
That is:
- $205 \le D \le 329$
Thus we have established bounds on $D$ and $N$.
Hence we can now establish bounds on $Q$:
\(\ds Q\) | \(\le\) | \(\ds \dfrac {\map \max N} {\map \min D}\) | abusing notation | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {10 \, 859 \, 999 \, 999} {205}\) | from $(1)$ and $(3)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 52 \, 975 \, 609\) |
\(\ds Q\) | \(\ge\) | \(\ds \dfrac {\map \min N} {\map \max D}\) | again abusing notation | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {10 \, 000 \, 000 \, 000} {329}\) | from $(1)$ and $(2)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 30 \, 395 \, 136\) |
So we immediately see that $3 \le q_1 \le 5$.
Suppose $q_1 = 5$.
Then:
\(\ds D\) | \(\ge\) | \(\ds 205\) | from $(3)$ | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds p_1\) | \(\ge\) | \(\ds 5 \times 205\) | as $p_1 = q_1 D$ | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds p_1\) | \(\ge\) | \(\ds 1025\) |
But we already have that $p_1 \le 987$.
So $q_1 \ne 5$.
Suppose $q_1 = 4$.
Then:
\(\ds D\) | \(\ge\) | \(\ds 205\) | from $(3)$ | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds p_1\) | \(\ge\) | \(\ds 4 \times 205\) | as $p_1 = q_1 D$ | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds p_1\) | \(\ge\) | \(\ds 820\) |
There is believed to be a mistake here, possibly a typo. In particular: The following analysis was based on $D \ge 247$, but now that limit has been reduced to $205$, the following argument no longer works. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by reviewing it, and either correcting it or adding some explanatory material as to why you believe it is actually correct after all. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Mistake}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
But we already have that $p_1 \le 987$.
So $q_1 \ne 4$.
This directly gives us that $q_1 = 3$.
We also have that:
\(\ds p_2\) | \(\le\) | \(\ds 987\) | ||||||||||||
\(\ds p_4\) | \(\le\) | \(\ds 987\) |
Hence by the same reasoning:
- $q_2 < 4$ and $q_4 < 4$
and so either:
- $q_2 = 1$ and $q_4 = 2$
or:
- $q_2 = 2$ and $q_4 = 1$
Now let us consider the lower bound and upper bound for $Q$.
Recall:
\(\ds q_7\) | \(=\) | \(\ds q_8 + 2\) | ||||||||||||
\(\ds q_5\) | \(=\) | \(\ds q_6 + 2\) |
and that $q_1$ to $q_8$ are unique.
We also have that:
\(\ds q_1\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds q_2\) | \(=\) | \(\ds 1 \text { or } 2\) | ||||||||||||
\(\ds q_4\) | \(=\) | \(\ds 2 \text { or } 1\) |
This gives us the limits on $Q$:
- $31 \, 427 \, 586 \le Q \le 32 \, 918 \, 675$
Now:
\(\ds Q\) | \(\le\) | \(\ds 32 \, 918 \, 675\) | from above | |||||||||||
\(\ds D\) | \(\le\) | \(\ds 329\) | from above | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds N\) | \(=\) | \(\ds D \times Q\) | |||||||||||
\(\ds \) | \(\le\) | \(\ds 10 \, 830 \, 244 \, 075\) |
Similarly:
\(\ds Q\) | \(\le\) | \(\ds 32 \, 918 \, 675\) | from above | |||||||||||
\(\ds N\) | \(\ge\) | \(\ds 10 \, 000 \, 000 \, 000\) | still no better lower bound on $N$ | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds D\) | \(=\) | \(\ds \dfrac N Q\) | |||||||||||
\(\ds \) | \(\ge\) | \(\ds 304\) |
Thus we have revised our bounds on $D$:
- $304 \le D \le 329$
Between $304$ and $329$ are $26$ numbers.
Of these, $4$ have duplicated digits:
- $311$, $313$, $322$ and $323$
so these cannot equal $D$.
There are sufficiently few of these to compute their multiples to investigate whether they have duplicated digits.
We require that $D k$ have no duplicate digits where $1 \le k \le 3$.
If none of them do, then we require that $D k$ have no duplicate digits for at least $5$ values of $k$ where $4 \le k \le 9$.
By the Pigeonhole Principle, in order to eliminate a candidate for $D$, we need to find just $2$ such multiples with duplicated digits where $4 \le k \le 9$.
We will present them as an array, where the numbers in $\color { red } {\text {red} }$ have duplicated digits.
We bother to go no further with a candidate $D$ once the criteria have been breached.
- $\begin{array} {r|rrrrrrrr} \times & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
304 & 608 & 912 & \color {red} {1216} & 1520 & 1824 & \color {red} {2128} & \\ 305 & 610 & 915 & \color {red} {1220} & \color {red} {1525} \\ 306 & 612 & 918 & \color {red} {1224} & 1530 & 1836 & \color {red} {2142} \\ 307 & 614 & 921 & \color {red} {1228} & \color {red} {1353} & \\ 308 & \color {red} {616} & \\ 309 & 618 & 927 & 1236 & \color {red} {1545} & 1854 & 2163 & \color {red} {2472} \\ 310 & 620 & 930 & 1240 & \color {red} {1550} & 1860 & 2170 & 2480 & 2790 \\ 312 & 624 & 936 & 1248 & 1560 & 1872 & 2184 & 2496 & \color {red} {2808} \\ 314 & 628 & 942 & 1256 & 1570 & \color {red} {1884} & 2198 & \color {red} {2512} & \\ 315 & 630 & 945 & 1260 & \color {red} {1575} & 1890 & \color {red} {2205} & \\ 316 & 632 & 948 & 1264 & 1580 & 1896 & \color {red} {2212} & \color {red} {2528} & \\ 317 & 634 & 951 & 1268 & \color {red} {1585} & 1902 & \color {red} {2219} & \\ 318 & \color {red} {636} & \\ 319 & 638 & 957 & 1276 & \color {red} {1595} & \color {red} {1914} & \\ 320 & 640 & 960 & 1280 & \color {red} {1600} & 1920 & \color {red} {2240} & \\ 321 & 642 & 963 & 1284 & 1605 & 1926 & \color {red} {2247} & 2568 & \color {red} {2889} \\ 324 & 648 & 972 & 1296 & 1620 & \color {red} {1944} & \color {red} {2268} & \\ 325 & 650 & 975 & \color {red} {1300} & 1625 & 1950 & \color {red} {2275} & \\ 326 & 652 & 978 & 1304 & 1630 & 1956 & \color {red} {2282} & 2608 & 2934 \\ 327 & 654 & 981 & 1308 & 1635 & 1962 & \color {red} {2289} & \color {red} {2616} & \\ 328 & \color {red} {656} & \\ 329 & 658 & 987 & \color {red} {1316} & 1645 & 1974 & \color {red} {2303} & \end{array}$
As can be seen, there are three candidates for $D$:
- $310$, $312$, $326$
Suppose $D = 326$.
Then $Q$ is such that it has no $7$.
So $Q$ is such that $q_8, q_8 + 2, q_6, q_6 + 2$ come from $\set {4, 5, 6, 8, 9}$.
It is seen that such a $Q$ is not possible.
Hence $D \ne 326$.
It remains to investigate $310$ and $312$.
- Let $D = 310$.
Then $Q$ is made from $\set {1, 2, 3, 4, 6, 7, 8, 9}$.
Hence $Q$ can be:
- $31428697$
- $31429786$
- $31826497$
- $31829764$
- $32418697$
- $32419786$
- $32816497$
- $32819764$
- Let $D = 312$.
Then $Q$ is made from $\set {1, 2, 3, 4, 5, 6, 7, 8}$.
Hence $Q$ can be:
- $31427586$
- $31428675$
- $31826475$
- $31827564$
- $32417586$
- $32418675$
- $32816475$
- $32817564$
But:
- $10000000000 = 32051282 \times 312 + 16$
and:
- $10000000000 = 32258064 \times 310 + 160$
and so it is seen that the candidate values for $Q$ which are smaller than $32000000$ are too small.
Hence we are left with the following to investigate.
For $D = 310$:
- $32418697$
- $32419786$
- $32816497$
- $32819764$
For $D = 312$:
- $32417586$
- $32418675$
- $32816475$
- $32817564$
These are to be tested one by one.