Activity 17: The Peruvian Coin Flip

What Is This About?

This game helps two people pick a winner by "flipping a coin."
They do it over the phone.
They do not need to meet.

The Story

Two soccer teams want to play a big game.
One team is from Lima.
One team is from Cuzco.

They need to pick who plays at home.
A coin flip would be easy.
But the cities are far apart.
Alicia is from Lima.
Benito is from Cuzco.
They talk only by phone.

Alicia could flip a coin.
Benito could guess heads or tails.
But that is not fair.
Alicia could lie about the flip.
Benito would never know.

Their Smart Plan

Alicia and Benito build a special "circuit."
A circuit is like a puzzle made of gates.

There are two kinds of gates.

And-gate: Takes two inputs.
Each input is a 0 or a 1.
The output is 1 only if both inputs are 1.
Otherwise, the output is 0.

Or-gate: Takes two inputs too.
The output is 1 if at least one input is 1.
The output is 0 only if both inputs are 0.

Gates can connect to other gates.
This makes bigger, trickier circuits.

How the Coin Flip Works

Alicia picks six secret numbers.
Each number is a 0 or a 1.
This is her secret input.

She puts her numbers through the circuit.
The circuit makes an output.
She sends the output to Benito.

Benito looks at the output.
He must guess something about Alicia's secret input.
He guesses: does it have an even or odd number of 1s?

If the circuit is tricky enough, Benito cannot solve it.
His guess is just random.

If Benito guesses right, Cuzco is the home team.
If Benito guesses wrong, Lima is the home team.

Then Alicia shows her real secret input.
Benito checks it matches the output.
This proves Alicia didn't cheat.

Can Someone Cheat?

Benito could cheat if he could figure out Alicia's secret input from the output.
So the circuit must make this very hard.
This is called a "one-way function."
It is easy to get the output from the input.
But it is very hard to work backward.

Alicia could cheat too.
She could cheat if two different inputs give the same output.
One input could have even 1s.
The other could have odd 1s.
Then she could pick whichever one helps her win!

So both players want a strong, tricky circuit.
This keeps the game fair.

Try It Yourself

1. Get into small groups.
2. Pick a color for 0.

Pick a color for 1.
Use counters for these colors.

1. Practice placing counters on the circuit.

Follow the and-gate and or-gate rules.

1. Pick one person to be Alicia.

Pick one person to be Benito.

1. Alicea picks a secret input.

She works out the output.
She tells Benito the output.

1. Benito guesses even or odd.
2. Alicia reveals her secret input.

Check who wins!

Think About It

Can you find a way for Alicia to cheat?
Can you find a way for Benito to cheat?

Try building your own circuit.
Make it easy to cheat.
Then make it hard to cheat.
See what you discover!