D - Digits of Prefix Product Editorial
by
miscalculation53
tester 解
次のように定められる \(a_1, \dots, a_{10}\) が条件を満たします:
\(\begin{aligned} a_1 &= 1818\dots1818 && (100\ 桁), \\ a_2 &= 9999\dots9999 && (100\ 桁), \\ a_3 &= 9999\dots\dots9999 && (200\ 桁), \\ &\vdots \\ a_{10} &= 9999\dots\dots\dots9999 && (25600\ 桁). \end{aligned}\)
桁数の合計は \(51200\) 桁です。
\(4\) つ目の条件を満たすことの略証:
数学的帰納法により示します。\(b_1\) はよいです。\(b_i\) において同じ桁が隣り合わないとします。\(b_{i+1} = b_i \cdot 10^{(b_i\ の桁数)} - b_i\) を筆算で計算することを考えます。繰り下がりは中央の \(1\) 箇所でしか発生しません。繰り下がりに関係ない箇所での \(b_{i+1}\) は、左半分は \(b_i\) そのまま、右半分は \(b_i\) の各桁を \(9\) から引いたものとなっているため同じ桁が隣り合いません。繰り下がりに関係ある箇所については、\(b_i\) の上 \(2\) 桁が \(18\)、下 \(2\) 桁が \(18\) か \(82\) であることからわかります(\(1800-18-1 = 1781\), \(8200-18-1=8181\))。
posted:
last update:
