数の集合$A$について,$sum(A)$で$A$の要素の和を表す. 集合$B = \{1,3,6,8,10,11\}$を考えよう. $B$の$3$要素の部分集合は$20$個あり, それぞれ和は以下になる.

これらの和は$1$つしか現れない場合もそうでない場合もある. 集合$A$について, $U(A,k)$で, $A$の$k$要素の集合全体について和を取ったときに$1$回のみ現れる和の集合を表す. 上の例をとると, $U(B,3) = \{10,12,14,18,21,25,27,29\}$であり, $sum(U(B,3)) = 156$となる.

今, $100$個の要素を持つ集合 $S = \{1^2, 2^2, ..., 100^2\}$を考える. $S$の$50$要素の部分集合は$100891344545564193334812497256$個ある.

$50$要素の部分集合の和の中で$1$回のみ現れる和の集合の総和を求めよ. すなわち, $sum(U(S,50))$を求めよ.

二項係数$\dbinom{n}{k}$は三角形の形に並べることができる. すなわちパスカルの三角形である. 以下を見よ.

上から$8$行見るとパスカルの三角形は$12$個の異なる数を含む. $1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35$である.

任意の素数の二乗が$n$を割り切らないとき, 正整数$n$が平方因子を持たないと言う. 先ほどの$12$個の数字を見ると, $4, 20$ の以外は平方因子を持たない. 従って, 最初の$8$行の平方因子を持たない異なる数の和は$105$になる.

二乗すると「$1\_2\_3\_4\_5\_6\_7\_8\_9\_0$」の形となるような唯一の正整数を求めよ. ただし「$\_$」は1桁の数である.

ハミング数とは, どの素因数も5以下であるような正整数のことである. 最初から順に並べると, $1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15$となる. $10^8$以下のハミング数は$1105$個ある.

素因数が$n$以下の正整数を,type $n$の一般化ハミング数と呼ぶことにする. するとハミング数はtype $5$の一般化ハミング数である.

$10^9$以下のtype $100$の一般化ハミング数の個数を答えよ.

$k$ 入力の2進真理値表は $k$ 個の入力ビット(2進数, 0(偽)または1(真))から 1 個の出力ビットへの写像である. 例えば, 論理和(AND)と排他的論理和(XOR)の 2 入力真理値表は以下の通り:

6ビットの入力 $(a,b,c,d,e,f)$ に対し, 以下の式を満たす6入力の2進真理値表 $\tau$ はいくつあるか.

式 $t(n) = 2n^{2}-1\ (n \gt 1)$ で表される数 $t(n)$ について考える. 最初の数個を挙げると, $7, 17, 31, 49, 71, 97, 127, 161$ となる. この中では $49 = 7\times7$ と $161 = 7\times23$ だけが素数でないことがわかる. $n \leq 10000$ では $2202$ 個の $t(n)$ が素数である.

$n \leq 50,000,000$ で素数である $t(n)$ はいくつあるか.

いくつかの正整数 $k$ は, 整数の分割式 $4^t = 2^t + k$ が成り立つ. $4^t, 2^t, k$ は全て正の整数, $t$ は実数とする.

最初の $2$ つの分割は $4^1 = 2^1 + 2$ と $4^{1.5849625...} = 2^{1.5849625...} + 6$ である.

$t$ も整数である分割を完全と呼ぶ. $m \geq 1$を満たす $m$ に対して $P(m)$ を $k \leq m$ で分割が完全である割合と定義する. つまり $P(6) = 1/2$ である.

次の表はいくつかの $m$ に対する $P(m)$ の例である.

$P(m) \lt 1/12345$ を満たす最小の $m$ を求めよ.

$a=7, b=24, c=25$ の直角三角形について考える. この三角形の面積は$84$であり, 完全数$6$と$28$で割り切れる. さらに, この三角形は原始 (primitive) 直角三角形である: つまり, $gcd(a,b)=1, gcd(b,c)=1$ を満たす. さらに, $c$ は平方数である.

以下の条件を満たす直角三角形を"完全" (perfect) と呼ぶ:

