I got this problem from Rustan Leino, who got it from Todd Proebsting.

I solved it and wrote up my solution.

Boris and Natasha live in different cities in a country with a corrupt postal service. Every box sent by mail is opened by the postal service, the contents stolen, and the box never delivered. Except: if the box is locked, then the postal service won't bother trying to open it (since there are so many other boxes whose contents are so much easier to steal) and the box is delivered unharmed.

Boris and Natasha each has a large supply of boxes of different sizes, each capable of being locked by padlocks. Also, Boris and Natasha each has a large supply of padlocks with matching keys. The padlocks have unique keys. Finally, Boris has a ring that he would like to send to Natasha. How can Boris send the ring to Natasha so that she can wear it (without either of them destroying any locks or boxes)?

Boris puts the ring into a box and locks it with one of his padlocks. He retains the key to that padlock and sends the box to Natasha. Natasha, upon receiving the box, puts one of her padlocks on the box. This way, it's now locked by two padlocks, both Boris's and Natasha's. She retains her key and sends the box back to Boris. When Boris receives the box, he unlocks his padlock with his key and sends the box, still locked with Natasha's key, back to Natasha. Finally, Natasha receives the box, unlocks the remaining padlock with her key, and opens the box to retrieve the ring.