All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Quite a coincidence (Posted on 2018-01-19)
"It's unbelievable!" exclaimed Jerry facing his three friends Adam, Dan and Betty.
"I've asked you to tell me independently each a 4-digit number and after a while, I'm happy to announce that if any of you will divide their number by mine you will end up with the same remainder! "
Now that you know it I'm sure that you will be able jointly to figure the value of my number...- of course it will be the largest of the qualifying candidate answers...

Adam: It could not be true for any three non-related 4-digit numbers!
Betty: You were extremely lucky to find such a special number!
Dan: And now we will be able to calculate the value of your number!

Indeed, Adam(2479), Betty(6181), and Dan(8649), after a not-so-long brainstorming session successfully restored Jerry's number.

a. What was it?
b. d4 bonus question:
What's the probability of Jerry "success" with 3 RANDOMLY CHOSEN
three 4-digits numbers.

Comments: ( Back to comment list | You must be logged in to post comments.)
 proposed solution | Comment 5 of 6 |
difference

3702
Betty 6181
2468
Dan   8649

The GCD of the differences is 1234, which is Jerry's number. All the remainders are 11.

Bonus:

Of course it's assumed Jerry is doing such a GCD calculation. The only question is How impressive is his calculated number. I don't know if it's implied that Jerry's number must be 4 digits. If that's the question then the probability is 1 - 0.99933419926 (see below); that's about 1 in 1502. In a simulation of 10,000 trials it happened only twice (see also below).

First we need a formula for the number of ways of getting a given pair of differences.

First of all it does not matter whether the order of any given set of three numbers a, b and c is abc, acb, bac, bca, cab or cba. Each is equally likely, with the caveat that aab is one of only three, not six, and aaa has no permutations.

We know that only 9000 out of the 9000^3 possible choices made by A, B and D have all three digits the same, so both differences are zero. (Yes here we're considering all orders separately, but we're just calculating the ratio--the probability that both differences are zero.) The probability that both differences are zero is 1/9000^2 ~= 0.00000001234.... In these cases no audience will be impressed that Jerry repeats back the number given, or any other number for that matter.

Similarly the probability that two of the numbers match and one is different is (9000*8999*3)/(9000^3) = 3*8999/9000^2 ~= 0.00033296.... The best Jerry can do in this instance is to give the GCD of the two numbers and the remainder is zero in both cases.

9000^3 = 729,000,000,000

Those with one or two matching numbers is 9000+9000*8999*3 =  242,982,000, leaving  728,757,018,000 where we're concerned with the GCD of two non-zero numbers.

By the below table, the overall probability that there are three distinct numbers chosen and that the GCD of the three is 1 is about 60.8%. So it's less than 50% likely that Jerry can come up with any number at all which would act as such a divisor. Then there's that approximately 15% probability that there would be such a divisor, but it would be 2--hardly amazing. In fact, the probability is less than 0.0007 (i.e., less than 7/100 of 1%) that the GCD would even be a 4-digit number.

Propabilities out of all 729000000000 possible configurations:

(while the denominator for the probability is
729000000000, the cumulative probability does not
include the above probabilities of any matching numbers.)