• 原始直角三角形である

• 斜辺が平方数である

以下の条件を満たす直角三角形を"超完全" (super-perfect) と呼ぶ:

• 完全な直角三角形である

• 面積が完全数である$6$と$28$の倍数である

$c \leq 10^{16}$ を満たす完全な直角三角形のうち, 超完全でないものはいくつあるか.

A と B をビット列(0と1の連続列)とする. Bの左端から"Aの長さ"ビットがAと一致する時, AをBの"接頭部"(prefix)と呼ぶ. 例えば 00110 は 001101001 の接頭部だが, 00111 や 100110 の接頭部ではない.

サイズ$n$の"接頭符号"(prefix-free code)とは, 次の条件を満たす $n$ 個の異なるビット列の集合である: どのビット列も他のビット列の接頭部ではない. 下の例はサイズ$6$の接頭符号である.

ここでビット0を送るのに1ペニー, ビット1を送るのに4ペンスかかると仮定する. 上で挙げた接頭符号にかかる総計は35ペンスとなる. この例は非対称なコスト分布となるが, なんと(同じサイズの中で)もっとも安い符号の１つである. 短く書くと, $\textrm{Cost}(6)=35$ となる.

$\textrm{Cost}(10^{9})$を求めよ.

[訳注 ペンス: ペニーの複数形]

正三角形$ABC$の内側に鏡が張られている. 各頂点にはレーザーが通れるような微小の穴がある.

$C$から入ったレーザーが, 内側の辺で$11$回反射し頂点Cから出て行くような経路は$2$つ存在する. $1$つを下に示す. もう$1$つはこの逆である.

$1000001$回反射し出て行くような経路は$80840$通り存在する.

$C$から入ったレーザーが, 内側の辺で$12017639147$回反射し, 元の頂点$C$から出て行くような経路はいくつ存在するか.

三辺 $(a \leq b \leq c)$ が全て整数の三角形で, 三辺が次の式を満たしているものを"わずかに鈍角(barely obtuse)"と呼ぶ.

周辺の長さが $75,000,000$ 以下のわずかに鈍角な三角形はいくつあるか.

三辺 $(a \leq b \leq c)$ が全て整数の三角形で, 三辺が次の式を満たしているものを"わずかに鋭角(barely acute)"と呼ぶ.

周辺の長さが $25,000,000$ 以下のわずかに鋭角な三角形はいくつあるか.

$\bm{D_{0}}$ を2文字の文字列$\text{``Fa''}$とする. $n \geq 1$ では, $\bm{D_{n}}$ は $\bm{D_{n-1}}$ から以下の変換ルールに従い作られる.

つまり, $\bm{D_{0}}=\text{``Fa''}, \bm{D_{1}} = \text{``FaRbFR''}, \bm{D_{2}} = \text{``FaRbFRRLFaLbFR''}, \dots$ となる.

これらの文字列はコンピューターグラフィックスプログラムへの命令と解釈できる: "F"を"1ユニット前へ描け", "L"を"90度左を向け", "R"を"90度右を向け", "a"と"b"は無視する. カーソルの初期位置は(0,0), 向きは(0,1)方向, つまり上とする.

$\bm{D_{n}}$ は $n$次の"Heighwayのドラゴン"(Heighway Dragon)として知られる奇妙な図となる. 例えば, 下図は $\bm{D_{10}}$ である. 各"F"を1ステップとして数えると, 500ステップ目で図中で強調してある(18,16)に到達する.

$\bm{D_{50}}$ において $10^{12}$ ステップ後の座標を求めよ. 回答は $x,y$ という形式でスペースを入れずに入力せよ.

正の整数 に対して、を約数の2乗の和とする。例えば

である。

で, が平方数である全てのの和を求めよ。

ピーターは4面のサイコロを9つ持っている。サイコロの各面には1,2,3,4と書いてある。コリンは6面のサイコロを6つ持っている。サイコロの各面には1,2,3,4,5,6と書いてある。

