Beemer (dr_tectonic) wrote,
Beemer
dr_tectonic

math

I am a super-mega-dork, because I stayed up until stupid o'clock last night working on a math problem.

Technology Review (which all MIT alumni get) has a puzzle column, and I was reading it last night and got sucked in to the raquetball problem, which goes like this:

In racquetball, if the server doesn't score a point, the other guy gets to serve. Whoever gets 15 points first wins. If the score is 13 to 14, the guy with 13 points is serving, and we assume that whoever serves has probability p of scoring a point, what does p have to be for it to be more likely that the guy with 13 points will win the game?

The answer is, "a little bit more than 55% or greater", and you totally don't care where that comes from, but I feel like explaining it anyway. Luckily for you, I'm nice and will hide it behind a cut rather than inflict it upon you involuntarily.

The thing that makes this tricky is the fact that if the server doesn't score a point, the serve passes to the other player, and it can go back and forth over and over as long as nobody scores a point. Figuring out how this translates into numbers (well, letters) is easier if you draw a little diagram showing the different possible states, like this:

(13)/14 <-- q --> 13/(14) -- p --> 13/15*
    \
     \
      -- p --> (14)/14 <-- q --> 14/(14) -- p --> 14/15*
                   \
                    \
                     -- p --> 15/14*


Notation: (13)/14 means player A has 13 points and player B has 14, player A is serving; the * indicates a final state where someone has won, and the arrows show the transitions between states with the probability of that transition.

So we can move from the initial state to 13/15* by going qp, or qqqp, or qqqqqp, and so on. We can get to player A winning by pp, or by qqqqpp, or pqqp, and so on. Recall that probability of X and Y = P(X and Y) = P(X)*P(Y), and P(X or Y) = P(X) + P(Y). Thus:

P(Player A wins) = (p + q2p + q4p + ...) · (p + q2p + q4p + ...)
and
P(Player A loses) = (qp + q3p + q5p + ...) + p (qp + q3p + q5p + ...)

Which we can rewrite as:

Condition for A winning = [p ∑n=0(q2)n]2 > pq(1+p) ∑n=0(q2)n

Now, since |q2|<1 (q is a probability, hence between 1 and 0), the sum is a geometric series, and it's equal to 1/(1-q2). Which gives us for the win condition:

p/(1-q2) · p/(1-q2) > pq(1+p)/(1-q2)

Cancel out a p/1-q2, multiply by 1-q2, and you can rewrite that as

p > q (1+p)(1-q2)

Now substitute back in q = (1-p), do a lot more algebraic rearrangement, and you end up with

p3 - 2p2 - p + 1 < 0

Does that give us an answer? Well, it's a cubic, so there's at least one real root, and p=0 gives us 1, while p=1 gives us -1, so it must cross zero somewhere between the two, which means there's a solution. Awesome!

Now, at this point, we could look up and plug numbers into the cubic formula, which is incredibly hairy, but it's much easier to just throw numbers into a spreadsheet real quick or google a cubic equation calculator, both of which will give you in short order a value of something like 0.55496. So player A is more likely to win than lose if p is greater than 0.55498. Hurrah!

I also found a covering of the chessboard with 12 knights, but I can't prove that's the minimum number you need, though I'm pretty sure it is.

EDIT: I found a site that has knight coverings! Optimality proofs down at the bottom.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 18 comments