# My Favorite Puzzle to Introduce Computer Science to Teenagers

Last week, a group of Japanese middle and high school kids flew from Tokyo to Silicon Valley. They visited local tech companies and attended fireside-chat style talks by Japanese expats working at those companies.

Tours like this is common nowadays, encouraging Japanese youngsters to look abroad. I volunteer as a speaker several times a year; in March, with kids visiting from my hometown Yokohama, we played a bingo game using rally speeches by Donald Trump and Bernie Sanders, to help them understand the 2016 Election.

I volunteered to speak again, and this time I decided to give kids a quick introduction to Computer Science. I majored in it (Carnegie Mellon Class of 2010), and without computer science and computer scientists, Silicon Valley would not exist.

To make it fun, we played an algorithms puzzle proposed by Danish computer scientist Peter Bro Miltersen in 2003. I heard about this puzzle in college, and recently again on Quora. It’s known as *The 100 prisoners problem*, and there’s a Wikipedia entry. Explanations on the Wikipedia article might seem technical, just like any other math articles Wikipedia, so here I’ll try to explain this problem in plain English.

### Introduction

There were 10 Japanese kids who participated in my workshop, and we’ll call them as A, B, C, D, E, F, G, H, I, and J. We also have 10 cards, and each card has a kid’s name.

There are two rooms: the big room and the small room. Kids wait in the big room, and in the small room, there’s a table where those cards are placed horizontally in a *random* order (below is an example). The cards are placed *facing down*, so kids don’t know which card is which.

From the big room, kids can’t see the inside of the small room. At each turn, one kid goes to the small room, and flips **five** out of the ten cards. If the kid can find his/her name in these five flips, that’s a **success**; otherwise, that’s a **failure.**

Kids must put all the cards face down after each turn, and cannot change the order of the cards.

Furthermore, **kids cannot communicate with each other once the game starts.** So they won’t be able to pass any information about each card between the turns. Each kid is on his/her own.

Naturally, kids would draw cards at random, and the chance of success is 50% each time. We tried this, and out of 10 kids, 5 successfully found their name and 5 failed to do so.

### Different Scenario

Suppose that there’s **the 11th person (call him/her “X”) **who can join to help the kids out (we had one of the tour conductors play this role). Person X can do the following:

- Person X will go into the small room before everyone else.
**Person X can flip all the cards, and either swap the positions of two cards, or do nothing.**When that’s done, person X must flip the cards back facing down again.**However, person X cannot communicate with the kids****afterwards**— so she won’t be able to pass the information about the cards.

### The Problem

Here’s the question:

Person X and the 10 kids can agree on a strategy before the game starts*.* And the goal is to **maximize** the number of kids who can find their own name. **What would be the optimal strategy, and how many kids will be able to find their name on average?**

I’ll give you an answer to one of the two questions. **There exists a strategy that, every single kid can find his/her name 100% of the time.**

Yes you read that right.

Consider “pick five cards at random” approach we tried before. The probability that each kid finds his/her name is 50%, so the probability that everyone finds his/her name is: (0.5)(0.5)…(0.5) = 0.5¹⁰ =0.1%. So they’d have to try about a thousand times before succeeding.

But there’s a clever strategy which guarantees everyone’s success. And the strategy can be understood by a ten year old. Can you think of one? **Remember**: once the game starts, there’s no communications allowed.

### Try to think for a few minutes before you read on…

I’ll give you the first hint on the next section, so pause here if you don’t want to be spoiled.

### First Hint

Try not to think about what person X should do yet. Instead, try to think about **which card each kid should flip at first.**

Again, think for a few minutes before you read on…

### Second Hint

Here’s an idea: each kid agrees on which card he/she would draw first. Let’s say that kid A picks the leftmost card, kid B picks the one next to it, and so on.

If they try this strategy, each kid will not find his/her own name on the first try.

Kid A will see the card that says “E,”kid B will see the card that says “H,” and so on. But they’ve got four more tries. **Which card should each kid pick on the second draw?**

Again, think for a few minutes before you read on…

### Third Hint

How about this: kid A picked the card that says “E” on the first draw. **So for the second draw, kid A picks what kid E would pick on his/her first draw. **Kid E would pick the fifth card from the left (D), so kid A should pick that for the second draw.

Let’s continue: kid A found “D” on his/her second draw. For the third pick, kid A picks what kid D would pick on his/her first draw. That would be the fourth card from the left, which says “F.” So go to kid F’s pick next, which would be the sixth card from the left.

Now this is interesting. Consider the case for kid E. Kid E will first flip his/her assigned card, which is the fifth one from the left and says “D.” If you follow kid E’s 2nd and 3rd pick, you’ll notice that:

