2つの数が10進数表記において少なくとも1つの共通する桁の数字を持つとき、それらをフレンド数と呼ぶことにする。例えば、1123と3981はフレンド数である。

$1 \leq p <q<n$ をみたすフレンド数の組 $(p, q)$ の個数を $f(n)$ とする。 $f(100)=1539$ である。

$f(10^{18}) \bmod 1000267129$ を求めよ。

n人のプレイヤーが隣り合ったペア同士で行うゲームを考える。1ラウンド目にはプレーヤー1と2が、2ラウンド目にはプレーヤー2と3が、というようにして、nラウンド目にはプレーヤーnと1が勝負を行う。$n+1$ ラウンド目には1と2が行い、その後は同じように繰り返していく。

つまり、$r$ ラウンド目にはプレーヤー $((r-1) \bmod n)+1$ とプレーヤー $(r \bmod n)+1$ が勝負をする。

各ラウンドでは、公平なコインを投げることによってどちらのプレーヤーの勝ちかを決める。あるプレーヤーがラウンド r と r+1 で両方勝ったとき、そのプレーヤーをこのゲーム全体の勝者とする。

$P_n(k)$ を、n人で行うゲームでプレーヤーkが勝者となる確率を既約分数で表したものとする。 例えば、$P_3(1)=12/49,$ $P_6(2) = 368/1323$ である。

$M_n(k)$ を、$P_n(k)$ の分子と分母の積とする。 例えば、$M_3(1) = 588,$ $M_6(2) = 486864$ である。

$M_{10^8+7}(10^4+7)$ の末尾の8桁を求めよ。

良く知られている通り、ガウスは全ての正整数が三つの三角数の和で表されることを証明した。（0は最も小さい三角数として含める。）実際、ほとんどの数は三つの三角数の和で表す方法が複数ある。

$G(n)$を、$n$を三つの三角数の和で表す方法の数とする。ただし、和を取る順番は区別する。

例えば$G(9)=7$であり次の通りである: $3+3+3, 0+3+6, 0+6+3, 3+0+6, 3+6+0, 6+0+3, 6+3+0$ $G(1000)=78, G(10^6)=2106$である。

$G(17526×10^9)$を求めよ。

デイブはバルコニーで宿題をしている。ピタゴラスの三角形についての発表の準備で厚紙から辺の長さが30cm、40cm、50cmの三角形を切り取ったときに突風が三角形を庭に吹き飛ばした。別の突風がこの三角形に小さな蟻を吹き付けた。哀れな蟻は完全に方角を見失い、草むらに戻るためにランダムな方向へまっすぐに這い始める。

蟻のすべての可能な三角形内の位置とすべての移動可能な方向が等確率であると仮定して、蟻が三角形の最も長い辺を超えて三角形を離れる確率はどれだけか？ 小数点以下10桁に四捨五入して回答せよ。

辺が整数長の三角形で、$120^\circ$ の角を持ち、辺長を $n$ 進数で表したときに、合わせるとその基数の数字全てをちょうど一度ずつ使うものを、n-パンデジタルと呼ぼう。

例えば、三角形 (217, 248, 403) は9-パンデジタルである。 これは $120^\circ$ の角を持ち、辺長を9進数で表すと $261_9, 305_9, 487_9$ となり、9進数の9個の数字を一度ずつ使っているからである。

$9 \leq n \leq 18$ について、全ての $n$-パンデジタル三角形の最長の辺の和を求めよ。

$s(n)$を数字の和が$n$となる最小の数と定義する。例えば$s(10)=19$である。 $\displaystyle S(k) = \sum_{n=1}^k s(n)$と定義する。$S(20)=1074$である。

また、$f_i$を$f_0 = 0, f_1 = 1,$$i \geq 2$について$f_i = f_{i-2} + f_{i-1}$と定義されるフィボナッチ数列とする。

$\displaystyle \sum_{i=2}^{90} S(f_i)$を求めよ。答えは$\mod 1000000007$で示せ。

重複のない直線の集合 $L$ が与えられたとき、 この集合の中の線の本数を $M(L)$、 それぞれの線が集合内の他の線と交差している回数の総和を $S(L)$ とする。 例えば、3本の線の2つの集合を下図に示す：