ピーターとコリンはサイコロを投じ、出た目の合計を比べる。合計が多い方が勝ちである。もし出た目の合計が等しければ勝負は引き分けになる。

ピーターがコリンに勝つ確率はいくつだろうか？10進7桁に四捨五入で丸め、0.abcdefgという形で答えよ。

$\mid x \mid + \mid y\mid \ \leq \ r$ を満たす整数の座標 $(x,y)$ の集合 $S(r)$ について考える. $O$ を点 $(0,0)$ とし, $C$ を点 $(r/4, r/4)$ とする. $N(r)$ を次の条件を満たす $S(r)$ 中の点 $B$ の数とする: 三角形 $OBC$ が鈍角を持つ, つまり 最大角 $\alpha$ が $90 \lt \alpha \lt 180$ を満たす. 例えば $N(4)=24, N(8)=100$ である.

$N(1,000,000,000)$ を求めよ.

ロボットは $1/5$ の円弧(72°)を描き続けながら動く. 各ステップでは, 次の円弧を時計回りにするか反時計回りにするか好きに選べるが, その場では曲がらない.

北向きから始めて$25$回の円弧を経て, 閉路を描く道筋は$70932$通りあり, 下図はその一例である.

ロボットが北向きから始めて, $70$回の円弧を経て, 最後は元の位置に戻る道筋は何通りあるか. (円弧は何度交差してもよい)

座標軸に平行な直方体 (axis-aligned cuboid) は で与えられ, , を満たす点で構成される. 直方体の体積は で求められる. 複数の直方体を結合したものの体積を考えた場合, 直方体に重なりがあれば, 結合直方体の体積は それぞれの直方体の体積の和より小さくなる.

を以下のパラメータで与えられる座標軸に平行な直方体とする.

はラグ付きフィボナッチ法により生成される.

したがって, は , は となる

の結合直方体の体積は である.

の結合直方体の体積を求めよ.

内半径が $50 \textnormal{mm}$ のパイプを考える. このパイプの中に半径が $30 \textnormal{mm}, 31 \textnormal{mm}, \dots, 50 \textnormal{mm}$ の $21$ 個の球を収めたい. 最短のパイプの長さを求めよ.

μm ($10^{-6}$ m) 単位で一番近い整数に丸めて答えよ.

"The Chase" とは2つのサイコロと偶数人のプレイヤーによって行われるゲームである.

各プレイヤーはテーブルの周りに座っている．対面にいる2人のプレイヤーがそれぞれ1つのサイコロを持っているところからゲームを開始する. 各ターンにサイコロを持っている2人のプレイヤーがそれぞれサイコロを振る. もしプレイヤーが1を出した場合は, そのプレイヤーは自分のサイコロを左隣の人に渡す. 6を出した場合には, 右隣の人に渡す. それ以外の数字が出た場合には, サイコロは移動しない. サイコロを振りサイコロの移動を終えたときに1人のプレイヤーが2つのサイコロを持っていた場合, そのプレイヤーは負けとなりゲームは終了する.

100人のプレイヤーでゲームを行ったとき, ゲームが終了するターンの期待値はいくつか?

11桁目を四捨五入し, 上位10進10桁を答えよ.

$3600$ は特殊な数字である, というのは以下の特徴があるからである.

同様に, $82201 = 99^{2} + 280^{2} = 287^{2} + 2×54^{2} = 283^{2} + 3×54^{2} = 197^{2} + 7×84^{2}$ である.

1747年, オイラーはどのような数が平方数の和で表せるか証明した. 我々は以下のような4通りの式で表せる数 $n$ に着目する.

$a_{k},b_{k}$ は正整数とする.

$10^{7}$ 以下ではこれを満たす整数は $75373$ 個ある. $2 \times 10^{9}$ 以下ではいくつあるか.

$S_{n}$ を正 $n$ 角形とし, 各頂点の座標が以下の式で表せるとする.

各 $S_{n}$ は辺上と内部の全ての点からなる, 塗りつぶされた図形とする.

