2.2.27

(a)

いっぱい円を描いて実験すると次のようになる。

16までは円を描いたがそこまでで規則性は見えたので17以降は以下のプログラム(python)で確認をした。

for n in range(2,25+1,1):
    xs = list(range(1,n+1))

    skip_num = 2
    i = -1
    for _ in range(n-1):
        for num in range(skip_num):
            i = (i+1) % n
            while xs[i] == None: i = (i+1) % n
        xs[i] = None
    ans = []
    for i in range(n):
        if xs[i] != None:
            ans.append(xs[i])
    print(n, ans)

(b)

$$n=2^i$$のとき$$1$$となっていること、そこから2ずつ増えていること、また偶数が出てこないことが分かる。 円を描いてみると分かるが、最初の1巡目で偶数番目の人が消え、2巡目以降はそれまでに消えた人を無視して数字を再度時計回りに付け替えると やはり偶数番目の人が消えることになる。 このことから$$n$$の偶奇で再帰的に$$j(n)$$は定まりそうに見える。

$$n$$が偶数のときを考え、$$n=2k$$とする。このとき1巡目で$$2,4,\ldots,2k-1$$が消え、残った$$1,3,\ldots,2k-1$$で再度1から順番に始めることになる。 この残った人間に$$1,2,\ldots,k$$と新しく割り当てる。このとき新しく$$i$$が割当てられた人の元の番号は$$2i-1$$である。 新しく割り当てた番号の1から同じように始まるので再帰的に計算ができて最後に残るのは$$j(k)$$である。 これらから$$j(n) = 2j(k)-1 = 2j(\frac{n}{2})-1$$と分かる。

次に$$n=2k+1$$と奇数のときを考える(但し$$n>1$$)。 このとき1巡目で$$2,4,\ldots,2k,1$$が消え、残るのは$$3,\ldots,2k+1$$である。 この場合は次は3から始めることになる。 そこで$$3,5,\ldots,2k+1$$を新しく$$1,2,\ldots,k$$と割り当てる。 このとき新しく$$i$$が割当てられた人の元の番号は$$2i+1$$である。 先と同じ議論により$$j(n) = 2j(k) + 1 = 2j(\lfloor\frac{n}{2}\rfloor)+1$$となる。

これらより以下の漸化式を得る。

$$j(n) = \begin{cases} 2j(\left\lfloor\frac{n}{2}\right\rfloor)-1 & \text{if n is even} \\ \\ 2j(\left\lfloor\frac{n}{2}\right\rfloor)+1 & \text{if n is odd} \end{cases}$$

この式を見ると$$n$$を2で割り小数部を無視(右シフト)したもののみに依存しているので、1を根とする完全二分木にすると 規則性が見えそうである。実際に書いてみると各深さにおいて一番左の頂点が1となり、右の兄弟(姉妹)に移るにつれて2ずつ増えることが分かる。

よって$$j(n) = 2(n - 2^p) + 1$$と予測できる(ただし$$p$$は自然数で$$2^p \leq n < 2^{p+1}$$)。 これは$$p$$に関する帰納法で示せる。