夢の１００連勝　　 　　　　　　　　　　　 　　　 　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「ＹＩ」さんからの出題です。（平成２６年５月２日付け）

　トーナメントに関係した問題です。１対１で、勝ち負けが決まるゲームをします。８人でトーナ
メントをすると、だれか一人が必ず一位になり、その人は３連勝しています。つまり、８人いれ
ば、３連勝している人を１００パーセントの確率で、有限時間の間に作り出すことができます。

　では、１００連勝している人を１００パーセントの確率で、有限時間の間に生み出すために
は、最低でも何人必要でしょうか。ただし、トーナメント形式をとる必要はありません。



































（コメント）　最大で、２¹⁰⁰人いれば、１００％の確率で、１００連勝している人を有限時間の間
　　　　　　に生みだすことは明らかに可能だが、問題は、最低で何人以上必要かということで
　　　　　　．．．。


　よおすけさんが考察されました。（平成２６年５月２日付け）

　2人で1対1勝負すると、どちらかが1勝します。これを後、99人繰り返せばよいから、101人。


　ＹＩ さんからのコメントです。（平成２６年５月２日付け）

　連勝している人が負けたら１からやり直しですから、「１００パーセントの確率で、有限時間
の間に」とは言えないと思います。ちなみに、答えはあってますが．．．。101人でうまく組めば
確実に100連勝させられるとは、直観とは反しているのではないでしょうか。


　よおすけさんからのコメントです。（平成２６年５月２日付け）

　これは、時間制限度外視で最短人数だけ重視したので、そこまで考えていなかったです。
貴殿が納得いくような説明ができればなお良かったのですが、難しいです・・・。


　らすかるさんが考察されました。（平成２６年５月３日付け）

　２人いれば、１連勝は可能。ｎ人で、ｎ−１連勝が可能だとすると、ｎ＋１人のうち１人を除い
たｎ人で、ｎ−１連勝の人が作れて、ｎ−１連勝以外の人ｎ人で、再度ｎ−１連勝の人を作り、
最後に、ｎ−１連勝の人２人でゲームを行えば、ｎ連勝の人が作れる。

　実際の方法としては、ｎ連勝の場合、２ⁿ人のトーナメント表を作り、最初のｎ＋１人を端か
ら順に割り当てて対戦が決まっているゲームを行い、負けた人を空いている箇所に順に割
り当てていけばよい。よって、101人。


（コメント）　なるほど！できそうですね。


　DD++さんからのコメントです。（平成２６年５月３日付け）

　２人だと思います。勝敗を確率的に決めるものとは指定されていないので、例えば、勝敗
は将棋で決めるものとして、八百長でどちらかがわざと100連敗すれば条件を満たします、
とかいう揚げ足取りはさておいて．．．。

　101人で、以下のようにすれば、ちょうど2¹⁰⁰-1回の勝負で、100連勝する人が現れます。

(1)　誰か1人を仲間外れにしておく。
(2)　残り100人は全員看板を持ち、0と記入しておく。
(3)　以下のルールでひたすら勝負を繰り返す。
　(a)　同じ数字を掲げた人と出会ったら勝負をする。
　(b)　勝った人は看板の数字に1を足す。
　(c)　負けた人は看板の数字を0に戻す。
(4)　やがて、0から99まで1人ずつになる。
(5)　仲間外れにしていた1人が看板を持ち、0と記入する。
(6)　以下のルールでひたすら勝負を繰り返す。
　(a)　同じ数字を掲げた人と出会ったら勝負をする。
　(b)　勝った人は看板の数字に1を足す。
　(c)　負けた人は看板を捨てる。
(7)　最後の勝負に勝った人が100連勝となる。

　看板に「k」と書いてある人は、2^k-1点（看板がない人は0点）として全員の点数を合計する
ことを考えると、最初は合計0点で、勝負1回ごとに合計は1点ずつ増えます。

　よって、最後に「100」と書いた人が1人だけいて、残り100人は看板を捨て、合計点2¹⁰⁰-1
点になっている時の合計勝負回数は、2¹⁰⁰-1回。気の遠くなる勝負回数ですが、有限は有
限です。

　回数が有限でさえあれば減らすことを考える必要はない、というのであれば以下でも十分
です。

(1)　全員看板を持ち、0と記入しておく。
(2)　以下のルールでひたすら勝負を繰り返す。
　(a)　同じ数字を掲げた人と出会ったら勝負をする。
　(b)　勝った人は看板の数字に1を足す。
　(c)　負けた人は看板の数字を0に戻す。
(3)　やがて、0から100まで1人ずつになる。
(4)　100を掲げた人は100連勝している。

　この場合、2¹⁰¹-102戦。


　よおすけさんからのコメントです。（平成２６年５月３日付け）

　DD++さんの冒頭の指摘にもありましたように、「対戦相手は100回とも同じ方でよいのか？」
が問題文で問われていなかったので、僕も当初は2人と答えようと思っていましたが、「100回
とも対戦相手はすべて異なる方とする」の場合も考えられるので、1回目の投稿では101人と、
とりあえず答えました。こんなこというと、キリがないですが。


　DD++さんからのコメントです。（平成２６年５月３日付け）

　そういえば、100連勝の中に同じ対戦相手がいるかいないかは全く考えませんでしたが、
「異なる100人に100連勝」とした場合、5051人が答えですかね。もっと少ない人数でいけるか
な？もちろん確率的勝負を前提として。


　らすかるさんからのコメントです。（平成２６年５月３日付け）

　5051人では無理では？

　異なる1人に1連勝→2人　、異なる2人に2連勝→4人　、異なる3人に3連勝→7人

までは良いと思いますが、「異なる4人に4連勝→11人」は多分不可能で、

　異なる4人に4連勝→13人

になると思います。

　実際、確実に100連勝が存在する最低試合数は、2¹⁰⁰-1試合で、このそれぞれの試合で
同じ組合せが存在してはいけませんので、₅₀₅₁Ｃ₂≪2¹⁰⁰-1 からも無理っぽい気がします。


　DD++さんからのコメントです。（平成２６年５月３日付け）

　4連勝以上の場合、注意深く組めば、同じ対戦カードを複数回組んでも大丈夫な場合があ
ります。


　らすかるさんからのコメントです。（平成２６年５月３日付け）

　ああ、なるほど、そうですね。ちょっと勘違いしていました。3連勝は7人で、4連勝ならば3連
勝している人と当たっていない3人が、あらためて別のトーナメントに加わって同じ人と再度対
戦しても問題ないですね。確かに、5051人になりそうです。

　となると、全然関係ない（？）ですが、

　　(「異なるｎ人にｎ連勝」の最少人数)＝(平面をｎ本の直線で分ける最大領域数)

ですかね。


（コメント）　興味をそそられる視点ですね．．．。


　ＹＩ さんからのコメントです。（平成２６年５月３日付け）

　同じ相手も可能だとしていて、そこまでは考えませんでした。
（ここから先は同じ相手も可の場合）

　一般式は、らすかるさんが考えた方法で導けます。ｎ人で作れる最多の連勝数を T(ｎ)と
書くことにします。当然のように、T(２)＝１ で、また、T(ｎ)について、

　１．ｎ−１人でできるだけ多くの連勝をさせる。
　２．連勝中の１人を除いたｎ−１人で多く連勝させる。
　３．その二人が勝負する

　以上より、　T(ｎ)＝T(ｎ−１)＋１