2つの図形 $S,T$ のミンコフスキー和(Minkowski sum) $S+T$ は, $S$ 上の全ての点と $T$ 上の全ての点を足した結果である. 点の足し算は $(u, v) + (x, y) = (u+x, v+y)$ で求める.

例として, $S_{3}$ と $S_{4}$ の和は下図のピンク色の六角形で表せる.

$S_{1864} + S_{1865} + \dots + S_{1909}$ はいくつ辺を持つか.

ブラマンジェ曲線(高木曲線, blancmange curve)は $0 \leq x \leq 1, y = \sum_{n=0}^{\infty} \frac{s(2^{n}x)}{2^{n}}$ を満たす $(x,y)$ の集合である.

$s(x)$ は $x$ から最も近い整数への距離を表す.

ブラマンジェ曲線より下の面積は $\frac{1}{2}$ であり, 下図のピンク色の部分である.

$C$ を $(\frac{1}{4}, \frac{1}{2})$ を中心とする半径 $\frac{1}{4}$ の円とする. 上図の黒線が $C$ である.

$C$ 内に含まれかつブラマンジェ曲線下部の面積を求めよ. 10進数8桁に四捨五入し, 0.abcdefgh という形で解答を入力せよ.

任意の2つの数字列 に対し, を という数列で定義する. 各項は前の2つの項をつなげたものである.

さらに を の中で最初に少なくても 桁ある項の, 番目の数字と定義する.

例:

とする. ここで を求めたい.

の最初の数項は以下の通り:

は 5項目の 35番目の数字となり, である.

を円周率 の小数点に続く 桁とする.

をさらに続く 桁とする.

$30 \times 30$ の格子状に並んだ正方形の中に$900$匹のノミがいる. 初期状態では, 1つの正方形に1匹のノミが入っている. 一回ベルが鳴るたびに, 各ノミはランダムに隣の正方形にジャンプする (殆どの場所では4方向を選べる. ただし, 端や角にいるノミは除く.)

50回ベルが鳴ったときに, 空っぽの正方形の数の期待値はいくつだろうか? 10進小数点以下6桁に四捨五入して答えよ.

次の条件を満たす(10進数で) $k$ 桁の正の整数を"バランスした"(balanced)と呼ぶ: 最上位 $\lceil \frac{k}{2} \rceil$ 桁の和と最下位 $\lceil \frac{k}{2} \rceil$ 桁の和が等しい. $\lceil x \rceil$ は"xのシーリング"(天井, ceiling of x)と呼び, $x$ 以上の最小の整数を表す. 例えば $\lceil \pi \rceil=4, \lceil 5 \rceil=5$ である.

例を挙げると, 全ての回文数はバランスしており, $13722$ もバランスしている.

$T(n)$ を $10^{n}$ 未満の全てのバランスした数の合計とする. 例えば, $T(1) = 45, T(2) = 540, T(5) = 334795890$ である.

$T(47)\ \textnormal{mod}\ 3^{15}$ を求めよ.

数列 $1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 \dots$ は, $T_{1}=T_{2}=T_{3}=1$ および $T_{n}=T_{n-1} + T_{n-2} + T_{n-3}$ によって定義される.

$27$ はこの数列の任意の項を割り切らないことが証明できる. $27$ はこの性質を持つ最初の奇数である.

この数列の任意の項を割り切らない $124$ 番目の奇数を求めよ.

整数$n \geq 4$に対して、$\sqrt{n}$以下の最大の素数を$n$の下位素数平方根 (lower prime square root)とし、$lps(n)$と表す。同様に、$\sqrt{n}$以上の最小の素数を$n$の上位素数平方根 (upper prime square root)とし、$ups(n)$で表す。

例えば$lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37$である。 $lps(n)$と$ups(n)$のいずれかが$n$を割り切るが、両方ではないとき、整数$n (\geq 4)$を半分割可能 (semidivisible)と呼ぼう。

15を超えない半分割可能な数は8, 10, 12で、それらの合計は30である。 15は$lps(15) = 3$と$ups(15) = 5$の両方の倍数なので、半分割可能でない。 さらに例を挙げると、1000 までの半分割可能な整数92個の合計は34825である。

