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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**Fruityloop****Member**- Registered: 2009-05-18
- Posts: 135

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

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

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

**Fruityloop****Member**- Registered: 2009-05-18
- Posts: 135

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

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

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

**Relentless****Member**- Registered: 2015-12-15
- Posts: 624

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

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

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

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

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

**Fruityloop****Member**- Registered: 2009-05-18
- Posts: 135

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

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

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

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

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!

Offline

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

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

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

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?

Offline

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

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

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

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.

Offline

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

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

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

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!

Offline

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

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

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

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

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

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

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

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

*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

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

*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

Pages: **1**