　数学的帰納法より、　T(ｎ＝ｎ−１

　この場合、ｎ−１＝１００　なので、　T(１０１)＝１００　です。

　この方法をとったときの必要な試合数は、２¹⁰⁰−１ 、一般に、２^n-1−１。

　余談ですが、正直に、２¹⁰⁰人でトーナメントをした時も必要な試合数は、２¹⁰⁰−１回。
試合数は、変わらないのですね。


　夏さんからのコメントです。（平成２６年５月３日付け）

　一回に二人の人間が必要で、かつ勝ち負けがはっきりするゲーム（じゃんけんなど）をする
とします。今確実にn連勝する人を作るとすると、

（１）　ｎ人いれば、最長で、２ⁿ−１回の試行が必要です。
（２）　２ⁿ人いれば、ｎ回の試行で終わります。

　どっちにしても指数的な部分が出てきてしまいますよね…。人数×試行回数を多項式的に
するようなやり方はないのでしょうか？


　らすかるさんからのコメントです。（平成２６年５月３日付け）

　２ⁿ人いても、試行は、２ⁿ−１回ですね。（→トーナメント表をイメージ）


　夏さんからのコメントです。（平成２６年５月３日付け）

　一回の試行の中に同時に幾つかの試合をするのもありにしています。リーグ制だと、一回
目で、２^n-1人が勝ち、もう半分が負けるという感じで．．．。


　らすかるさんからのコメントです。（平成２６年５月３日付け）

　そういう考え方ならば、「（１）　ｎ人いれば、最長で、２ⁿ−１回の試行が必要です。」が誤り
になります。全部で２ⁿ−１回ですが、同時に行える試行もたくさんありますので、２ⁿ−１回
よりはかなり減ります。


　ＹＩ さんからのコメントです。（平成２６年５月４日付け）

　計算できる見込みがないので、コンピューターを走らせてみました。100万回試行してもま
だ一人が30連勝している程度の段階なので、終わるのはいつになることやら。結局、人間
業で１００連勝は難しいみたいです。


　らすかるさんからのコメントです。（平成２６年５月４日付け）

　２ⁿ−１回よりはかなり減りますが、「101人で100連勝」ならば1回戦で最大50試合しかでき
ませんので、同時に行える試合を1回と数えても、少なくとも {(２¹⁰⁰−１)/５０} 回は必要です
ね。結局、指数的であることには変わりありません。


　ＹＩ さんからのコメントです。（平成２６年５月４日付け）

　そうですね。一桁しか減らないのに無茶していました。動かした感じだと、シミュレーション
は、２⁵⁶日で終わるようだったので、さすがにやめました。


　よおすけさんからのコメントです。（平成２６年５月５日付け）

　「２⁵⁶日という日数は、年数もしくは月数に換算するとおよそどのくらいか？」と興味がわき
ましたが、いきなりは大変なので、まずはそれより少ない日数から・・・。だいたいの目安を記
載しています。

　２³＝8日・・・・約１週間　、２⁴＝16日・・・・約半月　、２⁵＝32日・・・・約１ヶ月　、-中略-
　２⁸＝256日・・・・約８ヶ月半　、２⁹＝512日・・・・約１年４ヶ月半　、
　２¹⁰＝1024日・・・約２年９ヶ月半

　誤差はありますが、２ⁿ日(ｎは正の整数)は、ｎが１ずつ増える度、日数がおよそ２倍ずつ増
えていきます。ちなみに、２¹⁵日がおよそ８９年９ヶ月半ですから、２⁵⁶日だと何年かかるので
しょうネ！


　DD++さんからのコメントです。（平成２６年５月５日付け）

　グーグル先生に「２⁵⁶日を年で」と尋ねてみるとよいかと思います。


　ＹＩ さんからのコメントです。（平成２６年５月５日付け）

　「２¹⁰⁰=1000」で計算すると、175,342,465,753,424（年）(約175兆年!)でした。
　「WolframAlpha」によると、「1.973×10^14 average Gregorian years」だそうです。


　よおすけさんからのコメントです。（平成２６年５月５日付け）

　グーグルでの調査は逆に路頭に迷いそうだったので、２⁵⁶程度はパソコン付属の電卓で
やってみると、
　　　　　　　　　２⁵⁶＝72057594037927936

でした。これを1年の目安である365(日)で割ると、２⁵⁶日＝約197,418,065,857,336年10ヶ月
うーん、２⁵⁶日後って、遥か遠い未来ですネ。


　DD++さんからのコメントです。（平成２６年５月５日付け）

　Google電卓の単位換算機能が求める答えそのまんまを返してくれるので、路頭に迷う余地
ないと思うのですが……？


　よおすけさんからのコメントです。（平成２６年５月５日付け）

　今の計算は閏年を含んでいないので、閏年も含むとなると挙げたものより年数は減ります
が、あくまで目安、ということで。パソコン付属の電卓でも、２⁵⁶の値が桁数オーバーになって
いたらグーグル使おうと思いましたが、範囲内におさまったので、グーグルは前述のように
使わずに済みました。


　通りすがりさんからのコメントです。（平成２６年５月５日付け）

　こうやって計算できます。（→　Google電卓）

　「今の計算は閏年を含んでいないので」　→　現行のグレゴリオ暦がいつまで続くか……。


　らすかるさんからのコメントです。（平成２６年５月５日付け）

　今日2014年5月5日から２⁵⁶日後は、グレゴリオ暦が今のまま続けば、

　　　西暦197,286,991,625,190年7月20日(金)

です。


　通りすがりさんからのコメントです。（平成２６年５月５日付け）

　試しに「1年を日で」でGoogle検索したら、「365.242199日」と出てきました。これは暦上の1年
ではなく、地球の公転周期（1900年1月0日12:00(UTC)の太陽年。最近の値では0.8秒ほど短
くなった）です。つまり、「２⁵⁶年を日で」でGoogle先生が教えてくれる「1.97287154 × 10^14 年」
というのは、「地球の公転周期が1900年から変化せず、その公転周期に合わせて閏年のル
ールも改良された場合」の年数ということになります。

　ちなみに、現行のグレゴリオ暦がそのまま使われるとすると、

　　２⁵⁶ / 365.2425 = 1.9728699 × １０¹⁴（年）

になります。


　らすかるさんからのコメントです。（平成２６年５月５日付け）

　さらに自転周期も変化せず、かつ太陽も燃え尽きずに現状を維持する場合ですね。


　通りすがりさんからのコメントです。（平成２６年５月５日付け）

　言い方が難しいですね。

１．「地球の公転周期が1900年から変化しないという仮定のもと、何京年に1日ずれるかず
　　れないかという精度になるまで閏年のルールが改良した場合」

　　　計算上の暦として考えると楽

２．.「地球の公転周期も自転周期も1900年から変化せず、かつ太陽も燃え尽きずに現状を
　　維持し、またその周期の下では何京年に1日ずれるかずれないかという精度になるまで
　　閏年のルールも改良する知能（生物でなくても可）が存在する場合」

　　　実際にその日付が存在すると考えたらこうなる

３．「1900年現在の公転周期で何回公転するか」

　簡単だが、1.と違い月数が定義できない。しかしGoogle先生によると、

　　・1月 = 30.4368499 日　　　・12月 = 365.242199 日

ということで「1年 ÷ 12」でOKらしい。


らすかるさんからのコメントです。（平成２６年５月５日付け）

　１．について、これはつまり、「1年の長さが変わらない場合」と言いたいのだと思いますが、
1日の長さは変わりますので、やはり「自転周期も変化しない」というのも必要だと思います。
（実際、86401秒の日がたまにありますね。）

# 現在1日の長さはうるう秒で補正されていますが、もし自転が遅くなって、1日の長さが長く
　なっていった場合、「毎月うるう秒」→「毎日うるう秒」
　　　　　　　　　　　　　　　　　　　　　　　　　　　→「毎時うるう秒」→「1分を61秒に変更」→・・・
　のようになって、1日が長くなりますので、「２⁵⁶日」の年数も変わりますよね。

　　もしかしたら、「公転周期が変化しない」というのは、「1日の長さが変化しても、公転周期
　が、その1日の長さで、常に365.242199日である」という意味でしょうか。


　ＹＩ さんからのコメントです。（平成２６年５月５日付け）

　太陽はあと50億年程度しかもちませんが．．．。


　通りすがりさんからのコメントです。（平成２６年５月５日付け）

　その時に太陽暦が意味をなしているかは別にしても、365.242199日で議論するのは難しそ
うですね。Googleの答えをそのまま受け入れなくてよかったです。

　というわけで、今回の問題に対する私の答えはこうしたいと思います。

　「197,286,991,623,176年2ヶ月半。ただし、グレゴリオ暦が今のまま続くと仮定する」

　数字はらすかるさんの投稿から頂きました。端数の76日は閏日の入り方で±1日ずれる可
能性があるので、「2ヶ月半」と曖昧にして回避しました。問題文も「年数もしくは月数に」と言っ
ているので。あるいは有効数字2桁で「約200兆年」で（今までの議論は一体……（笑））