Our first guest is Peter Winkler who is a world expert in discrete mathematics and combinatorics
and a mathematics and computer science professor at Dartmouth College.
His work has had substantial impact on the design of algorithms
and theoretical computer science.
He is also a celebrated collector of mathematical puzzles,
having written two books on the subject as well as a monthly column
for the communications of the ACM.
Now, since I've started off every unit with a mathematical magic trick,
I thought Peter would be an excellent person to beguile us
with a few fascinating tricks of his own.
[Peter Winkler, Professor, Dartmouth College] I have a puzzle from my book about a spy
who is trying to convey information to her control,
but the only means she has for conveying information
is that there is a 15-bit radio broadcast every morning,
and she has the ability if she wishes to alter 1 bit of that broadcast.
But she doesn't know in advance what the broadcast will be.
So, this is a case where, potentially, there are 16 different things she can do.
There are 15 bits she can alter, or she can choose not to alter any bit,
which means that in theory perhaps she could convey as many as 4 bits
of information this way.
Well, surprisingly, she can actually do that.
All right. Let's make sure that we understand the setup here.
I'm going to do this as a magic trick.
So, I'm a spy, and I'm in enemy territory, and I've got a message--0110--
that I need to transmit to my boss.
Now, that's going to be tricky to do, because I don't want anybody to know
that I'm a spy in enemy territory.
Fortunately, there is a radio broadcast tower in enemy territory,
and everyday it sends out a 15-bit message.
There's an example of a 15-bit message.
Now, I can use that message to communicate with my boss,
but I can't just change it arbitrarily to something completely different,
because then people will know that something weird has happened.
But I can flip just 1 bit.
I can zap the message and change just one of the bits,
and my boss then is going to hear that,
and we'd like him to actually interpret that as the message that I want to send.
Let's see if it worked.
Hmm...based on the 15-bit broadcast I'm hearing,
and the protocol that my spy and I arranged in advance,
I know that the message he is sending to me is 0110. Nice work, agent P.
Ta-da!
Here's what you can do, and the solution involves nimbers,
which come up in other problems as well.
A nimber is just a binary number.
What makes it different from an ordinary number is that when you add two of them,
you add without carry.
So, they're added like vectors in a vector space over zÂ˛.
They were called nimbers by John Conway,
because, as you may know, they are useful in analyzing a game of Nim.
So, what we can do is we take these 15 bits
and we number them from 1-15,
but instead of thinking of those numbers as ordinary decimal numbers,
we think of them as nimbers.
Each position has a non-zero nimber starting with 001 for the first position
and ending with 1111 for the fifteenth position.
What the spy wants to do is to convey some nimber of her choice to her control.
For example, suppose to wants to convey the nimber 1100 to her control.
What she's going to do is she's going to simply tell her control,
"Look at this radio broadcast after I've altered it,
and add up the nimbers of all the positions of where you see a 1."
Now, when the spy sees the radio broadcast,
she looks at what the nimbers currently add up to.
Say the nimbers currently add up to 1010.
Then if she changed the 1010 bit, they would add up to 0000,
so that's what she would do if she wanted to convey 0000.
She wants to convey 1100 so she adds that to 1010.
That gives her a nimber. She changes the value of the bit at that nimber.
It works. Marvelous.