- E’s 1st pick = A’s 2nd pick.
- E’s 2nd pick = A’s 3rd pick.
- E’s 3rd pick = A’s 4th pick.
- …and so on.

How about kid D? If you write his/her draws, you’ll notice that:

- D’s 1st pick = E’s 2nd pick = A’s 3rd pick.
- D’s 2nd pick = E’s 3rd pick = A’s 4th pick.
- …and so on.

So it looks like kid A, E, and D are following the **same path**. E is one step behind A, and D is one step behind E.

Now, here’s a question:** in the above ordering of cards,** **how many different sets of paths are there? And what’s the longest path?**

Take a moment to enumerate all the paths. I’ll wait for you.

### Fourth Hint

In this ordering of cards,** there’s only 1 path of length 10**, and every single kid follows the same path.

The path can be written as (starting from kid A’s first draw):

- E → D → F → G → B → H → J → I → C → A → (loops back to E)

**And every kid will find his/her pick on the 10th draw** (if they’re allowed to continue beyond 5 draws). More importantly, this is when the path **“loops” back to the beginning**.

On kid A’s 10th draw, it’ll say “A,” and if this kid were to continue after finding his/her name, the 11th draw will be the same as the 1st draw, and the 12th draw will be the same as the 2nd draw — the path “loops.”

By using this strategy, the kid finds his/her name **right when the path loops back to the beginning**. **Thus, the length of the path a kid is on before it loops back (in this case, 10) is the number of picks it takes for the kid to find his name.**

To illustrate this better, I’ve created a different ordering like below. In this case, kid A is on path of length 5 before it loops back, so he’ll find his name on the 5th draw.

The path kid A belongs to is (starting from kid A’s first draw):

- E → D → F → G → A → (loops back to E)

Now, how about the path for kid B?

Turns out that his/her path is also of length 5 (starting from kid B’s first draw):

- H → J → I → C → B → (loops back to H)

If you actually try playing as other kids, you’ll notice that **every kid belongs to either A’s path or B’s path.** Kids D, E, F, and G belong to A’s path, and kids C, H, I, and J belong to B’s path. And because both paths are of length 5 before they loop back, **every kid can find his/her name on the 5th draw**.

Wait, what? We just beat the game!

But that’s only because the longest path in this new ordering was of length 5. In the previous case, the longest path was of length 10, and everyone was on this path. It really depends on the initial ordering of the cards.

Or does it? **Remember the person X who can look at all the cards and swap two if desired?** Can person X do something to ensure that the longest path is of length 5 or shorter?

### Solution

Turns out that it’s possible. If you look at the previous 2 orderings, the second ordering is actually the same as the first, except the positions of “A” and “B” were swapped.

If you recall the longest path on the first ordering, it was:

- E → D → F → G → B → H → J → I → C → A → (loops back to E)

This path of length 10 can be **cut in half** by swapping its 5th card (B) and 10th card (A):

- E → D → F → G →
**A**→ (loops back to E) - H → J → I → C →
**B**→ (loops back to H)

Similarly, if there was a path of length 8, it can be split into two paths of length 4 by swapping its 4th card and 8th card.

**So, this is what person X must do:**

- Look at all the cards, and enumerate all the different paths kids will follow.
- If there’s NO path of length longer than 5, do nothing.
- If there’s a path of length longer than 5, then swap the middle card in the path with the last card in the path.
- Note that there can’t be more than one path that are longer than 5 cards — then we’d have more than 10 cards in total.

Then the kids just need to follow their path, and they’re guaranteed to find their name within the first 5 draws.

This strategy can work even when there are 100 kids picking 50 out of 100 cards, although that’d take a really long time to finish.

### Lessons Learned

I think this problem is a great introduction to computer science because the problem contains these essential ingredients:

**Algorithms**: an algorithm is a process or set of rules to be followed in calculations or other problem-solving operations. In today’s problem, the “random” (suboptimal) algorithm was to pick random five cards, and the algorithm for the winning strategy was to assign cards to each kid, and draw the card pointed by the previous card at each step.**Graphs**: a lot of computer science problems involve graphs, which consist of nodes and edges connecting two nodes (see below). For example, one can construct a graph based on who follows who on Instagram, and run some graph algorithm to find a user “who you might know.” In today’s problem, a graph was constructed by following a path each kid follows.

**Patterns:**A key to solving a computer science problem is to notice patterns. In today’s problem, the key patterns were (1) some kids follow the same path, and (2) the number of flips it takes to find their name is equal to the length of the path they’re on.

Hope you enjoyed the puzzle and let me know if you have any questions! If you want to learn more about this puzzle, read the Wikipedia entry.