约瑟夫问题 - Numberphile

The Josephus Problem - Numberphile

频道:Numberphile · 时长:13:57 · 发布:2016-10-28 · 播放:6991131

在 YouTube 观看

简介

Numberphile 与 Daniel Erman 讨论约瑟夫问题,即围成一圈的人依次被淘汰。它展示了幸存者的位置如何遵循与 2 的幂和二进制相关的规律。

HN 为什么推荐

HN 引用它作为通过解决小案例来发现规律的绝佳例子,以及一个具有优雅二进制解法的最爱谜题。

有一个关于约瑟夫问题的优秀 Numberphile 视频 — HN, 2018

算法与数据结构 · 趣味与视觉数学

中文字幕节选

所以它被称为约瑟夫问题。 它基于历史上的某个事件。 有一群犹太士兵被罗马军队包围 他们不想被俘虏,所以他们决定想出一个办法—— ——来避免被俘或自杀。 于是他们围坐成一圈,第一个人会杀死他左边的人 下一个还活着的人会杀死 下一个还活着的人,用他们的剑。 他们就这样一圈圈地进行,直到只剩下一个人, 最后一个人当然必须自杀,而不是被俘虏。 而这个故事——至少我听到的故事是这样的, 我不确定这在历史上是否准确—— 是约瑟夫宁愿被俘也不愿自杀, 但他担心如果他说出来,其他士兵会转而对付他。 所以他想弄清楚:他应该坐在圆圈中的哪个位置—— ——才能成为最后活着的人。 然后他会投降,而不是自杀。 这就是问题所在。有点棘手,所以我们来看一个更小的例子。 假设有七个人。 为了明确起见,规则是这样的:一号杀死二号。 三号杀死四号,五号杀死六号, 但现在事情变得有点难以提前看清楚了 因为七号,没有八号,所以七号杀死一号,三号杀死五号, 七号杀死三号。所以七号是赢家;七号是最后剩下的那个。 对于约瑟夫来说,有41个人。他需要弄清楚该坐在哪里。 数学问题是,如果有n个人。 获胜的座位在哪里? 我学习这个问题时还在上高中, 这是最早让我理解如何着手—— ——困难和……数学问题的之一,当你不知道答案时 提前,或者没有人提前给你展示过。 我的一位教授,他的名字叫菲尔·汉隆 他在引导我走向数学方面发挥了重要作用。 他建议:我们应该做的是收集数据。 就是……取不同的n值,然后手动计算 并开始寻找规律。 我不知道,也许我们就这么做? n是座位数,w(n)将是获胜的座位。 目前我们知道的是:n是7,w(n)结果也是7。 所以我会开始计算其他值 所以,我不知道,为什么我不试试5呢? 一号杀死二号,三号杀死四号,五号杀死一号,三号杀死五号。 赢家是三号。 我想我没有理由跳过6,所以我们来填上6。 一号杀死二号,三号杀死四号,五号杀死六号…… ……一号杀死三号,五号杀死一号。 赢家是五号。所以 如果你在看,你可能已经开始注意到一些规律。 例如,它们总是奇数。我是说,这可能是你注意到的第一件事 然后你可以开始问“为什么它们总是 奇数?”也许你已经能看到—— ——在第一轮循环中,所有偶数的人都被杀死了。 所以,即使只做一点点实验,你也能开始看到一些规律。 - *布雷迪* 所以你不应该坐在偶数 座位? - 不要坐在偶数座位,不不不。 也许我们甚至能看到其他规律的一些端倪 但在我真正尝试表述这些之前,我 想再填一下表格。 所以我们来做一些。如果只有一个人…… 嗯……那个人就是赢家,所以那个很简单。 如果有两个人:一号杀死二号。一号是赢家 如果有三个人:一号杀死二号,三号杀死一号。三号是赢家 如果有四个人:一号杀死二号,三号杀死四号,一号杀死三号。 如果有八个人:一号杀死二号,三号 杀死四号,五号杀死六号,七号杀死八号,

HN 上的讨论

我非常喜欢约瑟夫问题([Numberphile 在 YT 上的视频]( [VIDEO] )),因为那个二进制的巧妙转折,也很喜欢 Veritasium 的 [3x+1]( [LINK] ),而我最喜欢的也是你提到的 [100 Prisoners Riddle]( [LINK] ) — hostcontroller, 2022-08
从桌前站起来去散散步、思考问题,这种方法对我来说屡试不爽,效果出奇地好。我第一次读到这个是在庞加莱一篇关于数学思想如何产生的文章里。说到休闲数学中通用的问题解决方法,我在动手之前总是先寻找对称性,把问题从一个问题空间变换到另一个问题空间,以及使用归纳技巧。对于研究/建模类问题,我的方法是先处理它最简化的版本,再逐步推进到原始问题。有一集非常棒的 Numberphile 视频讲约瑟夫问题,它展示了考察具体实例来观察规律如何有助于解决一般情况。[VIDEO] 编辑:格式调整 — yantrams, 2018-06
在我面试现在这家公司时,我对面试相当紧张,前一晚看了些 Numberphile 视频来分散注意力。奇怪的是,面试中讨论的其中一个问题正是约瑟夫问题,它有一个用二进制表示的巧妙解法 [0]。我不记得自己是否问过面试官他们最近是否也看过那个视频,或者他们是怎么想到这个问题的。[0]:[VIDEO] — leipert, 2022-06
简单的例子可能很有用。探索它们、证明关于它们的结论,正是人们为攻克更难问题打下立足点的方式。例如:约瑟夫问题 - Numberphile [VIDEO] — d0mine, 2019-12

相关视频