26th December 2019, 01:06 pm
I heard this puzzle many years ago, and do not remember the origins of it. The version below is from Peter Winkler’s paper Seven Puzzles You Think You Must Not Have Heard Correctly.
Puzzle.
Jan and Maria have fallen in love (via the internet) and Jan wishes to
mail her a ring. Unfortunately, they live in the country of Kleptopia
where anything sent through the mail will be stolen unless it is
enclosed in a padlocked box. Jan and Maria each have plenty of padlocks,
but none to which the other has a key. How can Jan get the ring safely
into Maria’s hands?
I don’t know whether this puzzle appeared before the Diffie-Hellman key
exchange was invented, but I am sure that one of them inspired the
other. The official solution is that Jan sends Maria a box with the ring
in it and one of his padlocks on it. Upon receipt Maria affixes her own
padlock to the box and mails it back with both padlocks on it. When Jan
gets it, he removes his padlock and sends the box back, locked only
with Maria’s padlock. As Maria has her own key, she can now open it.
My students suggested many other solutions. I wonder if some of them can be translated to cryptography.
- Jan can send the ring in a padlock box that is made of cardboard. Maria can just cut the cardboard with a knife.
- Jan can use the magic of the Internet to send Maria schematics of the
key so she can either 3d print it or get a professional to forge it. If they are
afraid of the schematics getting stolen Jan can send the schematics after the
package has been delivered.
- Jan can use a digital padlock and send the code using the Internet.
- Jan can send it in a secret puzzle box that can be opened without a key.
- Maria can smash the padlock with a hammer.
Now that we’ve looked at the Padlock Puzzle, let’s talk about
cryptography. I have an imaginary student named Charlie who doesn’t know
the Diffie-Hellman key exchange. Charlie decided that he can adapt the
padlock puzzle to help Alice send a secret message to Bob. Here’s what
Charlie suggests:
Suppose the message is M. Alice converts it to binary. Then she creates a
random binary key A and XORs it with M. She sends the result, M XOR A,
to Bob. Then Bob creates his own random key B and XORs it with what he
receives and sends the result, M XOR A XOR B, back to Alice. Alice XORs
the result with her key to get M XOR A XOR B XOR A = M XOR B and sends
it to Bob. Bob XORs it with his key to decipher the message.
Each sent message is equivalent to a random string. Intercepting it is
not useful to an evil eavesdropper. The scheme is perfect. Or is it?
Share:
23rd December 2019, 12:25 pm
Here is a logic puzzle.
Puzzle. You are visiting an island where all people know each
other. The islanders are of two types:
truth-tellers who always tell the truth and liars who always lie. You
meet three islanders—Alice, Bob, and Charlie—and ask each of
them, “Of the two other islanders here, how many are truth-tellers?”
Alice replies, “Zero.”
Bob replies, “One.” What will Charlie’s reply be?
The solution proceeds as follows. Suppose Alice is a truth-teller. Then
Bob and Charlie are liars. In this situation Bob’s statement is true,
which is a contradiction. Hence, Alice is a liar. It follows, that there
is at least one truth-teller between Bob and Charlie. Suppose Bob is a
liar. Then the statement that there is one truth-teller between Alice
and Charlie is wrong. It follows that Charlie is a liar. We have a
contradiction again. Thus, Alice is a liar and Bob is a truth-teller.
From Bob’s statement, we know that Charlie must be a truth-teller. That
means, Charlie says “One.”
But here is another solution suggested by my students that uses meta
considerations. A truth-teller has only one possibility for the answer,
while a liar can choose between any numbers that are not true. Even if
we assume that the answer is only one of three numbers—0, 1, or 2—then
the liar still has two options for the answer. If Charlie is a liar,
there can’t be a unique answer to this puzzle. Thus, the puzzle
question implies that Charlie is a truth-teller. It follows that Alice
must be lying and Bob must be telling the truth. And the answer is the
same: Charlie says, “One.”
Share:
20th December 2019, 02:31 pm
You might have noticed that my blogging slowed down significantly in the
last several months. I had mono: My brain was foggy, and I was tired
all the time. Now I am feeling better, and I am writing again. What
better way to get back to writing than to start with some jokes?
* * *
The wife of a math teacher threw him out from point A to point B.
* * *
At the job interview at Google.
—How did you hear about our company?
* * * (submitted by Sam Steingold)
50% of marriages end with divorce. The other 50% end with death.
* * *
People say that I am illogical. This is not so, though this is true.
* * *
Humanity invented the decimal system, because people have 10 fingers.
And they invented 32-bit computers, because people have 32 teeth.
* * *
When a person tells me, “I was never vaccinated, and, as you can see, I
am fine,” I reply, “I also want to hear the opinion of those who were
never vaccinated and died.”
* * *
I will live forever. I have collected a lot of data over the years, and
in all of the examples, it is always someone else who dies.
* * *
Just got my ticket to the Fibonacci convention! I hear this year is going to be as big as the last two years put together.
* * *
I am afraid to have children as one day I will have to help them with math.
Share:
29th November 2019, 02:30 pm
19th October 2019, 07:21 pm
12th October 2019, 02:16 pm
6th June 2019, 01:43 pm
I found this puzzle on Facebook:
Puzzle. Solve this:
1+4 = 5,
2+5 = 12,
3+6 = 21,
5+8 = ?
97% will fail this test.
Staring at this I decided on my answer. Then I looked at the comments:
they were divided between 34 and 45 and didn’t contain the answer that
initially came to my mind. The question to my readers is to explain the
answers in the comments and suggest other ones. Can you guess what my
answer was?
Share:
21st April 2019, 12:42 pm
4th April 2019, 12:41 pm
My friend Alice reminds me of me: she has two sons and she is never
straight with her age. Or, maybe, she just isn’t very good with numbers.
Once I visited her family for dinner and asked her point blank, “How old are you?” Here is the rest of the conversation:
Alice: I am two times older than my younger son was 5 years ago.
Bob: My mom is 12 times older than my older brother.
Carl: My younger brother always multiplies every number he mentions by 24.
Bob: My older brother is 30 years older than me.
Carl: My mom is 8 times older than me.
Alice: My older son always multiplies every number he mentions by 2.
How old is everyone?
Share:
4th March 2019, 05:51 pm
Last year, when I read an application file of Wayne Zhao to PRIMES, I
got very excited because he liked puzzles. And I’ve always wanted to
have a project about puzzles. After Wayne was accepted to PRIMES we
started working together. Wayne chose to focus on a variation of Sudoku
called Sudo-Kurve.
We chose a particular shape of Sudo-Kurve for this project, which ended up being very rewarding. It is called Cube Sudo-Kurve.
The Cube Sudo-Kurve consists of three square blocks. The
gray bent lines indicate how rows and columns continue. For
example, the
first row of the top left block becomes the last column of the middle
block and
continues to the first row of the bottom right block. As usual each row,
column, and square region has to have 9 distinct digits.
Wayne and I wrote a paper Mathematics of a Sudo-Kurve, which has been published at Recreational Mathematics Magazine.
A Cube Sudo-Kurve needs at least 8 clues to have a unique solution. Here
we have a puzzle with 8 clues that we designed for our paper.
Share: