Wild About Math! Making Math fun and accessible

30Jan/092

MMM #25: Monotonous Monday Math Madness

[ See below for MMM #25 ]

Blinkdagger has announced the winner for MMM #24 and I've got a new problem so keep reading.

Rich Berlin noticed the relationship to MMM #1 and submitted an interesting solution, based on Pat Ballew's Markov chain process which I wrote about in March.

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:

--------
require 'matrix'
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
monotonically increasing.

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

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.

Comments (2) Trackbacks (3)
  1. I know this is a bit off subject but I am a graduate student at UNLV as well as a weekly math based podcast called Combinations and Permutations where we start with a mathematical topic and spin off onto as many tangents as we can. You can follow the previous link to the blog page of our podcast, search for us on iTunes, or take a trip over to our host site http://cppodcast.libsyn.com. Give us a try I do think that you will enjoy what you hear.

  2. The obvious generalization for a future challenge would be to find the probability that the number will be monotonically non-decreasing. This would allow numbers like 24579 and 24559, but not 24759 or 24553.

    Clueless.


Leave a comment