Tower of goats

This week’s Riddler classic is a counting problem. Can the goats fit in the tower?

A tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor. One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower. What is the probability that all 10 goats will have their own floor, meaning no goat is left stranded on the roof of the tower?

My solution:
[Show Solution]

Penny Pinching

This week’s Riddler Classic is indeed a classic! Here it goes (paraphrased to make it a bit more general):

The game starts with $n$ pennies, which I then divide into two piles any way I like. Then we alternate taking turns, with you first, until someone wins the game. For each turn, a player may take any number of pennies he or she likes from either pile, or instead take the same number of pennies from both piles. Each player must also take at least one penny every turn. The winner of the game is the one who takes the last penny.

If we both play optimally, what starting numbers of pennies guarantee that you can win the game?

Here is my solution:
[Show Solution]

Paths to work

This Riddler puzzle is a classic problem: how many lattice paths connect two points on a grid? Here is a paraphrased version of the problem.

The streets of Riddler City are laid out in a perfect grid. You walk to work each morning and back home each evening. Restless and inquisitive mathematician that you are, you prefer to walk a different path along the streets each time. How many different paths are there? (Assume you don’t take paths that are longer than required). Your home is M blocks west and N blocks south of the office.

Here is my solution:
[Show Solution]

Card collection completion

This Riddler puzzle is a classic probability problem: how long can one expect to wait until the entire set of cards is collected?

My son recently started collecting Riddler League football cards and informed me that he planned on acquiring every card in the set. It made me wonder, naturally, how much of his allowance he would have to spend in order to achieve his goal. His favorite set of cards is Riddler Silver; a set consisting of 100 cards, numbered 1 to 100. The cards are only sold in packs containing 10 random cards, without duplicates, with every card number having an equal chance of being in a pack.

Each pack can be purchased for \$1. If his allowance is \$10 a week, how long would we expect it to take before he has the entire set?

What if he decides to collect the more expansive Riddler Gold set, which has 300 different cards?

Here is my solution:
[Show Solution]

Smudged secret messages

This Riddler is a twist on a classic problem: decoding equations! Here is the paraphrased problem:

The goal is to decode two equations. In each of them, every different letter stands for a different digit. But there is a minor problem in both equations. In the first equation, letters accidentally were smudged and are now unreadable. (These are represented with dashes below.) But we know that all 10 digits, 0 through 9, appear in the equation.

What digits belong to what letters, and what are the dashes? In the second equation, one of the letters in the equation is wrong. But we don’t know which one. Which is it?

Here is my detailed solution:
[Show Solution]

If you’re just interested in the answers, here they are:
[Show Solution]

Minimal road networks

This Riddler problem is about efficient road-building!

Consider four towns arranged to form the corners of a square, where each side is 10 miles long. You own a road-building company. The state has offered you \$28 million to construct a road system linking all four towns in some way, and it costs you \$1 million to build one mile of road. Can you turn a profit if you take the job?

Extra credit: How does your business calculus change if there were five towns arranged as a pentagon? Six as a hexagon? Etc.?

Here is a longer explanation:
[Show Solution]

Here is the solution with minimal explanation:
[Show Solution]

Inscribed triangles and tetrahedra

The following problems appeared in The Riddler. They involve randomly picking points on a circle or sphere and seeing if the resulting shape contains the center or not.

Problem 1: Choose three points on a circle at random and connect them to form a triangle. What is the probability that the center of the circle is contained in that triangle?

Problem 2: Choose four points at random (independently and uniformly distributed) on the surface of a sphere. What is the probability that the tetrahedron defined by those four points contains the center of the sphere?

Here is my solution to both problems:
[Show Solution]

The troll and the dwarves

This Riddler puzzle is a classic! Can you save the dwarves from the troll?

A giant troll captures 10 dwarves and locks them up in his cave. That night, he tells them that in the morning he will decide their fate according to the following rules:

  1. The 10 dwarves will be lined up from shortest to tallest so each dwarf can see all the shorter dwarves in front of him, but cannot see the taller dwarves behind him.
  2. A white or black dot will be randomly put on top of each dwarf’s head so that no dwarf can see his own dot but they can all see the tops of the heads of all the shorter dwarves.
  3. Starting with the tallest, each dwarf will be asked the color of his dot.
  4. If the dwarf answers incorrectly, the troll will kill the dwarf.
  5. If the dwarf answers correctly, he will be magically, instantly transported to his home far away.
  6. Each dwarf present can hear the previous answers, but cannot hear whether a dwarf is killed or magically freed.

The dwarves have the night to plan how best to answer. What strategy should be used so the fewest dwarves die, and what is the maximum number of dwarves that can be saved with this strategy?

Extra credit: What if there are only five dwarves?

Here is my solution:
[Show Solution]

The honest prince

This Riddler puzzle is about randomly generating convex quadrilaterals.

You’re the most eligible bachelorette in the kingdom, and you’ve decided to marry a prince. The king has invited you to his castle so that you may choose from among his three sons. The eldest prince is honest and always tells the truth. The youngest prince is dishonest and always lies. The middle prince is mischievous and tells the truth sometimes and lies the rest of the time. Because you will be forever married to one of the princes, you want to marry the eldest (truth-teller) or the youngest (liar) because at least you know where you stand with each. But there’s a problem: You can’t tell the princes apart just by looking, and the king will grant you only one yes-or-no question that you may address to only one of the brothers.

What yes-or-no question can you ask that will ensure that you do not marry the middle prince?

Here is my solution:
[Show Solution]

Space race

This Riddler puzzle is about a game involving filling up the space on a square table using coins.

Two players are seated at a square table. The first player places a coin on the table, the second places a coin on the table, and they carry on placing coins one after another, with the only condition being that the coins are not allowed to touch. The winner is the person who places the final coin on the table, meaning that he or she fills the last remaining space between the other coins.

The table has to be larger than a single coin, and all the coins placed must be identically sized. If the players play optimally, is one of the two players guaranteed to win? If so, what is the winning strategy?

Need a hint?
[Show Solution]

Here is my solution:
[Show Solution]