6 ms·
How to hang a picture using n nails such that removing any k nails makes it fall
- willvarfar 15y agoOne 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 15y agoI 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.
- deleted 15y ago[deleted]
- joshAg 15y agoone of my discrete math professors was cut from the same cloth. We didn't learn about stable marriages; we learned about stable orgies.
- Jun8 15y agoAnd 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 15y agoSounds like a future problem at the ICPC worlds. I would write it, but I lack horrible-pun skills.
- cperciva 15y agoThis is the first time I've come across an algorithm which is proven to operate in O(n^56556) time.
- thebooktocome 15y agoThat'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 15y agothe 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 15y agoThis 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 15y agoWhy 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 15y agoAlmost 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 15y agohttp://erikdemaine.org/ http://erikdemaine.org/
- cs702 15y agoAgree. I enjoy the annual origami puzzles too: http://erikdemaine.org/puzzles/ http://erikdemaine.org/puzzles/
- kapitalx 15y agoI 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/ http://erikdemaine.org/family/
- JadeNB 15y agoAs 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 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.
- tomdeakin 15y agoTried the "Black and White Squares" one. Was pretty fun and definitely suitable for 'young folders'!
- kylec 15y agoBad 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".
- willvarfar 15y agoYou mean it may fall sooner?
- kylec 15y agoThe 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.
- willvarfar 15y ago"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.
- kiiski 15y agoIf 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".
- spicyj 15y ago"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.
- aplusbi 15y ago"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."
- powrtoch 15y agoSimple. Let n = k.