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

Home > Just Math
Quite a coincidence (Posted on 2018-01-19) Difficulty: 2 of 5
"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.
Provide your estimate, listing your assumptions and reasoning.

No Solution Yet Submitted by Ady TZIDON    
Rating: 3.0000 (1 votes)

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

Adam  2479
              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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information