Donate to Remove ads

Got a credit card? use our Credit Card & Finance Calculators

Thanks to Fluke,barchid,Howyoudoin,servodude,tjh290633, for Donating to support the site

Subtractions

cinelli
2 Lemon pips
Posts: 234
Joined: November 9th, 2016, 11:33 am
Has thanked: 62 times
Been thanked: 30 times

Subtractions

#253838

Postby cinelli » September 25th, 2019, 12:56 pm

Choose any four digits (not all the same) such as 3, 6, 2, 8 and rearrange them to form the largest and smallest numbers possible, namely 8632 and 2368. Subtract the smaller number from the larger and repeat the process as the new starting point.

8632   6642   7641
2368 2466 1467
---- ---- ----
6264 4176 6174

In this example the digits 1, 4, 6, 7 occur at the second stage and no new numbers are generated from then on.
Why do you always get 1, 4, 6, 7? What is the longest chain of subtractions you can find before nothing new occurs?

Cinelli

Gengulphus
Lemon Quarter
Posts: 3018
Joined: November 4th, 2016, 1:17 am
Been thanked: 1560 times

Re: Subtractions

#253985

Postby Gengulphus » September 26th, 2019, 1:34 am

cinelli wrote:Choose any four digits (not all the same) such as 3, 6, 2, 8 and rearrange them to form the largest and smallest numbers possible, namely 8632 and 2368. Subtract the smaller number from the larger and repeat the process as the new starting point.

8632   6642   7641
2368 2466 1467
---- ---- ----
6264 4176 6174

In this example the digits 1, 4, 6, 7 occur at the second stage and no new numbers are generated from then on.
Why do you always get 1, 4, 6, 7? What is the longest chain of subtractions you can find before nothing new occurs?

Spoiler...

Suppose the four digits are A, B, C, D in increasing order. Then the smallest and largest numbers resulting from rearranging them is ABCD = 1000*A + 100*B + 10*C + D and DCBA = 1000*D + 100*C + 10*B + A, and the result of the subtraction is 999*D + 90*C - 90*B - 999*A = 999*(D-A) + 90*(C-B). Because A, B, C and D are digits, D-A and C-B must be <= 9, and because of the order of the digits, we must have D-A >= C-B >= 0. Furthermore, D-A cannot be 0, since that and the order of the digits would imply that all four digits are the same.

So the answer after one subtraction will always be one of the following:

If D-A = 1: 0999 or 1089, according to whether C-B is 0 or 1
If D-A = 2: 1998, 2088 or 2178, according to whether C-B is 0, 1 or 2
If D-A = 3: 2997, 3087, 3177 or 3267, according to whether C-B is 0, 1, 2 or 3
If D-A = 4: 3996, 4086, 4176, 4266 or 4356, according to whether C-B is 0, 1, 2, 3 or 4
If D-A = 5: 4995, 5085, 5175, 5265, 5355 or 5445, according to whether C-B is 0, 1, 2, 3, 4 or 5
If D-A = 6: 5994, 6084, 6174, 6264, 6354, 6444 or 6534, according to whether C-B is 0, 1, 2, 3, 4, 5 or 6
If D-A = 7: 6993, 7083, 7173, 7263, 7353, 7443, 7533 or 7623, according to whether C-B is 0, 1, 2, 3, 4, 5, 6 or 7
If D-A = 8: 7992, 8082, 8172, 8262, 8352, 8442, 8532, 8622 or 8712, according to whether C-B is 0, 1, 2, 3, 4, 5, 6, 7 or 8
If D-A = 9: 8991, 9081, 9171, 9261, 9351, 9441, 9531, 9621, 9711 or 9801, according to whether C-B is 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9

Those results from the first subtraction produce just the following thirty combinations of digits (each with the digits in ascending order) going into the second subtraction, which produces the results in brackets according to the above rules:

0,1,8,9 (9621)
0,2,8,8 (8532)
0,3,7,8 (8352)
0,4,6,8 (8172)
0,5,5,8 (7992)
0,9,9,9 (8991)
1,1,7,9 (8532)
1,2,6,9 (8352)
1,2,7,8 (7443)
1,3,5,9 (8172)
1,3,7,7 (6354)
1,4,4,9 (7992)
1,4,6,7 (6174)
1,5,5,7 (5994)
1,8,9,9 (8082)
2,2,6,8 (6354)
2,3,5,8 (6174)
2,3,6,7 (5265)
2,4,4,8 (5994)
2,4,6,6 (4176)
2,5,5,6 (3996)
2,7,9,9 (7173)
3,3,5,7 (4176)
3,4,4,7 (3996)
3,4,5,6 (3087)
3,5,5,5 (1998)
3,6,9,9 (6264)
4,4,4,6 (1998)
4,4,5,5 (1089)
4,5,9,9 (5355)