999966663333 を超えない半分割可能な数全ての合計を求めよ。

$\varphi$ をオイラーのトーティエント関数とする, つまり自然数 $n$ に対して $\varphi(n)$ を $gcd(k,n) = 1$ を満たす $k\ (1 ≤ k ≤ n)$ の数とする.

繰り返し $\varphi$ を適用することで, 正の整数は段々値が減っていき, 最後は $1$ となる鎖を作る.例えば $5$ から始めると, $5,4,2,1$ という数列ができる.長さ $4$ の数列を全て以下に列挙する.

このうち素数から始まるのは$2$つだけであり, 合計は $12$ である.

$40000000$ 未満で長さ $25$ の数列を作る素数全ての合計を求めよ.

$2 \times 1$ と $3\times 1$ のレンガ(水平$\times$垂直方向)を使って壁を建てる. ただし追加条件として, 水平方向に隣接したレンガ間の隙間が上下の層にまたがってはならない. つまり, "伝播亀裂(running crack)"がないようにする.

例として, 下図の $9 \times 3$ の壁は条件を満たしていない. 赤線が伝播亀裂だからである.

$9 \times 3$ の亀裂のない壁は$8$通りの建て方がある. これを $W(9,3)=8$ と表す.

$W(32,10)$ を計算せよ.

次の式を満たす整数 が存在するとき, 正整数 をアレクサンダー整数 (Alexandrian integer) と呼ぶ.

例えば, はアレクサンダー整数である . は 番目のアレクサンダー整数であり, 番目まで並べると となる.

番目のアレクサンダー整数を求めよ.

"Blum Blum Shub" 擬似乱数生成器を用いて数列を作る：

$s_0 = 14025256$ $s_{n+1} = (s_n)^2 \mod 20300713$

これらの数$s_0 s_1 s_2 \dots$を連結して無限長の数字列$w$を作る。 すなわち$w = 14025256741014958470038053646...$となる。

正の整数$k$に対し、もし数字の合計が$k$となる$w$の部分文字列が存在しないなら、$p(k)$を 0 と定義する。もし数字の合計が$k$となる$w$の部分文字列が少なくとも一つ存在するなら、$z$をそのような部分文字列の中で最も前に出てくる部分文字列の先頭の位置として、$p(k)=z$と定義する。

例えば：

部分文字列 1, 14, 1402, ... はそれぞれ数字の合計が 1, 5, 7, ... であり、 1文字めから始まるので、$p(1)=p(5)=p(7)=...=1$となる。

部分文字列 4, 402, 4025, ... はそれぞれ数字の合計が 4, 6, 11, ... であり、 2文字めから始まるので$p(4)=p(6)=p(11)=...=2$となる。

部分文字列 02, 0252, ... はそれぞれ数字の合計が 2, 9, ... であり、 3文字めから始まるので$p(2)=p(9)=...=3$となる。

部分文字列 025 は 3 文字めから始まり数字の合計は 7 だが、より前にある（1 文字めから始まる）部分文字列が数字の合計が 7 であるため、$p(7) = 1$であって 3 ではないことに注意せよ。

$0 < k ≤ 10^3$では$\sum p(k) = 4742$であることがわかる。

$0 < k ≤ 2 \times 10^{15}$において$\sum p(k)$を求めよ。

それぞれ 1 から 100 まで番号の書かれた円盤が一列に無作為に並んでいる。

ちょうど 22 個の素数の番号のディスクが、番号順の位置と異なる場所にある確率を求めよ。 （素数でない番号のディスクはどれも番号順の位置にあってもなくてもよい。）

解答は小数点以下12桁に四捨五入し, 0.abcdefghijkl の形で入力せよ。

$(0,0),(N,0),(0,N),(N,N)$を通る円上にある、整数の座標を持つ点の数を$f(N)$とする。

$f(10000) = 36$である。

$f(N) = 420$を満たす正の整数$N (\leq 10^{11})$全ての合計を求めよ。

