Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2016-01-23 16:26:22

Fruityloop
Member
Registered: 2009-05-18
Posts: 143

Boxes with disks.

You have two boxes.  We will call them box #1 and box #2.  Box #1 has 20 wooden disks inside that are numbered 1 to 20. Box #2 is empty.
You have a 20 sided die.  You roll the die and whichever number comes up on the die, the disk with that number gets moved to the other box.
So, if it is in box #1 it gets moved to box #2, if it is in box #2 it gets moved to box #1.
Starting with all 20 disks in box #1, on average how many rolls are required for box #2 to contain all of the disks and box #1 is empty?

Last edited by Fruityloop (2016-01-23 16:32:17)

Offline

#2 2016-01-24 03:10:58

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

Hi Fruityloop,

Here are the results from an Excel simulation for 200,000 rolls of the 20-sided die:

                      # of rolls after which Box2 held exactly  
# of disks in Box2    the # of disks listed in the first column
                0         0
                1         3
                2        35
                3       252
                4       951
                5      2951
                6      7355
                7     14735
                8     24017
                9     31966
               10     35327
               11     32247
               12     24076
               13     14674
               14      7220
               15      2919
               16       977
               17       245
               18        43
               19         5
               20         2
                     ------
       Total throws: 200000
                     ======

So, in 200,000 rolls, there were 2 occasions when Box2 contained all of the disks and Box1 was empty.

Unfortunately, I didn't think to code the program to note the rolls at which Box2 was full, but I do know that both occurred during the 70,000 rolls between 130,000 and 200,000.

EDIT: I ran another simulation for 1,000,000 rolls, resulting in similar ratios as before, but this time there was 1 occasion when Box2 was full and 1 when it was empty (not being the empty starting position).

Last edited by phrontister (2016-01-24 11:29:47)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#3 2016-01-24 12:09:23

Fruityloop
Member
Registered: 2009-05-18
Posts: 143

Re: Boxes with disks.

That's interesting.  I hope I have the correct answer.  I will wait for some more people to attempt to answer the problem.

Offline

#4 2016-01-25 03:32:00

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

Some more results, this time in Mathematica:

10,000,000 rolls: 6 occasions when Box2 was full and Box1 empty.
100,000,000 rolls: 117 occasions when Box2 was full and Box1 empty.
1,000,000,000 rolls: 965 occasions when Box2 was full and Box1 empty.

This is the full results list for 1 billion rolls:

                      # of rolls after which Box2 held exactly  
# of disks in Box2    the # of disks listed in the first column
                0            960
                1          19184
                2         180955
                3        1087879
                4        4623556
                5       14795300
                6       36979285
                7       73946508
                8      120155510
                9      160186747
               10      176186717
               11      160170444
               12      120119252
               13       73905084
               14       36949683
               15       14783309
               16        4622139
               17        1086434
               18         180978
               19          19111
               20            965
                   -------------
      Total rolls: 1,000,000,000
                   =============

Edit 14 June 2016: I ran another sim for 1 billion rolls today, yielding 989 occasions when Box2 was full and Box1 empty.

Last edited by phrontister (2016-06-14 00:23:26)


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#5 2016-01-25 04:16:43

Relentless
Member
Registered: 2015-12-15
Posts: 631

Re: Boxes with disks.

So we can conjecture that the number of rolls required is 1,000,000? Despite your 2 results in Excel.

It will be interesting to see a proof (unfortunately, I think it is beyond me).

Offline

#6 2016-01-25 05:22:26

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

Likewise me!


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#7 2016-01-26 12:32:42

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

Hi Fruityloop;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#8 2016-01-26 16:25:14

Fruityloop
Member
Registered: 2009-05-18
Posts: 143

Re: Boxes with disks.

Hi Bobbym,
   I have the same answer as you but I used a 20 x 20 Markov chain.  The way you got the answer involves some math that is way beyond me.
   I'm glad I got the right answer.

Offline

#9 2016-01-26 17:53:37

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

I used the same idea.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#10 2016-01-26 17:57:59

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

So that's a difference of about 6.76% from my last M simulation.

Maybe I should have let M keep rolling the die till now, and I might have got closer to the right answer!


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#11 2016-01-26 18:00:03

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

There was a very quick way using M.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#12 2016-01-26 18:05:33

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

