[math-fun] Russian Postal Problem
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on. The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives. He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy. So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option. How does he safely send the ring to his partner?
Diffie-Hellman key exchange. Best wishes, Adam P. Goucher
Sent: Monday, May 09, 2016 at 2:49 PM From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Russian Postal Problem
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Man-in-the-middle attack. --ms On 09-May-16 10:38, Adam P. Goucher wrote:
Diffie-Hellman key exchange.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 2:49 PM From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Russian Postal Problem
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Maybe I'm not entering into the proper spirit, but I imagine I would send her an innocent-seeming sketch of a cityscape, asking her to treasure it. Then weeks later I would send the locked box, with a letter saying "You already have the key." The profile of the cityscape would provide the shape of the key that she would have to manufacture in order to open the box. Or something like that. Jim Propp On Mon, May 9, 2016 at 10:45 AM, Mike Speciner <ms@alum.mit.edu> wrote:
Man-in-the-middle attack. --ms
On 09-May-16 10:38, Adam P. Goucher wrote:
Diffie-Hellman key exchange.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 2:49 PM
From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Russian Postal Problem
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The trouble with these puzzles is that it is insanely hard to state them correctly so as to capture the desired underlying formal problem, but exclude unwanted real-world hacks. It is probable that the puzzle is meant to elicit something like Diffie-Helman exchange, as Adam intuited. But the puzzle as stated by Henry does not preclude, for example, just sending the key in advance. The corrupt postal workers will hang on to any locked box if they think a key is coming later, but we are not told that they will hang on to a key if they think a box is coming later. On Mon, May 9, 2016 at 12:14 PM, James Propp <jamespropp@gmail.com> wrote:
Maybe I'm not entering into the proper spirit, but I imagine I would send her an innocent-seeming sketch of a cityscape, asking her to treasure it. Then weeks later I would send the locked box, with a letter saying "You already have the key." The profile of the cityscape would provide the shape of the key that she would have to manufacture in order to open the box.
Or something like that.
Jim Propp
On Mon, May 9, 2016 at 10:45 AM, Mike Speciner <ms@alum.mit.edu> wrote:
Man-in-the-middle attack. --ms
On 09-May-16 10:38, Adam P. Goucher wrote:
Diffie-Hellman key exchange.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 2:49 PM
From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Russian Postal Problem
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Will a locked box containing a key to some other box get through? Will a key send (before the corresponding box is send) get through? Best regards, jj * Henry Baker <hbaker1@pipeline.com> [May 09. 2016 16:23]:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A locked box containing a key to some other box will get through (unless the post office believes a key to that box will eventually be sent). You can assume a key send will not get through (or rather, that the postal system will retain a copy of any key sent through). There is a good solution that doesn't require any special tricks (landscapes or otherwise). The problem statement sets the parameters in a reasonable fashion; don't try to work around the parameters but instead look for a solution to the problem. -tom On Mon, May 9, 2016 at 10:12 AM, Joerg Arndt <arndt@jjj.de> wrote:
Will a locked box containing a key to some other box get through? Will a key send (before the corresponding box is send) get through?
Best regards, jj
* Henry Baker <hbaker1@pipeline.com> [May 09. 2016 16:23]:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
I'm unclear on the meaning of "unless the post office believes a key to that box will eventually be". What are the laws of belief? If I write a letter saying "I'm never going to send the key because you already have it," might the post office believe me? I could then break my word and send a key after all. Does the puzzle require that the post office never believes something that turns out to be wrong? Jim On Monday, May 9, 2016, Tom Rokicki <rokicki@gmail.com> wrote:
A locked box containing a key to some other box will get through (unless the post office believes a key to that box will eventually be sent).
You can assume a key send will not get through (or rather, that the postal system will retain a copy of any key sent through).
There is a good solution that doesn't require any special tricks (landscapes or otherwise). The problem statement sets the parameters in a reasonable fashion; don't try to work around the parameters but instead look for a solution to the problem.
-tom
On Mon, May 9, 2016 at 10:12 AM, Joerg Arndt <arndt@jjj.de <javascript:;>> wrote:
Will a locked box containing a key to some other box get through? Will a key send (before the corresponding box is send) get through?
Best regards, jj
* Henry Baker <hbaker1@pipeline.com <javascript:;>> [May 09. 2016 16:23]:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
James, I'm going to duck your question, and let Henry decide how to answer, if to answer at all. -tom On Mon, May 9, 2016 at 10:31 AM, James Propp <jamespropp@gmail.com> wrote:
I'm unclear on the meaning of "unless the post office believes a key to that box will eventually be". What are the laws of belief? If I write a letter saying "I'm never going to send the key because you already have it," might the post office believe me? I could then break my word and send a key after all. Does the puzzle require that the post office never believes something that turns out to be wrong?
Jim
On Monday, May 9, 2016, Tom Rokicki <rokicki@gmail.com> wrote:
A locked box containing a key to some other box will get through (unless the post office believes a key to that box will eventually be sent).
You can assume a key send will not get through (or rather, that the postal system will retain a copy of any key sent through).
There is a good solution that doesn't require any special tricks (landscapes or otherwise). The problem statement sets the parameters in a reasonable fashion; don't try to work around the parameters but instead look for a solution to the problem.
-tom
On Mon, May 9, 2016 at 10:12 AM, Joerg Arndt <arndt@jjj.de <javascript:;>> wrote:
Will a locked box containing a key to some other box get through? Will a key send (before the corresponding box is send) get through?
Best regards, jj
* Henry Baker <hbaker1@pipeline.com <javascript:;>> [May 09. 2016 16:23]:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
Send the key first. Only send the box after the key arrives. Brent On 5/9/2016 6:49 AM, Henry Baker wrote:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The postal service will eat and/or copy a key sent from A->B and store this key under the pair (A,B) for future use, should any locked boxes be sent to/from A,B. Very strong hint: keys -- even pictures of keys -- need not be sent. At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
Brent
On 5/9/2016 6:49 AM, Henry Baker wrote:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
Well, the lady could send the box (to which she has the key) to the guy. But we'd have to assume either (a) it's unlocked, can be locked without a key, and won't be locked by the Russian Postal Service, or (b) it's locked and has some sort of trap door mechanism that allows things to be put in without a key but not removed. On 09-May-16 13:58, Henry Baker wrote:
The postal service will eat and/or copy a key sent from A->B and store this key under the pair (A,B) for future use, should any locked boxes be sent to/from A,B.
Very strong hint: keys -- even pictures of keys -- need not be sent.
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
Brent
On 5/9/2016 6:49 AM, Henry Baker wrote:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
Is the following within the rules? 1) Man sends box containing ring, padlocked to the lady. 2) Lady adds her own padlock to the box and sends it to the man. 3) Man removes his padlock with his key and sends the locked box back to the lady. 4) Lady uses her own key to remove the her padlock. No keys are exchanged. On Mon, May 9, 2016 at 2:18 PM, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 5/9/2016 11:30 AM, Victor Miller wrote:
Is the following within the rules?
1) Man sends box containing ring, padlocked to the lady.
The post office keeps it, waiting for the key to be sent. Right? Brent
2) Lady adds her own padlock to the box and sends it to the man. 3) Man removes his padlock with his key and sends the locked box back to the lady. 4) Lady uses her own key to remove the her padlock. No keys are exchanged.
On Mon, May 9, 2016 at 2:18 PM, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives. No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If he has thoughtfully phoned the lady beforehand to explain the arrangements, which the eavesdroppers have passed on to the postal service, then they know that no key will be posted. WFL On 5/9/16, Brent Meeker <meekerdb@verizon.net> wrote:
On 5/9/2016 11:30 AM, Victor Miller wrote:
Is the following within the rules?
1) Man sends box containing ring, padlocked to the lady.
The post office keeps it, waiting for the key to be sent. Right?
Brent
2) Lady adds her own padlock to the box and sends it to the man. 3) Man removes his padlock with his key and sends the locked box back to the lady. 4) Lady uses her own key to remove the her padlock. No keys are exchanged.
On Mon, May 9, 2016 at 2:18 PM, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives. No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
But, knowing the KGB is listening, one could make false statements hoping to disinform them. But then the KGB is already aware of that strategy. -- Gene From: Fred Lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Monday, May 9, 2016 1:50 PM Subject: Re: [math-fun] Russian Postal Problem If he has thoughtfully phoned the lady beforehand to explain the arrangements, which the eavesdroppers have passed on to the postal service, then they know that no key will be posted. WFL
On Mon, May 9, 2016 at 2:30 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Is the following within the rules?
1) Man sends box containing ring, padlocked to the lady.
This works only if the post office is "convinced that the key will never come their way" How and why are they convinced of this? If this is intended as a closed-world puzzle with precisely defined operations and consequences, then the possible operations and their consequences need to be defined more precisely. In particular, when a locked box is sent, how does the post office decide whether to allow this? If it's intended as an open-world lateral thinking puzzle. there are lots of solutions I like better than the intended one. As it stands, the activity feels less like solving a puzzle, and more like "solutions get proposed, and the conditions of the puzzle get clarified/changed to invalidate that solution unless it's the intended solution". Andy
2) Lady adds her own padlock to the box and sends it to the man. 3) Man removes his padlock with his key and sends the locked box back to the lady. 4) Lady uses her own key to remove the her padlock. No keys are exchanged.
On Mon, May 9, 2016 at 2:18 PM, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
He sends her box and ring, locked with his padlock. She returns it, double-locked with her padlock. He unlocks his padlock and resends. She unlocks her padlock. Thinks "just as well this wasn't fresh caviar!" WFL On 5/9/16, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I see Victor just beat me to it. But the penny has just dropped about Diffie-Hellman and "man-in-the-middle" --- Alice and Bob must acknowledge receipt by telephone, otherwise the post office might impersonate each to the other and nab the goodies after all! WFL On 5/9/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
He sends her box and ring, locked with his padlock.
She returns it, double-locked with her padlock.
He unlocks his padlock and resends.
She unlocks her padlock.
Thinks "just as well this wasn't fresh caviar!"
WFL
On 5/9/16, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It doesn't work: the telephone cannot be used to authenticate the sender (though it is still required to inform the postal service indirectly that no key can be expected). The postman in the middle simply exchanges his empty box for the genuine one whenever either is received, until he gets lucky. I can't see an alternative to some kind of public-key: for example, exchanging unlocked boxes packed with (cheap) unlocked, snap-closing, padlocks without keys (prior to communicating the arrangement over the telephone). There's a lot to be said for just sticking to dating the girl next door! Fred Lunnon On 5/9/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I see Victor just beat me to it.
But the penny has just dropped about Diffie-Hellman and "man-in-the-middle" --- Alice and Bob must acknowledge receipt by telephone, otherwise the post office might impersonate each to the other and nab the goodies after all!
WFL
On 5/9/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
He sends her box and ring, locked with his padlock.
She returns it, double-locked with her padlock.
He unlocks his padlock and resends.
She unlocks her padlock.
Thinks "just as well this wasn't fresh caviar!"
WFL
On 5/9/16, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives.
No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Surely the lady and her beau share intimate secrets that no one else knows. These can be used as shared secrets that can form the basis for any number of schemes. Perhaps simplest is to determine the combination of a combination lock. --ms On 10-May-16 09:39, Fred Lunnon wrote:
It doesn't work: the telephone cannot be used to authenticate the sender (though it is still required to inform the postal service indirectly that no key can be expected). The postman in the middle simply exchanges his empty box for the genuine one whenever either is received, until he gets lucky.
I can't see an alternative to some kind of public-key: for example, exchanging unlocked boxes packed with (cheap) unlocked, snap-closing, padlocks without keys (prior to communicating the arrangement over the telephone).
There's a lot to be said for just sticking to dating the girl next door!
Fred Lunnon
On 5/9/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I see Victor just beat me to it.
But the penny has just dropped about Diffie-Hellman and "man-in-the-middle" --- Alice and Bob must acknowledge receipt by telephone, otherwise the post office might impersonate each to the other and nab the goodies after all!
WFL
On 5/9/16, Fred Lunnon <fred.lunnon@gmail.com> wrote:
He sends her box and ring, locked with his padlock.
She returns it, double-locked with her padlock.
He unlocks his padlock and resends.
She unlocks her padlock.
Thinks "just as well this wasn't fresh caviar!"
WFL
On 5/9/16, Dave Dyer <ddyer@real-me.net> wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives. No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The important word missing in the problem statement was "padlock". * Fred Lunnon <fred.lunnon@gmail.com> [May 10. 2016 16:19]:
He sends her box and ring, locked with his padlock.
She returns it, double-locked with her padlock.
He unlocks his padlock and resends.
She unlocks her padlock.
Thinks "just as well this wasn't fresh caviar!"
WFL [...]
On 5/9/2016 11:18 AM, Dave Dyer wrote:
At 10:49 AM 5/9/2016, Brent Meeker wrote:
Send the key first. Only send the box after the key arrives. No, send the box first. If an anonymous locked box won't get through, the whole exercise is pointless. Any attempt to send the key first might alert the authorities to watch for the box. Once the box is safely transferred, as many attempts as necessary can be made to send a key for the box, which is already secure.
Do you put an expensive ring in each box? Brent
This problem, and hundreds of other good ones, are in Peter Winkler's two books of fun problems for mathematicians. There is nary a clunker among them. I recommend his books highly. —Dan
On May 9, 2016, at 6:49 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
* Dan Asimov <asimov@msri.org> [May 10. 2016 16:19]:
This problem, and hundreds of other good ones, are in Peter Winkler's two books of fun problems for mathematicians.
Peter Winkler: {Mathematical Puzzles: A Connoisseur's Collection}, A K Peters, (2003). http://www.maa.org/publications/maa-reviews/mathematical-puzzlesa-connoisseu... Peter Winkler: {Mathematical Mind-Benders}, A K Peters, (2007). http://www.maa.org/publications/maa-reviews/mathematical-mind-benders In the latter we find our problem on page 9: "Love in Kleptopia 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 sent via 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?" Yes, lots of lovely problems there. Best regards, jj
There is nary a clunker among them. I recommend his books highly.
—Dan
On May 9, 2016, at 6:49 AM, Henry Baker <hbaker1@pipeline.com> wrote:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Good that it is not American/Russian/etc Postal Problem :)
Вторник, 10 мая 2016, 19:17 +03:00 от Joerg Arndt <arndt@jjj.de>:
* Dan Asimov < asimov@msri.org > [May 10. 2016 16:19]:
This problem, and hundreds of other good ones, are in Peter Winkler's two books of fun problems for mathematicians.
Peter Winkler: {Mathematical Puzzles: A Connoisseur's Collection}, A K Peters, (2003). http://www.maa.org/publications/maa-reviews/mathematical-puzzlesa-connoisseu...
Peter Winkler: {Mathematical Mind-Benders}, A K Peters, (2007). http://www.maa.org/publications/maa-reviews/mathematical-mind-benders
In the latter we find our problem on page 9:
"Love in Kleptopia
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 sent via 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?"
Yes, lots of lovely problems there.
Best regards, jj
There is nary a clunker among them. I recommend his books highly.
—Dan
On May 9, 2016, at 6:49 AM, Henry Baker < hbaker1@pipeline.com > wrote:
I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem
A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on.
The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives.
He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy.
So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option.
How does he safely send the ring to his partner?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The hypothesis is "anything sent through the mail will be stolen unless it is sent via padlocked box". Therefore, the padlocked box will be stolen unless it is sent in a larger padlocked box. And so on. This problem could serve to segue into the ordinal numbers. -- Gene From: Joerg Arndt <arndt@jjj.de> To: math-fun <math-fun@mailman.xmission.com> Sent: Tuesday, May 10, 2016 9:17 AM Subject: Re: [math-fun] Russian Postal Problem * Dan Asimov <asimov@msri.org> [May 10. 2016 16:19]:
This problem, and hundreds of other good ones, are in Peter Winkler's two books of fun problems for mathematicians.
Peter Winkler: {Mathematical Puzzles: A Connoisseur's Collection}, A K Peters, (2003). http://www.maa.org/publications/maa-reviews/mathematical-puzzlesa-connoisseu... Peter Winkler: {Mathematical Mind-Benders}, A K Peters, (2007). http://www.maa.org/publications/maa-reviews/mathematical-mind-benders In the latter we find our problem on page 9: "Love in Kleptopia 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 sent via 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?" Yes, lots of lovely problems there. Best regards, jj
Man sends check to local jewelry store. Woman goes to store and picks up ring. -- Gene From: Henry Baker <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Sent: Monday, May 9, 2016 6:49 AM Subject: [math-fun] Russian Postal Problem I don't recall if this problem was ever discussed on math-fun: --- The Russian Postal Service Problem A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on. The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives. He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy. So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option. How does he safely send the ring to his partner?
participants (15)
-
Adam P. Goucher -
Allan Wechsler -
Andy Latto -
Brent Meeker -
Dan Asimov -
Dave Dyer -
Eugene Salamin -
Fred Lunnon -
Henry Baker -
James Propp -
Joerg Arndt -
Mike Speciner -
Tom Rokicki -
Victor Miller -
Zak Seidov