2人のプレイヤーが偏りのないコインを使用して"The Race"というゲームを交代で行う。

プレイヤー1のターンでは、コインを1回投げる。表が出たら1ポイントを獲得する。裏がでたらポイントは得られない。

プレイヤー2のターンでは、まずプレイヤー2は正整数$T$を選び、そしてコインを$T$回投げる。 もし全て表だったら$2^{T-1}$ポイントを得る。それ以外の場合はポイントは得られない。

プレイヤー1が先手である。勝者は先に100以上のポイントを得たプレイヤーである。

各ターンでプレイヤー2は自分が最も勝つ確率の高いコインを投げる回数$T$を選択する。

プレイヤー2の勝つ確率を求めよ。

10進数8桁に四捨五入し、0.abcdefgh という形で解答を入力せよ。

仕入れ業者'A'と'B'が豪華ギフトセット販売用に次の商品と品数を準備する。

仕入れ業者は商品を完全な状態で輸送するよう懸命に努力するが、いくつかは損傷してしまう。つまり、商品が駄目になってしまう。

業者は実績を次の2種類の統計で比較する。

• 各業者ごとの 5 つの「商品ごとの損傷率」は、損傷した商品の数を仕入れた商品の数で割ったものであり、これを 5 つの商品それぞれで求める。

• 各業者ごとの「全体損傷率」は全ての損傷した商品の数を仕入れた商品全ての数で割って求める。

驚いたことに、5つの各商品ごとの損傷率はAよりもBが悪く（高く）、その係数（損傷率を比較した比率）は同じ値であった。さらに、矛盾して見えるが、全体損傷率はBよりもAが悪く、その係数はやはりであることが業者の調べでわかった。

この驚くべき結果が起こるような35通りのが存在する。最小のはである。

最大のを求めよ。 各項が最小になるように約分した分数での形にして入力せよ。

等差と等比を用いた次の数列を考える：$u(k) = (900-3k)r^{k-1}$ $s(n) = \sum_{k=1}^n u(k)$とする。

$s(5000) = -600,000,000,000$を満たす$r$を求めよ。

小数点以下12 桁に四捨五入して解答を入力せよ。

二項係数$\displaystyle \left (\begin{array}{c}10\\3\end{array} \right )= 120$は $120 = 2^3 \times 3 \times 5 = 2 \times 2 \times 2 \times 3 \times 5$および$2 + 2 + 2 + 3 + 5 = 14$を満たす。 つまり${}_{10}C_3$を素因数分解した項の和は$14$である。

$\displaystyle \left ( \begin{array}{c} 20\,000\,000 \\ 15\,000\,000 \end{array} \right )$を素因数分解した項の和を求めよ。

6面のサイコロ（各面は 1 から 6）を 5 個振って、上位 3 個の合計が 15 となる場合は 1111 通りある。いくつか例を挙げる：

$D_1,D_2,D_3,D_4,D_5 = 4,3,6,3,5$ $D_1,D_2,D_3,D_4,D_5 = 4,3,3,5,6$ $D_1,D_2,D_3,D_4,D_5 = 3,3,3,6,6$ $D_1,D_2,D_3,D_4,D_5 = 6,6,3,3,3$

12面のサイコロ（各面は 1 から 12）を 20 個振って、上位 10 個の合計が 70 となる場合は何通りあるか。

$T(n)$を、以下のルールに従い4 × n のゲーム盤上を進む順路の数と定義する：

• 左上の角から始める

• 1マス分の上下左右の移動を繰り返す

• 各マスを全てちょうど1回ずつ通る

• 左下の角で終わる

下の図は 4 × 10 の盤上の順路の一例である：

$T(10)$は 2329 である。$T(10^{12})$を$10^8$で割った余りを求めよ。

分子が分母より小さい正の分数を真分数という。 任意の分母に対し、真分数は個ある。例えばでは 1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12 である。

約分できない分数を弾性分数 (resilient fraction)と呼ぶことにしよう。 さらに分母に対し弾性(resilience)を真分数のうち弾性分数の比率と定義し、で表す。例えばである。 ちなみには弾性がを満たす最小の分母である。

