下記の5次の正方行列で, 左上のセルから開始し右下のセルで終わるパスを探索する. ただし下方向と右方向にのみ移動できるものとする. 通過したセルの和が最小となるパスは赤の太字で示されたもので, その値は2427である.

今, 31Kのテキストファイルmatrix.txt (右クリックして, 『名前をつけてリンク先を保存』)には80×80の行列が書かれている. 同様に左上のセルから開始し右下のセルで終わり, かつ右方向と下方向にのみ移動するときの最小のパスの和を求めよ.

注: この問題は問題81よりも挑戦しがいがあるだろう.

下記の5次の正方行列で, 一番左の行の任意のセルから開始し一番右の行の任意のセルで終わる道を探索する. ただし上下右にのみ移動できるものとする. 一番小さなパスは下で赤の太字で示されたものである. このときの合計は994になる.

今, 31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 一番左の行から一番右の行へ移動する際の一番小さなパスの和を求めよ.

注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている.

ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない. 一番近い解を持つような格子の面積を求めよ.

下に示す直方体は寸法が$6×5×3$である. この直方体の1つの頂点Sにクモがいる. また反対の頂点Fにはハエがいる. SからFまでの壁に沿って直線移動する最短ルートは図に示す通りで, この長さは10である.

この最短ルートの候補は3本あるが, 最短のものがいつも整数長さとは限らない.

さて, $M×M×M$以下の寸法の直方体について, 最短ルートが整数である直方体の個数を考える. $M=100$のとき, 条件を満たす直方体は2060個ある. この$M=100$は条件を満たす直方体の個数が2000を超える最小の$M$である. なお, $M=99$のときは1975個である.

条件を満たす直方体が100万個を超える最小の$M$を求めよ.

注: この問題は問題81よりも非常に挑戦しがいがあるだろう.

下記の5次の正方行列で, 上下左右に移動し左上のセルから開始し右下のセルで終了する道を探索する. 一番小さな道は下で赤で示されており, このときの合計は2297になる.

今, 31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 上下左右に移動し左上のセルから開始し右下のセルで終了する道に沿った和の最小を求めよ.

ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ). しかし, ある数については最良の記法が必ず存在する.

