フィボナッチ数列は再帰的な関係によって定義される:

$F_n = F_{n−1} + F_{n−2}$

$F_{541}$ (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. そして, $F_{2749}$ (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である.

$F_k$が, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき,$k$を求めよ.

大きさ$n$の集合$A$の要素の和を$S(A)$で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合$B$と$C$に対しても以下の性質が真であれば,$A$を特殊和集合と呼ぼう.

1. $S(B) ≠ S(C)$; つまり, 部分集合の和が等しくてはならない.

2. $B$が$C$より多くの要素を含んでいればこのとき$S(B) > S(C)$となる.

本問題に対しては, 与えられた集合は$n$個の単調増加する要素を含み, かつ第二のルールをすでに満たしているものと仮定しよう.

驚くべきことに,$n = 4$の集合から得ることができる 25 個の可能な部分集合の対のうち, 1 個の対のみが 同一性（第一のルール）をテストされる必要がある. 同様に,$n = 7$のときは, 966 個の部分集合の対のうち 70 個のみがテストされる必要がある.

$n = 12$に対して, 得られる 261625 個の部分集合の対のうち, 同一性をテストされる必要があるものは何個か.

注意: この問題は問題103と問題105に関連している.

3つの異なる点が$-1000 ≤ x, y ≤ 1000$かつ三角形となるように, デカルト平面上にランダムに与えられる.

以下の2つの三角形を考える.

• $A(-340,495), B(-153,-910), C(835,-947)$

• $X(-175,41), Y(-421,-714), Z(574,-645)$

三角形$ABC$が原点を内部に含み, $XYZ$は原点を内部に含まないことが確かめられる.

27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.

注: ファイル中の最初の二つは三角形ABC, XYZである.

大きさ$n$の集合$A$の要素の和を$S(A)$で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合$B$と$C$に対しても以下の性質が真であれば,$A$を特殊和集合と呼ぼう.

1. $S(B) ≠ S(C)$; つまり, 部分集合の和が等しくてはならない.

2. $B$が$C$より多くの要素を含んでいればこのとき$S(B) > S(C)$となる.

たとえば, $\{81, 88, 75, 42, 87, 84, 86, 65\}$は,$65 + 87 + 88 = 75 + 81 + 84$であるため特殊和集合ではないが,$\{157, 150, 164, 119, 79, 159, 161, 139, 158\}$はすべての可能な部分集合の対の組み合わせについて両方のルールを満たしており, また$S(A) = 1286$である.

7個から12個の要素を含む集合100個が記された 4K のテキストファイルsets.txt (右クリックして "名前をつけてリンク先を保存") を用いて (上の二例はファイルの最初の 2 集合である), 特殊和集合$A_1, A_2, \dots , A_k$をすべて特定し,$S(A_1) + S(A_2) + \dots + S(A_k)$を求めよ.

注意: この問題は問題103と問題106に関連している.

大きさ$n$の集合$A$の要素の和を$S(A)$で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合$B$と$C$に対しても以下の性質が真であれば,$A$を特殊和集合と呼ぼう.

1. $S(B) ≠ S(C)$; つまり, 部分集合の和が等しくてはならない.

2. $B$が$C$より多くの要素を含んでいればこのとき$S(B) > S(C)$となる.

ある$n$に対し$S(A)$が最小化されていれば, それを最適特殊和集合と呼ぼう. はじめの 5 つの最適特殊和集合は下に与えられる.

• $n = 1: \{1\}$

• $n = 2: \{1, 2\}$

• $n = 3: \{2, 3, 4\}$

• $n = 4: \{3, 5, 6, 7\}$

• $n = 5: \{6, 9, 11, 12, 13\}$

ある最適特殊和集合$A = \{a_1, a_2, \dots , a_n\}$に対し, 次の最適特殊和集合は$B = \{b, a_1+b, a_2+b, \dots ,a_n+b\}$となりそうである. ここで$b$は前列の「中央の」要素である.

この「法則」を用いると$n = 6$に対する最適特殊和集合は$A = \{11, 17, 20, 22, 23, 24\}$で, $S(A) = 117$と予期するだろう. しかしこれは, 最適に近い集合を与えるアルゴリズムを用いたにすぎないため, 最適特殊和集合とはならない.$n = 6$に対する最適特殊和集合は$A = \{11, 18, 19, 20, 22, 25\}$で,$S(A) = 115$である. これに対応する集合の文字列は 111819202225 である.

$A$を$n = 7$に対する最適特殊和集合とするとき, その集合の文字列を求めよ.

注意: この問題は問題105と問題106に関連している.

次の等式で$x, y, n$は正の整数である.

$\displaystyle \frac{1}{x} + \frac{1}{y} = \frac{1}{n}$

$n = 1260$では 113 の異なる解があり, この$n$が解の個数が 100 を超える最小の値である.

解の数が 4,000,000 を超える最小の n を求めよ.

注: この問題は問題108を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる.

数列の$k$個の項を与えられたときに, 次の項を確実に求めることは不可能である. その数列に合うような多項式が無限個存在するからである.

例として, 立方数の数列を考えよう. これは生成関数$u_n = n^3$で定義され, 1, 8, 27, 64, 125, 216, ...となる.

この数列の最初の2項のみが与えられているとしよう. "Simple is best"の法則にのっとり, 線形の関係があると仮定し, 3つ目の項が15であると予想する (差分が7). もし最初の3項のみが与えられていたとしても, 同じ原則により, 二次の関係があると仮定して次の項を予測する.

数列の最初の$k$項を生成できる最適な多項式の第$n$項を$\textrm{OP}(k, n)$で表すことにする. 明らかに,$n ≤ k$について$\textrm{OP}(k, n)$は正しい. 最初の異なる項 (First Incorrect Term, FIT) は$\textrm{OP}(k, k+1)$であろう. これを bad OP (BOP) と呼ぶことにする.

原則より, 最初の項しか与えられていない場合には, 定数項とするのが理に適っているだろう; 即ち,$n ≥ 2, \textrm{OP}(1, n) = u_1$.

従って, 立方数の数列について以下のOPを得る.

(BOPを赤くする)

明らかに,$k ≥ 4$のときにはBOPは存在しない.

BOPのFIT (上の例では赤で示されている) の和は,$1 + 15 + 58 = 74$である.

以下の10次多項式からなる生成関数を考える:

$u_n = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^{10}$

BOPのFITの総和を求めよ.

次の等式で$x, y, n$は正の整数である.

$\displaystyle \frac{1}{x} + \frac{1}{y} = \frac{1}{n}$

$n = 4$では 3 つの異なる解がある.

$\displaystyle \frac{1}{5} + \frac{1}{20} = \frac{1}{4}$

$\displaystyle \frac{1}{6} + \frac{1}{12} = \frac{1}{4}$

$\displaystyle \frac{1}{8} + \frac{1}{8} = \frac{1}{4}$

解の数が 1000 を超える最小の$n$を求めよ.

注: この問題は問題110の易しいケースである. こちらを先に解く事を強く勧める.

左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ. 例えば, 134468.

同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ. 例えば, 66420.

増加数でも減少数でもない正の整数をはずみ数と呼ぶことにする. 例えば, 155349.

100以下にはずみ数が無いのは明らかだが, 1000未満では半数を少し上回る525個がはずみ数である.

実際, はずみ数の割合が50%に達する最少の数は538である.

驚くべきことに, はずみ数はますます一般的になり, 21780でははずみ数の割合は90%に達する.

はずみ数の割合がちょうど99%になる最小の数を求めよ.

（原文からして、「xx以下の数がbouncyである割合」という言い方をしていない。）

以下の無向ネットワークは7つの頂点と重み付きの12個の辺からなり, 重みの総和は243である.

このネットワークを以下の行列で表現することができる.

しかし, このネットワークを, 全ての頂点が連結であるように適当な辺を除いた上で最適化することが出来る. 節約される量が最大化されるように取り除いたネットワークが以下の画像である. この場合, 辺の重みの総和は93であり, 元のネットワークからの節約量は 243 - 93 = 150 である.

6Kバイトのテキストファイルnetwork.txt (右クリックして保存すること) には40頂点のネットワークを行列表示したものが記されている. ネットワーク全体が連結であるが冗長な辺を取り除いたときの節約量を最大にするようにした場合の節約量を答えよ.

ダーツゲームでは, プレイヤーは 20 等分に分けられたダーツボードに 3 本のダーツを投げる. ダーツボードは 1 から 20 の番号がふられている.

ダーツの点数は, ダーツが刺さった領域の番号によって決まる. 外側の赤緑の輪の外に刺さったダーツは 0 点である. この輪の内側の黒と白の領域はシングル (1 倍) の点数を表している. しかし, 外側と内側の赤緑の輪はそれぞれダブル (2 倍) とトリプル (3 倍) の点数である.

ボードの中央の 2 つの同心円はブルやブルズアイと呼ばれる. 外側のブルは 25 点, 内側のブルはダブルの 50 点である.

ルールには多くのバリエーションがあるが, 最もポピュラーなゲームでは, プレイヤーは 301 または 501 点から始まり, 最も早く現在の得点を 0 点に減らしたプレイヤーが勝者となる. しかし, 普通は「ダブルアウト」方式でプレイをする. この方式では, プレイヤーは勝利するために, 最後のダーツをダブル (ボードの中央のダブルのブルズアイを含む) に刺さなければならない. それ以外で現在の得点を 1 点以下に減らした場合, 3 本のダーツに対する得点は「バースト(無効)」になる.

プレイヤーが現在の得点で終了できる場合を「チェックアウト」と呼ぶ. 最も高いチェックアウトは 170: T20 T20 D25 (トリプルの 20 を 2 回とダブルのブル) である.

得点が 6 でチェックアウトする異なるやり方はちょうど 11 通りある.

D1 D2 と D2 D1 は, 異なるダブルで終了しているので異なるとみなすことに注意しよう. しかし S1 T1 D1 の組み合わせは T1 S1 D1 と同じとみなす.

さらに, 組み合わせを考える上でミスは含まないこととする; たとえば, D3 は 0 D3 や 0 0 D3 と同じである.

信じられないことに, 異なるチェックアウトは全部で 42336 通りある.

得点が 100 未満の異なるチェックアウトは何通りあるか.

重複した桁を含む 4 桁の素数を考える. 全てが同じにならないのは明らかである: 1111 は 11 で割り切れ, 2222 は 22 で割り切れ, 以下同様だからである. しかし 3 個の 1 を含む 4 桁の素数は 9 つある:1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111

$n$桁の素数に対する重複した桁の最大個数を$M(n, d)$と表すことにしよう. ここで$d$は重複した桁の数字とする. またそのような素数の個数を$N(n, d)$と表し, これらの素数の和を$S(n, d)$と表す.

よって M(4, 1) = 3 は, 重複した桁を 1 としたときの, 4 桁の素数に対する重複した桁の最大個数である. そのような素数は N(4, 1) = 9 個あり, これらの素数の和は S(4, 1) = 22275 である. d = 0 に対しては, 重複した桁は M(4, 0) = 2 個だけ可能であることが分かるが, そのような場合は N(4, 0) = 13 個ある.

同じようにして 4 桁の素数に対して次の結果を得る.

d = 0 から 9 に対して,$S(4, d)$の総和は 273700 である.

$S(10, d)$の総和を求めよ.

長さ 7 ユニットからなる 1 列上に, 最低 3 ユニットの長さを持つ赤ブロックが置かれている. ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). これを敷き詰める方法は, ちょうど 17 通りある.

50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか.

注意: 上の例では起こりえないが, 通常はブロックの大きさが複数混ざっていてもよい. 例えば, 8 ユニットの長さの 1 列では, 赤(3), 黒(1), 赤(4) を使うことができる.

ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である.

同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである.

増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである.

nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. 例えば, 100万未満では, はずみ数でない数は12951個しかない. 同様に, 未満では277032個しかない.

googol数 () 未満ではずみ数でないものの個数を答えよ.

注意: これは問題114をより難しくした問題である.

長さ$n$ユニットからなる 1 列上に, 最低$m$ユニットの長さを持つ赤ブロックが置かれている. ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数$F(m, n)$は 1 列に敷き詰める方法が何通りかを表すとする.

例えば,$F(3, 29) = 673135$であり,$F(3, 30) = 1089155$である.

$m = 3$の時,$n = 30$がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.

同様に,$m = 10$では$F(10, 56) = 880711, F(10, 57) = 1148904$であることがわかり, つまり$n = 57$がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.

$m = 50$のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の$n$の値を求めよ.

512 という数は興味深い数である. というのも, 各桁の和を何乗かしたものに等しくなっているからである: $5 + 1 + 2 = 8, 8^3 = 512$である. この特性を持つ他の数は例えば$614656 = 28^4$である.

この数列の第$n$項を$a_n$と定義し, また 2 桁以上であるとしよう.

$a_2 = 512, a_{10} = 614656$となる.

$a_{30}$を求めよ.

1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り, 複数の集合を作ることができる. 集合$\{2,5,47,89,631\}$は面白いことに全ての要素が素数である.

1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?

袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される.

プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する.

ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字にならないようにこのゲームで勝ちに対して割り当てるべき賞金の最大は 10 ポンドとなるであろう. 支払いはすべてポンドの整数倍であり, またゲームをプレイするのに支払われたもともとの 1 ポンドを含んでいるため, 与えられた例では実際にはプレイヤーは 9 ポンドを獲得することに注意しよう.

15 ターンがプレイされるゲーム 1 回に割り当てられるべき賞金の最大を求めよ.

$(a-1)^n+(a+1)^n$を$a^2$で割った余りを$r$と定義する.

例えば,$a=7, n=3$のとき$r=42$である:$63 + 83 = 728 ≡ 42 \mod 49$. $n$が変われば$r$も変わるが,$a=7$のとき$r$の最大値r_\maxは$42$であることがわかる.

$3 ≤ a ≤ 1000$において,\sum r_\maxを求めよ.

5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで, この色のついた長方形のタイルでいくつか置き換える.

もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.

もし緑のタイルを選んだ場合は, 3 通りである.

もし青のタイルを選んだ場合は, 2 通りである.

複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.

50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか. ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.

注: この問題は問題117に関連する

黒い正方形のタイルと, 2 ユニットの長さの赤のタイル, 3 ユニットの長さの緑のタイル, 4 ユニットの長さの青のタイルから選んで組み合わせて, 5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.

長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか.

注: この問題は問題116に関連する

$p_n$を$n$番目の素数とする. $(p_1 = 2, p_2 = 3, ...)$また$r$を$(p_n - 1)^n + (p_n + 1)^n$を${p_n}^2$で割った余りとする.

例えば$n = 3$のとき$p_3 = 5$であり$4^3 + 6^3 = 280 ≡ 5 \mod 25$である。

余り$r$が$10^9$より大きくなる$n$の最小値は$7037$である.

余り$r$が$10^{10}$より大きくなる最初の$n$を求めよ.

$n^{15}$を求めるのに最も単純な方法では 14 回の掛け算が必要である.

$n × n × \dots × n = n^{15}$

しかし、2進法を用いれば6 回の掛け算で計算できる.

$n × n = n^2$ $n^2 × n^2 = n^4$ $n^4 × n^4 = n^8$ $n^8 × n^4 = n^{12}$ $n^{12} × n^2 = n^{14}$ $n^{14} × n = n^{15}$

ところがたった 5 回の掛け算のみでも計算できる.

$n × n = n^2$ $n^2 × n = n^3$ $n^3 × n^3 = n^6$ $n^6 × n^6 = n^{12}$ $n^{12} × n^3 = n^{15}$

$m(k)$を$n^k$を求めるのに必要最低限な掛け算の回数と定義する. たとえば$m(15)=5$である.

$1 ≤ k ≤ 200$に対し、$\sum m(k)$を求めよ.

1のみからなる数をレプユニット(repunit)という。$R(k)$を長さ$k$のレプユニットとする。 例えば$R(6) = 111111$となる。

$\textrm{GCD}(n, 10) = 1$なる正の整数$n$が与えられたとき、$R(k)$が$n$で割り切られるような$k$が常に存在することが示せる。$A(n)$をそのような$k$の最小のものとする。例えば$A(7) = 6, A(41) = 5$となる。

$A(n)$の値が10を超える最小の$n$は17である。

$A(n)$の値が100万を超える最小の$n$を求めよ。

1のみからなる数をレプユニット(repunit)という。$R(k)$を長さ$k$のレプユニットとする。 例えば$R(6) = 111111$となる。

$\textrm{GCD}(n, 10) = 1$なる正の整数$n$が与えられたとき、$R(k)$が$n$で割り切られるような$k$が常に存在することが示せる。$A(n)$をそのような$k$の最小のものとする。例えば$A(7) = 6, A(41) = 5$となる。

5より大きい素数$p$について、$A(p)$が$p - 1$を割り切ることが知られている。$p = 41$のときには$A(41) = 5$であり, 40は5で割り切れる.

非常に少ないのだが、合成数においても上が成立する場合がある。最初の5つの例は 91, 259, 451, 481, 703 である。

$\textrm{GCD}(n, 10) = 1$かつ$A(n)$が$n - 1$を割り切るような最初の25個の合成数$n$の総和を求めよ。

1のみからなる数をレプユニットという. $R(k)$を長さ$k$のレプユニットとする.

例えば,$R(10) = 1111111111 = 11×41×271×9091$となり, 素因数の和は9414となる.

$R(10^9)$の最初の40個の素因数の和を求めよ.

1のみからなる数をレプユニット(repunit)という。$R(k)$を長さ$k$のレプユニットとする。 例えば$R(6) = 111111$となる。

$R(10^n)$というレプユニットについて考える.

$R(10), R(100), R(1000)$は 17 では割り切れないが, $R(10000)$は 17 で割り切られる. さらに,$R(10^n)$が 19 で割り切られるような$n$は存在しない. 驚くべきことに, $R(10^n)$の因数となりうる100未満の素数は 11, 17, 41, 73 の4個のみである.

$R(10^n)$の因数となりえない100000未満の素数の和を求めよ.

$x, y, z$を等差数列となるような正の整数とする. 正の整数$n$が$n = 20$と与えられたときに, 方程式$x^2 - y^2 - z^2 = n$は唯一つの解を持つ.

$13^2 - 10^2 - 7^2 = 20$

実のところ100未満の$n$について方程式が唯一つの解を持つような$n$は25個存在する.

5000万未満の$n$について方程式が唯一つの解を持つような$n$は何個存在するか?

連続する素数$p_1 = 19, p_2 = 23$について考える. $1219$は末尾の桁が$p_1$からなり$p_2$で割り切れる最小の数であることが確かめられる.

実際,$p_1 = 3, p_2 = 5$を除けば, 全ての$p_2 > p_1$なる連続する素数のペアについて, 末尾の桁が $p_1$からなり$p_2$で割り切れる数$n$が存在する.$S$を$n$の最小のものであるとする.

$5 ≤ p_1 ≤ 1000000$を満たす連続する素数のペア全てに対し$\sum S$を求めよ.

$n$の"根基"(radical)を$\textrm{rad}(n)$で書き、$n$の異なる素因数の積とする。例えば$504 = 2^3 × 3^2 × 7$なので$\textrm{rad}(504) = 2 × 3 × 7 = 42$である。

正整数の3つ組$(a, b, c)$が abc-hit であるとは

1. $\textrm{GCD}(a, b) = \textrm{GCD}(b, c) = \textrm{GCD}(c, a) = 1$

2. __$a < b$__

3. __$a + b = c$__

4. $\textrm{rad}(a b c) < c$

の4つの性質を満たすことである.

$(5, 27, 32)$は abc-hit である:

1. $\textrm{GCD}(5, 27) = \textrm{GCD}(5, 32) = \textrm{GCD}(27, 32) = 1$

2. $5 < 27$

3. $5 + 27 = 32$

4. $\textrm{rad}(4320) = 30 < 32$

abc-hit は非常に稀である.$c < 1000$には31個しかなく, そのときの$\sum c$は 12523 である.

$c < 120000$での$\sum c$を求めよ.

$x + y, x - y, x + z, x - z, y + z, y - z$が全て平方数となる整数の組$x > y > z > 0$で, 最小の$x + y + z$を求めよ.

フィボナッチ数列$F_k = 1, 1, 2, 3, 5, 8, \dots$すなわち$F_k = F_{k-1} + F_{k-2}, F_1 = 1, F_2 = 1$によって与えられる無限級数$A_F(x) = xF_1 + x^2F_2 + x^3F_3 + \dots$を考える.

この問題では, $A_F(x)$が正の整数となるような$x$の値について考える. 驚くべきことに, $A_F(\frac{1}{2}) = (\frac{1}{2})\times 1 + (\frac{1}{2})^2\times 1 + (\frac{1}{2})^3\times 2 + (\frac{1}{2})^4\times 3 + (\frac{1}{2})^5\times 5 + \dots = \frac{1}{2} + \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \frac{5}{32} + \dots = 2$である.

最初の5つの自然数に対する x の値を下表に示す.

xが有理数のときの$A_F(x)$の値を, 非常に稀なので, "金塊" (golden nugget) と呼ぶ. 実際, 10番目の"金塊"は74049690である.

15番目の"金塊"を求めよ.

$(a, b, c)$で各辺の長さが整数の直角三角形の三辺を表す. 一辺の長さが$c$の正方形中に先ほどの三角形を4つ配置することが可能である.

例えば$(3, 4, 5)$-三角形は$5×5$の正方形に4つ配置される. このとき, 中央部に$1×1$の穴が空いている. また, $5×5$の正方形は25個の$1×1$の正方形で敷き詰めることができる.

しかし, $(5, 12, 13)$-三角形を使った場合は穴のサイズが$7×7$になり, $7×7$の正方形では$13×13$の正方形を敷き詰めることができない.

では, $10^8$未満の周囲長を持つ直角三角形を考え, 上のような敷き詰め方を許す直角三角形の数を答えよ.

3項間漸化式$G_k = G_{k-1} + G_{k-2}, G_1 = 1, G_2 = 4$ ($G_k = 1, 4, 5, 9, 14, 23, \dots$) によって与えられる無限級数$A_G(x) = xG_1 + x^2G_2 + x^3G_3 + \dots$を考える.

この問題では,$A_G(x)$が正の整数となるような$x$の値について考える.

最初の5つの自然数に対する$x$の値を下表に示す.

x が有理数となるときの AG(x) の値を"金塊" (golden nugget) と呼ぶことにする. "金塊"は次第に稀になっていき, 20番目の"金塊"は 211345365 となる.

最初の30個の"金塊"の和を求めよ.

正の整数$n$について、その逆順との和$n + \textrm{reverse}(n)$が奇数の数字のみで表されるようなものが存在する。例えば$36 + 63 = 99, 409 + 904 = 1313$がそうである。この性質を持つ数をreversibleと呼ぶことにする。つまり36, 63, 409, 904はreversibleである。$n$と$\textrm{reverse}(n)$のいずれにも先頭に0が来ることは許されない。

1000未満には120個のreversibleな数が存在する。

10億($10^9$)未満にはreversibleな数はいくつ存在するか。

正の整数$n$を$d$で割った商と余りをそれぞれ$q$と$r$で表す. $d, q, r$を適当に並び替えたときに正の項からなる等比数列（幾何数列）になる場合がある.

例えば58を6で割ると商が9で余りが4である. 4, 6, 9は公比3/2の幾何数列になっている. 以下, このような $n$を累進数と呼ぶ. (訳者注: progressive numberの定訳が分からないので適当な名前にしておく.)

いくつかの累進数$9$や$10404=102^2$は平方数になっている. 100000未満の累進平方数の和は124657である.

$10^{12}$未満の累進平方数の総和を答えよ.

正の整数$x, y, z$が等差数列として与えられたとき,$x^2 - y^2 - z^2 = n$がちょうど2個の解を持つような最小の正の整数$n$は$n = 27$である.

$34^2 − 27^2 − 20^2 = 12^2 − 9^2 − 6^2 = 27$

$n = 1155$は, 方程式がちょうど10個の解を持つ最小の値である.

ちょうど10個の解を持つような$n$は, 100万未満にいくつ存在するか?

ABCを全ての内角が120度未満の三角形とする. Xを三角形の内点とし, XA = p, XB = q, XC = rとする.

フェルマーは「p+q+rを最小にするXを探す方法はあるか?」とトリチェリに問題を出した.

正三角形 AOB, BNC, AMC がABCの各辺に構成できるならば, AOB, BNC, AMCに外接する3つの円が三角形の内部の1点 T で交わることをトリチェリは示した. さらに, トリチェリ-フェルマー点と呼ばれる T が, p + q + r を最小化することも示した. 更には, 和が最小となるときには, AN = BM = CO = p + q + r であり, AN, BM, COもまた T と交わることも示せる.

和が最小化されているとして, a, b, c, p, q, r が全て正の整数であるとき, 三角形 ABC をトリチェリ三角形と呼ぶ. 例えば, a = 399, b = 455, c = 511 は p + q + r = 784 のトリチェリ三角形である.

トリチェリ三角形について 異なる値をとる p + q + r ≤ 120000 の総和を求めよ.

レーザー物理学では, "white cell"とはレーザー光線を遅延させるための鏡の装置のことである. 光線はcellに入り, 鏡で反射して, 最終的には飛び出す.

特定のwhite cellは, 方程式 4x2 + y2 = 100 で表される楕円と考えることができる.

−0.01 ≤ x ≤ +0.01 に対応する上部に穴が空いていて, 光線が出入りできるようになっている.

この問題では, 光線はwhite cellの外側 (0.0,10.1) から始まり, 最初に (1.4,-9.6) で鏡に反射するものとする.

光線は, 楕円の表面に当たるごとに, 反射の法則に従う. つまり, 入射する光線と反射する光線は入射する点の法線に対して同じ角度をなす.

上の左の図では, white cellと赤線で光線の最初に反射する2点を, 青線で最初に反射する点の接線を示している.

与えられた楕円に対する点 (x,y) での接線の傾きmは, m = -4x/y となる.

法線とは, 反射する点での接線に垂直な線である.

右側のanimationは光線の最初の10回の反射を示している.

光線はwhite cellから出るまでに何回反射するか?

底の長さ$b$が$16$, 脚の長さ$L$が17の二等辺三角形を考える.

ピタゴラスの定理より, 三角形の高さ$h = \sqrt{17^2 − 8^2} = 15$となる. 高さは底の長さより1だけ短い.

$b = 272, L = 305$とすると, $h = 273$となり, これは底の長さより1だけ長い. この三角形は$h = b ± 1$という性質を持つ二等辺三角形の中で二番目に小さい.

$h = b ± 1, b, L$が全て正の整数であるとし, そのような二等辺三角形の中で小さい順に12個取ったときの$\sum L$を求めよ.

三角形配列において, 含まれる要素の和が最小となるような部分三角形を求めたい.

下図では, マークされた三角形が, 和が -42 となり, この条件を満たすことは簡単に確かめられる.

1000行の三角形配列を作りたいので, 500500個の値の範囲が±219の擬似乱数を以下のような線形合同法によって生成する.

三角配列は, 以下のように配置される.

部分三角形は, ある要素から始めて下にいくにつれ広くなっていくようなものを考える. (最初の要素の次の行は2つの要素を含む, その次の行は3つの要素を含む, といったように) "部分三角形の和"はそれが含む全ての要素の和とする. 最小の部分三角形の和を求めよ.

が連続する素数になる最小の正整数は 10 である. 100万未満のの総和は 1242490 である.

それでは, 1億5000万未満のの総和を求めよ.

下の表において, 任意の方向(縦横斜め)に隣り合うものの和の最大値は16 (= 8 + 7 + 1)となることは簡単に確かめられる.

いま, 同じ探索をより大きなものについてもしてみることにする.

まず, 400万個の擬似乱数を"Lagged Fibonacci Generator"によって生成する.

について, について,

つまり, s10 = -393027 , s100 = 86613 となる.

s の項は, 最初の2000個を最初の行に(順番に), 次の2000個を2番目の行に, というように, 2000x2000の表に並べ替えられる.

任意の方向(縦横斜め)に隣り合うものの和の最大値を求めよ. (連続して足す領域は３マス以上でもよい, 斜め４マス等も認める)

とある印刷屋では毎週16回の定期的な仕事がある. 毎回 A5 サイズの特殊な色校正用紙 (special colour-proofing paper) を1枚使う.

月曜日の朝になると, 主任はA1サイズの特殊紙が入った新しい封筒を開ける.

彼はA1の紙を半分に切る. するとA2の紙が2枚出来上がる. 片方を半分に切りA3の紙が2枚出来上がる. 以下繰り返し, A5の紙を得るまで繰り返し, 1枚をその週の最初の仕事に使う.

使われなかった紙は全て元の封筒に収める.

さて, 各仕事の際に, 主任は封筒からランダムに紙を1枚取り出す. もしA5の紙を取り出したならそのまま仕事に使う. そうでない場合は 半分に切る ことを繰り返し, A5の紙を1枚使い, 残りは元の封筒に戻す.

週の最初と最後の仕事以外で, 封筒に紙が1枚だけ入っている回数の期待値を求めよ.

回答は, 四捨五入し小数点以下6桁で答えること (x.xxxxxxという形).

パスカルの三角形の最初の7列には7で割り切れる要素は一つもないことが簡単に分かる.

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1

しかし最初の100列を調べると, 5050個の要素の内, 7で割り切れないものは2361個しかない.

パスカルの三角形の最初の10億列 ($10^9$列) の要素で7で割り切れないものの数を答えよ.

以下のように, 10進法で自然数を0から書いていく. 0 1 2 3 4 5 6 7 8 9 10 11 12....

ある桁の数が d = 1 について考える. 数nを書いた後, 1が出現する回数を更新する. この数を f(n,1) とする. f(n,1) の最初の値は以下のようになる.

f(n,1) は決して3にならないことに注意. つまり, f(n,1) = n の最初の2つの解は, n = 0 と n = 1 となる. 次の解は n = 199981 である.

同様にして, f(n,d) はある桁の数dがnまでに何回現れたか, と定義する. 実は, d ≠ 0 の全てのdについて, 0 が f(n,d)=n の最初の解となる.

s(d) を, f(n,d) = n の解の総和として定義する. s(1) = 22786974071 となる.

1 ≤ d ≤ 9 について, ∑ s(d) を求めよ.

注意: もし, f(n,d) = n となるnが異なったdについて存在した場合, このnは重複して数えるものとする.

(数式化、「桁の数」)

1/2 を異なる整数の平方の逆数の和として書き表す方法はいくつかある.

例えば, {2,3,4,5,7,12,15,20,28,35}を使うと,

$\frac{1}{2} = \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \frac{1}{5^2} + \frac{1}{7^2} + \frac{1}{12^2} + \frac{1}{15^2} + \frac{1}{20^2} + \frac{1}{28^2} + \frac{1}{35^2}$

実際, 2から45までの整数を使うと, ちょうど3通りの方法がある. 残りの方法は, {2,3,4,6,7,9,10,20,28,35,36,45} か {2,3,4,6,7,9,12,15,28,30,35,36,45} を使う方法である.

2から80までの異なる整数の平方の逆数の和として 1/2 を書き表す方法は何通りあるか求めよ.

3x2 の斜め線が引かれた格子には, 下図で示されるように全部で37個の異なった長方形が存在する.

3x2 より横にも縦にも小さい5個の格子(つまり, 1x1, 2x1, 3x1, 1x2, 2x2)を考えると, それらに存在する長方形の数は以下のようになる.

1x1: 1 2x1: 4 3x1: 8 1x2: 4 2x2: 18

これらに3x2の格子の37を加えると, 全部で72個の異なった長方形が3x2以下の格子について存在する.

47x43以下の格子について存在する異なった長方形の数を求めよ.

1つの球が下の層の3つの球の上に乗るように作られた三角錐がある.

頂上から各球への経路の数を計算することにする.

経路は, 頂上から始まって, すぐ下の3つのいずれかへと下向きに進む.

したがって, ある位置への経路の数はすぐ上のものの和となる. (位置に依るが, 最大で3つが上にある)

結果はパスカルのピラミッドとなり, 深さ$n$の層に含まれる数は$(x + y + z)^n$を展開したものの係数である.

$(x + y + z)^{200000}$を展開したものの係数で,$10^{12}$の倍数となるものはいくつあるか?

ディオファントス方程式(は正の整数で,) について考える. について, この方程式は以下に挙げられる20個の解を持つ.

について, この方程式の解はいくつ存在するか?

任意の N に対して, f(N) を N! の末尾の 0 の前にある最後の5桁とする.

例えば,

9! = 362880, f(9)=36288

10! = 3628800, f(10)=36288

20! = 2432902008176640000, f(20)=17664

である.

f(1,000,000,000,000) を求めよ.

トリオミノとは3つの正方形を辺で繋げたものである. 以下は2つの基本形.

すべての方向を可能性に入れると, 以下の6つがある.

n x m が3で割り切れるならば, どのn x m の格子もトリオミノによって埋めることができる. 反転, 回転によって得られる埋めかたを別の埋め方とすると, 2 x 9 の格子では41通りの埋め方がある.

9 x 12 の格子では何通りの埋め方があるか?

16進法では, 数は以下の16個の数字によって表される

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

16進数の AF は, 10進法での$10\times 16 + 15 = 175$と等しい.

3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A の全てが現れている. 10進数で書くときと同様に, 先頭の0は書かないことにする.

0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか? 16進数で答えよ.

(A,B,C,D,E,F は大文字とし, 先頭や末尾の16進数であることを表す記号や先頭の0は許されない. つまり, 1A3F ならOK. 1a3f, 0x1a3f, $1A3F, #1A3F, 0000001A3Fは許されない. )

0 ≤ d ≤ 9 なる d で埋められた 4x4 の格子がある.

以下の格子では, それぞれの行, 列の和が12となる. さらに, 斜めの和も12となる.

6 3 3 0 5 0 4 3 0 7 1 4 1 2 4 5

0 ≤ d ≤ 9 なる d で 4x4 の格子を, それぞれの行, 列, 斜めの和が同じとなるように埋める方法は何通りあるか?

どの連続した3桁の和も9以下のような(9以下は9を含む)20桁の数(先頭の0は認めない)はいくつあるか?

$3 \times 2 \times 1$の直方体の表面全てを覆いつくすのに必要最小限の立方体の数は 22 個である.

さらにこの立体に表面を覆いつくすように2層目を追加すると, 46 個の立方体が必要である. 3層目は 78 個, 4層目は 118 個の立方体が表面を覆いつくすのに必要である.

ところで$5 \times 1 \times 1$の直方体への1層目も 22 個の立方体が必要である. 同様に$5 \times 3 \times 1, 7 \times 2 \times 1, 11 \times 1 \times 1$の直方体への1層目も全て 46 個の立方体である.

何層目かが$n$個の立方体からなる直方体の数を$C(n)$と定義する. $C(22) = 2, C(46) = 4, C(78) = 5, C(118) = 8$となる.

154 は$C(n) = 10$を満たす最小の$n$であることがわかる.

$C(n)=1000$を満たす最小の$n$を求めよ.

各頂点から対辺の中点に足を下ろした正三角形を考える. 以下に大きさ1の三角形を示す.

この三角形には形, 大きさ, 方向, 位置のいずれかが異なる三角形が16個含まれる. 大きさ1の三角形をブロックとして, 大きい三角形が作れる. 大きさ2の三角形を上図に示す. 大きさ2の三角形には形, 大きさ, 方向, 位置のいずれかが異なる三角形が104個含まれる.

大きさ2の三角形は4個の大きさ1の三角形のブロックを含み, 大きさ3の三角形は9個の大きさ1の三角形のブロックを含む. 大きさの三角形は個の大きさ1の三角形のブロックを含む.

T(n) を大きさnの三角形に含まれる三角形の数とすると,

T(1) = 16 T(2) = 104 となる.

T(36) を求めよ.

静電容量が等しい理想的なキャパシタのみを使った電気回路がある.

複数のキャパシタを直列または並列に接続してサブユニットを形成し, そのサブユニットを他のキャパシタやサブユニットと直列または並列に接続してより大きなサブユニットを形成し, そのようにして最終的な回路を形成する.

この単純な手続きを個以下の理想的なキャパシタに適用し, 全体の静電容量が異なる複数の回路を構成することができる. 例えば, 60μFのキャパシタでの場合は, 以下のように7通りの異なる静電容量を得ることができる.

(equal-valued は「容量の等しい」ではないか？)

の"根基"(radical)をで書き、の異なる素因数の積とする。例えばなのでである。

に対してを計算し,を対象にソートし,が同じ場合はを対象にソートすると以下のようになる.

ソートした表のの列の番目の要素をとする. 例えばである.

をでソートした場合,を求めよ.

正の整数について, Ulam数列は以下のように定義される.,については, は二つの異なったのそれまでの値の和としての表し方が一通りである数のを超える最小値となる.

例えば, 数列は, 1, 2, 3 = 1 + 2, 4 = 1 + 3, 6 = 2 + 4, 8 = 2 + 6, 11 = 3 + 8; となる. 5は, 5 = 1 + 4 = 2 + 3 というように二つの和の表し方があるのでこの数列に含まれない. 7 = 1 + 6 = 3 + 4 も同様である.

をについて求めよ.

----書き直してみる。

正の整数に対して、Ulam数列は次のように定義される。 についてはを超える最小の値で、のそれ以前の要素のうち異なる２要素の和としてただ１通りの表し方を持つ値とする。

例えばは となる。は、というように二つの和の表し方があるので5にならず、5はこの数列に含まれない. におけるも同様である。

の第項をと表す。を求めよ。