を満たす最小の分母を求めよ。

正整数に対し、をの約数全ての和とする。 例えばとなる。

おそらく知っているだろうが、完全数とはとなる数である。

正整数の完全商 (perfection quotient)を、と定義する。

に対し、が(は整数)となる正の整数全ての和を求めよ。

集合$\{1,2,\dots,n\}$に対し、$f(n,k)$を要素の合計が奇数となるような$k$要素からなる部分集合の個数と定義する。例えば$f(5,3) = 4$である。なぜなら集合$\{1,2,3,4,5\}$には合計が奇数となる要素 3 個からなる部分集合は 4 つあるからである。すなわち$\{1,2,4\}, \{1,3,5\}, \{2,3,4\}, \{2,4,5\}$である。

$n, k, f(n,k)$が全て奇数であるとき、$[n,k,f(n,k)]$を三つ子奇数 (odd-triplet)と呼ぶことにする。

$n ≤ 10$ではちょうど 5 個の三つ子奇数が存在する。それらは： [1,1,f(1,1) = 1], [5,1,f(5,1) = 3], [5,5,f(5,5) = 1], [9,1,f(9,1) = 5], [9,9,f(9,9) = 1]

$n ≤ 10^{12}$に対し三つ子奇数はいくつあるか。

おそらく15パズルはご存知だろう。ここでは、数字の書かれたタイルの代わりに、7枚の赤いタイルと8枚の青いタイルを使用する。

移動は、タイルの動いた方向 (Left, Right, Up, Down) の大文字のイニシャルで表す。すなわち、 最初の状態 (S) から文字列 LULUR を経て状態 (E) に至る。

各経路は、以下に示す擬似コードによってチェックサムが計算される：

checksum = 0 checksum = (checksum × 243 + $m_1$) mod 100 000 007 checksum = (checksum × 243 + $m_2$) mod 100 000 007 … checksum = (checksum × 243 + $m_n$) mod 100 000 007

$m_k$は移動の文字列の$k$番目の文字のアスキーコードの値である。アスキーコードは以下の通り：

上で例に挙げた文字列 LULUR の場合、チェックサムは 19761398 になるだろう。

では、状態 (S) から始めて、状態 (T) に到達する最短の経路を全て求めよ。

最小の長さを持つ経路のチェックサム全ての合計を求めよ。

$1 ≤ x, 0 ≤ y ≤ 1/x$の領域について考える。

$S_1$をこの曲線の下に入る最大の正方形とする。 $S_2$を残りの空間に入る最大の正方形とし、これを繰り返す。 $S_n$ のインデックスを (left, below) とする。left は$S_n$の左にある正方形の数を、below は $S_n$の下にある正方形の数を表す。

これらの正方形に番号を記したものを上の図に示す。 $S_2$は左に 1 個、下に 0 個の正方形があるので、$S_2$のインデックスは (1,0) である。 $S_{32}$のインデックスは (1,1) であることがわかる。$S_50$のインデックスも同じである。 50 は (1,1) をインデックスに持つ$S_n$の中で最大の$n$である。

(3,3) をインデックスに持つ$S_n$の中で最大の$n$を求めよ。

楕円の定義は以下の通り： 中心 M と半径 r を持つ円 c と、d(G,M)<r を満たす点 G が与えられたとき、 c と G から等距離にある点の軌跡が楕円となる。

楕円上の点の作成手順を下に示す。 (ToDo: アニメーションGIFが見えない) （訳注：円上の点UとGの垂直二等分線と、MからUの半径との交点が楕円上の点である。）

点 M(-2000,1500), G(8000,1500) とする。 円 c は中心が M, 半径 15000 とする。 G と c から等距離にある点の軌跡を楕円 e とする。 e の外の点 P から楕円に対し 2 本の接線$t_1, t_2$を描く。 $t_1, t_2$が楕円に接する点を R, S とする。

