A picture-hanging puzzle is the task of hanging a framed picture with a wire around a set of nails in such a way that it can remain hanging on certain specified sets of nails, but will fall if any more are removed. The classical brain teaser asks us to hang a picture on two nails in such a way that it falls when any one is detached. Demaine et al (2012) proved that all reasonable puzzles of this kind are solvable, and that for the $k$-out-of-$n$ problem, the size of a solution can be bounded by a polynomial in $n$. We give simplified proofs of these facts, for the latter leading to a reasonable exponent in the polynomial bound.
翻译:挂图的谜题是用铁钉环绕钉子的铁丝钉挂上一张挂图,这样它就可以继续挂在某些特定的钉子上,但如果再去掉的话,就会掉下来。古典的大脑挑逗者要求我们把照片挂在两个钉子上,这样在任何人分离时就会掉下来。 Demaine 等人(2012年)证明所有合理的这种拼图都是可以解开的,对于美元以外的钉子来说,解决方案的大小可以被一个以美元计的多元货币捆绑起来。我们简化了这些事实的证明,因为后者可以导致在多面框中找到一个合理的表率。