My daughter's favorite board game is Here, Fishy, Fishy! . I recommend it highly to all parents of 2-year-olds.
Players take turns rolling a standard six-sided die with five main colors (red, purple, blue, yellow, green) and a sixth "wildcard" color (white). The goal is to catch one fish of each of the five main colors. Rolling one of the five main colors allows you to catch the fish of that color, if you have not already caught it. Rolling a white allows you to catch an uncaught fish of whichever color you pick. The first person to catch a fish of all five colors wins.
Suppose my daughter and I play a two-player game of Here, Fishy, Fishy!, and she goes first (as she always does!). The probability that she wins is b a , where a and b are coprime positive integers. What is a + b ?
(You will probably want to use a computer.)
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
My method differs. I first noticed that the probability of catching all 5 fishes in n + 1 number of turns is independent of the other player. So if I'm able to find an expression relating the probability of the player catching all 5 fishes in n + 1 turns ( P n + 1 ), then the answer to this problem is j = 4 ∑ ∞ P j + 1 n = 4 ∑ j P n + 1 With some thinking, P n + 1 = 6 n 5 ! ⋅ 2 4 4 n − 4 ⋅ 3 n + 6 ⋅ 2 n − 4 The final answer is evaluated by computing the large sum. Tedious but doable by hand.
This approach also allows easy generalisation to more players, however, the final sum that needs to be computed gets much bigger.
Log in to reply
Nice! Does this generalize to more fish? It seems like it does. Can you give the derivation of your formula?
Log in to reply
It does generalise easily for more fishes. The technique I used to calculate P k + 1 is by first drawing a probability tree and summing all the cases that end with k + 1 moves. Supposed there are n -fishes, then among the k + 1 moves, there will be n moves where you catch a fish. So, every case would have the probability of occurring in the form
[ Probability of catching all n fish ] × [ Probability that you get this set of moves where you don’t catch a fish ] = n + 1 1 × n + 1 2 . . . × n + 1 n × [ Probability that you get this set of moves where you don’t catch a fish ] = ( n + 1 ) n n ! × [ Probability that you get this set of moves where you don’t catch a fish ]
For instance, n=5, if you were to catch the first fish, then miss for the next 8 moves, and then catch all the remaining 4 fishes in succession, the probability of that happening would be
1 ⋅ 6 8 1 ⋅ 6 5 ⋅ 6 4 ⋅ 6 3 ⋅ 6 2 ⋅ 6 1 = [ 1 ⋅ 6 5 ⋅ 6 4 ⋅ 6 3 ⋅ 6 2 ⋅ 6 1 ] [ 6 8 1 ] = [ Probability of catching all n fish ] × [ Probability of getting this set of moves where you don’t get a fish ]
So now
P k + 1 = Sum over all S ∑ ( n + 1 ) n n ! × [ Probability that you get this set (S) of moves where you don’t catch a fish (X) ] = ( n + 1 ) n n ! 1 ≤ a 1 ≤ a 2 ≤ . . . ≤ a k − n + 1 ≤ n − 1 { a j ∈ Z } ∑ j = 1 ∏ k − n + 1 n + 1 a j = ( n + 1 ) k n ! 1 ≤ a 1 ≤ a 2 ≤ . . . ≤ a k − n + 1 ≤ n − 1 { a j ∈ Z } ∑ j = 1 ∏ k − n + 1 a j = ( n + 1 ) k n ! S ( k , n − 1 ) ( ∗ )
Where S ( k , n ) denotes the Stirling numbers of the second kind. Using the explicit formula for S ( k , n ) , we can then compute the sum to get the final answer:
j = n − 1 ∑ ∞ P j + 1 k = n − 1 ∑ j P k + 1
(*) Proof that 1 ≤ a 1 ≤ a 2 ≤ . . . ≤ a k − n + 1 ≤ n − 1 { a j ∈ Z } ∑ j = 1 ∏ k − n + 1 a j = S ( k , n − 1 )
Suppose that
F ( k , n − 1 ) = 1 ≤ a 1 ≤ a 2 ≤ . . . ≤ a k − n + 1 ≤ n − 1 { a j ∈ Z } ∑ j = 1 ∏ k − n + 1 a j
Then
F ( k , n − 1 ) = a k − n + 1 = 1 ∑ n − 1 a k − n + 1 1 ≤ a 1 ≤ a 2 ≤ . . . ≤ a k − n ≤ a k − n + 1 ∑ j = 1 ∏ k − n a j = a k − n + 1 = 1 ∑ n − 1 a k − n + 1 F ( k − n + a k − n + 1 , a k − n + 1 )
Also notice that F ( 1 , 1 ) = F ( n , 1 ) = 1 . This means that F ( k , n − 1 ) follows the exact same recurrence relation as S ( k , n − 1 ) (Given Here ). Therefore F ( k , n − 1 ) = S ( k , n − 1 )
I found it very hard to type out this solution, hence it might be unclear.
Extra: Using a 12 sided die (n=11), the probability that the first player wins is 6 0 0 0 7 7 3 1 2 8 1 4 . For a 20 sided die (n=19), the probability is ~0.5114185
Problem Loading...
Note Loading...
Set Loading...
Let P ( a , b ) be the probability that the player whose move it is will win eventually, at the moment when he has a fish left to catch and the other player has b fish left. The fundamental recursion is P ( a , b ) = 6 1 + a ( 1 − P ( b , a − 1 ) ) + 6 5 − a ( 1 − P ( b , a ) ) = 1 − 6 1 + a P ( b , a − 1 ) − 6 5 − a P ( b , a ) . The first term of the left equality corresponds to catching a fish, and the second term corresponds to not catching one.
This is a little tricky to compute with in practice because you need the fundamental recursion twice. As written above, the recursion doesn't give a terminating function, since it will bounce back and forth computing P ( a , b ) and P ( b , a ) forever. To get around this, use the recursion again to solve for P ( b , a ) on the right side, and now you have a formula for P ( a , b ) with a term on the right side involving P ( a , b ) in it (corresponding, basically, to both players taking a turn without catching a fish). Now you can get something effective by solving for P ( a , b ) , bringing that term to the left side. If you don't do this, you'll get an infinite recursion error (for the same reason that the game might go on forever with no one catching a fish).
More explicitly: P ( a , b ) P ( b , a ) P ( a , b ) ( 1 − 3 6 ( 5 − a ) ( 5 − b ) ) P ( a , b ) = 1 − 6 1 + a P ( b , a − 1 ) − 6 5 − a P ( b , a ) = 1 − 6 1 + b P ( a , b − 1 ) − 6 5 − b P ( a , b ) , so = 1 − 6 1 + a P ( b , a − 1 ) a s d f a s d f a s d f − 6 5 − a ( 1 − 6 1 + b P ( a , b − 1 ) − 6 5 − b P ( a , b ) ) = 6 1 + a − 6 1 + a P ( b , a − 1 ) + 3 6 ( 5 − a ) ( 1 + b ) P ( a , b − 1 ) and this last formula expresses P ( a , b ) in terms of P ( b , a − 1 ) and P ( a , b − 1 ) . Coupled with the initial values P ( m , 0 ) = 0 and P ( 0 , n ) = 1 , this allows us to build up P ( a , b ) inductively.
Using this last formula, the Python code below computes P ( 5 , 5 ) = 1 5 7 0 8 8 7 5 9 , so the answer is 2 4 4 6 7 .
Notes: You can check that P ( 4 , 4 ) = P ( 5 , 5 ) , which makes sense because the game always starts out with each player catching a fish.
Note also that the program computes P ( 1 , 1 ) = 3 / 5 , which is an instructive warmup exercise to work out without computer assistance.