角 RPS が 45 度より大きくなるような格子点 P はいくつあるか。

となる数は 6227180929 が 1 番目である。

この性質を持つ 150,000 番目の数を求めよ。

約分できない分数を弾性分数 (resilient fraction)と呼ぶことにする。 さらに分母に対し弾性 (resilience)を、真分数のうち弾性分数の比率と定義し、で表す。例えばである。

数の弾性はとなる。はオイラーのトーティエント関数である。

さらに、数に対し共役弾性 (coresilience)をと定義する。

素数の共役弾性はである。

が単位分数であるようなを満たす合成数全ての合計を求めよ。

訳注：243が関連問題

S = {2, 3, 5, ..., 4999} を 5000 より小さい素数の集合とする。

要素の合計が素数となるような, S の部分集合の個数を求めよ。 最下位の 16 桁を答えとして入力せよ。

集合$\{1^1, 2^2, 3^3, \dots, 250250^{250250} \}$の空でない部分集合で、要素の合計が250で割り切れるようなものの個数を求めよ。最下位の 16 桁を答えとして入力せよ。

3 個の正整数の組$(a,b,c)$が次の式を満たすときこれをカルダノトリプレット (Cardano Triplet) と呼ぶ：

$\sqrt[3]{a + b \sqrt{c}} + \sqrt[3]{a - b \sqrt{c}} = 1$

例えば (2,1,5) はカルダノトリプレットである。

$a+b+c ≤ 1000$を満たすカルダノトリプレットは 149 ある。

$a+b+c ≤ 110,000,000$を満たすカルダノトリプレットはいくつあるか。

小さい子供が"数字イモムシ"を持っている。これは 40 のジグソーピースからなり、それぞれのピースは 1 つ数字が書いてあり、一列につなげると 1 から 40 まで順番に並ぶ。

毎晩、子供の父親は遊戯室にばらまかれたイモムシのピースを拾い集めなければならない。父親は無作為にピースを拾っていき、正しい順序に並べていく。 このようにイモムシを組み立てていくと、徐々にくっついていっていくつかの断片が出来上がっていく。 断片の数は0（何もない状態）から始まり、だいたい 11 か 12 まで増えた後、やがてまた減っていき 1 （全部くっついた状態）で終わる。

例えば：

無作為にイモムシを片づける過程で起こった最大の断片の数をMとする。 10ピースのイモムシの場合では、各 M が起こる場合の数は次のようになる。

つまり M の最頻値は 3 で平均値は 385643/113400 = 3.400732 である。（小数点以下6桁に四捨五入）

40 ピースのイモムシの場合は M の最頻値は 11 である。では M の平均値は？

小数点以下6桁に四捨五入し回答せよ。

与えられた平面上の点の集合に対し、以下を満たす凸多角形を凸ホール (convex hole)と定義する： 頂点は与えられた点のいくつかから成り、与えられた点を内部に含まない（頂点以外に、多角形の辺上に与えられた点があっても構わない）

例として、下の図は 20 個の点とそれに対するいくつかの凸ホールを示している。赤い多角形で示した凸ホールは 1049694.5 の単位正方形と面積が等しく、この点の集合に対し最大の凸ホールである。

この例では、次の擬似乱数によって生成された 最初の 20 個の点$(T_{2k−1}, T_{2k})$$(k = 1,2,\dots,20)$を使用した。

$S_0 = 290797$ $S_{n+1} = (S_n)^2 \mod 50515093$ $T_n = (S_n \mod 2000 ) − 1000$

すなわち$(527, 144), (−488, 732), (−454, −947), \dots$である。

この擬似乱数生成器による最初の 500 個の点を使用する凸ホールの中で、最大の面積を求めよ。 小数点以下に1桁をつけて回答を入力せよ。

をの各桁の階乗の和とする。例えばである。

をの各桁の和とする。つまりである。

をを満たす最小の正整数とする。は 5 だが、も 5 であり、であることがわかる。

をの各桁の和とする。つまりである。

さらに、は 267 であり、においては 156 であることがわかる。

においてを求めよ。