次のゲームは, 組み合わせゲーム理論の古典的な例である:

２人のプレイヤーが, 一列に並んだ n 個の白い正方形から開始して, 交互にターンを行う. 各ターンでは, プレイヤーは２つの隣り合う白い正方形を選び, 黒で塗る. 最初に色を塗ることができなくなったプレイヤーが負けとなる.

• n = 1 の場合, 有効な手はないため, 先手が自動的に負けとなる.

• n = 2 の場合, 有効な手は１つのみであり, その後, 後手が負けとなる.

• n = 3 の場合, 有効な手は２つあるが, どちらも後手が負ける状況となる.

• n = 4 の場合, 有効な手は先手に３つある; 先手は中央の２つの正方形を塗ると勝利できる.

• n = 5 の場合, 有効な手は先手に４つある(下図に赤で示す); しかしいずれを選んでも, 後手(青)が勝利する.

したがって, 1≦n≦5 に対し, 先手必勝となる n の値は 3 個ある. 同様に, 1≦n≦50 に対し, 先手必勝となる n の値は 40 個ある.

1≦n≦1 000 000 に対し, 先手必勝となる n の値は何個あるか.

Sを、10進で表した(1から始まる)自然数を連続してつなげた(無限に続く)文字列とする. すなわち S = 1234567891011121314151617181920212223242... となる.

いかなる数もこの文字列の中に無限回現れることは容易にわかる.

$f(n)$を$n$がSの中で$n$回目に現れた先頭の位置とする. 例えば,$f(1)=1, f(5)=81, f(12)=271, f(7780)=111111365$となる.

$1 ≦ k ≦ 13$について$\sum f(3^k)$を求めよ.

Nimは2人のプレイヤーがいくつかの山に分かれた石を交互にとっていくゲームである.

ここでは以下のようなNimについて考える.

• ゲーム開始時点で3つの山がある

• 各ターンでプレイヤーは任意の1つの山から1つ以上の任意の数の石をとる

• すべての石がなくなり, 石を取ることができなくなった最初のプレイヤーが負けとなる

$(n_1,n_2,n_3)$がそれぞれの山に残っている石の数を表すとすると

• 後手必勝の場合 0

• 先手必勝の場合 0以外

を返す関数$X(n_1,n_2,n_3)$が定義できる.

例えば$X(1,2,3) = 0$である. なぜなら先手がどのように石をとっても, 後手は二つの山に同じ数の石が残るようにとることができ,その後は先手と同じように他方の山から石をとっていけば勝てるからである. 具体的に書くと以下ようになる

• 先手 (1,2,1)

• 後手 (1,0,1)

• 先手 (0,0,1)

• 後手 (0,0,0)

正の整数$n ≦ 2^{30}$のうち$X(n,2n,3n) = 0$となるものはいくつあるか.

任意の自然数$n$について、関数\textrm{next_prime}(n)は$p>n$となるような最小の素数$p$を返す。

数列$a(n)$は a(1)=\textrm{next_prime}(10^{14}), a(n)=\textrm{next_prime}(a(n-1))（$n>1$のとき） で定義される。

フィボナッチ数列$f(n)$は $f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)$ （$n>1$のとき） で定義される。

数列$b(n)$は$f(a(n))$で定義される。

$1 ≦ n ≦ 100000$について$\sum b(n)$を求めよ。答えは1234567891011で割った余りで示せ。

アリスとボブは「ニム・スクエア」で遊んでいる. 「ニム・スクエア」とは3つの山で行う普通のニムと似ているが, プレイヤーは平方数の石だけを山から取れる. 3つの山の石の数を (a,b,c) として表す. 0 ≤ a ≤ b ≤ c ≤ 29 では先手が負ける状態は 1160 ある.

0 ≤ a ≤ b ≤ c ≤ 100 000 の場合に先手が負ける状態の数を求めよ.

ある工場で製造するICチップ個あたり箇所の欠陥がランダムに生じる. （一つのチップにつき複数の欠陥が生じ得る）

少なくとも3箇所以上の欠陥を持つチップができる確率をと置く 例えば

を小数点以下10桁に丸めて0.abcdefghijの形で答えよ.

四角形は各辺の長さが整数でをみたす凸四角形である. の長さは整数である. はの中点で,の長さも整数である. となるこのような四角形をbiclinic整数四角形と呼ぶ.

例えば以下の四角形はbiclinic整数四角形である. となっている.

を をみたす, 異なるbiclinic整数四角形の数とする. であることが確かめられる.

プログラミング言語Fractranで書かれたプログラムは, 分数のリストから構成される.

Fractranの仮想マシンの内部状態は正の整数であり, あるシード値が初期にセットされる. Fractranの各反復では, リストのうち, 状態の整数との積が整数となる初めの分数が状態の整数に掛けられる.

例えば,John Horton Conwayが書いた素数生成を行うFractranのプログラムの一つは, 次の14の分数から構成される:

$\displaystyle \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1}$

シードの整数 2 から始めると, プログラムの反復計算を行うと次の数列が得られる: 15, 825, 725, 1925, 2275, 425, ..., 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

この数列に現れる 2 のべき乗は$2^2, 2^3, 2^5, \dots$ である. この数列のすべての 2 のべき乗は素数の指数を持ち, かつすべての素数は 2 のべき乗の指数として, 適切な順序で現れることが示せる.

上のFractranのプログラムを用いてProject EulerのProblem 7（10001 番目の素数を求めよ）を解くと, プログラムが$2^{(10001番目の素数)}$を生成するまでに何回の反復が必要になるか.

爆竹が地上$100\,m$の高さで爆発する. 爆竹は爆発すると非常に細かい破片となり四方八方に初速$20 \, m/s$で広がる.

破片は空気抵抗を受けず,$g=9.81 \, m/s^2$で一定の重力場において動くものと仮定する.

