千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2023年8月実施 専門 A5

标签：

• Recurrence-Relation

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の擬似コードでは、配列の添字は $0$ 始まり、% は剰余、[True]*n は長さ $n$ の真の配列である。

def f(n):
    b = [True]*n
    pos = -1
    m = 0
    while m < n-1:
        c = 0
        while c < 2:
            pos = (pos+1)%n
            if b[pos]:
                c = c+1
        b[pos] = False
        m = m+1
    i = 0
    while i < n:
        if b[i]:
            return i
        i = i+1
    return -1

(1) $f(15),f(16)$ を求めよ。(2) 正整数 $n$ に対し $f(2n),f(2n+1)$ を $f(n)$ で表し、導出せよ。(3) 正整数 $k$ に対し $f(2^k-1)$ を求め、証明せよ。

题目描述

给定上述循环删除程序。(1) 求 $f(15),f(16)$。(2) 对正整数 $n$，用 $f(n)$ 表示 $f(2n),f(2n+1)$ 并说明理由。(3) 求 $f(2^k-1)$ 并证明。

Kai

(1)

$$\boxed{f(15)=14,\qquad f(16)=0}.$$

(2)

円周上に $0,1,\ldots,n-1$ を並べ、$0$ を一人目として数え、二人目を順に除く Josephus 問題である。

$2n$ 個の場合、最初の一周で奇数番が消え、残る $0,2,\ldots,2n-2$ の $0$ から同じ操作が始まる。よって

$$\boxed{f(2n)=2f(n)}.$$

$2n+1$ 個の場合、奇数番と続く $0$ が消えると、$2,4,\ldots,2n$ の $2$ から同じ操作が始まる。よって

$$\boxed{f(2n+1)=2f(n)+2}.$$

(3)

$f(1)=0$ であり、(2) より $a_k=f(2^k-1)$ は $a_1=0$、$a_k=2a_{k-1}+2$ を満たす。帰納法により

$$\boxed{f(2^k-1)=2^k-2}.$$