Those results from the second subtraction produce just the following seventeen combinations of digits (each with the digits in ascending order) going into the third subtraction, which produces the results in brackets according to the above rules:

0,1,8,9 (9621)
0,2,8,8 (8532)
0,3,7,8 (8352)
1,2,6,9 (8352)
1,2,7,8 (7443)
1,3,7,7 (6354)
1,4,6,7 (6174)
1,8,9,9 (8082)
2,3,5,8 (6174)
2,4,6,6 (4176)
2,5,5,6 (3996)
2,7,9,9 (7173)
3,4,4,7 (3996)
3,4,5,6 (3087)
3,5,5,5 (1998)
3,6,9,9 (6264)
4,5,9,9 (5355)

Those results from the third subtraction produce just the following twelve combinations of digits (each with the digits in ascending order) going into the fourth subtraction, which produces the results in brackets according to the above rules:

0,2,8,8 (8532)
0,3,7,8 (8352)
1,2,6,9 (8352)
1,3,7,7 (6354)
1,4,6,7 (6174)
1,8,9,9 (8082)
2,3,5,8 (6174)
2,4,6,6 (4176)
3,4,4,7 (3996)
3,4,5,6 (3087)
3,5,5,5 (1998)
3,6,9,9 (6264)

Those results from the fourth subtraction produce just the following eight combinations of digits (each with the digits in ascending order) going into the fifth subtraction, which produces the results in brackets according to the above rules:

0,2,8,8 (8532)
0,3,7,8 (8352)
1,4,6,7 (6174)
1,8,9,9 (8082)
2,3,5,8 (6174)
2,4,6,6 (4176)
3,4,5,6 (3087)
3,6,9,9 (6264)

Those results from the fifth subtraction produce just the following five combinations of digits (each with the digits in ascending order) going into the sixth subtraction, which produces the results in brackets according to the above rules:

0,2,8,8 (8532)
0,3,7,8 (8352)
1,4,6,7 (6174)
2,3,5,8 (6174)
2,4,6,6 (4176)

Those results from the sixth subtraction produce just the following two combinations of digits (each with the digits in ascending order) going into the seventh subtraction, which produces the results in brackets according to the above rules:

*1,4,6,7 (6174)
*2,3,5,8 (6174)

So the seventh subtraction always produces 6174, and we can then backtrack through the subtractions:

If the sixth subtraction didn't produce the digits 1,4,6,7, it must have produced the digits 2,3,5,8, so the fifth subtraction must have produced the digits 0,2,8,8 or 0,3,7,8, so the fourth subtraction must have produced the digits 1,8,9,9 or 3,4,5,6, so the third subtraction must have produced the digits 1,3,7,7 or 3,5,5,5, so the second subtraction must have produced the digits 2,7,9,9 or 4,5,9,9, so the first subtraction must have produced the digits 0,5,5,8 or 1,5,5,7 or 1,4,4,9 or 2,4,4,8, so the digits going into the first subtraction must have had (D-A,C-B) = (5,1), (5,2), (9,5) or (8,5). That means that the chains of the maximum length 7 are:

DCBA   8550   9972   7731   6543   8730   8532
ABCD 0558 2799 1377 3456 0378 2358
---- ---- ---- ---- ---- ---- ----
5085 7992 7173 6354 3087 8352 6174

for any of DCBA = 5100, 5210, 5320, 5430, 5540,
6211, 6321, 6431, 6541, 6651,
7322, 7432, 7542, 7652, 7762,
8433, 8543, 8653, 8763, 8873,
9544, 9654, 9764, 9874 or 9984


DCBA 7551 9954 5553 9981 8820 8532
ABCD 1557 4599 3555 1899 0288 2358
---- ---- ---- ---- ---- ---- ----
5175 5994 5355 1998 8082 8532 6174

for any of DCBA = 5200, 5310, 5420, 5530,
6311, 6421, 6531, 6641,
7422, 7532, 7642, 7752,
8533, 8643, 8753, 8863,
9644, 9754, 9864 or 9974


DCBA 9441 9972 7731 6543 8730 8532
ABCD 1449 2799 1377 3456 0378 2358
---- ---- ---- ---- ---- ---- ----
9441 7992 7173 6354 3087 8352 6174

for any of DCBA = 9500, 9610, 9720, 9830 or 9940


DCBA 8442 9954 5553 9981 8820 8532
ABCD 2448 4599 3555 1899 0288 2358
---- ---- ---- ---- ---- ---- ----
8442 5994 5355 1998 8082 8532 6174

for any of DBCA = 8500, 8610, 8720, 8830,
9611, 9721, 9831 or 9941

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 3775
Joined: November 4th, 2016, 8:17 pm
Has thanked: 421 times
Been thanked: 623 times

