Tag Archives: puzzle

538 Riddler: The Perplexing Puzzle Of The Proud Partygoers

It's party time at this week's Riddler:

It’s Friday and that means it’s party time! A group of people are in attendance at your shindig, some of whom are friends with each other. (Let’s assume friendship is symmetric — if person A is friends with person B, then B is friends with A.) Suppose that everyone has at least one friend at the party, and that a person is “proud” if her number of friends is strictly larger than the average number of friends that her own friends have. (A competitive lot, your guests.)

Importantly, more than one person can be proud. How large can the share of proud people at the party be?

Continue reading

538 Riddler: Can You Solve The Puzzle Of Your Misanthropic Neighbors?

This week's Riddler involves some not-so-nice neighbors:

The misanthropes are coming. Suppose there is a row of some number, N, of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s the expected fraction of occupied houses as the development gets larger, that is, as N goes to infinity?

Continue reading

538 Riddler: You Have $1 Billion To Win A Space Race. Go.

This week's Riddler is a race into space:

You are the CEO of a space transport company in the year 2080, and your chief scientist comes in to tell you that one of your space probes has detected an alien artifact at the Jupiter Solar Lagrangian (L2) point.

You want to be the first to get to it! But you know that the story will leak soon and you only have a short time to make critical decisions. With standard technology available to anyone with a few billion dollars, a manned rocket can be quickly assembled and arrive at the artifact in 1,600 days. But with some nonstandard items you can reduce that time and beat the competition. Your accountants tell you that they can get you an immediate line of credit of $1 billion.

You can buy:

  1. Big Russian engines. There are only three in the world and the Russians want $400 million for each of them. Buying one will reduce the trip time by 200 days. Buying two will allow you to split your payload and will save another 100 days.
  2. NASA ion engines. There are only eight of these $140 million large-scale engines in the world. Each will consume 5,000 kilograms of xenon during the trip. There are 30,000 kg of xenon available worldwide at a price of $2,000/kg, so 5,000 kg costs $10 million. Bottom line: For each $150 million fully fueled xenon engine you buy, you can take 50 days off of the trip.
  3. Light payloads. For $50 million each, you can send one of four return flight fuel tanks out ahead of the mission, using existing technology. Each time you do this, you lighten the main mission and reduce the arrival time by 25 days.

What’s your best strategy to get there first?

Continue reading

Revenge of the Pancakes! (Google CodeJam 2016)

In the second problem of the Qualification Round we find ourselves in a strange IHOP:

The Infinite House of Pancakes has just introduced a new kind of pancake! It has a happy face made of chocolate chips on one side (the "happy side"), and nothing on the other side (the "blank side").

You are the head waiter on duty, and the kitchen has just given you a stack of pancakes to serve to a customer. Like any good pancake server, you have X-ray pancake vision, and you can see whether each pancake in the stack has the happy side up or the blank side up. You think the customer will be happiest if every pancake is happy side up when you serve them.

You know the following maneuver: carefully lift up some number of pancakes (possibly all of them) from the top of the stack, flip that entire group over, and then put the group back down on top of any pancakes that you did not lift up.

What is the smallest number of times you will need to execute the maneuver to get all the pancakes happy side up, if you make optimal choices?

Continue reading

538 Riddler: Can You Win This Hot New Game Show?

This Riddler puts us in the shoes of a contestant on an unusual game show:

Two players go on a hot new game show called “Higher Number Wins.” The two go into separate booths, and each presses a button, and a random number between zero and one appears on a screen. (At this point, neither knows the other’s number, but they do know the numbers are chosen from a standard uniform distribution.) They can choose to keep that first number, or to press the button again to discard the first number and get a second random number, which they must keep. Then, they come out of their booths and see the final number for each player on the wall. The lavish grand prize — a case full of gold bullion — is awarded to the player who kept the higher number. Which number is the optimal cutoff for players to discard their first number and choose another? Put another way, within which range should they choose to keep the first number, and within which range should they reject it and try their luck with a second number?

Continue reading

538 Riddler: Can You Best The Mysterious Man In The Trench Coat?

In this Riddler we have a shot to win some cash!

A man in a trench coat approaches you and pulls an envelope from his pocket. He tells you that it contains a sum of money in bills, anywhere from $1 up to $1,000. He says that if you can guess the exact amount, you can keep the money. After each of your guesses he will tell you if your guess is too high, or too low. But! You only get nine tries. What should your first guess be to maximize your expected winnings?

Continue reading

538 Riddler: Should You Shoot Free Throws Underhand?

Just in time for March Madness, a(nother) basketball-themed Riddler:

Consider the following simplified model of free throws. Imagine the rim to be a circle (which we’ll call C) that has a radius of 1, and is centered at the origin (the point (0,0)). Let V be a random point in the plane, with coordinates X and Y, and where X and Y are independent normal random variables, with means equal to zero and each having equal variance — think of this as the point where your free throw winds up, in the rim’s plane. If V is in the circle, your shot goes in. Finally, suppose that the variance is chosen such that the probability that V is in C is exactly 75 percent (roughly the NBA free-throw average).

But suppose you switch it up, and go granny-style, which in this universe eliminates any possible left-right error in your free throws. What’s the probability you make your shot now? (Put another way, calculate the probability that |Y| < 1.)

Continue reading

538 Riddler: Can You Solve The Impossible Puzzle?

In this April Fools' Day Riddler we're asked to solve this "impossible" puzzle:

Three very skilled logicians are sitting around a table — Barack, Pete and Susan. Barack says: “I’m thinking of two natural numbers between 1 and 9, inclusive. I’ve written the product of these two numbers on this paper that I’m giving to you, Pete. I’ve written the sum of the two numbers on this paper that I’m giving to you, Susan. Now Pete, looking at your paper, do you know which numbers I’m thinking of?”

Continue reading

538 Riddler: Will Someone Be Sitting In Your Seat On The Plane?

In this Riddler we are taking flight:

There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?

Continue reading