Activity 17

The Peru Coin Flip — Secret Code Games

Who is this for: Older kids in elementary school and up.

What you should know first: You should be able to count, and know what odd and even numbers are. It also helps to know the words "and" and "or." If you've learned about binary numbers (numbers made only of 0s and 1s), and about "one-way functions" (something easy to do one way but very hard to undo), this activity will make even more sense.

Time needed: About 30 minutes.

Group size: Just one kid, or a whole class.

What you'll learn: How computers use "and" and "or" logic. How to solve a tricky puzzle.

Summary: This activity shows a cool trick. Two people who don't fully trust each other can still flip a coin fairly — even over the phone!

---

The Story

Two soccer teams — one from Lima and one from Cuzco — need to pick who plays at home for the big game. Normally, you'd just flip a coin. But Lima and Cuzco are far apart. Alicia (from Lima) and Benito (from Cuzco) can't meet in person to flip a coin together.

Could they do it over the phone? What if Alicia flips a coin and Benito guesses "heads" or "tails"? That's a problem! If Benito guesses "heads," Alicia could just lie and say, "Sorry, it was tails!" Benito would never know. Even if Alicia told the truth, would Benito believe her if he lost?

So instead, Alicia and Benito build a special "circuit" together, made of and-gates and or-gates. They can even build it over the phone. Everyone gets to see the finished circuit, so it's fair.

What Are And-Gates and Or-Gates?

A "gate" takes in two numbers — either 0 or 1 — and gives out one number.

Think of 1 as true and 0 as false.

• An and-gate gives a 1 (true) only if both numbers going in are 1. Otherwise, it gives a 0.
• An or-gate gives a 1 (true) if at least one number going in is a 1. It only gives a 0 if both numbers are 0.

You can connect gates together, so the output of one gate becomes the input of another. This lets you build bigger, trickier circuits. One example circuit has six inputs (six 0s or 1s going in) and six outputs (six 0s or 1s coming out).

How the Coin Flip Works

1. Alicia secretly picks six numbers (each a 0 or 1).
2. She puts them through the circuit and gets six output numbers.
3. She tells Benito only the output numbers — not her secret input.
4. Benito must guess: did Alicia's secret input have an even or an odd number of 1s in it?
5. If the circuit is tricky enough, Benito can't figure out the answer — he's really just guessing, like flipping a coin!
6. If Benito guesses right, Cuzco gets to host the game. If he guesses wrong, Lima hosts.
7. Finally, Alicia reveals her secret input so Benito can check that it really matches the output she gave him.

Try It Yourself

1. Get into small groups. Each group gets a copy of the circuit sheet and some colored counters (like red and blue buttons).
2. Pick a color for 0 and a color for 1. Write it down so you remember.
3. Place counters on the circuit to show the numbers Alicia picks. Then follow the and-gate and or-gate rules to work out what comes out the other end. Go slowly and carefully!
4. Pick one person to be Alicia and one to be Benito. Alicia picks her secret numbers, works out the output, and tells Benito. Benito guesses odd or even. Then Alicia reveals her secret numbers so everyone can check.

That's it — the coin flip is done!

Can Someone Cheat?

Benito could cheat if he could figure out Alicia's secret input just by looking at the output. That's why Alicia wants the circuit to be a one-way function — easy to solve going forward (input → output), but really hard to solve backward (output → input).

Alicia could cheat if she could find two different secret inputs — one with an odd number of 1s, one with an even number — that both give the same output. Then no matter what Benito guesses, she could pick whichever input proves him wrong! That's why Benito wants a circuit where many different inputs don't lead to the same output.

Sometimes, with a certain output, there's only one possible input that could have made it. If Alicia happens to land on a number like that, Benito can figure out the parity (odd or even) for sure — and win every time! A real computer system would use way more digits, so there'd be too many possibilities for anyone to cheat. (Each extra digit doubles the number of possibilities!)

1. Now try to find ways to cheat! Can your group find a way for Alicia to trick Benito? Can you find a way for Benito to figure out Alicia's secret?

1. Try designing your own circuit for this game! See if you can build one where cheating is easy — and another where it's hard. Your circuit doesn't need exactly six inputs and outputs — you can experiment with different numbers.

More Ideas to Try

1. Building together is hard. In real life, it would be a lot of work for Alicia and Benito to build one circuit together over the phone. Instead, they could each build their own circuit separately and share it publicly. Alicia would run her secret input through both circuits, then compare the two outputs number by number: if the matching numbers are the same, the final answer is 1; if they're different, it's 0. This way, neither person can cheat unless the other person's circuit is weak too.

1. All-zero and all-one inputs. You might notice that if Alicia picks all 0s as her input, the output will always be all 0s too. The same goes for all 1s. (Sometimes other inputs can also make an all-0 or all-1 output.) This happens because the circuit only uses and-gates and or-gates. If we add a new kind of gate called a not-gate — which flips a single number (0 becomes 1, and 1 becomes 0) — we can build circuits that don't always do this.

1. Two more gates: "and-not" and "or-not" work like "and" and "or," but with a not-gate added at the end. For example, "a and-not b" means: first do "a and b," then flip the result.