プロジェクト・オイラー(086-090)
Problem 86
Probem 「直方体のルート」
下に示す直方体は寸法が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を求めよ.
Answer
+ | 解答 |
Problem 87
Probem 「3つの素数のべき乗」
素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である. 50未満のこのような数は丁度4つある. 28 = 22 + 23 + 24 33 = 32 + 23 + 24 49 = 52 + 23 + 24 47 = 22 + 33 + 24 では, 50,000,000未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?
Answer
+ | 解答 |
Problem 88
Probem 「積和数」
少なくとも2つの自然数 {a1, a2, ... , ak} の集合の和かつ積として表せる自然数Nを積和数と呼ぶ: N = a1 + a2 + ... + ak = a1 × a2 × ... × ak. 例えば, 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 に対する全ての最小積和数の和は何か?
Answer
+ | 解答 |
Problem 89
Probem 「ローマ数字」
ローマ数字の記法は一つの数について沢山ある場合が存在する (FAQを見よ). しかし, ある数については最良の記法が必ず存在する.例えば, 16の正しい記法を全て並べてみる. IIIIIIIIIIIIIIII VIIIIIIIIIII VVIIIIII XIIIIII VVVI XVI最後の例は, 最小の文字数で表せるという意味で, 最も効率が良い.11Kのテキストファイルroman.txt は1000個のローマ記法で書かれた数を含んでいる. これらは, 正しい記法に従っている. 即ち, 大きい数から順に書かれていて, 引き算ペアのルールにも従っている(このルールについてはFAQを見よ) 但し, 最小の文字数で表されているとは限らない. 最小形で書いたときに, 何文字節約できるかを求めよ.注: ファイル中の全てのローマ数字には, 5つ以上の同じ文字が連続して含まれることはない. (訳者:概略のみ与える)全ての文字はサイズの降順に並ぶ引き算ペアについて.X (10) + IX (9) として19=XIXと表せる. ただし, 8をIIXと二文字以上を引くことは許されない.
Answer
+ | 解答 |
Problem 90
Probem 「2つの立方体の数字」
立方体の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} という(要素数が7つに)拡張された配列を使用して2桁の数をつくることにする.すべての平方数を表示し得る2つの立方体の異なる配列の組はいくつあるか.
Answer
+ | 解答 |