My code for 1 billion rolls took M 4.75 hours. I know a maths way is quicker than a sim, but I couldn't think of one...and I've never heard of a Markov chain.

What's the quick M way?


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#13 2016-01-26 19:00:33

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

Hi;

n = 20;
A = DiagonalMatrix[Table[k/n, {k, 1, n}], -1] + 
   DiagonalMatrix[Table[k/n, {k, n, 1, -1}], 1];
A[[1, 1]] = 1;
A[[1, 2]] = 0;
A[[n + 1, n]] = 1;
(*A//MatrixForm*)
v = ConstantArray[0, n + 1];
v[[n + 1]] = 1;
A = DiscreteMarkovProcess[v, A];
Mean[FirstPassageTimeDistribution[A, 1]]

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#14 2016-01-26 19:21:03

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

Wow - hardly gave me time to blink!! smile I don't understand it, of course. Waaay over my head!

Oh, well...coding up a working sim was satisfying enough for me. It didn't take me long to sack Excel and let M take over.

M rolled the die at about 58000rps compared to Excel's 4000rpm, but Excel had to wade through updating spreadsheet cells, whereas M just counted under the table.


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#15 2016-01-26 19:23:50

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

If you want and feel you are ready I will teach you Absorbing Markov chains. You will absorb them easily ( no pun intended.) But not tonight, I am sleepy.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#16 2016-01-26 19:32:15

phrontister
Real Member
From: The Land of Tomorrow
Registered: 2009-07-12
Posts: 4,810

Re: Boxes with disks.

Thanks for the offer, but I think I'll pass...for a while at least.

I have so many unfinished projects at home that I should be doing at a quicker rate than I have. As is the case with many owner-built houses - which mine is - I've left a lot of jobs till later. And now it's later!


"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson

Offline

#17 2016-01-27 04:30:41

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

Hi;

Okay, when you are ready. I just moved, so I have much maintenance to do.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#18 2016-02-09 11:21:52

javanaut
Member
Registered: 2016-02-02
Posts: 5

Re: Boxes with disks.

Thanks. I looked up the "absorbing" Markov chains. It turns out that it does not matter how many absorbing states there are. The answer only depends on the fundamental matrix Q.
Fascinating that matrices (n-by-n ones anyway) obey the rules of algebra, like:

                                                           I - Q (to the n+1)
I + Q + Q² + Q³ + ... + Q (to the n) =  -------------------------
                                                                  I - Q

Is that correct?

Offline

#19 2016-02-09 13:56:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Boxes with disks.

Hi;

Remember that Matrix division is undefined and they use the inverse instead. As such I know of the formula


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#20 2016-06-13 17:34:53

thickhead
Member
Registered: 2016-04-16
Posts: 1,086

Re: Boxes with disks.

Very interesting problem.Let us consider the fate of  only one disk. on 1st roll its possibility of going to box 2 is 19/20 and that of remaining in box 1 is 19/20. On 2nd roll if we get same number it is shifted back to box1. so the probability of remaining in box 2  is 1/20x19/20 and that of remaing in box1 is 19/20 (of first roll)x 1/20 (of second roll.) This way we can continue in excel sheet for further rolls.

Roll	box1         	box2
1	0.95          	0.05
2	0.905	        0.095
3	0.8645	        0.1355
4	0.82805	        0.17195
5	0.795245        0.204755
6	0.7657205	0.2342795
7	0.73914845	0.26085155
8	0.715233605	0.284766395
9	0.693710245	0.306289756
10	0.67433922	0.32566078
. 
.
.
61	0.500808655	0.499191345
62	0.500727789	0.499272211
63	0.50065501	0.49934499
64	0.500589509	0.499410491
65	0.500530558	0.499469442 

This compelled me to accept the long term probability of disk being in box2 as 0.5.
Now for 20 disks to be in box2 

So we can expect all 20 disks to be in box 2 by 1/0.5^20=2^20=

Last edited by thickhead (2016-06-13 19:57:10)


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

#21 2016-06-13 21:59:54

thickhead
Member
Registered: 2016-04-16
Posts: 1,086

Re: Boxes with disks.

Last edited by thickhead (2016-06-15 01:47:24)


{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}

Offline

Board footer

Powered by FluxBB