约瑟夫环学习笔记

Posted by WildCow on November 12, 2018

写在前面


震耳欲聋,未闻其声





故事


$n$ 个人标号从 $1$ 到 $n$ 围成一个圈圈
每隔一个就山区一个
知道只有一个人幸存下来
问最后幸存下来的人的编号




解决


我们设 $J(n, m)$ 为有 $n$ 人,每隔 $(m - 1)$ 个人就杀死一个人时最后存活下来的人数
先考虑简单的 $J(n, 2)$ 下情况的解
首先我们很容易就能发现一个并没有什么用的规律:
最后的答案不会是偶数
因为在第一轮游戏就消掉了所有的偶数号码
所以我们很容易想到要分奇偶(???)

  • 对于偶数 我们假设一开始有 $n$ 个人
    可以得到一个初始状态下的数列:
    $1, 2, 3, ……, n$
    而对于一个一开始有 $2n$ 个人
    第一轮消掉了所有的偶数后
    剩下的人构成的数列有:
    $1, 3, 5, ……, 2n - 1$
    很容易找到一个映射函数 $f(x) = 2x - 1$
    来让这两个数列形成一一对应的关系
    所以有 $J(2n, 2) = f(J(n, 2))$
    即 $J(2n, 2) = 2J(n, 2) - 1$
  • 对于奇数 我们依旧假设一开始有 $n$ 个人
    可以得到一个初始状态下的数列:
    $1, 2, 3, ……, n$
    而对于一开始有 $2n + 1$ 个人
    先经过第一轮消掉了所有的偶数
    且当我们删掉 $2*n$ 后
    再下一个删掉的显然是 $1$
    剩下的人构成的数列有:
    $3, 5, 7, ……, 2n+1$
    让我们再找一个映射函数 $f’(x) = 2x+1$
    安排上了
    即 $J(2n + 1, 2) = 2J(n, 2) + 1$
    所以综上我们暂时有:


    然后我们用这个规律随手打一个表
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
$J(n, 2)$ 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1

然后我们就会发现我们把表中的数据按照 $n$ 在二进制下的位数进行分组
在每一组的开始有 $J(N, 2) = 1$
且在组里的数据每次都递增 2
即我们可以把 $n$ 写成 $2^m + l$ 的形式
其中 $m$ 为 $n$ 在二进制下的位数减一
而 $l$ 为剩下的数字
那么我们显然有:

$J(2^m + l, 2) = 2l+1, m \geq 0, 0 \leq l < 2^m $
可以用归纳法证明
证明:

  • $J(1, 2)$ = 1
  • 当 $m > 0$ 且 $2^m + l = 2n$ $J(2^m + l, 2) = 2J(2^{m - 1} + l / 2, 2) - 1 = 2(2l / 2 + 1) - 1 = 2l + 1$
  • 当 $m > 0$ 且 $2^m + l = 2n - 1$ $J(2^m + l, 2) = J(2(2^{m - 1} + (l - 1)/ 2), 2) = 2J(2^{m - 1} + (l - 1) / 2, 2) + 1 = 2(2(l - 1) / 2 + 1) + 1 = 2l + 1$ 证毕




一些推广


来研究 $n$ 和 $J(n, 2)$ 在二进制下的一些特性
我们假设 $n$ 的二进制的展开式为


也就是说


其中每个 $b_i$ 都为 $1$ 或 $0$
特别的我们一定有首位数字 $b_m = 1$
且 $n = 2^m + l$
那么我们有:


那么就证明了


用听起来很酷的语言来说就是
$n$ 向左循环移动一位就得到了 $J(n, 2)$!




一些嘿嘿嘿的推广


我们可以先研究在什么条件下 $J(n, 2) = \frac{n}{2}$ 成立

如果 $l = \frac{1}{3}(2^m - 2)$ 是整数
那么 $n = 2^m + l$ 就是一个解
首先有当 $m$ 为奇数时
$(2^m - 2)$ 一定是三的倍数
证明:


对于 $(3 + 1)^n$ 的展开式
除了最后一项是 $1$ 外其余每项都含有系数 $3$
对于最后一项 $1$ 我们把它乘上前面的 $2$ 再减去最后的 $2$ 得 $0$
当 $m = 1$ 时单独验证有 $2^1 - 2 = 0$ 成立
证毕
这也说明了 $J(n, 2) = n / 2$ 有无穷多个解
可以尝试简单的列举一下:

$m$ $l$ $n = 2^m+l$ $(n)_2$
1 0 2 10
3 2 10 1010
5 10 42 101010
7 42 170 10101010

这样我们对 $J(n, 2)$ 就有了更进一步的了解(???)




一些嘤嘤嘤的推广


我们讨论更一般的递推式下的求解:

然后按照常规去打表:

n $f(n, 2)$
1 $1\alpha$
2 $2\alpha + 1\beta$
3 $2\alpha \quad \quad + 1\gamma$
4 $4\alpha + 3\beta$
5 $4\alpha+2\beta + 1\gamma$
6 $4\alpha + 1\beta + 2\gamma$
7 $4\alpha \quad \quad + 3\gamma$
8 $8\alpha + 7\beta$
9 $8\alpha + 6\beta + 1\gamma$

这个规律就很清晰
$\alpha$ 的系数是不超过 $n$ 的最大二次幂
在 $2$ 的幂之间
$\beta$ 的系数逐渐递减
$\gamma$ 的系数逐渐递增
我们用函数来描述系数的变化
$f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$
接下来讨论一个牛逼的做法来解出三个函数 $A(n)、B(n)、C(n)$
因为 $A(n)、B(n)、C(n)$ 对于任意一个函数 $f(x)$ 都要成立
我们先令 $f(n) = A(n)$
即 $\alpha = 1、\beta = \gamma = 0$ 的情形
那么我们有:


其实它脸上都写着 $A(2^m + l) = 2^m$
接下来我们选择一些简单的函数
$f(n) = 1$ 带入有


即 $\alpha = 1、\beta = -1、\gamma = -1$
最后有 $A(n) - B(n) - C(n) = f(n) = 1$
$f(n) = n$ 带入有


即 $\alpha = 1、\beta = 0、\gamma = 1$
最后有 $A(n) + C(n) = n$
我们把这三个联立一下

这样我们最终就能解出 $A(n)、B(n)、C(n)$




一些咕咕咕的推广


咕了