`  GCD    number     cumulative    cumulative                      number      probability    1 443178686352 443178686352 0.60792686742    2 110794710792 553973397144 0.75990863806    3  49242120084 603215517228 0.82745612788    4  27698603232 630914120460 0.86545146840    5  17727171780 648641292240 0.88976857646    6  12310427448 660951719688 0.90665530821    7   9044391612 669996111300 0.91906188107    8   6924651696 676920762996 0.92856071742    9   5471295228 682392058224 0.93606592349   10   4431773520 686823831744 0.94214517386   11   3662582244 690486413988 0.94716929216   12   3077597232 693564011220 0.95139096189   13   2622335724 696186346944 0.95498813024   14   2261038272 698447385216 0.95808969165   15   1969595100 700416980316 0.96079146820   16   1731112752 702148093068 0.96316610846   17   1533483480 703681576548 0.96526965233   18   1367801208 705049377756 0.96714592285   19   1227619692 706276997448 0.96882990048   20   1107880800 707384878248 0.97034962723   21   1004901696 708389779944 0.97172809320   22    915611640 709305391584 0.97298407625   23    837712044 710143103628 0.97413320114   24    769357584 710912461212 0.97518856133   25    709023300 711621484512 0.97616115845   26    655532664 712277017176 0.97706038021   27    607891824 712884909000 0.97789425103   28    565267008 713450176008 0.97866965159   29    526925760 713977101768 0.97939245784   30    492404760 714469506528 0.98006791019   31    461134548 714930641076 0.98070046787   32    432729168 715363370244 0.98129406069   33    406904472 715770274716 0.98185222869   34    383313192 716153587908 0.98237803554   35    361717680 716515305588 0.98287421891   36    341909856 716857215444 0.98334323106   37    323673948 717180889392 0.98378722825   38    306849816 717487739208 0.98420814706   39    291320964 717779060172 0.98460776430   40    276936720 718055996892 0.98498765006   41    263616084 718319612976 0.98534926334   42    251213832 718570826808 0.98569386393   43    239664864 718810491672 0.98602262232   44    228897648 719039389320 0.98633661086   45    218814480 719258203800 0.98663676790   46    209398632 719467602432 0.98692400882   47    200572140 719668174572 0.98719914207   48    192315024 719860489596 0.98746294869   49    184542840 720045032436 0.98771609388   50    177217200 720222249636 0.98795919017   51    170341812 720392591448 0.98819285521   52    163838112 720556429560 0.98841759885   53    157719804 720714149364 0.98863394974   54    151921872 720866071236 0.98884234737   55    146449800 721012521036 0.98904323873   56    141268176 721153789212 0.98923702224   57    136352772 721290141984 0.98942406308   58    131696808 721421838792 0.98960471714   59    127270596 721549109388 0.98977929957   60    123054480 721672163868 0.98994809858   61    119061216 721791225084 0.99011141987   62    115252992 721906478076 0.99026951725   63    111619944 722018098020 0.99042263103   64    108161040 722126259060 0.99057100008   65    104847180 722231106240 0.99071482337   66    101693736 722332799976 0.99085432095   67     98688180 722431488156 0.99098969569   68     95803584 722527291740 0.99112111350   69     93041712 722620333452 0.99124874273   70     90401280 722710734732 0.99137274998   71     87866028 722798600760 0.99149327951   72     85444848 722884045608 0.99161048780   73     83129052 722967174660 0.99172451942   74     80898216 723048072876 0.99183549091   75     78760800 723126833676 0.99194353042   76     76702128 723203535804 0.99204874596   77     74720472 723278256276 0.99215124318   78     72812736 723351069012 0.99225112347   79     70974024 723422043036 0.99234848153   80     69201360 723491244396 0.99244340795   81     67498488 723558742884 0.99253599847   82     65856000 723624598884 0.99262633592   83     64269456 723688868340 0.99271449704   84     62738640 723751606980 0.99280055827   85     61279140 723812886120 0.99288461745   86     59865864 723872751984 0.99296673798   87     58488012 723931239996 0.99304696844   88     57165456 723988405452 0.99312538471   89     55881744 724044287196 0.99320204005   90     54656640 724098943836 0.99327701486   91     53465376 724152409212 0.99335035557   92     52310544 724204719756 0.99342211215   93     51188472 724255908228 0.99349232953   94     50114784 724306023012 0.99356107409   95     49065720 724355088732 0.99362837960   96     48053520 724403142252 0.99369429664   97     47068200 724450210452 0.99375886207   98     46113024 724496323476 0.99382211725   99     45181800 724541505276 0.99388409503  100     44286000 724585791276 0.99394484400 ...  984       418896 728508474540 0.99932575383  985       417840 728508892380 0.99932632700  986       416784 728509309164 0.99932689872  987       415728 728509724892 0.99932746899  988       414672 728510139564 0.99932803781  989       413616 728510553180 0.99932860519  990       412560 728510965740 0.99932917111  991       411504 728511377244 0.99932973559  992       410448 728511787692 0.99933029862  993       409392 728512197084 0.99933086020  994       408336 728512605420 0.99933142033  995       407280 728513012700 0.99933197901  996       406224 728513418924 0.99933253625  997       405168 728513824092 0.99933309203  998       404112 728514228204 0.99933364637  999       403056 728514631260 0.99933419926 1000       402000 728515033260 0.99933475070`

728757018000

729000000000 done

A simulation with 10000 trials verifies the general nature of these probabilities:

(The numbers add up to 9999--there was one case of a match among the 3 numbers drawn)

GCD Number of occurrences

1  6098
2  1556
3  629
4  380
5  240
6  180
7  121
8  89
9  84
10  44
11  51
12  42
13  35
14  35
15  21
16  21
17  21
18  18
19  22
20  14
21  22
22  11
23  16
24  5
25  14
26  7
27  5
28  11
29  5
30  2
31  5
32  8
33  6
34  4
35  3
36  5
37  2
38  3
39  3
40  3
41  1
42  5
43  4
44  5
45  4
46  5
47  1
48  2
49  4
50  1
51  1
52  3
54  2
55  3
56  7
57  2
58  2
59  1
60  1
61  2
62  4
63  2
64  3
66  1
67  2
69  1
70  1
71  1
72  1
73  3
75  1
76  2
77  4
78  2
79  1
80  1
81  1
82  1
83  1
84  2
85  1
86  3
87  1
88  1
90  2
91  1
92  1
94  2
96  1
97  1
98  2
99  2
102  1
104  1
105  2
107  1
109  1
114  1
119  1
128  1
134  1
138  2
140  2
152  2
156  2
159  2
171  1
180  2
185  1
195  1
217  1
224  1
230  1
251  1
274  1
287  2
291  1
302  1
329  1
347  1
390  1
425  1
429  1
452  1
472  1
492  1
521  1
543  1
878  1
964  1
969  1
1189  1
3856  1

For tr = 1 To 10000
a = 1000 + Int(Rnd(1) * 10000)
b = 1000 + Int(Rnd(1) * 10000)
c = 1000 + Int(Rnd(1) * 10000)
If a <> b And b <> c And a <> c Then
If b < a Then h = b: b = a: a = h
If c < a Then h = c: c = a: a = h
If c < b Then h = b: b = c: c = h
d1 = b - a: d2 = c - b
g(gcd(d1, d2)) = g(gcd(d1, d2)) + 1
If tr Mod 100 = 0 Then
Text1.Text = Text1.Text & tr
End If
End If
DoEvents
Next

Text1.Text = Text1.Text & crlf

For i = 1 To 10000
If g(i) > 0 Then
Text1.Text = Text1.Text & i & "  " & g(i) & crlf
End If
DoEvents
Next

...

Function gcd(a, b)
x = a: y = b
Do
q = Int(x / y)
z = x - q * y
x = y: y = z
Loop Until z = 0
gcd = x
End Function

Edited on January 19, 2018, 11:44 am
 Posted by Charlie on 2018-01-19 11:41:55

 Search: Search body:
Forums (0)