破片が地面に到達するまでに動いた領域の体積($m^3$)を小数点以下4桁に丸めて答えよ.

実数$\sqrt{2}+\sqrt{3}$について考える. $\sqrt{2}+\sqrt{3}$の偶数乗を計算すると以下が得られる. $(\sqrt{2}+\sqrt{3})^2 = 9.898979485566356\dots$ $(\sqrt{2}+\sqrt{3})^4 = 97.98979485566356\dots$ $(\sqrt{2}+\sqrt{3})^6 = 969.998969071069263\dots$ $(\sqrt{2}+\sqrt{3})^8 = 9601.99989585502907\dots$ $(\sqrt{2}+\sqrt{3})^{10} = 95049.999989479221\dots$ $(\sqrt{2}+\sqrt{3})^{12} = 940897.9999989371855\dots$ $(\sqrt{2}+\sqrt{3})^{14} = 9313929.99999989263\dots$ $(\sqrt{2}+\sqrt{3})^{16} = 92198401.99999998915\dots$

これらの小数部分の先頭から連続している9の数は非減少であるように見える. 実際に$(\sqrt{2}+\sqrt{3})^{2n}$の小数部分は$n$を大きくすると$1$に近づいていくことが証明できる.

$p,q$を正の整数で$p<q$としたときに, $(\sqrt{p}+\sqrt{q})^{2n}$の小数部分が1に近づいていくような全ての実数$(\sqrt{p}+\sqrt{q})$について考える.

$C(p,q,n)$を$(\sqrt{p}+\sqrt{q})^{2n}$の小数部分の先頭から連続する9の数とする.

$N(p,q)$を$C(p,q,n) \geq 2011$となる最小の$n$とする.

$p+q \leq 2011$について$\sum N(p,q)$を求めよ.

$x_1, x_2, \dots, x_n$を以下のような長さ$n$の数列とする.

• $x_1 = 2$

• $1 < i \leq n$について$x_{i-1} < x_i$

• $1 \leq i,j \leq n$について$(x_i)^j < (x_j+1)^i$

長さ2のこのような数列は$\{2,4\}, \{2,5\}, \{2,6\}, \{2,7\}, \{2,8\}$の5つのみである. 長さ5のこのような数列は293ある. 以下がそのうちの3つの例である. $\{2,5,11,25,55\}, \{2,6,14,36,88\}, \{2,8,22,64,181\}$

$t(n)$を長さ$n$のこのような数列の個数とする. $t(10) = 86195, t(20) = 5227991891$である.

$t(10^{10})$を$\mod 10^9$で求めよ.

$n \leq i<m$（$i,m,n$は正の整数）に対し、10で割り切れる二項係数$_iC_n$の個数を$T(m,n)$とする。 $T(10^9, 10^7-10) = 989697000$である。

$T(10^{18}, 10^{12}-10)$を求めよ。

2つの石の山と2人のプレイヤーでゲームをする。 それぞれの手番で、プレイヤーは大きいほうの山から石を取り除く。 取り除く石の個数は、小さい方の山の石の個数の正の整数倍でなくてはならない。

例えば、順序つきの対 (6,14) で、小さいほうの山に6個の石、大きいほうの山に14個の石がある状態を表すとすると、先手は大きいほうの山から6個または12個の石を取り除くことができる。

いずれかの山から石を全て取り除いたプレイヤーが勝利する。

先手が必勝となる状態を勝利状態と呼ぶ。例えば、(1,5), (2,6), (3,12) は、先手は二つ目の山から即座に全ての石を取り除けるため、勝利状態である。

先手がどうしようとも後手が必勝となる状態を敗北状態と呼ぶ。例えば、(2,3)や(3,4)は敗北状態である：どのような手をとっても後手が勝利状態となる。

$0< x_i < y_i \leq N$について、すべての敗北状態$(x_i, y_i)$に対する$x_i+y_i$の総和を$S(N)$と定義する。$S(10) = 211, S(10^4) = 230312207313$となることが確かめられる。

$S(10^{16}) \mod 7^{10}$を求めよ。

$a\_n$を以下の式によって再帰的に定義される数列とする。

$a_1 = 1$ $\displaystyle a_n = \left ( \sum_{k=1}^{n-1} k \cdot a_k \right ) \mod n$

従って、$a_n$の最初の10個の要素は1,1,0,3,0,3,5,4,1,9となる。

下記を満たす対$(p,q)$の個数を$f(N,M)$で表す。

$1 \leq p \leq q \leq N$かつ$\displaystyle \left ( \sum_{i=p}^q a_i \right ) \mod M = 0$

$f(10,10)=4$であることが分かる。（(3,3), (5,5), (7,9), (9,10) の４個）

また$f(10^4,10^3)=97158$である。

$f(10^{12},10^6)$を求めよ。

月が開拓され, 土地はただで手に入るようになったが, 困ったことがある. 確保した土地の周りに壁を作らなければならないのだが, 月に壁を作るにはお金がかかるのだ. 各国には$500\textrm{m} × 500 \textrm{m}$の正方形の土地が割り当てられているが, 壁の内側にある領域だけ保有することになる. 251001 本の杭が１メートル間隔で格子状に設置されている. 壁は閉じた一つながりの直線であり, 各直線は杭どうしを結んでいなければならない.

大きな国はもちろん$250,000\textrm{m}^2$の土地全体を囲うよう$2000\textrm{m}$の壁を建てた. グランドフェンウィック大公国は予算が厳しく, あなた（皇室プログラマ）に, 囲われた面積／壁の長さ の比が最大となる形はどのようなものか計算するよう依頼した.

