プログラミングクイズ第４弾！！(解答編)

 
こんにちは、志學舎若葉台教室KID’sプログラミングラボ担当の阿部龍之介です。
 
前回のクイズの答え合わせをしましょう！
 

問題　２５頭の馬がいます。

これからレースを行い、足が速い３頭を見つけます。

しかし、１回のレースで走れる馬は５頭まで。

しかも、レースのタイムは計測できないため、「Ａの馬はＢより速い」というように、馬同士を比べるしかありません・・・

さて、最速の３頭を見つけるために必要な最小のレース回数は？

 

正解は…なんと７回で済んでしまいます！

 

解説
まず、２５頭の馬を５グループに分けます。そのグループ内で１回ずつレースを行います。すると、５グループ内における１位～５位のウマが分かります。
 
グループ名を仮にあ,い,う,え,お、順位を1,2,3,4,5とすると以下の通りになりますね。
 

• あ1,あ2,あ3,あ4,あ5
• い1,い2,い3,い4,い5
• う1,う2,う3,う4,う5
• え1,え2,え3,え4,え5
• お1,お2,お3,お4,お5

 
ここで、１つ目のポイントがあります。この時点で、各グループの4位および5位は「２５頭の中でトップ3頭」にはなれないので候補から外れます。
 
そのため、残った馬は以下の15頭になりますね
 

• あ1,あ2,あ3
• い1,い2,い3
• う1,う2,う3
• え1,え2,え3
• お1,お2,お3

 
しかし、ここからがすこし複雑です。一瞬、1位の馬だけでレースを行って上位3頭を選べばいいように思えます。
 
しかしグループ間順位差がはっきりしていない（例えば「あ」グループと「い」グループの馬の速さの比較ができてない）ため、その場合に選んだ3頭は全25頭の中でのトップ3頭にはならない可能性があります。
たとえば、Aグループに全頭最速の3頭が固まっている場合。このときの「25頭のうち最速の3頭」はA1, A2, A3です。では、どうやって比べればいいのでしょうか…
 
そこで、6レース目はとりあえず、各グループ1位の馬5頭による競争を行います。順位が以下の様になったと仮定しましょう。
 

• 1位：あ1
• 2位：い1
• 3位：う1
• 4位：え1
• 5位：お1

 
このとき、少なくともえ1とお1は「全体のトップ3」には入れないことが確定します。同時に、え1,お1より遅いえ,おグループの2位3位も「全体のトップ3」には入れないことが判明します。残った候補は以下の9頭。
 

• あ1,あ2,あ3
• い1,い2,い3
• う1,う2,う3

 
6レース目の結果の一部をもう一度見てみます。
 

• 1位：あ1
• 2位：い1
• 3位：う1

 
よく考えたら、う2とう3は「全体でトップ3頭」には入れません。う1より速い馬が現時点で2頭もいるからです。同じように、い3にもチャンスはありません。だから6レース終了時点で残る候補は以下の6頭になります。

 

• あ1,あ2,あ3
• い1,い2
• う1

 
あ1は全25頭で最速の馬です。なので最後の7レース目では、あ1を除く5頭での競争になります。あ1、および最終レースの1位2位が「全25頭で最も速いトップ3の馬」です。
 
 
すこしごちゃごちゃしてきましたね…そこで、前回説明したフローチャートを活用すると、理解が早まると思います！
 
いままで出したクイズは、こちらの記事を引用させていただきました。このサイトには他にもたくさん魅力的な論理クイズがあります。
 
https://sist8.com/logic
 

 

志學舎若葉台教室と高幡教室では、小学校低学年から中学生・高校生までを対象に、ゲーム作成をメインとしたプログラミング教室「Kidsプログラミングラボ」が行われています。

「プログラミングって難しいんでしょ？」「まだタイピングやパソコン操作が慣れていなくて…」って方、ご安心ください！

Kidsプログラミングラボなら、マウス操作のみで作れるプログラミング「Scratch」を扱っているため、パソコン操作が不安なお子様でも大丈夫！！

「もっと高度なゲームを作りたい」って思う方は、YouTubeやAIなどに使われる「Python」、Web制作に必要な「HTML,CSS,JavaScript」、3DゲームやUnityに使われる「C++」など、初心者から上級者まで楽しめます！

少しでも気になった方は是非、志學舎若葉台教室、志學舎高幡教室のKidsプログラミングラボに来てみてはいかがでしょうか！