Re: Subtractions

#254002

Postby UncleEbenezer » September 26th, 2019, 7:49 am

Well, here's a non-cure for insomnia ...
digits 0 <= a <= b <= c <= d <= 9, and d > a.

Subtraction is
1000*d + 100*c + 10*b + a - 1000*a - 100*b - 10*c - d
= 999 * (d-a) + 90 * (c-b)

That looks kind-of like few enough cases to enumerate! We can tabulate cases, with c-b on a vertical axis and d-a horizontal, noting that 9 >= d-a >= c-b >=0 by definition. I'll add a second entry to each number indicating the new values of c-b and d-a: this gives us a state machine which will lead to the answer. Noting that your digits 1,4,6,7 yield c-b=2 and d-a=6, we're looking for everything to converge to state 2/6.

.
1 2 3 4 5 6 7 8 9
0 0999 1998 2997 3996 4995 5994 6993 7992 8991
0/9 1/8 2/7 3/6 4/5 4/5 3/6 2/7 1/8
1 1089 2088 3087 4086 5085 6084 7083 8082 9081
7/8 6/8 4/8 2/8 0/8 2/8 4/8 6/8 7/8
2 2178 3177 4176 5175 6174 7173 8172 9171
5/7 4/6 2/6 0/6 2/6 4/6 5/7 6/8
3 3267 4266 5265 6264 7263 8262 9261
3/5 2/4 0/4 2/4 3/5 4/6 4/8
4 4356 5355 6354 7353 8352 9351
1/3 0/2 1/3 2/4 2/6 2/8
5 5445 6444 7443 8442 9441
1/1 0/2 0/4 0/6 0/8
6 6534 7533 8532 9531
1/3 2/4 2/6 2/8
7 7623 8622 9621
3/5 4/6 4/8
8 8712 9711
5/7 6/8
9 9801
7/8


Does this converge at 2/6? 2/6 itself does, and states 2/4, 4/8 and 6/8 lead directly there. Iterating backwards and counting states enumerated and length of chain,
2/6 <-- 2/4, 2/6, 4/8, 6/8 (4/0 or 1)
2/4 <-- 3/4, 3/6, 4/7, 6/7 (8/2)
3/6 <-- 0/4, 0/7 (10/3)
0/4 <-- 3/5, 5/7 (12/4)
3/5 <-- 3/3, 3/7, 7/7 (15/5)
5/7 <-- 2/2, 2/8, 8/8 (18/5)
2/8 <-- 1/4, 1/6, 4/9, 6/9 (22/6)
4/8 <-- 1/3, 1/7, 3/9, 7/9 (26/2)
1/3 <-- 4/4, 4/6, 6/6 (29/3)
4/6 <-- 2/3, 2/7, 3/8, 7/8 (33/4)
2/7 <-- 0/3, 0/8 (35/5)
0/8 <-- 1/5, 5/9 (37/6)
7/8 <-- 1/1, 1/9, 9/9 (40/5)
1/1 <-- 5/5 (41/6)
6/8 <-- 1/2, 1/8, 2/9, 8/9 (45/2)
1/8 <-- 0/2, 0/9 (47/3)
0/2 <-- 4/5, 5/6 (49/4)
4/5 <-- 0/5, 0/6 (51/5)
0/6 <-- 2/5, 5/8 (53/6)
0/9 <-- 0/1 (54/4)
So all 54 possible start states do indeed converge on state 2/6 as required. The longest chain is 6, from various start states enumerated.

Gengulphus
Lemon Quarter
Posts: 3018
Joined: November 4th, 2016, 1:17 am
Been thanked: 1560 times

Re: Subtractions

#254107

Postby Gengulphus » September 26th, 2019, 3:11 pm

UncleEbenezer's answer and mine differ, both with regard to the maximum length of a chain of subtractions to get to the digits 1,4,6,7 and to how many starting states produce a maximum-length chain. I've tracked down the reason why, and it's a subtle flaw in UncleEbenezer's solution: it lumps together some sets of digits that require different numbers of subtractions into the same state of its state machine...

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 3775
Joined: November 4th, 2016, 8:17 pm
Has thanked: 421 times
Been thanked: 623 times

Re: Subtractions

#254118

Postby UncleEbenezer » September 26th, 2019, 3:52 pm

Gengulphus wrote:UncleEbenezer's answer and mine differ, both with regard to the maximum length of a chain of subtractions to get to the digits 1,4,6,7 and to how many starting states produce a maximum-length chain.

Do they? I haven't read the whole of your post. I note you claim a "chain of length 7", but I don't see one in your post.

If I read you right, you cite 5100 as your first starting number for a chain of length 7. Working through that in my state machine, I get
1/5(6) -> 0/8(5) -> 2/7(4) -> 4/6(3) -> 1/3(2) -> 4/8(1) ->2/6(0)
which looks like six steps.

Aha, got it, your 7 is nodes, my six is steps (actual subtractions).

As for the number of start states, I made no attempt to count them. It wasn't part of the question as I read it!

UncleEbenezer
Lemon Quarter
Posts: 3775
Joined: November 4th, 2016, 8:17 pm
Has thanked: 421 times
Been thanked: 623 times

Re: Subtractions

#254142

Postby UncleEbenezer » September 26th, 2019, 4:58 pm

There is a simple missing step in my solution. But it turns out, it does matter for the length of chain (which I counted as kind-of an afterthought :roll: )

Since my states are equivalence classes of actual sets of numbers, state 2/6 represents not just 1,4,6,7, but also 2,3,5,8 (other would-be candidates can be trivially eliminated by virtue of not being multiples of 9).
Our state machine already verifies that 2,3,5,8 goes to state 2/6, which we can verify instantiates as 1,4,6,7:
8532
-2358
-----
6174

Trying to find Gengulphus' additional step, it seems we do indeed arrive prematurely at node 2/6:

5100 - 0015 = 5085
8550 - 0558 = 7992
9972 - 2799 = 7173
7731 - 1377 = 6354
6543 - 3456 = 3087
8730 - 0378 = 8352
8532 - 2358 = 6174


Ho, hum.

Gengulphus
Lemon Quarter
Posts: 3018
Joined: November 4th, 2016, 1:17 am
Been thanked: 1560 times

Re: Subtractions

#254177

Postby Gengulphus » September 26th, 2019, 7:18 pm

UncleEbenezer wrote:There is a simple missing step in my solution. But it turns out, it does matter for the length of chain (which I counted as kind-of an afterthought :roll: )

Since my states are equivalence classes of actual sets of numbers, state 2/6 represents not just 1,4,6,7, but also 2,3,5,8 (other would-be candidates can be trivially eliminated by virtue of not being multiples of 9). ...

Yes - basically the problem was that your 2/5 state really had to be treated as two states, the first of which I might call "End", consisting of only the set of digits 1,4,6,7, and the other of which I might call "Other2/5", consisting of the other 19 sets of digits with c-b = 2, d-a = 5, and only End of those two has chain length 0. The extra subtraction comes for some paths through the state machine because they include an Other2/5 -> End transition that disappears when those two states are inadvertently merged into a single 2/5 state.

Must admit that I too thought at first that the difference between your answer of 6 and mine of 7 was probably a "fencepost problem" (*). It was when I saw that your solution had 9 states at maximum distance and mine had only 4 that I realised it wasn't that simple... Which incidentally is the reason why I mentioned the number of starting states that produce a maximum-length chain - agreed that it wasn't part of the puzzle posed, but it was a fairly simple feature to check about the two solutions, that showed that there was a more fundamental disagreement than an across-the-board off-by-1 counting issue.

(*) In case anyone hasn't come across the term, it refers to the fact that a straight fence of N spans of fencing requires N+1 fenceposts to support it.

Gengulphus

UncleEbenezer
Lemon Quarter
Posts: 3775
Joined: November 4th, 2016, 8:17 pm
Has thanked: 421 times
Been thanked: 623 times

Re: Subtractions

#254265

Postby UncleEbenezer » September 27th, 2019, 9:24 am

There's a simple error in my enumeration, where I misclassify the digits 0,1,8,9 - state 7/9 - as 7/8.

The solution happens to work either way (as expected), but this kind of thing is precisely why I generally avoid allowing enumeration (at least beyond the scope of a finger-count) to enter into my solutions on this board!

Anecdote: as a young software engineer back in the 1980s, I made myself very unpopular with the powers-that-be (and determine my career) by pointing out their vulnerability to errors like this, and finding an instance that made a crucial difference. The scenario was software controlling satellite orbits (so a very high potential cost to getting it wrong), and this was about Formal Testing, on a theory that you could mathematically prove your software correct.

I proved that the tests themselves contained errors, and argued that the whole methodology was broken, because it shifted the programmer's focus from getting it right to getting it through the tests. Furthermore, because the tests were more complex than the software tested, there was more scope for errors in them. And there was no process for a junior bod like me to correct an error from something that passed the tests to something that didn't.

cinelli
2 Lemon pips
Posts: 234
Joined: November 9th, 2016, 11:33 am
Has thanked: 62 times
Been thanked: 30 times

Re: Subtractions

#255096

Postby cinelli » October 1st, 2019, 11:24 am

Apologies for the lateness of this response. The quality of these answers by Gengulphus and Uncle is superb. And I note the times of these posts: 1:34am and 7:49am. Well done.

Cinelli


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 5 guests