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

Coin Jam - What I Did (Google CodeJam 2016)

In my quest to learn more about this competition that I just recently discovered, I came across this page where the Google Code Jam problem authors discuss their process for creating well-designed competition problems.  The whole thing was an enlightening read, but I mention it here to reference the section where they discuss problem difficulty, which ends with this:

This is (very roughly) what we aim for in Code Jam's qualification round: easy; easy, but insight required; medium-hard.

When I read this it made perfect sense to me in the context of the Qualification Round problems I've been documenting here.  The first problem was easy.  The second problem was easy, once you had the right insight about how to optimally flip the pancakes.  With that said, we now move onto the third problem where the difficulty definitely ramps up.

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

Counting Sheep (Google CodeJam 2016)

The first (and presumably easiest) of the four problems in the Qualification Round is a pretty straightforward counting problem:

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

What is the last number that she will name before falling asleep?

Continue reading

My CodeJam Experiment

A few weeks back I saw a mention of Google Code Jam 2016.  I'm relatively new to programming but I love a good challenge.  So I registered, figuring it would be a good test of what I've learned so far.  However, I pretty quickly forgot about it, and would've totally missed it if not for an email reminder yesterday.  I felt totally unprepared but decided to give it a shot, and here's what happened...

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