どちらの場合も、$M(L)$ は 3 で $S(L)$ は 6 である。 3本の線はそれぞれ、他の2本の線と交差している。 線が1点で交差していても、個々の線の交差はすべて別に数えることに注意せよ。

整数 $k \geq 1$ に対して点 $(T_{2k-1}, T_{2k})$ を考える。これは以下のように生成する：

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

例えば、最初の3つの点は (527, 144), (-488, 732), (-454, -947) である。 この方法で生成された点群の最初の $n$ 個が与えられたとき、それぞれの点を他の点と結んで作られる、他と異なる(unique)直線の集合を $L_n$ とする。 直線は両方向に無限に延長される。 次に、上記のように $M(L_n)$ と $S(L_n)$ を定義する。

例えば、$M(L_3) = 3,$ $S(L_3) = 6$ である。 また、$M(L_{100}) = 4948$, $S(L_{100}) = 24477690$ である。

$S(L_{2500})$ はいくつか。

$2^7 = 128$は2の累乗の中で最初に出てくる "12" から始まる数である。 次に小さい "12" から始まる数は$2^{80}$である。

ここで、関数$p(L, n)$を$2^j$の10進表記が$L$で始まるような$j$であって$n$番目に小さい値とする。先述の例を用いると$p(12, 1) = 7, p(12, 2) = 80$となる。

さて、ここで$p(123,45) = 12710$である。

$p(123,678910)$を求めよ。

ジークベルトとジョーがN個の小石の山を使い交互に行うゲームをする。

1. ジークベルトが最初に小石を取る。

   彼は（1からNの間で）好きなだけ小石を取ることができる。

2. 以降の各ターンで、順番になったプレイヤーは、

   少なくとも1個、最大で前回のプレイヤーが取った小石の数の倍の

   個数の小石を取る必要がある。

3. 最後の小石を取ったプレイヤーが勝ちとなる。

ジークベルトが最初のターンにすべての小石を取ることで常に勝つことができるが、 ゲームをより面白くするために、 （ジークベルトとジョーの両方が以降のゲームで最適な手を打つと仮定して） 彼がまだ勝つことを保証する最小数の小石を取ることを選択する。

小石$N$個の山に対するその最小の量を$H(N)$とする。$H(1)=1, H(4)=1, H(17)=1, H(8)=8, H(18)=5$である。

$G(n)$を$\displaystyle \sum_{k=1}^n H(k)$とする。$G(13)=43$である。

$G(23416728348467685)$はいくつか。

「ひふみ数」を次のように定義する。

• 1 は最小の ひふみ数 である。

• 10進数で表記したとき 1,2,3 のみで表記され、それぞれの出現回数が 0 またはひふみ数である正の整数は ひふみ数 である。

よって 2 は、数字 "2" ひとつからなり、1 は ひふみ数 なので、2 は ひふみ数 である。また 33 は、数字 "3" ふたつからなり、 2 は ひふみ数 なので 33 は ひふみ数 である。

一方で、3333 は数字 "3" 4つからなり、4 は ひふみ数 ではないので、3333 は ひふみ数 ではない。（原文の例では 1111 なのを変更した理由は何かしら。）

昇順に ひふみ数 を挙げると次のようになる： 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, 131, ...

$F(n)$を$n$番目の ひふみ数 とする。例えば $F(4)=11,$ $F(10)=31,$ $F(40)=1112,$ $F(1000)=1223321,$ $F(6000)=2333333333323$ である。

$F(111\,111\,111\,111\,222\,333)$ を $\bmod 123123123$ で求めよ。

Leonhard Eulerは1707年4月15日に生まれた。

数列$1504170715041707n \bmod 4503599627370517$を考える。

この数列の項は、それが全ての既に見つかったオイラーコインよりも真に小さいとき、オイラーコインであると定義する。

例えば、第1項$1504170715041707$は最初のオイラーコインである。第2項は$3008341430083414$で、これは$1504170715041707$より大きいのでオイラーコインではない。しかし第3項$8912517754604$は十分小さく、新たなオイラーコインとなる。

初めのふたつのオイラーコインの和は$1513083232796311$である。

全てのオイラーコインの和を求めよ。

正の数$n$に対して,$n+k$が$k+1$で割り切れないような最小の正の整数$k$をもって関数 $\textit{streak}(n)=k$と定義しよう.

