r/probabilitytheory • • Dec 10 '18

Interesting probability problem!

Post image
45 Upvotes

13 comments sorted by

6

u/mattdhanley Dec 10 '18

Curious if anybody can figure this out analytically! I've solved it with Monte Carlo simulations, but cannot figure out for the life of me how to get an analytical solution. My results from Monte Carlo yielded an average of ~71-72 sticks to get a pizza party.

3

u/ilovetheuniverse Dec 10 '18

Really curious how you approached this with a monte carlo simulation. These are new concepts to me so would love to learn!

2

u/mattdhanley Dec 10 '18

What /u/not_really_redditing proposed is a good description. I've got my code hosted on my github here.

1

u/not_really_redditing Dec 10 '18

For anyone more familiar with R, here's another solution in 9 rather horrible lines of R code. Could be faster, could be prettier, could be more interpretable, but it works.

mean(sapply(1:1000,function(x){
  draw_order <- sample.int(100,100)
  for (i in 10:100) {
    sticks <- draw_order[1:i]
    if ( all(c((1:10)) %in% sticks) || all(c(10 + (1:10)) %in% sticks) || all(c(20 + (1:10)) %in% sticks) || all(c(30 + (1:10)) %in% sticks) || all(c(40 + (1:10)) %in% sticks) || all(c(50 + (1:10)) %in% sticks) || all(c(60 + (1:10)) %in% sticks) || all(c(70 + (1:10)) %in% sticks) || all(c(80 + (1:10)) %in% sticks) || all(c(90 + (1:10)) %in% sticks) || all(c(1 + 10*(0:9)) %in% sticks) || all(c(2 + 10*(0:9)) %in% sticks) || all(c(3 + 10*(0:9)) %in% sticks) || all(c(4 + 10*(0:9)) %in% sticks) || all(c(5 + 10*(0:9)) %in% sticks) || all(c(6 + 10*(0:9)) %in% sticks) || all(c(7 + 10*(0:9)) %in% sticks) || all(c(8 + 10*(0:9)) %in% sticks) || all(c(9 + 10*(0:9)) %in% sticks) || all(c(10 + 10*(0:9)) %in% sticks) ) {
      return(i)
    }
  }
}))

3

u/not_really_redditing Dec 10 '18

Not OP, but the beauty of Monte Carlo simulation is that you simply describe the process probabilistically once, then you draw from that distribution repeatedly.

You write out the win conditions, initialize the sticks with all numbers 1 to 100, and then have a loop to draw sticks (and remove them from the pool) randomly until victory is achieved. Then you can do this many times, counting how many sticks were drawn each time. Take the average and you have your MC estimate.

2

u/Bayes_the_Lord Dec 11 '18

This is what I ended up doing in Python. I'm trying to learn more numpy to see if I can get away from for loops.

import numpy as np

n_sims = 10**5
sticks = np.arange(1,101)
total_sticks = 0
for _ in range(n_sims):
    grid = np.arange(1,101).reshape(10,10)
    np.random.shuffle(sticks)
    for stick_num in sticks:
        total_sticks += 1
        grid[np.where(grid==stick_num)] = 0
        if np.all(np.any(grid, axis=1)) and np.all(np.any(grid, axis=0)):
            continue
        else:
            break
print(total_sticks/n_sims)
# 71.58

1

u/selib Jan 10 '19
    grid[np.where(grid==stick_num)] = 0
    if np.all(np.any(grid, axis=1)) and np.all(np.any(grid, axis=0)):
        continue

Could you explain these two lines to me?

1

u/Bayes_the_Lord Jan 10 '19
grid[np.where(grid==stick_num)] = 0    

For the stick number we've drawn, find where that number is in the grid and set the value equal to 0.

if np.all(np.any(grid, axis=1)) and np.all(np.any(grid, axis=0)):
        continue

For each row and column is any value True (not equal to 0) in that row/column? If all rows and columns have at least 1 non-zero we continue the game.

2

u/PolliSoft Aug 24 '22

Sorry, new to this sub.

Nowhere in the problem is it stated that the grid is started over once a pizza party is held. That means that a valid solution to the problem is 20 parties per 100 sticks = every 5 sticks on average.

I'm a bit drunk, I'll see myself out...

1

u/Bromskloss Dec 10 '18

Meh, no possibility to influence the outcome! I mean, except being good.

1

u/Holiday-Pay193 Mar 20 '25 edited Mar 20 '25

Tried this in 2x2 to 20x20 square.

a = Squares per row/column (a x a square)

s = average number of sticks needed

a    s         s/a^2
1    1         1
2    2.3335    0.583374 ± 0.000033
3    5.0705    0.563388 ± 0.000059
4    9.3568    0.584801 ± 0.000088
5    15.2915   0.61166  ± 0.00012
6    22.9479   0.63744  ± 0.00014
7    32.3627   0.66046  ± 0.00017
8    43.5892   0.68108  ± 0.00019
9    56.6319   0.69916  ± 0.00022
10   71.5339   0.71534  ± 0.00024
11   88.3952   0.73054  ± 0.00026
12   107.063   0.74349  ± 0.00028
13   127.543   0.75469  ± 0.00030
14   150.033   0.76547  ± 0.00032
15   174.397   0.77510  ± 0.00034
16   200.639   0.78374  ± 0.00036
17   229.076   0.79265  ± 0.00037
18   258.964   0.79927  ± 0.00039
19   291.262   0.80682  ± 0.00040
20   325.425   0.81356  ± 0.00042

0

u/[deleted] Dec 10 '18

[deleted]

6

u/mattdhanley Dec 10 '18

Great solution! I'll combine with my Monte Carlo sims to get a new plot with both analytical and experimental! Thanks

4

u/mfb- Dec 11 '18

How did you get that formula?