Boris and Natasha


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)?

Solution     Reveal