東京大学 情報理工学研究科 数理情報学 2022年8月実施 第5問

标签：

• Tokyo-University
• Non-Adjacent-Form-Signed-Binary-Representation

Author

hari64boli64, 祭音Myyura

Description

自然数（正の整数）$d$ に対して、

$$d = \sum_{i=0}^{n} d_i 2^i, \quad d_i \in \{-1,0,1\} \quad (i = 0,1, ..., n - 1), \quad d_n = 1$$

を満たす整数の列 $(d_0, d_1, ..., d_n)$ を $d$ の三値表現と呼ぶ。 また、$d$ の三値表現 $(d_0, d_1, ..., d_n)$ で、$1 \leq i \leq n$ の範囲の各整数 $i$ に対して、

$$d_{i-1}d_i = 0$$

が成立するものを $d$ の疎な三値表現と呼ぶ。以下の設問に答えよ。

(1) 自然数 $n$ に対し、疎な三値表現 $(d_0, d_1, ..., d_n)$ で表現可能な自然数の最大値 $L_n$ を求めよ。

(2) 任意の自然数 $d$ に対し、$d$ の疎な三値表現は一意的に定まることを示せ。

(3) 自然数 $d$ の二進表現を疎な三値表現へ変換する $O(\log d)$ 時間アルゴリズムを設計せよ。

(4) 整数の列 $(a_0, a_1, ..., a_n)$ に対して、零でない整数 $a_i$ の個数を $w(a_0, a_1, ..., a_n)$ と表す。自然数 $d$ の疎な三値表現 $(d_0^*, d_1^*, ..., d_m^*)$ と任意の三値表現 $(d_0, d_1, ..., d_n)$ に対し、

$$w(d_0^*, d_1^*, ..., d_m^*) \leq w(d_0, d_1, ..., d_n)$$

が成り立つことを示せ。

(5) 自然数 $n$ に対し、$X_n$ を集合 $\{z \in \mathbb{N} \mid z \leq L_n\}$ 上の離散一様分布に従う確率変数とする。 $X_n$ の疎な三値表現 $(d_0^*, d_1^*, ..., d_m^*)$ を用いて、確率変数 $Y_n = w(d_0^*, d_1^*, ..., d_m^*)$ で定める。 このとき、

$$\lim_{n \to \infty} \frac{\mathbb{E}[Y_n]}{n} = \frac{1}{3}$$

が成り立つことを示せ。ただし、$\mathbb{N}$ は自然数全体の集合、$\mathbb{E}[Y_n]$ は $Y_n$ の期待値とする。

题目描述

对自然数（正整数）$d$，将满足

$$d=\sum_{i=0}^{n}d_i2^i,\qquad d_i\in\{-1,0,1\}\ (i=0,1,\ldots,n-1),\qquad d_n=1$$

的整数序列 $(d_0,d_1,\ldots,d_n)$ 称为 $d$ 的三值表示。 若 $d$ 的三值表示还满足：对每个整数 $i=1,\ldots,n$，

$$d_{i-1}d_i=0,$$

则称其为 $d$ 的稀疏三值表示。回答下列问题。

(1) 对自然数 $n$，求能够用稀疏三值表示 $(d_0,d_1,\ldots,d_n)$ 表示的自然数的最大值 $L_n$。

(2) 证明任意自然数 $d$ 的稀疏三值表示都唯一确定。

(3) 设计一个时间复杂度为 $O(\log d)$ 的算法，将自然数 $d$ 的二进制 表示转换为稀疏三值表示。

(4) 对整数序列 $(a_0,a_1,\ldots,a_n)$，以 $w(a_0,a_1,\ldots,a_n)$ 表示其中非零整数 $a_i$ 的个数。设 $(d_0^*,d_1^*,\ldots,d_m^*)$ 是自然数 $d$ 的稀疏三值表示， $(d_0,d_1,\ldots,d_n)$ 是 $d$ 的任意三值表示。证明

$$w(d_0^*,d_1^*,\ldots,d_m^*) \leq w(d_0,d_1,\ldots,d_n).$$

(5) 对自然数 $n$，令 $X_n$ 是集合

$$\{z\in\mathbb{N}\mid z\leq L_n\}$$

上的离散均匀随机变量。利用 $X_n$ 的稀疏三值表示 $(d_0^*,d_1^*,\ldots,d_m^*)$，定义

$$Y_n=w(d_0^*,d_1^*,\ldots,d_m^*).$$

证明

$$\lim_{n\to\infty}\frac{\mathbb{E}[Y_n]}{n}=\frac13.$$

其中 $\mathbb{N}$ 表示自然数集，$\mathbb{E}[Y_n]$ 表示 $Y_n$ 的期望。

Kai

