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年)证明所有合理的这种拼图都是可以解开的,对于美元以外的钉子来说,解决方案的大小可以被一个以美元计的多元货币捆绑起来。我们简化了这些事实的证明,因为后者可以导致在多面框中找到一个合理的表率。

0
下载
关闭预览

相关内容

如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
64+阅读 · 2021年2月12日
专知会员服务
123+阅读 · 2020年9月8日
【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
inpluslab
8+阅读 · 2019年10月29日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年3月24日
Arxiv
0+阅读 · 2021年3月23日
Arxiv
1+阅读 · 2021年3月23日
VIP会员
相关VIP内容
如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
64+阅读 · 2021年2月12日
专知会员服务
123+阅读 · 2020年9月8日
【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
已删除
inpluslab
8+阅读 · 2019年10月29日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员