[ See below for MMM #25 ]
Blinkdagger has announced the winner for MMM #24 and I've got a new problem so keep reading.
The technique for solving this is the same as for MMM #1, except the numbers are a bit nastier to work with.
I solved MMM #1 using a decision tree, but as a result of reading Sol's blog I learned the Markov state approach and am happy to use that instead.
Number the states from 0-5, corresponding to the number of different songs that have been played, and create a matrix where each row corresponds to one of the six states and each element in the row contains P(r,c) which is the probability of transitioning from state r to state c. (Row 0 and column 0 could be omitted, and the exponentiation changed, but I think it's clearer this way.)
The matrix looks like this:
0, 1, 0, 0, 0, 0
0, 1/5, 4/5, 0, 0, 0
0, 0, 2/5, 3/5, 0, 0
0, 0, 0, 3/5, 2/5, 0
0, 0, 0, 0, 4/5, 1/5
0, 0, 0, 0, 0, 1
Now we raise the matrix to the 8th power, because we're making 8 independent choices. Call the result P. Our answer is in P[0,5], i.e. the probability of transitioning from state 0 all the way to state 5.
Not wanting to do the math by hand, and not knowing matlab, I resorted to Ruby:
p = Matrix[ [0, 1.0 0, 0, 0, 0],
[0, 1/5.0, 4/5.0, 0, 0, 0],
[0, 0, 2/5.0, 3/5.0, 0, 0],
[0, 0, 0, 3/5.0, 2/5.0, 0],
[0, 0, 0, 0, 4/5.0, 1/5.0],
[0, 0, 0, 0, 0, 1.0]]
p8 = p**8
print "The probability of playing all five songs is %6.3f%%\n" % (100*p8[0,5])
The probability of playing all five songs is 32.256%
I may not be able to post over the weekend or on Monday so I'm posting MMM #25 early. You still get till Tuesday after next. This is good, from what Quan says, because this problem is a bit tougher than some others.
Surprise - another counting problem!
A number is considered to be monotonically increasing
if each digit is greater than the one preceding it. For
example, 24579 is monotonically increasing but 24559 is
not (the 4th digit is not greater than the third digit) nor is
24759 (the 4th digit is not greater than the third digit.)
If you randomly select a number between 1 and 1,000,000
what is the probability that the number will be monotonically
increasing? Assume that all single-digit numbers are
While you are welcome to write a computer program to
verify your answer, to be eligible for a prize you must
demonstrate how to solve the problem without use of a
Here are the rules for the contest:
1. Email your answers with solutions to mondaymathmadness at gmail dot com.
2. Only one entry per person.
3. Each person may only win one prize per 12 month period. But, do submit your solutions even if you are not eligible.
4. Your answer must be explained. You must show your work! Wild About Math! and Blinkdagger will be the final judges on whether an answer was properly explained or not.
5. The deadline to submit answers is Tuesday, February 10, 12:01AM, Pacific Time. (That’s Tuesday morning, not Tuesday night.) Do a Google search for “time California” to know what the current Pacific Time is.)
6. The winner will be chosen randomly from all timely well-explained and correct submissions, using a random number generator.
7. The winner will be announced Friday, February 13, 2009.
8. The winner (or winners) will receive a Rubik’s Revolution or a $10 gift certificate to Amazon.com or $10 USD via PayPal. For those of you who don’t want a prize I’ll donate $10 to your favorite charity.
9. Comments for this post should only be used to clarify the problem. Please do not discuss ANY potential solutions.
10. I may post names and website/blog links for people submitting timely correct well-explained solutions. I’m more likely to post your name if your solution is unique.