有奖做题 第一个做出来 奖励10积分

[huangchong]

站内帖子：童年阴影

bihai

好的，我多年前经高人指点，了解到高手解法，但是很快就忘了。现在请指教

100个人，有100个座位。第一个人进去的时候没有看号码，随便坐了。之后每一个人都安顺序按照下面的方案：如果自己的座位空着，就坐；否则就随便找一个。

解题要求：不得使用数学归纳法。求第100个人坐到自己座位的概率

[YWY]

这题以前出过，或是这个版，或是stem版，我记得我也参与了。

答案是二分之一，因为最后一个真正需要做选择的人，只有两个选择：第一个人的座位 or 第100个人的座位。

[YWY]

不好意思，原来就是我在stem版出的：站内帖子：我也出个题

不过我当时给的解答思路和我楼上给的解答思路略有不同。

[huangchong]

递归：

总共n+1人 第一个坐错了，于是我们有这个状况：
有 n个座位 n个人要来 其中1个人和座位错号

使事件链条截止的条件是 错号的第一个来 并且恰好坐在错号位置 （n+1 号人的座位） 这个概率是1/n/n

如果此人坐了其他人的座位 会导致问题传导到另一个人身上 但是问题本质不变 变成了n-1个人，一人错号

其余任何人来 都是有号的 会把问题挤压成n-1的小一号同样问题 还是n-1人 一人错号

所以1/n^2的机会终止问题 （最后一人坐正确座位） 剩下的情况传递问题

特殊地，n=1情况下 终止问题的可能是0 因为他没得选

n=2 25%概率终止问题

n=3 1/9的机会立即解决问题 8/9的机会传递问题给n=2 总的概率是3/9

n=4 1/16机会解决问题 15/16的机会传递给n=3 总解决是 6/16

n=5: 1/25+24/25*3/8=10/25

n=6: 1/36+ 35/36*10/25= 15/36

n=7： 1/49+ 48/49*15/36= 21/49

n=8：1/64+63/64*3/7=28/64
...

[ferrygao]

蝗虫来了 蝗虫来了 蝗虫来了

[huangchong]

这题以前出过，或是这个版，或是stem版，我记得我也参与了。

答案是二分之一，因为最后一个真正需要做选择的人，只有两个选择：第一个人的座位 or 第100个人的座位。

那3个人 票123, 3号先坐了1号 那么12乘客剩下23 座位可选：

2号来了坐了2号，1号只能坐3号
1号来了 坐了2号 2号只好坐3号
1号来了 坐了3号，2号可以坐2号 成功

这个成功几率是1/3吗？还是25%呢？ 首先 谁先来是随机的 所以一开始要选12谁先来，然后没座位的人可以选座位，看着像是4种情况，实际是3种情况（第二个来的人是否需要做选择取决于谁先来）。所以我上面递归那里说1/n^2的几率立即解决问题似乎不对。1先来确实是50%的几率 他选3确实也是50%的几率 但是似乎这个情况却是总情况的1/3？

我开始糊涂了 几率是怎么定义的呢？

[huangchong]

不好意思，原来就是我在stem版出的：站内帖子：我也出个题

不过我当时给的解答思路和我楼上给的解答思路略有不同。

我得仔细琢磨琢磨 按道理 100人和3人没本质区别吧？ 适用于100人的想法 应该适用于3人吧？ 为啥我觉得3人是1/3的概率能坐对呢？

[YWY]

我得仔细琢磨琢磨 按道理 100人和3人没本质区别吧？ 适用于100人的想法 应该适用于3人吧？ 为啥我觉得3人是1/3的概率能坐对呢？

是的，100个人和3个人的思路是一样的。在3个人的情况下，按一楼的假设，第一人坐对的概率是三分之一，第二人能坐在自己座位的概率是三分之二，第三人能坐在自己座位的概率是二分之一。

[YWY]

那3个人 票123, 3号先坐了1号 那么12乘客剩下23 座位可选：

2号来了坐了2号，1号只能坐3号
1号来了 坐了2号 2号只好坐3号
1号来了 坐了3号，2号可以坐2号 成功

这个成功几率是1/3吗？还是25%呢？ 首先 谁先来是随机的 所以一开始要选12谁先来，然后没座位的人可以选座位，看着像是4种情况，实际是3种情况（第二个来的人是否需要做选择取决于谁先来）。所以我上面递归那里说1/n^2的几率立即解决问题似乎不对。1先来确实是50%的几率 他选3确实也是50%的几率 但是似乎这个情况却是总情况的1/3？

我开始糊涂了 几率是怎么定义的呢？

三个人，可是这么想：第一个人进来，有三种（第一层）可能：

• 第一个坐了自己的座位，那么第三人坐到自己的座位。
• 第一个坐了第二人的座位，然后第二人又有两种（第二层）可能
  • 第二个坐了第一人的座位，那么第三人坐到自己的座位。
  • 第二个坐了第三人的座位，那么第三人不能坐到自己的座位。
• 第一个坐了第三人的座位，那么第三人不能坐到自己的座位。

所以，第三人有二分之一概率坐到自己的座位。

[huangchong]

三个人，可是这么想：第一个人进来，有三种（第一层）可能：

• 第一个坐了自己的座位，那么第三人坐到自己的座位。
• 第一个坐了第二人的座位，然后第二人又有两种（第二层）可能
  • 第二个坐了第一人的座位，那么第三人坐到自己的座位。
  • 第二个坐了第三人的座位，那么第三人不能坐到自己的座位。
• 第一个坐了第三人的座位，那么第三人不能坐到自己的座位。

所以，第三人有二分之一概率坐到自己的座位。

还是不大明白
"第一个坐了自己的座位，那么第三人坐到自己的座位。"
题目假设不就是第一个人坐了第二个人和第三个人的座位吗？ 第一个人坐一号 是不存在的呀 所以我说3个人 只有三分之一的机会 第三人坐回自己座位

[YWY]

"第一个坐了自己的座位，那么第三人坐到自己的座位。"
This is a precondition. How can this be regarded as one outcome?

题目规定：之后每一个人都安顺序按照下面的方案：如果自己的座位空着，就坐；否则就随便找一个。

按此规定，如果第一个坐了自己的座位，那么第三人必须要坐到自己的座位。

[huangchong]

题目规定：之后每一个人都安顺序按照下面的方案：如果自己的座位空着，就坐；否则就随便找一个。

按此规定，如果第一个坐了自己的座位，那么第三人必须要坐到自己的座位。

哦 我题目理解错了 以为第一个人必须坐错