Author |
Topic: MISSISSIPPI (Read 603 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
A circular spinner is divided into four sectors, labelled with the letters M, I, S, and P, respectively. The relative sizes of the sectors can be varied. Each time the spinner is spun, it comes to rest at a random point on the circumference, thereby indicating a letter.
The spinner is spun 11 times, without adjusting the sector sizes between spins. What should the relative sizes of the sectors be in order to maximize the probability that the word "MISSISSIPPI" is spelt out, and what is that probability?
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
 |
Re: MISSISSIPPI
« Reply #1 on: Jun 6th, 2003, 5:09pm » |
 Quote  Modify
|
Would not the answer be
M = 1/11
I = 4/11
S = 4/11
P = 2/11
and the probability 1*44*44*22/1111 = 218/1111 ~ 1/1,000,000?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: MISSISSIPPI
« Reply #3 on: Jun 6th, 2003, 9:06pm » |
Quote Modify
|
Yes: Letting m, i, s, p represent the respective relative sector size, the probability of spelling MISSISSIPPI is mi4s4p2. The question is to maximize this subject to the restraint m+i+s+p = 1. Differentiating and setting to zero for the extremum gives
i4s4p2dm + 4mi3s4p2di + 4mi4s3p2ds + 2mi4s4pdp = 0
Simplifying,
ispdm + 4mspdi + 4mipds + 2misdp = 0
Also from the constraint,
dm + di + ds + dp = 0.
The only way to satisfy the first eqution for all solutions of the second is if the coefficients are pairwise equal. Thus
isp = 4msp ==> i = 4m.
isp = 4mip ==> s = 4m.
isp = 2mis ==> p = 2m.
m + i + s + p = 1 ==> m = 1/11, i = s = 4/11, p = 2/11, and the probability is (1/11)(4/11)4(4/11)4(2/11)2 = 218/1111.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: MISSISSIPPI
« Reply #4 on: Jun 7th, 2003, 3:16pm » |
Quote Modify
|
A non-calculus solution is... to use the AM-GM inequality.
We must maximize mi4s4p2, subject to m + i + s + p = 1.
Then (m + i/4 + i/4 + i/4 + i/4 + s/4 + s/4 + s/4 + s/4 + p/2 + p/2)/11 >= (mi4s4p2/218)1/11, and so
mi4s4p2 <= 218/1111, with equality iff m = i/4 = s/4 = p/2.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: MISSISSIPPI
« Reply #5 on: Jun 8th, 2003, 8:02pm » |
Quote Modify
|
And how is the AM-GM inequality proved?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: MISSISSIPPI
« Reply #6 on: Jun 8th, 2003, 9:44pm » |
Quote Modify
|
AM-GM inequality can be proved by induction
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: MISSISSIPPI
« Reply #7 on: Jun 9th, 2003, 12:44am » |
Quote Modify
|
on Jun 8th, 2003, 8:02pm, Icarus wrote:| And how is the AM-GM inequality proved? |
|
Using Jensen's inequality, f((x1+x2+...+xn)/n)<=(f(x1)+f(x2)+...+f(xn ))/n holds for convex functions.
As ln(x) is a convex function, ln((x1+x2+...+xn)/n)<=(ln(x1)+ln(ln2)+...+ln(lnn))/n=ln((x1*x2*...*xn)(1/n) )
Therefore (x1+x2+...+xn)/n)<=(x1*x2*...*x n) (1/n).
That is, geometric mean of x1,x2,...,xn<=arithmetic mean of x1,x2,...,xn.
Although I don't know how to prove Jensen's inequality. 
(I believe it is by a method of forwards and backwards induction?)
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: MISSISSIPPI
« Reply #9 on: Jun 9th, 2003, 4:58pm » |
Quote Modify
|
Interesting - I have never heard of that one before. There is a small error in the statement of the inequality on that page by the way. It says that equality only holds when the rearrangment is trivial (ie - not a rearrangement at all). But equality will also hold if all the b[sub]k[/sup] are equal.
Still, when finding extrema, calculus is generally a good place to start looking. (Of course, I just posted a couple days ago on another thread about experience blinding people to other ways of doing things...  )
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print