5814 - 新约瑟夫游戏

你一定听说过经典的“约瑟夫”问题吧？现在来组织一个皆大欢喜的新游戏（图9.4-5）：假设n个人站成一圈，从第1人开始交替的去掉游戏者，但只是暂时去掉（例如，首先去掉2），直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人将得到1块钱，并且永久性地离开，其余剩下的人将重复以上过程，比幸存者号码高的人每人将得到1块钱后离开。一旦经过这样的过程后，人数不再减少，最后剩下的那些人将得到2块钱。请计算一下组织者一共要付出多少钱？

如图9.4-5所示，第一轮有5人，幸存者是3，所以4、5得到1块钱后离开，下一轮幸存者仍然是3，因此没有人离开，所以每人得到2块钱，总共要付出2+2*3＝8块钱。