A mailing list I’m on that mainly focuses on cryptography has some fun applications into more real world problems. A fun puzzle came across the list recently that is built on some crypto ideas, but on the face of it, is a simple problem solving challenge. The first question is easy, the second one is harder, and I’m not even sure if my solution to the second is right, and I’m quite sure there are better solutions. It goes a little something like this:
Zero Knowledge in the Cave
There is a cave with a large entry room. From this room lead two
passageways, 1 and 2. Each of 1 and 2 branches into a myriad of smaller
passages, twisting and turning through the massive rock formation.
The passageways go on for miles and have never been fully explored.
One of the big questions has been whether passageways 1 and 2 ever
connect up. Is there a way of getting from 1 to 2? Many have
searched, but none have ever succeeded. Most people believe that
no connection will ever be found.
At least, no one used to. Now an explorer comes to you and claims to
have found a passage from 1 to 2, not a very long one, either. He will
prove it to you, but to you alone. Being a secretive type, he wants no
one else to know. If you accompany him to the cave, he will prove the
existence of the passageway to you.
But there’s a problem. You carry a video camera and record everything
that you see. If he shows you the existence of the passage, you will
be able to show the video tape to others, and they will learn of its
existence as well.
Not to worry, he says. Come with me. So you enter the large entry room
of the cave together.
Now the simplest thing to do in order to demonstrate the existence of the
connection would be for him to leave through passage 1 and return through
passage 2. He could easily do this. However, your film record of the
event would prove to anyone else who saw it that there was a connection.
Another way must be found. The explorer tells you what to do.
Following his instructions, you leave the entry room for a few minutes,
while the explorer enters one of the passageways. You then re-enter the
room, and loudly call out one of the passageway numbers, either 1 or 2.
In a few minutes, the explorer comes out of the requested passageway.
You then leave the cave and repeat the process many times. Each time, the
reporter enters one of the passageways unknown to you; when you return and
name one of them, he is able without fail to exit from the named passage.
You reason that if there were no connection between the passageways,
the only way the explorer could come out the passage that you named
would be if he had gone in that same one. He would have to guess
which one you were going to choose, and if he were right, he could
come out that one. But you have repeated the test dozens of times.
The chances that someone could guess right so often is infinitisimal.
The only logical explanation is that the passageway does exist.
Excited, you return to the tavern where you met the explorer and show
the other patrons your tape. But to your surprise, they just laugh.
They don’t deny that the tape is real, that the explorer did come out
of the passageway you named. But they don’t believe in the connection.
Instead, they claim you are in league with the explorer in an attempt to
perpetrate a fraud. You have simply predetermined together the sequence
of numbers you would call out. Each of you has memorized the sequence,
and so each time the explorer is able to anticipate the number you will
call next. He enters that passage and is able, after a suitable pause,
to exit from that same one when you call its number.
You leave the bar, frustrated. You are convinced that the connection
exists, but even though the tape shows all of the evidence that was so
convincing to you, no one else finds it persuasive. The explorer has
achieved his goal of proving the existence of the connection to you and
you alone.
Questions for the student:
1. How could you have done things differently, to produce a tape that
would be convincing to others?
2. What counter-measures and conditions could the explorer have put in
place to prevent you from getting a convincing tape in this manner?
Originally from the Cryptography mailing list. See my email response on the list for my answers.
I’m not sure about #2, but for #1 you could have the guys at the bar draw up a sheet with a list of what numbers you should call out, so that the explorer would have to get all of the people in the bar to agree to the fraud.
Left by John on May 18th, 2003
#1 I would have videotaped myself deducting an even (2) or uneven (1) number from naturally changing occurances outside the cave (number of birds in a flock, number of leaves on a branch, number of trees in an area, number of pebbles that fills the videotape case, …)
#2 He could have blindfolded me in the dark cave while he would go into one of the two passageways so I would have no possibility to show tape viewers that the number was derived from a natural occurance.
Rainer
Left by Rainer on December 30th, 2003
Who can shave 25 times and still have a beard??
Left by Kelly on December 10th, 2004
Someone who shaves one hair at a time?
Left by Jordan on December 13th, 2004
I am me and you and me are I. Everyone knows a touchdown makes six. So tell me truth fully what are lies.
I cannont solve this riddle. If anyone can get an answer please email it to me. thank you.
Left by darcy whitenight on January 24th, 2005
answer to #5 I think. This is what I have been able to come up with. Thinking about Roman numerals. I = 1 so in the riddle me has 1 consanant. Touchdown would have 6 and then lies would have 2. This may be to simple of a solution but it is what I have come up with.
Left by Wendell Hand on February 9th, 2005
Kindly solve this riddle and mail me back with the answer as i dont know the answer.
The riddle is .
I live in water if you cut my head i am at your door , if you cut my tail i am a fruit, if you cut both i am with you.
if any one can solve it please mail the answer to
draasofi@yahoo.com.
Left by eshan on June 27th, 2005
Answer to #3,
Who can shave 25 times and still have a beard?
Ans: A Barber
Left by sandy on July 10th, 2005
answer to #7 (only guess)
pearl
i live in water -> pearl
cut my head -> earl ( not sure)
cut my tail -> pear ( a type of fruit grown from rose family tree)
i am with you -> ear.
Left by maverick on July 18th, 2005
maverick,
am 1 of the searchers for the answer to the i live in water riddle. but what earl is ‘at of the door’? more response pls. thanks
madin
Left by madin tamayo on September 23rd, 2005
i think earl is a tiltle or a rank of an officer in England. Probably an earl is someone who serves as a messenger of the King and he knocks at every one’s door to spread news, etc.
Left by myk bongais on November 22nd, 2005
An egg salesman was asked how many eggs he had sold that day. He replied, “My first customer said, ‘I’ll buy half your eggs and half an egg more’. My second and third said the same thing. When I had filled all three orders, I sold out of eggs without having to break a single egg the whole day.” How many eggs were sold in all? explain this!
Left by tanya on January 26th, 2006
answer to #7
pearl
i live in water -> pearl
cut my head -> earl
cut my tail -> pear
i am with you -> ear.
reason for earl == In 1642, Robert Ker, 1st Earl of Roxburghe and Keeper of the Privy Seal of Scotland, opened the locked door of house of commons for the King Charles I, to enter and arrest five disruptive members, when William Lenthall was the speaker [are'nt parliamentary members immune from arrest?...just a thought] —-Source Wikipedia
Left by braindead on February 2nd, 2006
I am glad to see this webside because i have lerned a lot and i can easily get the answers to all of our assignment. I wish that you are going to continue your webside and can help lots of student’s like me.
Left by mylene on February 19th, 2006
Glad to be of service, Mylene. Good luck on your assignment.
Left by Jordan on February 19th, 2006
Pls solve,Its a 4letter word.Boys have,girls dont have.poor have,rich dont have.if u get u can fly,animals drinks,i cant…
Find out the word
Left by Misha on February 22nd, 2006
I turn polar bears white
and I will make you cry.
I make guys have to pee
and girls comb their hair.
I make celebrities look stupid
and normal people look like celebrities.
I turn pancakes brown
and make your champane bubble.
If you sqeeze me, I’ll pop.
If you look at me, you’ll pop.
Can you guess the riddle?
Left by Michelle on April 16th, 2006
7 eggs were sold. First customer bought 4 eggs (half of 7 eggs plus half an egg more or 3.5 plus .5 = 4 eggs) Leaving only 3 eggs left to sell. Second customer bought 2 eggs (half of 3 eggs plus half an egg more or 1.5 plus .5 = 2 eggs) Leaving only 1 egg left to sell. Third and last customer bought 1 egg (half of 1 egg plus half an egg more or .5 plus .5 = 1) Leaving no eggs left to sell
Left by Elaine on April 22nd, 2006
What is the answer to number 17????????
Left by Elaine on April 22nd, 2006
Answer to 17
The answer to the Polar Bears riddle is “NO”
Source:
http://fun.egreetingsetc.com/2F/D/AI/index.shtml
http://teensetc.com/0F/0D/BI/index.shtml
Left by McSpock on May 5th, 2006
i want to know the answer for question # 16. Pls help me out
Left by kamal on May 17th, 2006