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

From ProofWiki
Jump to navigation Jump to search

Puzzles and Curious Problems by Henry Ernest Dudeney: $112$

Simple Division
There is a simple division sum.
Can you restore it by substituting a figure for every asterisk, without altering or removing the sevens?
If you start out with the assumption that all the sevens are given, and that you must not use another,
you will attempt an impossibility, though the proof is difficult;
but when you are told that though no additional sevens may be used in divisor, dividend or quotient,
any number of extra sevens may be used in the working.
It is comparatively easy.
             **7**
       -----------
 ****7*)**7*******
        ******
        -------
        *****7*
        *******
        -------
          *7****
          *7****
          -------
          *******
           ***7**
          --------
            ******
            ******
            ------


Solution

The solution given by Dudeney is as follows:

Solution $1$

             39782
       -----------
 124972)4971636104
        374916
        -------
        1222476
        1124748
        -------
          977281
          874804
          -------
          1024770
           999776
          --------
            249944
            249944
            ------


There are further solutions:

Solution $2$

             19781
       -----------
 124974)2472110694
        124974
        -------
        1222370
        1124766
        -------
          976046
          874818
          -------
          1012289
           999792
          --------
            124974
            124974
            ------


Solution $3$

             19782
       -----------
 124972)2472195104
        124972
        -------
        1222476
        1124748
        -------
          977281
          874804
          -------
          1024770
           999776
          --------
            249944
            249944
            ------


Solution $4$

$124 \, 974 \times 39 \, 781 = 4 \, 971 \, 590 \, 694$ 

             39781
       -----------
 124974)4971590694
        374922
        -------
        1222370
        1124766
        -------
          976046
          874818
          -------
          1012289
           999792
          --------
            124974
            124794
            ------

There may be more.


Solution $5$

Dudeney points out that if additional $7$s were to be allowed in the dividend, a further solution could be found: 

             59782
       -----------
 124972)7471076104
        624860
        -------
        1222476
        1124748
        -------
          977281
          874804
          ------
          1024770
           999776
          -------
            249944
            249944
            ------


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:

\(\ds 124 \, 470 \times 19 \, 780\) \(=\) \(\ds 2 \, 462 \, 016 \, 600\)
\(\ds 124 \, 470 \times 29 \, 780\) \(=\) \(\ds 3 \, 706 \, 716 \, 600\)
\(\ds 124 \, 470 \times 39 \, 780\) \(=\) \(\ds 4 \, 951 \, 416 \,600\)
\(\ds 124 \, 470 \times 49 \, 780\) \(=\) \(\ds 6 \, 196 \, 116 \, 600\)
\(\ds 124 \, 470 \times 59 \, 780\) \(=\) \(\ds 7 \, 440 \, 816 \, 600\)
\(\ds 124 \, 470 \times 69 \, 780\) \(=\) \(\ds 8 \, 685 \, 516 \, 600\)
\(\ds 124 \, 470 \times 79 \, 780\) \(=\) \(\ds 9 \, 930 \, 216 \, 600\)

Now notice that:

\(\ds N\) \(=\) \(\ds 124 \, 47x \times y9 \, 78z\)
\(\ds \) \(=\) \(\ds \paren {124 \, 470 + x} \paren {y9 \, 780 + z}\)
\(\ds \) \(=\) \(\ds 124 \, 470 \times y9 \, 780 + \paren {y9 \, 780} x + 124 \, 470 z + x z\)
\(\ds \) \(<\) \(\ds 124 \, 470 \times y9 \, 780 + 80 \, 000 \times 4 + 125 \, 000 \times 8 + 3 \times 8\)
\(\ds \) \(<\) \(\ds 124 \, 470 \times y9 \, 780 + 1 \, 500 \, 000\)

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$



This needs considerable tedious hard slog to complete it.
In particular: Next we use the $7$ in $N$ to find determine the possible $\tuple {Q, D}$ pairs as we did $124 \, 47x$ above. We get $q_1 = 1,3,5,7$, then we test them all. Note that we still haven't used the rule of no additional sevens may be used in divisor, dividend or quotient until this point. $5$ and $7$ gives extra sevens in the dividend and quotient.
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 {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



This needs considerable tedious hard slog to complete it.
In particular: All sevens given in the puzzle have been considered at this point, so $q_1 = 1,3$ with the $\tuple {D, q_5}$ pairs all give a solution. In other words, Dudeney missed $124 \, 974 \times 39 \, 781 = 4 \, 971 \, 590 \, 694$ for some reason.
In fact, Dudeney only actually found $1$ solution: see where I documented that in Henry Ernest Dudeney/Puzzles and Curious Problems/112 - Simple Division/Mistake, and note where I said "there may be more" above. The other two were found pencilled into the solution page by a previous owner of my copy of Puzzles and Curious Problems. But from where I sit there could be any number of solutions. I have added this fourth one as yet another solution page.
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 {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Henry_Ernest_Dudeney/Puzzles_and_Curious_Problems/112_-_Simple_Division/Solution&oldid=670066"