54という数字について考えよう. 54 は 1 より大きい因数を1つ以上使って7つの異なる方法で因数分解することができる. 54, 2×27, 3×18, 6×9, 3×3×6, 2×3×9 そして 2×3×3×3. 無平方(squarefree)の因数のみを使う場合は, 2つが残る: 3×3×6 と 2×3×3×3.

1 よりも大きい無平方の1つ以上の因数で n を因数分解する方法の個数を Fsf(n) と呼ぼう, つまり Fsf(54)=2 となる.

k=2 から n までの ΣFsf(k) を S(n) としよう.

S(100)=193 である.

S(10 000 000 000) を求めよ.

スー・モース数列 (Thue-Morse sequence) {Tn} は, 以下の条件を満たす二値数列である.

• $T_0 = 0$

• $T_{2n} = T_n$

• $T_{2n+1} = 1 - T_n$

$\{T_n\}$の最初のいくつかの項は以下のようになる. 01101001_10010_1101001011001101001.... (* 10010だけ赤強調)

$\{T_n\}$の部分数列として現れる各要素を二進表記の整数とし, それを(小さい方から)並べた数列を$\{A_n\}$と定義する. たとえば, 十進数の 18 は二進表記で 10010 と表される. これは$\{T_n\}$に$T_8$から$T_{12}$として現れる. したがって18 は$\{A_n\}$の要素となる. 十進数の 14 は二進表記で 1110 と表される. これは$\{T_n\}$に現れない. したがって14 は$\{A_n\}$の要素ではない.

数列$\{A_n\}$の最初のいくつかの項は以下のようになる.

同様に, $A_{100} = 3251, A_{1000} = 80852364498$となる.

$\displaystyle \sum_{k=1}^{18} A_{10^k}$の下9桁を求めよ.

N 個の一列に並んだ座席がある. N 人の人たちが以下のルールに従って次々に座席を埋めていく.

1. 隣接する座席が空いている座席があれば, その座席を取る.

2. そのような座席がなく, 隣接する座席が一つのみ埋まっている座席があれば, その座席を取る.

3. それ以外の場合は, 残っている利用可能な座席を取る.

このルールで N 人の人たちが N 個の座席を取るときの可能性の数を T(N) としよう. 以下の図により T(4)=8 であることがわかる.

T(10) = 61632, そして T(1 000) mod 100 000 007 = 47255094 となることが確かめられる.

T(1 000 000) mod 100 000 007 を求めよ.

二項係数は90億 () 以上の桁を持つ数である.

二項係数のを法とする剰余を表す関数をとしよう.

, かつが素数のときのを計算せよ.

2人の対局者, アントンとベルンハルトが次のようなゲームをしている. n 個の石が1つの山に積まれている. 初回, 先手は取りうる正の整数個の石を取る, ただし山全体を取ることは出来ない. それから, 対局者はお互いに, 相手が前回取った数の最大2倍まで石を取れる. 最後の石を取ったものが勝者となる.

n=5 の場合をみてみよう. もし先手が2個以上の石を取ったときは後手が残りの石を取ることができる. もし先手が1個石を取れば, 残りは4個となり, 後手も1個取ると, 残りは3個になる. ここで先手は残りの3個の石をすべて取ることはできない, なぜなら 2x1=2, 最大2個の石しか取れないからである. 先手は1個石を取ると残りは2個になる. 後手は残りの2個の石を取ることができ, 勝者となる. つまり石の山が5個のときは後手必勝となる. 先手が勝勢の局面 ( ※ 訳注 : 最善の手を打てば相手がどんな手を打っても勝つことができる局面 ) となる石の取りかたは複数存在することがある. 例えば n=17 の場合, 先手は最初に1個, または4個の石を取ると勝つことができる.

先手が最初のターンで勝勢の局面に持ち込むことができる石の取り方のうち最大の石の数を M(n) と定義し, 後手必勝のときは M(n)=0 としよう.

n≤100 のときの ΣM(n) は 728 となる.

$n≤10^{18}$のときの ΣM(n) を求め,$10^8$を法として答えよ.