あなたは紙の上で予備計算を行った.$2000\textrm{m}$の壁で$250,000\textrm{m}^2$の土地を囲うと, 囲われた面積／壁の長さの比は125となる. 認められてはいないが, いくらか良いかもしれないアイデアを試してみよう：正方形の内部に, 四辺に接するように円を置けば, 面積は $250^2\pi \textrm{m}^2$に等しく, 周囲の長さは$500\pi \textrm{m}$となり, したがって囲われた面積／壁の長さの比はこれも125となる.

しかしながら, 三辺が75m, 75m, 75$\sqrt{2}$mの三角形を四つ正方形から切り離すと, 総面積は$238750\textrm{m}^2$で, 周囲の長さは$1400+300\sqrt{2}\textrm{m}$となる. したがって囲われた面積／壁の長さの比は130.87と著しく良くなる.

囲われた面積／壁の長さの比の最大値を求めよ. 答えを小数第９位で四捨五入し abc.defghijk の形で答えよ.

スライドパズルでは, カウンタを空白のスペースに向けて横または縦へスライドさせることができる. ゲームの目的は, 赤のカウンタを盤の左上角から右下角へ動かすことである；スペースはつねに右下角にある状態から始まる. 例えば次の一連の図は, $2×2$の盤にて5手でゲームを完了させる様子を示している.

$S(m,n)$を,$m×n$の盤でゲームを完了させる最小の手数を表すとする. 例えば,$S(5,4) = 25$であることが確かめられる.

$100$未満の素数$p$について,$S(m,n)=p^2$となる盤はちょうど 5482 個ある.

$10^6$未満の素数 p について,$S(m,n)=p^2$となる盤は何個あるか.

Sam と Max は, ２個のデジタル時計を「デジタルルート（数字根）時計」に作り変えるよう依頼されている. デジタルルート時計は, 数字根をステップごとに計算するデジタル時計である.

時計に数字が与えられると, 時計は数字を表示し計算を開始する. 結果にたどりつくまでの途中の値がすべて表示される. 例えば, 時計に 137 という数が与えられると, "137"→"11"→"2" と表示してから真っ黒になり, 次の数を待つ.

各デジタル数字はセグメント状のライトから構成される：横セグメントが３本（上, 中, 下）と縦セグメントが４本（左上, 右上, 左下, 右下）である. 数 "1" は右上と右下の縦セグメントでできており, 数 "4" は中の横セグメントと, 左上, 右上, 右下の縦セグメントからできている. 数 "8" はすべてのセグメントが点灯する.

時計はセグメントを点灯/消灯させるときに限りエネルギーを消費する. "2" を点灯させるには 5 回の遷移を要する. "7" は 4 回だけ遷移を要する.

Sam と Max は２個の異なる時計を作る.

Sam の時計は 137 のような数を与えられると, "137" を表示し, パネルを消灯してから次の数（"11"）を点灯し, 再び消灯してそして最終的に最後の数（"2"）を点灯, しばらくして消灯する. たとえば, 137 では, Sam の時計は次のように動く.

• "137"：(2 + 5 + 4) × 2 = 22 回の遷移（"137" の点灯/消灯）

• "11" ：(2 + 2) × 2 = 8 回の遷移（"11" の点灯/消灯）

• "2"　　：(5) × 2 = 10 回の遷移（"2" の点灯/消灯）

合計で 40 回の遷移である.

Max の時計は異なる動きをする. パネル全体を消灯するのではなく, 次の数に必要のないセグメントのみを消灯するという賢いやり方である. 数 137 に対して, Max の時計は次のように動く.

• "137"：2 + 5 + 4 = 11 回の遷移（"137" の点灯） 　　　　　7 回の遷移（数 "11" に必要ないセグメントの消灯）

• "11" ：0 回の遷移（数 "11" はすでに正しく点灯済み） 　　　　　3 回の遷移（始めの "1" と２つ目の "1" の下部分を消灯； 　　　　　上部分は数 "2" と共通である）

• "2"　　：4 回の遷移（"2" にするため残りのセグメントを点灯） 　　　　　5 回の遷移（"2" を消灯）

合計で 30 回の遷移である.

もちろん, Max の時計のほうが Sam より電力の消費が少ない. ２つの時計に$A = 10^7$から$B = 2×10^7$の間の素数が与えられる. Sam の時計で必要な遷移の総数と Max の時計で必要な遷移の総数の差を求めよ.

• 1次のシェルピンスキーグラフの三角形($S_1$)は正三角形である

• $S_{n+1}$は$S_n$3つをそれぞれのペアが角の頂点を一つ共有するように配置したものである

$C(n)$を$S_n$のすべての頂点を一度だけ通るような閉路の数とする. 例えば,$S_3$については下図のように8つの閉路が描けるため$C(3) = 8$となる.

$C(1) = C(2) = 1$ $C(5) = 71328803586048$ $C(10\,000) \mod 10^8 = 37652224$ $C(10\, 000) \mod 13^8 = 617720485$ であることが確認できる.

$C(C(C(10\, 000))) \mod 13^8$を求めよ.

正の整数$n$に対し$f(n)$を、$n$の倍数であり 10 進数で表すと 2 以下の数字のみが用いられる最小の数と定義する。

すると$f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222$である。

また$\displaystyle \sum_{n=1}^{100}\frac{f(n)}{n} = 11363107$である。

$\displaystyle \sum_{n=1}^{10000} \frac{f(n)}{n}$を求めよ。

ある自然数$n$がそのすべての素因数$p$について$p^2$で割り切れるとき多冪数と呼ぶ.

また, ある自然数$n$が別の自然数の累乗であるとき累乗数と呼ぶ.

多冪数のうち塁乗数でないものをアキレス数と呼ぶ. 例えば, $864(=2^5 \cdot 3^3)$や$1800(=2^3 \cdot 3^2 \cdot 5^2)$はアキレス数である.

