東京大学情報理工学研究科数理情報学 2023年度第5問

Author

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\) の期待値とする。

Kai

平衡三進法と呼ばれる有名な記法が元ネタ？

(1)

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

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

(2)

存在性は (3) より言えるので、一意性のみ言えばよい。相異なる疎な表現 \(\{d_i\}\)と\(\{e_i\}\) が存在したとする。これらの内、相異なる添え字 \(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

import math
from collections import defaultdict

from numba import jit
from tqdm import tqdm


@jit(cache=True)
def toSparseTernaryRepresentation(S: str):
    ret = ""
    i = 0
    while i < len(S):
        if S[i] == "0":
            ret += "0,"
            i += 1
        elif S[i] == "1":
            cnt = 0
            while i < len(S) and S[i] == "1":
                cnt += 1
                i += 1
            if cnt == 1:
                ret += "1,"
            else:
                ret += "-1," + "0," * (cnt - 1)
                # originally, the following
                # must be inplace operation
                # for the sake of efficiency
                S = S[:i] + "1" + S[i + 1 :]
    return ret[:-1]


def anotherSolution(n: int):
    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(math.ceil(math.log2(n)) + 3)[::-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 tqdm(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\) に対して、疎な三値表現以外の表現によって、\(w\) の最小値は達成される。そのような最小値を達成する表現に対して、(3) と似たような手順を踏むことによって、さらに疎な表現が得られることを示し、最小値である事に対する矛盾か、疎な三値表現の一意性に対する矛盾を導く。

下位ビットから上位ビットに向かって対象としている疎でない表現に対する文字列検索を走査していく。

まず、表現に \((1,-1)\) か \((-1,1)\) が出現する場合、それぞれ \((0,1)\) と \((0,-1)\) で置き換えればより疎な表現が得られるので、\(w\) が減少している。その時点で操作を終了する。

次に、表現に \((1,1,\cdots)\) や \((-1,-1,\cdots)\) が出現する場合について考える。そのようなまとまり (ラン) を (3) と同様に最後まで考えて、\((0,1,1,\cdots,1)\) や \((0,-1,-1,\cdots,-1)\) が出現しているとしてよい。それぞれ \((1,0,\cdots,0,-1)\) と \((-1,0,\cdots,0,1)\) でそれぞれ置き換えるという操作を行う。 \(w\) が減少すれば、終了する。そうでない場合、すなわち、まとまりの長さが \(2\) の場合、\(w\) は変化こそしていないが、その時点までの疎性は保証されることに注意する。

以上の操作を最上位ビットになるまで繰り返す。

これが \(w\) の減少如何を問わず、最後のビットまで見た、という条件によって終了することは、 (3) の操作で高々1つしか桁が増えないこと、および、最後のビットが定義より \(1\) で、その先は \(0\) だけであることから従う。この時点で \(w\) は変化していないが、先述の通り、また、操作の内容より、必ず疎な表現になっている。そして、仮定より、この表現の \(w\) は、仮定の時点で登場している疎な三値表現の \(w\) よりも小さい。よって、自然数 \(d\) に対して二つの異なる疎な三値表現が得られるので、疎な三値表現の一意性に矛盾する。

以上より、疎な三値表現以外の表現によって、\(w\)の最小値は達成されないことが示された。

(5)

あまり想定解な気はしないが、一応 \(1/3\) の値が出てきたので、書いておく。

ある桁に注目した際に、その桁が \(0\) になる確率を求める。ただし、左右の方向に無限に列が続くとする。 \(n\) が無限であることから、そのような値と求めるべき値は一致する。

(3) のアルゴリズムにおける、変換前の 2 進数における状態で場合分けをして考える。すると、以下のような表が得られる。

変換前の2進数(当該桁+前後)	その桁が0になる確率
000	1
001	½(後続が0) \(\times\) ⅔(繰り上がりなし)
010	¼(後続が11) + ¼(後続が10) \(\times\) ⅓(繰り上がり)
011	1
100	1
101	½(後続が0) \(\times\) ⅔(繰り上がりなし)
110	¼(後続が11) + ¼(後続が10) \(\times\) ⅓(繰り上がり)
111	1

この表における確率を合計すると、\((16/3)\times(1/8)=2/3\) となるが、これは、求めるべき確率が \(1/3\) であることと一致する。

この表の意味を説明する。まず、前準備として、変換前の 2 進数において、\(0\) になっている桁が、変換により繰り上がって \(1\) になる確率を考える。例えば、変換前に \(\boldsymbol{0}11\) だった場合、変換によって、\((\boldsymbol{1},0,-1)\) と \(1\) になる。このような確率を求める。これは、この確率を \(p\) と置くと、

\[ \begin{aligned} p &= 0\ (\text{後続が0}) \\ &+ 1/4 \times p\ (\text{後続が10、かつ、ここでも繰り上がりが起きる場合}) \\ &+ 1/4\ (\text{後続が11...}の場合) \end{aligned} \]

であるので、\(p=1/3\) となる。

次に、実際に表を埋める。

\(000\) の場合に当該桁 (つまり、真ん中の桁) が必ず \(0\) になることは、その変換アルゴリズムから明らか。

\(001\) の場合に当該桁が \(0\) になる確率を考える。後続が \(0\) の場合、変換前の二進数は \(0\boldsymbol{0}10\) となり、変換によって、\((0,\boldsymbol{0},1,0)\) となるので、\(0\) となる。しかし、先述の繰り上がりによって、後続が \(0\boldsymbol{0}11\) となってしまうと、変換によって、\((0,\boldsymbol{1},0,-1)\) となり、\(1\) となる。よって、繰り上がりが起きない確率を求めなければならず、これは、\(1/2 \times 2/3\) である。

\(010\) の場合に当該桁が \(0\) になる確率を考える。これも殆ど同様で、繰り上がりが起きるかどうかに注意すると、これは \(1/4+1/4 \times 1/3\) となる。

他も同様。

よって、期待値は \(1/3\) と示された。

東京大学 情報理工学研究科 数理情報学 2023年度 第5問