(FAQとは？https://projecteuler.net/about=roman_numeralか。)

例えば, 16の正しい記法を全て並べてみる.

IIIIIIIIIIIIIIII VIIIIIIIIIII VVIIIIII XIIIIII VVVI XVI

最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.

11Kのテキストファイルroman.txtは1000個のローマ記法で書かれた数を含んでいる. これらは, 正しい記法に従っている. 即ち, 大きい数から順に書かれていて, 引き算ペアのルールにも従っている(このルールについてはFAQを見よ) 但し, 最小の文字数で表されているとは限らない.

最小形で書いたときに, 何文字節約できるかを求めよ.

注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない.

FAQ: ローマ数字のルール †

(訳者:概略のみ与える)(えっ)

基本法則1

全ての文字はサイズの降順に並ぶ

基本法則2

引き算ペアについて.

X (10) + IX (9) として19=XIXと表せる. ただし, 8をIIXと二文字以上を引くことは許されない.

1. I, X, Cのみが引き算ペアの最初の文字として許される.

2. IはVまたはXの前に来ることが許される

3. XはLまたはCの前に来ることが許される

4. CはDまたはMの前に来ることが許される

少なくとも2つの自然数からなる多重集合$\{a_1, a_2, \dots , a_k\}$の和としても積としても表せる自然数$N$を積和数と呼ぶ：$N = a_1 + a_2 + \dots + a_k = a_1 × a_2 × \dots × a_k$

（訳注：原文にはsetとあるが、下の例では1,1,2,4などと要素が重複することを許しているのでこれは集合ではない。）

例えば $6 = 1 + 2 + 3 = 1 × 2 × 3$である。

ある多重集合の大きさ$k$に対して、この性質を持つ最小の$N$を最小積和数と呼ぼう。 多重集合の大きさ$k = 2, 3, 4, 5, 6$に対する最小積和数は次のとおりである。

• $k=2: 4 = 2 × 2 = 2 + 2$

• $k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3$

• $k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4$

• $k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2$

• $k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6$

したがって、$2 ≤ k ≤ 6$に対して,全ての最小積和数の和は$4+6+8+12 = 30$である。 8 は和に一度だけカウントされていることに気をつけよう。

実際、$2 ≤ k ≤ 12$に対する最小積和数の完全な集合は$\{4, 6, 8, 12, 15, 16\}$なので、その和は61である。

$2 ≤ k ≤ 12000$に対する全ての最小積和数の和は何か？

(うだうだ長いので直すのつらい)

モノポリーの標準的な盤面は以下である:

各プレイヤーはGOのマスから開始し, 2個の6面サイコロを用いて時計回りに進む. 他のルールが無いとすれば, 各マスに止まる確率は全て等しく, 2.5%である. しかし, G2J (Go To Jail), CC (Community Chest, 共同基金), CH (Chance, チャンス) のマスによってこの確率は変えられてしまう.

G2Jに止まる, または, CCやCHのマスに止まると引くカードのうちそれぞれ1枚によって, プレイヤーはJAILのマスに飛ばされる. またプレイヤーが連続して3回ゾロ目を出すと, 3投目の結果のマスに進むのではなく, 直接JAILのマスに飛ばされる. (訳注: モノポリーではゾロ目が出るともう1回サイコロをふる. 6,6→2,1の場合は合計15マス進む. 4,4→2,2→1,2の場合は合計15マス進む. 3,3→4,4→2,2の場合は6マス目, 14マス目に止まったのちJAILに飛ばされる.)

ゲーム開始前にCCカードとCHカードはシャッフルされる. プレイヤーがCCまたはCHマスに止まった場合, プレイヤーはCCカードまたはCHカードの山の一番上からカードを1枚引く. カードの指示に従ったのち, そのカードは山の一番下に戻される. それぞれのカードは16枚あるが, 今回は問題を進み方に限定するので, 移動の指示があるカードのみを考える. 移動の指示が無いカードに関しては何もせずカードをそのまま山の下に戻す. プレイヤーはそのままCC/CHマスに残るものとする.

• Community Chest (16枚中2枚が移動カード)

  1. GOへ進め

  2. JAILへ進め

• Chance (16枚中10枚が移動カード)

  1. GOへ進め

  2. JAILへ進め

  3. C1へ進め

  4. E3へ進め

  5. H2へ進め

  6. R1へ進め

  7. 次のRへ進め (Rはrailway company, 鉄道会社の意)

  8. 次のRへ進め

  9. 次のUへ進め (Uはutility company, 公共事業会社の意)

  10. 3マス戻れ

今回考えるのは, どのマスに止まりやすいかである. 即ち, サイコロを投げた後に止まる確率である. より正確には, サイコロを1回振ってカードやマスによる移動を終えた後に各マスに止まる確率を求めたい. 従って, G2Jに止まる確率は0であり, CHマスに止まる確率はその次に少ない(16枚中10枚が移動カードなので). またJAILマスにたまたま止まることとJAILマスに送られることを区別しない. またJAILマスから抜けるルール (自分のターンにゾロ目を2回出す) を無視する. つまり必ず保釈金を払ってJAILマスから進むものとする.

GOマスを00とし番号を00-39と順番に振る. これにより各マスを2桁の数で表すことが出来る.

統計的には, 3つのマスに止まりやすいことを示せる. JAIL (6.24%) = 10番目, E3 (3.18%) = 24番目, GO (3.09%) = 00番目である. 従ってもっとも止まりやすいマスを6桁で表せて102400となる.

2つの6面サイコロではなくて, 2つの4面サイコロを用いた場合の, もっとも止まりやすいマスを6桁で表せ.

（翻訳ヒント、サイコロを振りぞろ目だろうがでなかろうが止まったマス目の指示に従う。カードマスならカードを引く。これを繰り返す。繰り返す途中で三連続でぞろ目が出たら強制的に刑務所行き）

立方体の6面それぞれに異なる数字(0から9)が書かれている;2番目の立方体も同様になっている. 異なる位置に2つの立方体を隣り合わせることで様々な2桁の数を作ることができる.

例えば, 平方数である64も作ることができる:

事実, 両方の立方体の数字を注意深く選ぶと100以下のすべての平方数を示すことが可能である:01, 04, 09, 16, 25, 36, 49, 64, 81.

例えば, これを実現する一つの方法としては {0, 5, 6, 7, 8, 9} を一方の立方体に, そして {1, 2, 3, 4, 8, 9} を他方の立方体に配置すればよい.

しかし, 6と9を逆さまに回転することを許すと {0, 5, 6, 7, 8, 9} と {1, 2, 3, 4, 6, 7} のような配列で9つすべての平方数を示す事ができる; そうでなければ09を得ることができない.

順番ではなくそれぞれの立方体の数字に着目して配列を区別する.

{1, 2, 3, 4, 5, 6} は {3, 6, 4, 1, 2, 5} と同じものとし {1, 2, 3, 4, 5, 6} は {1, 2, 3, 4, 5, 9} と異なるものとする.

しかし6と9を逆さにすることを許すために, 最後の例で区別された両方の配列のかわりに, {1, 2, 3, 4, 5, 6, 9} という(要素数が７つに)拡張された配列を使用して2桁の数をつくることにする.

すべての平方数を表示し得る2つの立方体の異なる配列の組はいくつあるか.

素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である. 50未満のこのような数は丁度4つある.

• $28 = 2^2 + 2^3 + 2^4$

• $33 = 3^2 + 2^3 + 2^4$

• $49 = 5^2 + 2^3 + 2^4$

• $47 = 2^2 + 3^3 + 2^4$

では, 50,000,000未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?