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

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

arxiv.org

128 pointsrobinhouston26 comments

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.

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

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...

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.

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.

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

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

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.

http://erikdemaine.org/

Agree.

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

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/

As the note at the bottom of the page mentions, the 'tree' part of that can be got for any mathematician from the wonderful Mathematics Genealogy Project: http://genealogy.math.ndsu.nodak.edu/index.php.

While we're on collaborations and curiosities, I could have sworn that there was a page out there that would try to calculate your Erdös number automatically (maybe through MathSciNet?), but I can't seem to find it.

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

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".

You mean it may fall sooner?

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.

"such that the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed."

I interpret that to mean exactly K nails; no more, no less.

If it falls when exactly K nails are removed, I don't think it will go back up when you remove the K+1th nail. And if you remove k-1 nails first, and then remove 2 more simultaneously, the picture will fall anyway. So it's ">= K".

"At least k" might imply that removing more than k nails is necessary to make the picture fall, which is not the case. I think "exactly k" is perfectly clear.

"Exactly k" is not clear because the picture will still fall if you remove k+1 nails. I think it's harder to get clearer than the way it's stated in the paper: "the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed."

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.

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)

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.

Simple. Let n = k.

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

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

Reply on news.ycombinator.com