Stop the alien invasion!

Today’s puzzle is from The Riddler, and has to do with spherical geometry.

A guardian constantly patrols a spherical planet, protecting it from alien invaders that threaten its very existence. One fateful day, the sirens blare: A pair of hostile aliens have landed at two random locations on the surface of the planet. Each has one piece of a weapon that, if combined with the other piece, will destroy the planet instantly. The two aliens race to meet each other at their midpoint on the surface to assemble the weapon. The guardian, who begins at another random location on the surface, detects the landing positions of both intruders. If she reaches them before they meet, she can stop the attack.

The aliens move at the same speed as one another. What is the probability that the guardian saves the planet if her linear speed is 20 times that of the aliens’?

Here is my solution for the case of interest, where the guardian is faster than the intruders.
[Show Solution]

Here is a partial solution for the more complicated case where the guardian is slower than the intruders.
[Show Solution]

Random walk with endpoints

The Riddler post for today is about a bar game where you flip a coin and move forward or backward depending on the result. Here is the problem:

Consider a hot new bar game. It’s played with a coin, between you and a friend, on a number line stretching from negative infinity to positive infinity. (It’s a very, very long bar.) You are assigned a winning number, the negative integer -X, and your friend is assigned his own winning number, a positive integer, +Y. A marker is placed at zero on the number line. Then the coin is repeatedly flipped. Every time the coin lands heads, the marker is moved one integer in a positive direction. Every time the coin lands tails, the marker moves one integer in a negative direction. You win if the coin reaches -X first, while your friend wins if the coin reaches +Y first. (Winner keeps the coin.)

How long can you expect to sit, flipping a coin, at the bar? Put another way, what is the expected number of coin flips in a complete game?

Here is my solution:
[Show Solution]

and here is a much slicker solution, courtesy of Daniel Ross:
[Show Solution]

Cutting polygons in half

This Riddler puzzle is about cutting polygons in half. Here is the problem:

The archvillain Laser Larry threatens to imminently zap Riddler Headquarters (which, seen from above, is shaped like a regular pentagon with no courtyard or other funny business). He plans to do it with a high-powered, vertical planar ray that will slice the building exactly in half by area, as seen from above. The building is quickly evacuated, but not before in-house mathematicians move the most sensitive riddling equipment out of the places in the building that have an extra high risk of getting zapped.

Where are those places, and how much riskier are they than the safest spots? (It’s fine to describe those places qualitatively.)

Extra credit: Get quantitative! Seen from above, how many high-risk points are there? If there are infinitely many, what is their total area?

Here is my solution:
[Show Solution]

And here is a bonus interactive graphic showing the solution

How to beat Roger Federer at Wimbledon

This Riddler problem is about the game of tennis!

Your wish has been granted, and you get to play tennis against Roger Federer in his prime in the Wimbledon final. You have only a 1 percent chance to win each point, but Roger, sporting gentleman that he is, offers to let you name any score and begin the match at that point. (So, if you’ve entertained a fantasy of storming back after being down three match points in the fifth set, now’s the time to live it.) What score can you name that gives you the best chance to win, and what is your chance of winning the title?

A rough (and approximate) solution:
[Show Solution]

A more detailed (and exact) solution:
[Show Solution]

What if robots cut your pizza?

This Riddler puzzle is about random chords of a circle and the regions they describe.

At RoboPizza™, pies are cut by robots. When making each cut, a robot will randomly (and independently) pick two points on a pizza’s circumference, and then cut along the chord connecting them. If you order a pizza and specify that you want the robot to make exactly three cuts, what is the expected number of pieces your pie will have?

Here is a simple solution, which was pointed out to me in a comment to my original post.
[Show Solution]

The following solution is a bit more complicated, and computes the entire distribution rather than just its expected value.
[Show Solution]

If you’ve already read the solution above and you’re interested in the distribution of pieces for the general case, read on!
[Show Solution]

The puzzle of the picky eater

Today’s Riddler post is a neat problem about calculating areas.

Every morning, before heading to work, you make a sandwich for lunch using perfectly square bread. But you hate the crust. You hate the crust so much that you’ll only eat the portion of the sandwich that is closer to its center than to its edges so that you don’t run the risk of accidentally biting down on that charred, stiff perimeter. How much of the sandwich will you eat?

Extra credit: What if the bread were another shape — triangular, hexagonal, octagonal, etc.? What’s the most efficient bread shape for a crust-hater like you?

Here is my solution:
[Show Solution]

The blue-eyed islanders

Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.

A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”

What happens then? Why?

Here is the solution:
[Show Solution]

The puzzle of the pirate booty

Today’s puzzle was posed on the Riddler blog, but it’s actually a classic among problem-solving enthusiasts, and is commonly known as the pirate game. Here is the formulation used in the Riddler:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

  1. Self-preservation: A pirate values his life above all else.
  2. Greed: A pirate seeks as much gold as possible.
  3. Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is the solution to the main problem:
[Show Solution]

And here is a solution to the general case:
[Show Solution]

If this sort of problem interests you, I recommend taking a crack at the riddle of the blue-eyed islanders, or the unfaithful husbands. More information here as well.

Baseball division champs

Today’s post is a Riddler problem about baseball, and it goes like this:

Assume you have a sport (let’s call it “baseball”) in which each team plays 162 games in a season. Assume you have a division of five teams (call it the “AL East”) where each team is of exact equal ability. Specifically, each team has a 50 percent chance of winning each game. What is the expected value of the number of wins for the team that finishes in first place?

The problem statement is a bit vague, so we must make some assumptions in order to solve the problem. Our first solution assumes that the win-loss records of the teams are mutually independent.
[Show Solution]

This next solution explains how to tackle the more realistic case where the games are not played independently, and explains why the independence assumption is a good one for the AL East.
[Show Solution]

Double-counting, Part 2

This post is a follow-up to Part 1, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills!

First identity. This is Vandermonde’s Identity.
\[
\sum_{k=0}^p {m \choose k}{n \choose p-k} = {m+n \choose p}
\]

[Show Solution]

Second identity. This is the Christmas Stocking Identity. It is also sometimes called the Hockey-Stick Identity.
\[
\sum_{k=0}^m {n+k \choose n} = {m+n+1 \choose n+1}
\]

[Show Solution]

Third identity. This one looks similar to the first one, but notice that the upper coefficient is varying this time.
\[
\sum_{k=0}^p {k \choose m}{p-k \choose n} = {p+1 \choose m+n+1}
\]

[Show Solution]