ここで$S$と$φ(S)$（$φ$はオイラーのトーティエント関数）が共にアキレス数となるような自然数$S$を強アキレス数と呼ぶことにする. 例えば, 864は強アキレス数だが($φ(864)=288=2^5 \cdot 3^2$), 1800は強アキレス数ではない($φ(1800)=480=2^5 \cdot 3^1 \cdot 5^1$).

強アキレス数は$10^4$以下には7個, $10^8$以下には656個存在する.

$10^{18}$以下に強アキレス数はいくつ存在するか.

$N(i)$を$n!$が$(i!)^{1234567890}$で割り切れるような最小の整数$n$とする.

$S(u)$を$10 \leq i \leq u$に対し$S(u)=\sum N(i)$とする.

$S(1000)=614538266565663$である.

$S(1\, 000\, 000) \mod 10^{18}$を求めよ.

全ての整数$n$に対し、実数の無限数列$a(n)$は次のように定義される：

$a(n) = \left \{ \begin{array}{ll} 1 & n < 0 \\ \displaystyle \sum_{i=1}^\infty \frac{a(n-i)}{i!} & n \geq 0 \end{array} \right .$

例えば、

$\displaystyle a(0) = \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots = e - 1$

$\displaystyle a(1) = \frac{e-1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots = 2e - 3$

$\displaystyle a(2) = \frac{2e-3}{1!} + \frac{e-1}{2!} + \frac{1}{3!} + \dots = \frac{7}{2}e - 6$

ここで$e = 2.7182818...$はオイラーの定数である。

$a(n)$は整数$A(n)$と$B(n)$に対し$\displaystyle \frac{A(n)e + B(n)}{n!}$の形となることが示せる。

例えば$\displaystyle a(10) = \frac{328161643e - 652694486}{10!}$である.

$A(10^9)+B(10^9)$を求め、答えを$77\,777\,777$で割った余りを答えよ。

$y_0, y_1, y_2, \dots$を, ランダムな 32 ビット符号なし整数からなる数列とする。 （つまり、$0 \leq y_i < 2^{32}$で全ての値が同様に確からしい。）

数列$x_i$に対し次の漸化式が与えられる：

• $x_0 = 0$

• $i>0$のとき$x_i = x_{i-1} \,|\, y_{i-1}$（$|$はビットごとの論理和演算）

すべての$i \geq N$に対し$x_i = 2^{32}-1$（32ビットすべてが1）となるような添え字$N$が最終的に存在することが分かる。

$N$の期待値を求めよ。 答を小数点以下10桁に四捨五入して求めよ。

Susanは素数カエルを飼っている。 このカエルは、1から500までの番号がつけられた500個の正方形の上を跳びまわる。左右のいずれかの正方形に等確率で跳ぶことができ、範囲[1,500]の外に跳ぶことはできない。 （いずれかの端に着地したなら、次は自動的に移動可能な正方形に跳ぶ。）

素数である数が書かれた正方形にいる場合、次の正方形に跳ぶ直前に、カエルは2/3の確率で 'P' (PRIME)と鳴き、1/3の確率で 'N' (NOT PRIME)と鳴く。 素数でない数が書かれた正方形にいる場合、次の正方形に跳ぶ直前に、カエルは1/3の確率で 'P' と鳴き、2/3の確率で 'N' と鳴く。

カエルの開始位置は全ての正方形に対し等確率でランダムであり、また最初の15回の鳴き声を聞いたとすると、PPPPNNPPPNPPNPNと聞こえる確率は何か。

約分済みの分数 p/q の形で答えを入力せよ。

整数の集合$\{1, 2, \dots, n\}$から選ばれた秘密の数を、質問により当てようとしている。数（質問）を尋ねる際は、尋ねた数に等しいコストがかかり、次の三つのいずれかの答えを得る：

• 「秘密の数はあなたの推測した数より小さいです」

• 「そう、まさにその数です！」

• 「秘密の数はあなたの推測した数より大きいです」

$n$の値が与えられたとき、最適な戦略をとると、起こり得る最悪の場合に対し、総コスト（尋ねた質問の全ての和）が最小になる。例えば、

$n=3$の場合、とり得る最良の方法はもちろん"2"と尋ねることである。答えによりたちどころに秘密の数が分かるだろう。総コストは2である。

$n=8$の場合、「二分探索」型の戦略を用いるべきだろう：最初の質問は"4"となり、もし秘密の数が4より大きければ、追加で1または2回の質問をする必要があるだろう。 2番目の質問を"6"としよう。秘密の数がなおも6より大きければ、7と8を見分けるため3番目の質問を必要とするだろう。 このようにして3番目の質問は"7"となり、この最悪の場合のシナリオに対する総コストは4+6+7=17となる。

最初の質問として"5"を尋ねると、$n=8$に対する最悪の場合のコストを大幅に改善することができる。 もし秘密の数は5より大きいと告げられた場合は、2番目の質問を"7"とすれば、秘密の数が何であるか確実に分かる。（総コストは 5+7=12） もし秘密の数は5より小さいと告げられた場合は、2番目の質問を"3"とすれば、もし秘密の数が3より小さければ3番目の質問は"1"となり、総コストは 5+3+1=9 となる。 12 > 9なので、この戦略に対する最悪の場合のコストは12となる。これは先ほどの「二分探索」の戦略の結果より優れている；また他のいかなる戦略より優れているか、同コストである。 以上の通り、$n=8$に対する最適な戦略を述べた。

上述のように、$n$に対し最適な戦略をとることで得られる最悪の場合のコストを$C(n)$とする。 $C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12$である。 同様に、$\displaystyle C(100) = 400, \sum_{n=1}^{100} C(n) = 17575$である。

$\displaystyle \sum_{n=1}^{200000} C(n)$を求めよ。

$p = p_1\, p_2\, p_3 \dots$を、$\{0,1,2,3,4,5,6,7,8,9\}$から等確率で選んだランダムな数字からなる無限の数字列とする。 $p$は実数$0.p_1 \, p_2 \, p_3 \dots$に対応することが分かる。 また、区間$[0,1)$からランダムに実数を選ぶことは、$\{0,1,2,3,4,5,6,7,8,9\}$から等確率で選んだランダムな数字からなる無限数字列を選ぶことと等価であることが分かる。

任意の$d$桁の正の整数$n$に対して、$p_k, p_{k+1}, \dots ,p_{k+d-1}$が$n$の十進表記と同じ順序で一致するような最小の添字を$k$とする。 また、$g(n)$を$k$の期待値とする。$g(n)$は常に有限であり、面白いことに、常に整数であることが示せる。

たとえば、$n = 535$なら、 $p = 31415926\underline{535}897\dots$に対して$k = 9$である。 $p = 35528714365004956000049084876408468\underline{535}4\dots$に対して$k = 36$である。 他も同様にして$g(535) = 1008$となることが分かる。

$\displaystyle \sum_{n=2}^{999} \, g \Big ( \Big \lfloor \frac{10^6}{n} \Big \rfloor \Big ) = 27280188$である。$\displaystyle \sum_{n=2}^{999999} \, g \Big ( \Big \lfloor \frac{10^{16}}{n} \Big \rfloor \Big )$を求めよ。

注： $\lfloor \cdot \rfloor$は床関数を表す。

古典的な「はしごの交差」問題では, 狭く平らな通路の両壁に立てかけられた二本のはしごの長さ x と y が与えられる. 二本のはしごが交差する場所の通路からの高さ h がさらに与えられ, 通路の幅 w を求めることが要求される.

ここで, 四つの変数すべてが正の整数となる場合のみを対象にする. 例えば, x = 70, y = 119, h = 30 なら, w = 56 と計算できる.

実際, 0 < x < y < 200 となる整数 x, y, h に対し, w が整数解となる組み合わせ (x,y,h) は 5 つのみである: (70, 119, 30), (74, 182, 21), (87, 105, 35), (100, 116, 35), (119, 175, 40).

0 < x < y < 1 000 000 となる整数 x, y, h に対し, w が整数解となる組み合わせ (x,y,h) はいくつあるか.

3つの部屋が自動ドアをへだてて互いにつながっている。

各ドアはセキュリティカードによって操作される。いったん部屋に入るとドアは自動で閉まり、セキュリティカードは二度と使えなくなる。スタート地点にあるカード発行機からカードを無制限に出すことができるが, （スタートの部屋を含む）各部屋には検知機があり、もし 3 枚を超える枚数のカードを持っていたり、カードが床に放置されていることを検知すると、全てのドアは永久的にロックされる。しかし、各部屋には保管ボックスがあり、後で使うために任意の枚数のセキュリティカードを安全に蓄えておくことができる。

単純に部屋を一つずつ通り抜けようとすると、部屋 3 に入った時点で 3 枚のカードを使い切ってしまい、永久に部屋に閉じこめられてしまうことになるだろう。

しかし、保管ボックスを利用すると脱出は可能である。例えば、1枚目のカードを用いて部屋1に入り、保管ボックスにカードを1枚置き、3枚目のカードを使って部屋を出てスタートに戻る。そしてさらに3枚のカードをカード発行機から出せば、1枚を使って部屋1に入り、先ほどボックスに置いたカードを回収する。これで再びカードは3枚になるので、残りの3つのドアを通り抜けることができる。このやり方だと、計6枚のセキュリティカードを使って3つの部屋を通り抜けることができる。

最大3枚のカードを持てるとき、計123枚のセキュリティカードを用いれば6つの部屋を通り抜けることが可能である。

一度に持つことができるカードの最大の枚数を$C$とする。

通り抜ける部屋の数を$R$とする。

一度に持てるカードの枚数が最大$C$枚のときに、$R$個の部屋を通り抜けるのにカード発行機から出す必要のあるカードの最小数を$M(C,R)$とする。

たとえば、$M(3,6)=123, M(4,6)=23$である。 また、$3 \leq C \leq 4$に対し$\sum M(C,6)=146$である。

$3 \leq C \leq 10$に対し$\sum M(C,10)=10382$である。

$3 \leq C \leq 40$に対し$\sum M(C,30)$を求めよ。

$N \times N$の円盤が正方形のゲーム盤に置かれている。円盤にはそれぞれ黒面と白面がある。

各手番では、円盤を１枚選び、同じ横列と同じ縦列にある円盤をすべて裏返す：ゆえに$2 \times N-1$枚の円盤が裏返される。すべての円盤が白面となればゲームは終了する。 次の例は$5 \times 5$の盤でのゲームを示している。

このゲームを終わらせる最小の手数は 3 であることが示せる.

$N \times N$の盤の左下の円盤を座標$(0,0)$とする。 右下の円盤は座標$(N-1,0)$で左上の円盤は座標$(0,N-1)$である。

$N \times N$枚の盤での次の配置を$C_N$とする： $N - 1 \leq \sqrt{x^2 + y^2}$を満たす$(x,y)$の円盤は黒面である；さもなくば白面である。$C_5$は上に示されている。

配置$C_N$から始めてゲームを終わらせる最小の手数を$T(N)$とする。配置$C_N$が解けない場合は$T(N)$は$0$である。 $T(5)=3$であることが分かる。また$T(10)=29, T(1000)=395253$である。

$\displaystyle \sum_{i=3}^{31} T(2^i-1)$を求めよ。

$3 \times 3 \times n$の塔を$2 \times 1 \times 1$のブロックで埋める場合の数を$f(n)$とする。 ブロックは好きな方向に回転することができる。しかし、塔自身を回転・反転等させたものは別のものとして数える。

たとえば ($q=100\,000\,007$として)： $f(2) = 229,$ $f(4) = 117805,$ $f(10) \mod q = 96149360,$ $f(10^3) \mod q = 24806056,$ $f(10^6) \mod q = 30808124$

$f(10^{10000}) \mod 100000007$を求めよ。

あらゆる正の整数は、各項がいずれも$2^i \times 3^j$（$i,j \geq 0$）と表されるように分割することができる。

いずれの項も他の任意の項を割り切らないような分割のみを有効(valid)なものと考えよう。 例えば、$17 = 2 + 6 + 9 = (2^1 \times 3^0 + 2^1 \times 3^1 + 2^0 \times 3^2)$という分割は、2 が 6 を割り切るので有効でない。$17 = 16 + 1 = (2^4 \times 3^0 + 2^0 \times 3^0)$という分割も、1 が 16 を割り切るので有効でない。17 の唯一の有効な分割は $8 + 9 = (2^3 \times 3^0 + 2^0 \times 3^2)$である。

多くの整数は１つより多くの有効な分割を持つ。そのような最初の数である 11 は次の２つの分割がある。 $11 = 2 + 9 = (2^1 \times 3^0 + 2^0 \times 3^2)$ $11 = 8 + 3 = (2^3 \times 3^0 + 2^0 \times 3^1)$

$n$ の有効な分割の数を$P(n)$としよう。例えば$P(11)=2$である。

$P(17)$のように、有効な分割が１つのみとなる素数$q$だけを考えよう。

$P(q)=1$となる素数 $q<100$ の和は 233 である。

$P(q)=1$となる素数 $q<1000000$ の和を求めよ。

球面三角形とは, 球面上で, ３頂点の各対で交わる３本の大円弧によって作られる図形である.

中心$(0,0,0)$, 半径$r$の球を$C(r)$とする. 整数の座標をもつ$C(r)$の面上の点の集合を$Z(r)$とする. $Z(r)$を頂点とする球面三角形の集合を$T(r)$とする. 縮退した球面三角形, すなわち同一の大円弧上の３点から作られる球面三角形は$T(r)$に含まれない. $T(r)$のうち最小の球面三角形の面積を$A(r)$とする.

例えば$A(14)$は小数第７位で丸めると$3.294040$である.

$\displaystyle \sum_{r=1}^{50} A(r)$を求めよ. 答えを小数第７位で丸めて入力せよ.

汽車を使って, 4 個の貨物を ABCD の順に輸送する. しかし, 汽車が荷物を集めに来た際, ときに貨物が正しい順でないことがある. 並び替えのために貨物はすべて大きな回転台に移される. 特定の点で貨物が切り離されると, 汽車は自身につながったままの貨物ごと回転台から離れる. 残された貨物は 180 度回転する. 貨物はすべて再びつなげられ, 回転台を使う回数がなるだけ少なくなるようにこの手続きが繰り返される. ADCB のような配置は簡単に解くことができる：貨物を A と D の間で切り離し, DCB を回転すると正しい順が得られる. しかし, 汽車の操縦者であるシンプル・サイモンは効率があまりよくなく, いつも最初に貨物 A を正しい位置に移し, 次に貨物 B を移し, 以下これを繰り返すというやり方でこの問題を解く.

４個の貨物を使うと, Simon にとってあり得る最悪の配置（maximix 配置と呼ぶ）は DACB と DBAC である；それぞれ 5 回の回転を要する（最も効率的なアプローチを使うと 3 回の回転のみで解くことができるが）. DACB に対する彼の手順を以下に示す.

6 個の貨物に対する maximix 配置は 24 個あることが確かめられる. そのうち辞書順で 10 番目の maximix 配置は DFAECB である.

11 個の貨物に対し辞書順で 2011 番目の maximix 配置を求めよ.

ピーターは退屈するといつも, 何枚かボウルを円状に置き, １個ずつ豆を入れる. 次に, ある１枚のボウルから豆をすべて取り出し, 時計回りにボウルに１個ずつ落とし入れていく. 最後の豆を落とし入れたボウルから始めて, 最初の状況が再び現れるまでこれを繰り返す. 例えば５枚のボウルでは次のように動かす：

したがって５枚のボウルではピーターは最初の状況に戻るのに 15 手かかる.$x$枚のボウルから始めて, 最初の状況に戻るのに必要な手の数を$M(x)$と表そう. ゆえに$M(5) = 15$である. また$M(100) = 10920$であることが確かめられる.

$\displaystyle \sum_{k=0}^{10^{18}} M(2k+1)$を求めよ. 答えを$\mod 7^9$で入力せよ.

プラトンの天国には, 直線状に無限の枚数のボウルが存在する. 各ボウルは０個以上の有限個の豆が含まれている. 子供がゲームをプレイする. このゲームでは, １種類の手だけが許される：どれかのボウルから豆を２個取り除き, 両隣の２個のボウルに１個ずつ入れる. どのボウルも１個ないしは０個の豆を含んでいれば, ゲームは終了する.

例えば, それぞれ２個と３個の豆を含んだ隣り合う２枚のボウルを考えよう. 他のボウルはすべて空である. 次の８手でゲームは終了する：

次の数列が与えられる：

• $t_0 = 123456$

• $\displaystyle t_i = \left \{ \begin{array}{ll}\displaystyle \frac{t_{i-1}}{2} & t_{i-1}が偶数のとき\\ \\ \displaystyle \Big \lfloor \frac{t_{i-1}}{2} \Big \rfloor \oplus 926252 & t_{i-1}が奇数のとき \end{array} \right .$

  • $\lfloor \cdot \rfloor$は床関数を表す

  • $\oplus$はビットごとのXOR演算を表す

• $b_i = ( t_i \mod 2^{11} ) + 1$

最後の数列の最初の２項は$b_1 = 289, b_2 = 145$である. ２枚の隣り合うボウルに$b_1$個と$b_2$個の豆がある状態から始めると, ゲームを終えるのに 3419100 手が必要である.

1500枚の隣り合うボウルにそれぞれ$b_1, b_2,\dots, b_{1500}$個の豆がある状態を考えよう. 他のボウルはすべて空である. ゲームを終えるのにかかる手の数を求めよ.

個の正方形からなる水平方向の列に、中央の空白の正方形をへだてて、片側に個の赤の駒があり、もう一方の側に個の青の駒がある。例えばでは次のとおりである：

駒は、ある正方形から隣に移動させるか、隣の駒のさらにその隣が空いていれば、その駒を飛び越えることができる。

この数列の最初の 40 個の項の和を求めよ。

50 という数を考える. $50^2 = 2500 = 2^2×5^4$のため, $φ(2500) = 2×4×5^3 = 8×5^3 = 2^3×5^3$である. よって 2500 は平方数, かつ φ(2500) は立方数である.

$φ(n^2)$が立方数となる$1＜n＜10^{10}$の範囲の$n$の和を求めよ.

$φ$はオイラーのトーティエント関数を表す.

整数の寸法$w × h$をもつ長方形の方眼紙がある. 罫線の間隔は1である. 罫線に沿って方眼紙を二つに切り離し, 二つを重なりなく並び替えると, 別の寸法の長方形を新たに作ることができる.

例えば,$9 × 4$の寸法の方眼紙からは, 下のように切って並び替えると, 寸法$18 × 2, 12 × 3, 6 × 6$の長方形を作ることができる.

同様に, 寸法$9 × 8$の方眼紙からは, 寸法$18 × 4, 12 × 6$の長方形を作ることができる.

$w$と$h$の組に対し, 寸法$w × h$の方眼紙から作ることができる異なる長方形の数を$F(w,h)$とする. 例えば,$F(2,1) = 0, F(2,2) = 1, F(9,4) = 3, F(9,8) = 2$である. 始めの長方形と合同な長方形は$F(w,h)$に数えないことに注意しよう. また寸法$w × h$と寸法$h × w$の長方形は別とみなさないことに注意しよう.

整数$N$に対し,$0 < h ≤ w ≤ N$を満たす全ての$w$と$h$の組に対する$F(w,h)$の和を$G(N)$とする. $G(10) = 55, G(10^3) = 971745, G(10^5) = 9992617687$であることが確かめられる.

$G(10^{12})$を求めよ. 答えを$\mod 10^8$で入力せよ.

$\{a_1, a_2,\dots, a_n\}$を次のような長さ$n$の 整数列とする.

• $a_1 = 6$

• $1 \leq i < n$に対し : $φ(a_i) < φ(a_{i+1}) < a_i < a_{i+1}$

$a_n \leq N$となる数列の数を$S(N)$とする. 例えば$S(10) = 4$である：{6}, {6, 8}, {6, 8, 9}, {6, 10}. $S(100) = 482073668$と$S(10\, 000) \mod 10^8 = 73808307$であることが確かめられる.

$S(20\, 000\, 000) \mod 10^8$を求めよ.

注：$φ$はオイラーのトーティエント関数を表す.

Golomb の自己記述的数列 $\{G(n)\}$は,$n$が数列にちょうど$G(n)$回現れるような, 自然数の非減少の数列である. 最初のいくつかの$n$に対する$G(n)$の値は次の通りである.

$G(10^3) = 86, G(10^6) = 6137$である. また,$1 ≤ n < 10^3$に対し,$\sum G(n^3) = 153506976$である.

$1 ≤ n < 10^6$に対し,$\sum G(n^3)$を求めよ.

やがてペレドゥルは川の流れる谷にやってきた. そのへりには木々が生い茂り, 川の両岸には平らな牧草地があった. そしてこちらの岸には白い羊の群れ, 向こう岸には黒い羊の群れがいた. 白い羊の一匹がメェと鳴くと, 黒い羊の一頭が川を渡って, 白い羊となった. 黒い羊の一匹がメェと鳴くと, 白い羊の一頭が川を渡って, 黒い羊となった. ()

初期状態として, 黒い羊頭の群れと白い羊頭の群れが存在する. 羊全体の中からランダムで一頭が相手の群れに呼びかけ, 呼びかけられた群れの羊が一頭だけ色を変えて呼ばれた群れに合流する. この合流のあと, ペレドゥルは任意の数の白羊を除去してよい. 彼の目標は最後に残った黒羊の数を最大化することである.

うまく最大化できる戦略をとったときの, 最後の黒羊の期待値をとする.

であることがわかっている (小数点下6桁になるよう四捨五入してある)

を求めよ (同様に小数点下6桁になるよう四捨五入すること)

多くの数は平方数と立方数の和として表せる。複数のやり方で表せるものもある。

回文数であり、平方数と立方数の和として、ちょうど4通りのやり方で表せるものを考える。ただし、平方数と立方数はいずれも1より大きいものでなくてはならない。 例えば、5229225 は回文数であり、以下のようにちょうど４通りの異なるやり方で表せる：

• $2285^2 + 20^3$

• $2223^2 + 66^3$

• $1810^2 + 125^3$

• $1197^2 + 156^3$

このような回文数を小さいものから順に5つ求め、その和を答えよ。

7という数字は特別な数字である, なぜなら7は2進数では111と表せ, また6進数では11と表せる. (すなわち$7_{10} = 11_6 = 111_2$). 別の言い方をすると, 7は少なくとも二種類の1より大きい底の記数法でレプユニット(全ての桁が1である自然数)である.

ここで上記の特徴を有する正の整数を「強いレプユニット」と呼ぶことにする. 50未満には8つの強いレプユニットが存在する. :{1,7,13,15,21,31,40,43}. さらに, 1000未満の強いレプユニットの和は15864になる.

$10_{12}$未満の強いレプユニットの和を求めよ.

素数 2 と 3 の両方のみで割り切れる100以下の最大の整数は 96 である. $96 = 32 \times 3 = 2^5 \times 3$である. ２つの異なる素数$p$と$q$に対し,$p$と$q$の両方のみで割り切れる$N$以下の最大の正の整数を $M(p,q,N)$とする. そのような正の整数が存在しなければ$M(p,q,N) = 0$である.

例えば$M(2,3,100) = 96$である. $M(3,5,100) = 75$であって90ではない.90は2,3,5で割り切れるためである. また$M(2,73,100) = 0$である.2と73の両方で割り切れる100以下の正の整数は存在しないためである.

$S(N)$を全ての$M(p,q,N)$の和とする.$S(100) = 2262$である.

$S(10\, 000\, 000)$を求めよ.

任意の正の整数$k$に対して、分数$x_i/y_i$の有限数列$a_i$は次のように定義される：

$a_1 = 1 / k$ $a_i = (x_{i-1}+1)/(y_{i-1}-1)$($i>1$のとき。約分可能な場合は約分する）

$a_i$がある整数$n$になったとき（つまり$y_i=1$になったとき）数列はそこで終了とする。 ここで関数$f(k) = n$と定義する。 例えば$k = 20$のとき

$1/20 → 2/19 → 3/18 = 1/6 → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 = 6$

したがって$f(20) = 6$となる。

同様に$f(1) = 1, f(2) = 2, f(3) = 1$、$1 ≤ k ≤ 100$について$\sum f(k^3) = 118937$となる。

$1 ≤ k ≤ 2×10^6$について$\sum f(k^3)$を求めよ。

N.G. de Bruijn の銀貨ゲームの一変種

は次のように説明される :

四角いマスが帯状に並んだ盤面があり, そこにある個数の硬貨が最大一マスに一個で置かれている. 銀貨と呼ばれる硬貨がひとつだけ任意の位置にあり, 二人のプレイヤーは交互に硬貨の移動を繰り返す. プレイヤーはそれぞれの局面で基本移動か特殊移動のどちらかを行わなければならない.

基本移動はひとつの硬貨を選択しマスひとつ以上左に移動させる. 硬貨は盤面を出たり, 他の硬貨の上に乗せたり飛び越えたりしてはならない.

その一方, プレイヤーは基本移動ではなく, 一番左にある硬貨を手に入れるという特殊移動を選択することができる. もし基本移動が不可能な場合, プレイヤーは強制的に一番左の硬貨を手に入れなければならない.

銀貨を手に入れたプレイヤーが勝者となる.

後手がどのようにプレイしても, 先手が勝利できる硬貨の配列を「勝利配置」と呼ぶ.

仮に n 個のマスの盤面, c 個の普通の硬貨, 1個の銀貨の場合の勝利配置の数を W(n,c) とする.

すでに W(10,2) = 324, W(100,10) = 1514704946113500 が求められている.

半素数 1 000 036 000 099 (= 1 000 003 · 1 000 033 ) を法とする W(1 000 000, 100) の値を求めよ.

整数を定めたとき、クレイジー関数を次のように定義する：

また、と定義する。

例えば,なら、である。 またである。

の下 9 桁を求めよ。

黒白いずれかで色づけされた正方形の規則的な格子上をアリが動く. アリは四方（上下左右）のいずれかを向いており, 次のルールに則って正方形から隣接する正方形へ動く：

• 黒い正方形上にいる場合, その正方形の色を白に変えて反時計回りに向きを変え, １マス前進する.

• 白い正方形上にいる場合, その正方形の色を黒に変えて時計回りに向きを変え, １マス前進する.

格子全体が白の状態から始めるとき, アリが $10^{18}$回動いた後の黒い正方形の数は何個あるか.

月を中心、半径の球として表そう。

月面上、すなわちの表面で整数座標の位置には月面基地がある。座標にあるものを北極基地、座標にあるものを南極基地と呼ぼう。

すべての基地は、他の基地と互いに最短最短距離となる道路で結ばれている。それは両基地を通る大圏コース上にある。基地間の旅行は危険をともなう。2基地間の距離がならば、旅行のリスク測度はとなる（これをその道路のリスクと呼ぼう）。旅行が3基地以上からなる場合、利用する道路のリスクの合計がその旅行のリスクとなる。

北極基地から南極基地へ直接旅行すると距離はとなりリスクは1になる。北極基地から南極基地へ、にある基地を経由して旅行すると、距離は同じだがリスクは小さくなる：

月での北極基地から南極基地への旅行にともなう最小リスクをとしよう。

小数点以下11桁で四捨五入するととなる。

を求めよ。

小数点以下11桁で四捨五入し a.bcdefghijk の形式で回答せよ。

すべての部屋が辺の長さ1の完全な正六角形からなるミツバチの蜂の巣を考えよう.

ある特定の部屋に女王蜂が居る.

正の実数に対し, 女王蜂の部屋からの距離がある部屋の個数をとしよう(すべての距離は部屋の中心から部屋の中心までを計測したものとする). ここで蜂の巣はどんな距離でも対応できるほど大きいと仮定する.

次数 n の六角形果樹園(hexagonal orchard)は, 辺の長さ n の正六角形状に配置された三角形格子と定義される. 次数5の六角形果樹園の例を以下に示す :

緑色で強調された部分は, 中心から見たときにより近くの点によって隠されてしまう点を示している. 上記の次数5の六角形果樹園の場合, 中心から見て30個の点が隠されることがわかるだろう.

次数 n の六角形果樹園において中心から隠される点の個数を H(n) としよう. 以下に例を示す.

H(5) = 30. H(10) = 138. H(1 000) = 1177848.

H(100 000 000)を求めよ.