ボゴソート (bogo sort) より若干効率的な別種のソート, ボゾソート (bozo sort) は, 入力数列がソートされているかをチェックし, ソートされていなければランダムに二つの要素を入れ替える. この操作を数列がソートされるまで繰り返す.

入力数列を最初の4つの自然数からなるすべての順列として, 入れ替えの回数の期待値を計算すると, 4! 個の入力数列に対する入れ替え回数の平均は 24.75 となる. すでに数列がソートされている場合は入れ替え回数を0回とみなす.

この問題では, ボゾソートの変種について考える. 数列がソートされていなければランダムに3個の要素を選び, その3個の要素をランダムにシャッフルして入れ替える. これら3個の要素の置換は 3!=6, つまり6通りあり, 等しく起こりうるとする. すでに数列がソートされている場合はシャッフル回数を0回とみなすことにしよう. 入力数列を最初の4つの自然数からなるすべての順列として, シャッフルの回数の期待値を計算すると, 4! 個の入力数列に対するシャッフル回数の平均は 27.5 となる. ここで入力数列を最初の11個の自然数からなるすべての順列として考えよう. 11! 個の入力数列に対するシャッフル回数の平均, すなわちこのソートアルゴリズムが行われた場合のシャッフル回数の期待値はいくらになるだろう?

回答は整数になるよう四捨五入して答えよ.

三次ベジェ曲線は四点により定義される.

曲線は以下のように作られる : 線分上の点を, (の範囲内のに対し) となるように描く. 線分上の点を, 同じ値を使ってとなるように描く. 線分上の点を同じ値を使ってとなるように描く. 点によるベジェ曲線は, 線分上に取りうるすべてのによる, 点の軌跡と定義される. ( 全ての点に対しの値は同じであることに注意. )

(以下途中、アプレットをJSに作り替えよう)

調和級数$\displaystyle 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots$は発散することで知られている.

もし分母に9を含む項すべてを調和級数から削除すると, 驚くべきことにこの級数はおおよそ 22.9206766193 に収束する. この修正した調和級数をケンプナー級数 (Kempner series) と呼ぶ.

調和級数から分母に3つ以上の連続する桁がある項を削除する事によってできる別の修正調和級数について考えよう. 調和級数の最初の1200項から削除されるのは20項のみであることが確かめられる. その20個の削除される項とは, 以下の通りである.

$\displaystyle \frac{1}{111}, \frac{1}{222}, \frac{1}{333},\frac{1}{444},\frac{1}{555},\frac{1}{666},\frac{1}{777},\frac{1}{888},\frac{1}{999},\frac{1}{1000},\frac{1}{1110},$

$\displaystyle \frac{1}{1111},\frac{1}{1112},\frac{1}{1113},\frac{1}{1114},\frac{1}{1115},\frac{1}{1116},\frac{1}{1117},\frac{1}{1118},\frac{1}{1119}$

この級数は同様に収束する.

この級数の収束値を求めよ. 小数点以下11桁の位で四捨五入して答えよ.

標準的な52枚のトランプから, ペアや同じスートの2枚組を含まない4枚のカードを選んだ時, その4枚のカードの組をバドージ (Badugi) という.

トランプからn枚のカードを取る選び方のうち、そのn枚から4枚を選んでバドージを作れるような選び方の数をf(n)としよう。<!--4枚のカードの部分集合がバドージとなる n 枚のカードの選びかたの数を f(n) としよう. -->例えば, 標準的な52枚のトランプから5枚のカードを取る選び方は 2598960 通りあり, そのうち4枚のカードの部分集合がバドージとなるものは 514800 通りあるので, f(5) = 514800 となる.

4 ≤ n ≤ 13 のときの ∑f(n) を求めよ.

整数の辺が幾何数列 (等比数列), すなわちとなる三角形を幾何三角形 (geometric triangle) と定義しよう.

例えば, a = 144, b = 156, c = 169 の辺を持つとき, これは幾何三角形となる.

周囲の長さが以下となる幾何三角形は 861805 個ある.

周囲の長さが以下となる幾何三角形は何個あるか.