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: 135

### 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)

The eclipses from Algol come further apart in time when the Earth is moving away from Algol and closer together in time when the Earth is moving towards Algol, thereby proving that the speed of light is variable and that Einstein's Special Theory of Relativity is wrong.

Offline

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

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

### 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: 135

### 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.

The eclipses from Algol come further apart in time when the Earth is moving away from Algol and closer together in time when the Earth is moving towards Algol, thereby proving that the speed of light is variable and that Einstein's Special Theory of Relativity is wrong.

Offline

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

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

### 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: 624

### 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,592

### 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: 135

### 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.

The eclipses from Algol come further apart in time when the Earth is moving away from Algol and closer together in time when the Earth is moving towards Algol, thereby proving that the speed of light is variable and that Einstein's Special Theory of Relativity is wrong.

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,592

### 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,592

### 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,592

### Re: Boxes with disks.

Wow - hardly gave me time to blink!! 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,592

### 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