例えば: 13は1で割り切れる 14は2で割り切れる 15は3で割り切れる 16は4で割り切れる 17は5で割り切れない よって, $\textit{streak}(13)=4$

同様に: 120は1で割り切れる 121は2で割り切れない よって, $\textit{streak}(120)=1$

$P(s,N)$を、$1<n<N$の範囲で$\textit{streak}(n)=s$である整数$n$の個数と定義する. 例えば, $P(3,14)=1, P(6,10^6)=14286$となる.

$i$が$1$から$31$の範囲にあるときの$P(i, 4^i)$の和を求めよ.

リフルシャッフルは次のように行う： 1組のトランプを2等分し、上半分を左手に、下半分を右手に持つ。 次に、カードを正確に交互に挟み込む。右半分の一番上のカードを左半分の一番上のカードの直後に挿入し、右半分の2番目のカードを左半分の2番目のカードの直後に挿入する。以下同様にする。 （この手順は、デッキの一番上と一番下のカードの位置を保持する。）

枚のカードからなるデッキを元に戻すために必要な連続したリフルシャッフルの最小回数を とする。ここで は正の偶数である。

驚くべきことに、52枚のカードからなるデッキは、わずか8回のパーフェクトシャッフルで元の順に戻る。よって である。 カード86枚のデッキもちょうど8回のシャッフルで元に戻ることが確認できる。 を満たす全ての の値の和は 412 である。

を満たす全ての の値の和を求めよ。

オイラー大学では、1から $n$ までの番号が付けられた $n$ 人の学生が、それぞれ寮のベッドと教室の机を割り当てられる。

ベッドには、学生が1人で占有する個室にあるものと、2人の学生がルームメイトとして入っている二人部屋にあるものとがある。同様に、各々の机は、1人の学生のみが使用するシングルデスクか、2人の学生がデスクパートナーとして一緒に座るツインデスクのいずれかである。

ベッドとデスクの共有の取り決めは、それぞれ学生番号のペアのリストで表される。たとえば、$n=4$で、$(2,3)$がベッドのペアを表し、$(1,3)(2,4)$がデスクのペアを表す場合、学生2と3はルームメイトであり、1と4は個室を持ち、学生1と3はデスクパートナーであり、学生2と4も同様である。

大学の新しい学長は、ベッドと机の構成を変更することを決定した。すなわち、数$1, 2, \dots, n$の順列$\sigma$が選択され、各学生$k$には、以前は学生番号$\sigma(k)$が使っていたベッドと机の両方が与えられる。

学生は、次の条件の下で、この変更に同意する。

1. 現在部屋を共有している2人の学生は、引き続きルームメイトになる。

2. 現在デスクを共有している2人の学生は、引き続きデスクパートナーになる。

上記の例では、これらの条件を満たす方法は2つしかない。何もしない（$\sigma$は恒等置換)、または学生の順序を逆にするものである。

$n=6$の場合、ベッドペア$(1, 2)(3, 4)(5, 6)$とデスクペア$(3, 6)(4, 5)$には、条件を満たす8つの順列がある。1つの例は、写像$(1, 2, 3, 4, 5, 6)\mapsto(1, 2, 5, 6, 3, 4)$である。

$n=36$の場合、次のベッドペアがあり、 $(2,13)(4,30)(5,27)(6,16)(10,18)(12,35)(14,19)(15,20)(17,26)(21,32)(22,33)(24,34)(25,28)$またデスクペアは次とすると、 $(1,35)(2,22)(3,36)(4,28)(5,25)(7,18)(9,23)(13,19)(14,33)(15,34)(20,24)(26,29)(27,30)$ $36!$の可能な順列（恒等順列を含む）のうち、663552個が学生によって規定された条件を満たす。

ダウンロード可能なテキストファイルbeds.txtおよびdesks.txt に $n=500$のペアが入っている。各ペアは、2人のルームメイト（またはデスクパートナー）の学生番号をカンマで区切って、一行に記述される。たとえば、前述の$n=4$の例のデスクペアはをこのファイル形式で表すと次のようになる：

1,3
2,4

これらの組み合わせで、受講者の条件を満たす順列の個数を見つけよ。$999\,999\,937$を法として答えよ。