この疎な三値表現は、符号付き二進数の非隣接形式（NAF）である。

(1)

貪欲に 1 を割り当てていくのが最善。$2^n+2^{n-2}+\cdots$ が答え。

$$\begin{aligned} L_n=\begin{cases} \frac{2(2^{n+1}-1)}{3} & n\text{が奇数} \\ \frac{2^{n+2}-1}{3} & n\text{が偶数} \end{cases} \end{aligned}$$

(2)

存在性は (3) より言えるので、一意性のみ言えばよい。 相異なる疎な表現 $\{d_i\}$と$\{e_i\}$ が存在したとする。 長さが異なる場合は上位に $0$ を補う。これらの内、相異なる添え字 $i$ の内、最小のものを考える。

$d_i,e_i$ の内、片方が $0$ の場合、この桁において $2^i$ のズレが生じるが、これ以降の桁において生成できるズレは、$2^{i+1}$ の倍数のみ。 よって、$d$ と $e$ で表す数が異なり矛盾。

$d_i,e_i$ が、共に $1$ か $-1$ の場合、この桁において $2^{i+1}$ のズレが生じるが、これ以降の桁において生成できるズレは、疎性に注意すると、$2^{i+2}$ の倍数のみ。 よって、$d$ と $e$ で表す数が異なり矛盾。

以上より、示された。

(3)

下位のビットから見ていって、二進数の $0111(8*0+4*1+2*1+1*1)$ を $(1,0,0,-1)(8*1+4*0+2*0+1*(-1))$ に変換していくのが主な方針である。 詳細は以下。計算量は自明に $O(\log d)$ である。

油断した実装だと、十進法における $11$ (二進表現で $1011$) が三値表現で $(1,1,0,-1)$ になって、疎でなくなるので注意(一敗)。 正しくは、$(1,0,-1,0,-1)=16-4-1=11$ である。 実装の入力文字列と出力列は、いずれも下位桁から上位桁の順である。

なお、Slack 上では、上位のビットから貪欲に見ていくという方針もあった。 コード 1 において、anotherSolution という関数で実装している。 尤も、二進表現を疎な三値表現に変換せよという問題だったので、あまり想定解ではないかも知れない。

コード 1

from collections import defaultdict

def toSparseTernaryRepresentation(S: str):
    bits = [int(c) for c in S]
    ret = []
    i = 0
    carry = 0
    while i < len(bits) or carry:
        b = (bits[i] if i < len(bits) else 0) + carry
        next_bit = bits[i + 1] if i + 1 < len(bits) else 0

        if b % 2 == 0:
            ret.append(0)
            carry = b // 2
        else:
            digit = -1 if next_bit == 1 else 1
            ret.append(digit)
            carry = (b - digit) // 2
        i += 1
    return ",".join(map(str, ret))


def anotherSolution(n: int):
    # ここで L(i) は第 0,...,i-1 桁だけで作れる絶対値の最大値であり、
    # 問 (1) の L_{i-1} に対応する。
    def L(i):
        if i <= 0:
            return 0
        if i % 2 == 1:
            return (2 ** (i + 1) - 1) // 3
        else:
            return 2 * (2**i - 1) // 3

    d = []
    for i in range(n.bit_length() + 2)[::-1]:
        if abs(n - (2**i)) <= L(i - 1):
            n -= 2**i
            d.append(1)
        elif abs(n + (2**i)) <= L(i - 1):
            n += 2**i
            d.append(-1)
        else:
            d.append(0)

    d = d[::-1]
    while d[-1] == 0:
        d.pop()
    return ",".join(map(str, d))


