Hey, this is Presh Talwalkar.
An evil warden holds you prisoner,
but offers you a chance to earn your freedom.
You are given 101 coins,
of which 51 are genuine and 50 are counterfeit.
Each counterfeit coin is identical to a genuine coin,
except that it differs in weight by exactly one gram.
All of the counterfeit coins are lighter, or all of them are heavier.
Only the warden knows this information.
The warden gives you a randomly selected coin
from the 101 coins.
You have to guess whether it is genuine or counterfeit.
If you are incorrect, you are imprisoned forever,
but if you are correct, then you are set free.
You are given a tool to help.
You are given a weighing balance
that displays the difference in weight
between its left and right pans.
For example,
if the left pan has 8.3 grams
and the right pan has 10.3 grams,
the display would show negative two grams.
You can weigh any of the 101 coins,
but you only get to use the weighing balance once
before you have to guess.
What is your best strategy to identify your coin
and escape the prison?
Can you figure it out?
Give this problem a try, and when you're ready,
keep watching the video for the solution.
It seems impossible because you're at a huge disadvantage.
You don't know the weight of a genuine coin
and you don't know if the counterfeit coin
is lighter or heavier.
Plus, the weighing balance only gives
the difference in weight between its left and right pans.
But amazingly, you can always escape.
And remarkably, you don't actually weigh
the coin you need to identify,
you end up weighing all of the other coins.
Here's how it works.
You place your coin aside.
Then you split the remaining 100 coins
into left and right pans
with 50 coins in each pan.
Now the display on the balance
will always be an integer.
I'll explain why later in the video.
If the integer is even,
then you initially received a genuine coin.
If the integer is odd,
then you initially received a counterfeit coin.
By a clever mathematical scheme,
you can outsmart the evil warden
and guarantee your freedom.
This will always let you identify
whether your coin is genuine or counterfeit,
but why does it work?
Let's go through a proof.
Let w equal the weight of a genuine coin
and let c sub i equal the weight of coin i.
We'll number the coins in the left pan
from 1 to 50,
and we'll number the coins in the right pan
from 51 to 100.
We can then write the difference
of the weight in the coins
on the left hand pan
from the right hand pan
as equaling the sum of the coins in the left pan
minus the sum of the coins in the right pan.
We now are going to introduce
the weight of a genuine coin.
We'll start out with the simple expression
that zero is equal to negative 50 w
minus negative 50 w.
We will then expand out each term
so that we have zero equaling
negative w fifty times
minus negative w fifty times.
We can now add up these equations.
The reason we're doing this
is we're going to pair the weight of each coin
with the weight of a genuine coin.
So we have a result that left minus right
is equal to the sum
of the weight of each coin
minus the weight of a genuine coin.
We have one hundred of these terms
consisting of fifty terms
that are added on the left pan
and fifty terms which are subtracted
from the right pan.
Now we know something
about each of these terms.
For a genuine coin,
its weight is exactly equal
to the weight of a genuine coin,
so each of these terms will equal zero
and they'll vanish.
If all of the counterfeit coins are heavier,
then the weight of a counterfeit coin
minus the weight of a genuine coin
will equal 1.
If instead all of the counterfeits are lighter,
then the weight of a counterfeit coin
minus the weight of a genuine coin
will equal minus 1.
We'll consider each of these cases separately.
So let's continue the proof by considering
if all of the counterfeit coins are heavier.
So how many counterfeit coins are there?
We will either be weighing 50 counterfeit coins
if we received a genuine coin,
or we will be weighing 49 counterfeit coins
if we received a counterfeit.
So we'll consider each of these cases.
Suppose that we are weighing 50 counterfeit coins,
and we're placing x of them on the left pan
and 50 minus x on the right pan.
Each of these counterfeit coins
will contribute one
to this left minus right.
So we have left minus right equals
x from the left pan
minus 50 minus x
from the right pan.
This simplifies to be 2x minus 50,
and what's important is that 2x is even,
50 is even, and the difference
of two even terms is even.
If instead there were 49 counterfeit coins,
suppose we placed x on the left pan
and 49 minus x on the right pan.
We can again calculate that left minus right
will equal x minus 49 minus x,
and this simplifies to be 2x minus 49.
The only difference here is that 49 is an odd number.
We have an even number, 2x, minus an odd number,
which will therefore give us an odd result.
So what we've figured out is that
the even-ness and odd-ness of our result will depend
on whether we're weighing 50 or 49 coins
that are counterfeit.
This will also be true
if the counterfeits are all lighter.
It's a very similar calculation.
If we ended up weighing 50 counterfeit coins,
we'll end up with an even result,
and if we were weighing 49 counterfeit coins,
we would end up with an odd result.
So we can generalize all of these cases together
whether we're dealing with heavier or lighter counterfeit coins.
If we end up with the balance showing an even integer,
then that means we would have weighed
all 50 of the counterfeit coins,
so that means initially
we would have received one of the genuine coins.
If instead the balance is showing an odd number,
that means we would have been weighing
49 of the counterfeit coins,
so initially we would have received
one of those counterfeit coins.
Therefore, with certainty, we can figure out,
from what the weighing balance is showing,
whether the coin we had
is genuine or counterfeit.
Did you figure this out?
Thanks for watching this video.
Please subscribe to my channel.
I make videos on math and game theory.
You can catch me on my blog, "Mind Your Decisions,"
which you can follow on Facebook, Google+, and Patreon.
You can catch me on social media: @preshtalwakar,
and if you liked this video, please check out my books.
There are links in the video description.