How to hang a picture using n nails such that removing any k nails makes it fall

by robinhouston • 14 years ago

128 26 14 years ago

willvarfar3• 14 years ago

One can imagine a guillotine that chops the king's head off only if K members of the revolutionary council reach agreement and turn their keys...

mad44• 14 years ago

I see what you did there. A professor of mine once said that humans remember stories related to violence or sex (which is a no-no in class). I guess, hence, two-generals problem, byzantine-generals.

joshAg• 14 years ago

one of my discrete math professors was cut from the same cloth. We didn't learn about stable marriages; we learned about stable orgies.

Jun8• 14 years ago

And you can combine the two, e.g. another paper from the same conference: "The Byzantine Brides Problem" Swan Dubois, Sébastien Tixeuil and Nini Zhu.

ahelwer• 14 years ago

Sounds like a future problem at the ICPC worlds. I would write it, but I lack horrible-pun skills.

cperciva• 14 years ago

This is the first time I've come across an algorithm which is proven to operate in O(n^56556) time.

thebooktocome• 14 years ago

That's really weird. My complex analysis professor assigned a few cases of these as joke homework problems (vaguely related to winding numbers around poles) around two years ago.

lell• 14 years ago

the case where n=2, k=1 was an IMO problem around 2001/2002 (and the parent article says it is first from spivak '97) and it's pretty easy to see the generalization if you know about fundamental groups. I used to pose the n arbitrary, k=1 case to other math students :D (parent article claims this version is first from mathpuzzle.com, 2002)

ma2rten• 14 years ago

This was published at the The Sixth International conference on Fun with Algorithms (FUN 2012). Maybe it's worth looking looking into other papers from that conference. I am wondering what a keynote of such a conference might sound like.

losvedir• 14 years ago

Why am I not surprised the Demaines are behind this? They're a hilarious father-son team at MIT.

I worked next to Martin (the father) at CSAIL one summer. He excitedly ushered me and some friends into his office one day to show us all a new video he had finished shooting with Erik. It was a real-life demonstration of some algorithmic problem about rolling a cube over a pattern on the ground. In the video, Martin proceeded to put on a helmet and then climb into a box which Erik then rolled everywhere. And by 'rolled', I mean, tipped the cube up onto its edge to have it come crashing down onto a new face (with Martin inside, sometimes upside down). It was very funny.

Also, looks like Ron Rivest of RSA fame is an author.

arihant• 14 years ago

Almost every paper or artwork by Erik Demaine opens me to something I wouldn't ever imagine. I encourage everyone to look at his website. He is closest to the da Vinci of our times.

kang• 14 years ago

http://erikdemaine.org/

cs7022• 14 years ago

Agree.

I enjoy the annual origami puzzles too: http://erikdemaine.org/puzzles/

kapitalx• 14 years ago

I enjoyed his 'family' tree. Showing his academic ancestry to the likes of Fourier and Euler at the bottom of this page: http://erikdemaine.org/family/

tomdeakin• 14 years ago

Tried the "Black and White Squares" one. Was pretty fun and definitely suitable for 'young folders'!

kylec2• 14 years ago

Bad title, "removing any k nails makes it fall" is NOT the same thing as "the picture remains hanging when fewer than k nails get removed".

willvarfar3• 14 years ago

You mean it may fall sooner?

kylec2• 14 years ago

The title implies that removing at most k nails makes it fall, the actual paper deals requires at least k nails to be removed to make it fall.

powrtoch• 14 years ago

Simple. Let n = k.

cs7022• 14 years ago

I just knew someone would post this. Upvoted :-)

meepmorp• 14 years ago

Right, from the title, that's what I first thought, and figured that the lower bound on the value of n is 1.

How to hang a picture using n nails such that removing any k nails makes it fall

Related Stories