def problem5():
    maxN = 16
    zeroCnt = 0
    cntPer3 = defaultdict(int)
    for n in range(1, (1 << maxN) + 1):
        S = bin(n)[2:][::-1]
        T = toSparseTernaryRepresentation(S)
        S += "0" * (maxN - len(S))
        listT = list(map(int, T.split(",")))
        listT += [0] * (maxN - len(listT))
        if listT[maxN // 2] == 0:
            zeroCnt += 1
            cntPer3[tuple(S[maxN // 2 - 1 : maxN // 2 + 2][::-1])] += 1
    print(f"result: {zeroCnt/(1<<maxN)}")
    print(f"cntPer3: {sorted(cntPer3.items())}")


def main():
    maxIntPerDigit = defaultdict(int)
    for n in range(1, 1000 + 1):
        S = bin(n)[2:][::-1]

        # ternary representation
        T = toSparseTernaryRepresentation(S)
        print(f"binary: {S} | ternary: {T}")

        # another solution
        T2 = anotherSolution(n)
        assert T == T2, f"{T} != {T2}"

        # assertion
        TasInt = sum([c * (2**i) for i, c in enumerate(list(map(int, T.split(","))))])
        assert TasInt == n

        # count
        maxIntPerDigit[len(T.split(","))] = max(maxIntPerDigit[len(T.split(","))], n)

    print(f"maxIntPerDigit: {maxIntPerDigit}")


if __name__ == "__main__":
    main()
    # problem5()

result

binary: 1 | ternary: 1
binary: 01 | ternary: 0,1
binary: 11 | ternary: -1,0,1
binary: 001 | ternary: 0,0,1
binary: 101 | ternary: 1,0,1
binary: 011 | ternary: 0,-1,0,1
binary: 111 | ternary: -1,0,0,1
binary: 0001 | ternary: 0,0,0,1
binary: 1001 | ternary: 1,0,0,1
binary: 0101 | ternary: 0,1,0,1
binary: 1101 | ternary: -1,0,-1,0,1
binary: 0011 | ternary: 0,0,-1,0,1
binary: 1011 | ternary: 1,0,-1,0,1
binary: 0111 | ternary: 0,-1,0,0,1
binary: 1111 | ternary: -1,0,0,0,1
binary: 00001 | ternary: 0,0,0,0,1

(4)

整数 $d$ の符号付き二進表現における非零桁数の最小値を $\mu(d)$ とし、 $\mu(0)=0$ とおく。符号を反転すれば $\mu(-d)=\mu(d)$ である。 最下位桁の偶奇から、

$$\mu(2k)=\mu(k),\qquad \mu(2k+1)=1+\min\{\mu(k),\mu(k+1)\}$$

が成り立つ。また、最小表現に $1$ または $-1$ を加え、同じ指数の項を整理すると、 非零項数を高々 $1$ 増やした表現が得られる。実際、逆符号の同じ項は相殺し、 同符号の二項 $\pm2^i\pm2^i$ は一項 $\pm2^{i+1}$ にまとめればよい。 この操作は項数を減らすので有限回で終わる。したがって

$$|\mu(k+1)-\mu(k)|\leq1.$$

これを用いると、

$$\begin{aligned} \mu(2k+1)&=1+\min\{\mu(k),\mu(k+1)\}\geq\mu(k)=\mu(2k),\\ \mu(2k+1)&\geq\mu(k+1)=\mu(2k+2). \end{aligned}$$

従って、奇数 $d>1$ の最下位桁を選ぶ際、 $d\equiv1\pmod4$ なら $+1$ を、$d\equiv3\pmod4$ なら $-1$ を選ぶと、 残りを $2$ で割った整数が偶数となり、上の二つの候補のうち最小の重みを達成する。 $d=1$ では一桁の表現を選ぶ。偶数の場合は最下位桁を $0$ として $2$ で割る。 これは (3) のアルゴリズムであり、奇数の処理の直後には $0$ の桁が現れるので疎な表現になる。 残りの整数に関する帰納法により、この表現の重みは $\mu(d)$ である。 よって題意の不等式が成り立つ。

最小の重みを達成する表現自体は一意とは限らない。 例えば $3=2+1=4-1$ では、どちらの表現も重み $2$ である。

(5)

長さ $k$ の疎な列 （各桁は $-1,0,1$）の総数を $F_k$、その全列にわたる重みの総和を $T_k$ とする。このとき

$$\begin{aligned} &F_0=1,\quad F_1=3,\quad F_k=F_{k-1}+2F_{k-2},\\ &T_0=0,\quad T_1=2,\quad T_k=T_{k-1}+2T_{k-2}+2F_{k-2}. \end{aligned}$$

したがって母関数は

$$F(x)=\frac{1+2x}{1-x-2x^2},\qquad T(x)=\frac{2x+2x^2F(x)}{1-x-2x^2}.$$

支配的な極 $x=1/2$ を比較すると

$$F_k=\frac43\,2^k+O(1),\qquad T_k=\frac49\,k2^k+O(2^k),$$

ゆえに $T_k/F_k=k/3+O(1)$ である。

$(1)$--$(3)$ より、$1,\ldots,L_n$ は最高位が高々 $n$ の疎な表現と ちょうど一対一に対応する。最高位が $m\geq1$ の疎な表現では、その桁は $1$、第 $m-1$ 桁は $0$ であり、残る $m-1$ 桁は上記の任意の疎な列である。従って、

$$L_n=1+\sum_{m=1}^nF_{m-1},\qquad \mathbb E[Y_n] =\frac{1+\sum_{m=1}^n(F_{m-1}+T_{m-1})} {1+\sum_{m=1}^nF_{m-1}}.$$

$F_k=\Theta(2^k)$ と上の漸近式を代入すれば $\mathbb E[Y_n]=n/3+O(1)$ となる。したがって

$$\lim_{n\to\infty}\frac{\mathbb E[Y_n]}{n}=\frac13.$$