Problem 522 の編集

*[[Problem 522:https://projecteuler.net/problem=522]] 「ヒルベルトの停電」 [#n8253f15]

ヒルベルトの無限ホテルが盛況であるにもかかわらず、ヒルベルトはその代わりに超巨大有限ホテルの管理に乗り出すことに決めた.

コスト削減のため, ヒルベルトは彼お手製の特別な発電機で新しいホテルに電力を供給しようとしている. それぞれのフロアは上階のフロアに, そして最上階のフロアは最下階に電力を供給する. このようにすることで, ヒルベルトはどのフロアにでも発電機を配置し, ホテル全体にわたり自由に電気を流すことができる.

しかし不運なことに, 請負業者がホテルの建設の際に配線図を間違って解釈してしまった. 業者はそうではなくそれぞれのフロアから別のフロアに対しランダムに電力を供給するようになっているとヒルベルトに説明した. これによりヒルベルトはどこにでも自由に発電機を設置できたはずが, どこかのフロアが停電してしまうはめになってしまった.

例えば, 次のような3階のホテルのフローダイヤグラムの一例について考えてみよう:

#ref(p522_hilberts_blackout.png,center,nolink)

もし発電機が1階に設置されていたら, 全てのフロアが電力を受け取ることができる. しかしもしその代わりに2階や3階に設置されていたら, 1階が停電してしまう. あるフロアが他のフロアから電力を供給されている間に限り, そのフロアはまた別のフロアに電力を供給できるという点に注意.

停電の不安を解消するため, ヒルベルトは最小限のフロアを再び配線することに決めた. あるフロアを再配線するというのはすなわちあるフロアの電力供給先フロアを変更すると言うことだ. 上記の配線例では, 起こり得るすべての停電可能性は2階の電力供給先を3階から1階に変更することで回避できる.

'''n''' 階のホテルで可能なすべての電力供給配線に対し再配線が必要となる最小のフロア数の和を F('''n''') としよう. 例として F(3) = 6, F(8) = 16276736, そして F(100) mod 135707531 = 84326147.

F(12344321) mod 135707531 を求めよ.

タイムスタンプを変更しない

*[[Problem 522:https://projecteuler.net/problem=522]] 「ヒルベルトの停電」 [#n8253f15]

ヒルベルトの無限ホテルが盛況であるにもかかわらず、ヒルベルトはその代わりに超巨大有限ホテルの管理に乗り出すことに決めた.

例えば, 次のような3階のホテルのフローダイヤグラムの一例について考えてみよう:

#ref(p522_hilberts_blackout.png,center,nolink)

F(12344321) mod 135707531 を求めよ.

テキスト整形のルールを表示する