Halloween Puzzle

This week’s Fiddler is about rounding!

You are presented with a bag of treats, which contains $n \geq 3$ peanut butter cups and some unknown quantity of candy corn kernels (with any amount being equally likely). You reach into the bag $k$ times, with $3 \leq k \leq n$, and pull out a candy at random. Each time, it’s a peanut butter cup! How many candy kernels do you expect to be in the bag?

My solution:
[Show Solution]

Tiling a Tilted Square

This week’s Fiddler is a challenging counting problem.

Consider the following array of 25 squares:

You are filling the array with rectangles by repeating the following two steps:

  1. Select one of the 12 squares along the outer perimeter that has not yet been selected as part of a rectangle.
  2. Form the largest rectangle you can that includes the square you just selected and other squares that are not yet part of any such rectangle.

You repeat these steps until every square along the perimeter has been selected. Here are two final states you might encounter:

How many distinct final states are possible? (Note: States that are rotations or reflections of each other should be counted as distinct.)

My solution:
[Show Solution]

Picking a speaker at random

This week’s Fiddler is about selecting a speaker of the house at random. How long will it take?

There are three candidates who want the job of Speaker. All 221 members of the party vote by picking randomly from among the candidates. If one candidate earns the majority of the votes, they become the next Speaker. Otherwise, the candidate with the fewest votes is eliminated and the process is repeated with one less candidate. If two or more candidates receive the same smallest number of votes, then exactly one of them is eliminated at random. What is the average number of rounds needed to select a new Speaker?

Extra Credit
What if there were 10 candidates running for Speaker?

My solution:
[Show Solution]

The slow car chase

This week’s Fiddler is a problem about probability and a slow car chase!

You and your pursuer are stopped at traffic lights one block away from each other, as shown below. For both cars, it takes 1 minute to get to each subsequent light, and there is a 50-50 chance any light will be red upon arrival (independent of what happened previously). If a light is red, you must wait one minute before it turns green. What is the probability you will make it to the city limits without being caught by your pursuer?

Extra Credit
In the same scenario as before, imagine there are infinitely many lights. On average, how many minutes will it be until you are ultimately caught?

My solution:
[Show Solution]

Braille puzzle

This week’s Fiddler is a counting problem about the Braille system.

Braille characters are formed by raised dots arranged in a braille cell, a three-by-two array. With six locations for dots, each of which is raised or unraised, there are 26, or 64, potential braille characters.

Each of the 26 letters of the basic Latin alphabet (shown below) has its own distinct arrangement of dots in the braille cell. What’s more, while some arrangements of raised dots are rotations or reflections of each other (e.g., E and I, R and W, etc.), no two letters are translations of each other. For example, only one letter (A) consists of a single dot – if there were a second such letter, A and this letter would be translations of each other.

Of the 64 total potential braille characters, how many are in the largest set such that no two characters consist of raised dot patterns that are translations of each other?

Extra Credit In addition to six-dot braille, there’s also an eight-dot version. But what if there were even more dots? Let’s quadruple the challenge by doubling the size of the cell in each dimension. Consider a six-by-four array, where a raised dot could appear at each location in the array. Of the 224 total potential characters, how many are in the largest set such that no two characters are translations of each other?

My solution:
[Show Solution]

Making something out of nothing

This week’s Fiddler is a problem about composing functions. Here it goes:

Consider $f(n) = 2n+1$ and $g(n) = 4n$. It’s possible to produce different whole numbers by applying combinations of $f$ and $g$ to $0$. How many whole numbers between $1$ and $1024$ (including $1$ and $1024$) can you produce by applying some combination of $f$’s and $g$’s to the number $0$?

Extra Credit: Now consider the functions $g(n) = 4n$ and $h(n) = 1−2n$. How many integers between $-1024$ and $1024$ (including $-1024$ and $1024$) can you produce by applying some combination of $g$’s and $h$’s to the number $0$?

My solution:
[Show Solution]

Loteria

This week’s Riddler Classic is about Lotería, also known as Mexican bingo!

A thousand people are playing Lotería, also known as Mexican bingo. The game consists of a deck of 54 cards, each with a unique picture. Each player has a board with 16 of the 54 pictures, arranged in a 4-by-4 grid. The boards are randomly generated, such that each board has 16 distinct pictures that are equally likely to be any of the 54.

During the game, one card from the deck is drawn at a time, and anyone whose board includes that card’s picture marks it on their board. A player wins by marking four pictures that form one of four patterns, as exemplified below: any entire row, any entire column, the four corners of the grid and any 2-by-2 square.

Four four-by-four grids are shown. In the first grid, the third row has four blue markers. In the second grid, the second column has four blue markers. In the third grid, the four corner squares are marked. And in the fourth grid, the two middle squares in the third and fourth columns are marked, forming a smaller two-by-two square.

After the fourth card has been drawn, there are no winners. What is the probability that there will be exactly one winner when the fifth card is drawn?

My solution:
[Show Solution]

Shared birthdays

This week’s Riddler Classic is a challenging counting problem about shared birthdays.

Suppose people walk into a room, one at a time. Their birthdays happen to be randomly distributed throughout the 365 days of the year (and no one was born on a leap day). The moment two people in the room have the same birthday, no more people enter the room and everyone inside celebrates by eating cake, regardless of whether that common birthday happens to be today.

On average, what is the expected number of people in the room when they eat cake?

Extra credit: Suppose everyone eats cake the moment three people in the room have the same birthday. On average, what is this expected number of people?

My solution:
[Show Solution]

Knocking down the last bowling pin

This week’s Riddler classic is a tough one! Here is a paraphrased version of the problem.

Imagine $n^2$ bowling pins arranged in a rhombus. The image to the right illustrates the case $n=3$. We knock down the topmost pin. When any pin gets knocked down, each of the (up to two) pins directly behind it has a probability $p$ of being knocked over (independently of each other). We are interested in the probability that the bottommost pin gets knocked down in the limit of large $n$.

The original problem specifically asked about $p=0.5$ and $p=0.7$.

My solution:
[Show Solution]

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]