JuniorAnswer2021

ジュニア問題解説(中学３年生・高校１年生)

A
2021-森の見はり-解説
- 考案国：オーストリア
- 正解
  - 3つの見はり台を使った下の図が正解です。
- 説明
  - 道は8本あります。
  - もし見はりだいを2つしか使わないと、4本ずつ見はる必要がありますが、4本の道を見はることのできる見はりだいはありませんので、2つの見はりだいではぜんぶの道を見はれないことがわかります。
- 実際のコンピュータでは
  - コンピュータの世界では、多くの情報を、点と線で表す「グラフ」で扱います。この問題では、グラフは次の図のように表せます。
  - この問題は、「すべての線が、選ばれた点のどれかにつながっている」と考えることができます。このような問題は最小頂点被覆問題と呼ばれ、「すべての通りを照らすことのできる街灯の配置」や「すべての廊下を撮影できるカメラの配置」などを考えるときに使うことができます。
2021-カッコウ-解説
- 考案国：カナダ
- 正解
- 説明
  - 順に考えてみましょう。
- 実際のコンピュータでは
  - この問題のように、データを木の形で表現することを、木構造のデータ構造と呼びます。
  - データを木構造で表現し、値の大小を比較して適切な場所に入れて扱うと、「探している値が現在見ている値より小さければ左を探し、小さければ右を探す」のように、探す範囲を半分に絞りながらデータを高速に探すことができます。
  - このような左右に分かれる木構造は二分木と呼ばれ、コンピュータのプログラムの中で、データを高速に検索する際に使われています。
2021-いちご-解説
- 考案国：スイス
- 正解
  - ビバ子はイチゴのかわりにきのこを置きました。そして、次の図のように枝を抜き取りました。
- 説明
  - イチゴが置かれていた「？」には、5本の棒が置かれています。
  - どんぐりや小石を置くと、同じ種類の2箇所とつながっているため、2本の棒をぬき取る必要があります。
  - きのこを置くと、きのことつながっている1本をぬき取るだけですみます。
- 実際のコンピュータでは
  - ビ太郎が描いた絵は、点と線で関係を表す「グラフ」という構造で考えることができます。
  - グラフの中で、「すべての点が、他の点とつながっている」ような点の集まりをクリークと呼びます。この問題の図では、左と右に、4個ずつの点から作られた四角形のクリークが2個あることがわかります。
  - イチゴを他の物で置き換えると、置かれている物は3種類になりますので、4個の点を使ったクリークは作れなくなるはずです。そこで、4個の点から作られた2個のクリークを壊す棒を探すと、真ん中の縦の棒をぬき取ればよいことがわかります。
  - この問題は、「最小限の色数でグラフを着色する問題」として知られています。そして、スポーツ競技のスケジュール管理、座席表の設計、数独の解答など、多くの用途で利用されています。
2021-枝がり-解説
- 考案国：ウズベキスタン
- 正解
  - この図の赤色の枝を切り落とす 20 が正解です。
- 説明
  - 具体的に考えてみましょう。
  - 左側の枝を考えると、葉が付いている細い枝を切ると「3+1」と「3+1」になります。「3+1」の代わりに5の枝を切ることもできますが、「3+1」のほうが4の時間で切れるので、5の枝を切るより短い時間で済むことがわかります。また、いちばん太い9の枝を切ることもできますが、細い枝を4本切ると「3+1+3+1」で8になるので、9の枝を切るより短い時間で済むことがわかります。
  - 次に、上側の枝を考えると、左の2本を「3+5」で切るよりも、根本の4を切ったほうが短い時間で済むことがわかります。右の2本は「2+1」で3になりますので、根本の5を切るより短い時間で済むことがわかります。
  - 最後に右側の枝を考えると、3本を「3+2+1」で切るよりも、根本の5を切ったほうが短い時間で済むことがわかります。
- 実際のコンピュータでは
  - 木構造はコンピュータ科学で重要なデータ構造です。
  - 庭の木を木構造として考えることで、この問題は、根からすべての葉を分離するための、枝の最小の重みを求める問題として考えることができます。
  - これはミニマルカット（略してmin-cut）と呼ばれるグラフ理論の標準的な問題で、様々な標準的なアルゴリズム（例えばFord-Fulkesronアルゴリズム）で解くことができます。
B
2021-プレゼント2-解説
- 考案国：ドイツ
- 正解
- 説明
  - 同じプレゼントを欲しいビーバーが2匹いますので、全員に一番好きなプレゼントを渡すことはできません。まず、一番好きなプレゼントが重なっていない3匹については、そのプレゼントを渡すことにしましょう。
    次に、一番好きなプレゼントが重なっている2匹について考えます。2匹を見ると、二番目に好きなプレゼントは、1匹はまだ渡されていませんが、もう1匹はすでに他のビーバーに渡されていることがわかります。
    そこで、「2番目に好きなプレゼントが他のビーバーに渡されている」ビーバーに一番好きなプレゼントを渡し、「2番目に好きなプレゼントがまだ渡されていない」ビーバーに二番目に好きなプレゼントを渡すことで、すべてのビーバーが一番好きなプレゼントか二番目に好きなプレゼントを受け取ることができました。
- 実際のコンピュータでは
  - この問題では、ビーバーたちは一番目と二番目の希望を言いました。他のプレゼントは、すべて三番目と考えることができます。
  - できるだけ一番目の希望をかなえるか、できるだけ二番目の希望をかなえる組み合わせが他にないとき、その組み合わせは最適になります。
  - コンピュータ科学では、このような組み合わせ問題を「最大マッチング問題」と呼んでいます。組み合わせ問題にはいろいろなものがありますが、中には「安定した結婚問題」というものがあります。面白そうですよね。ぜひコンピュータ科学を学んでみてください！
2021-停電-解説
- 考案国：ハンガリー
- 正解
- 説明
  - まず、停電している家を見ると、Eにつながる2本の電線と、Cにつながる3本の電線はすべて切れていることがわかります。1本でもつながっていれば、EやCは停電になりません。
  - 次に、停電していない家を見ると、その家には電気が届いていることから、風車からAまでの電線は切れていません。Hにつながる電線も切れていません。Fにつながる電線は、Eとつながる電線は切れているので、Gとつながる電線は切れていません。
  - 残りの停電していないB, G, Dの家は、複数の電線でAとつながっています。そのため、たとえばBの家は、Aとつながる電線が切れても、Gとつながる電線から電気をもらえます。このように、A,B,G,D,Aをつなぐ電線は、どれか1本が切れても停電しないことがわかります。
- 実際のコンピュータでは
  - コンピュータのネットワークでは、この問題の電線と同様に、多くの通信線で実現されています。通信線の中には、速度が遅かったり、過負荷だったり、あるいは完全に壊れていたりといったような、障害が発生することがあります。ネットワークの構造に冗長性を持たせることで、1箇所で障害が発生しても継続的に利用できるようになる工夫が行われています。
  - コンピュータの科学者は、ネットワーク構造を表現するために、「グラフ」という表記法を使います。グラフを扱うアルゴリズムは数多く存在します。例えば、ネットワーク構造を考えた上で、できるだけ効率的に障害のある線を発見することができます。
  - システムの故障（エラー）を修正することは、コンピュータネットワークだけでなく、ソフトウェア開発においても、コンピュータ科学者が頻繁に行う作業です。エラーを修正するためには、その原因を正確に特定する必要があり、この作業は通常、いくつかのステップで徐々に行われます。プログラマーの中には、プログラムに含まれるすべてのエラーやバグを見つけることはできないと考える人もいます。
2021-出会い-解説
- 考案国：リトアニア
- 正解
  - 正解は4分です。下の図のように進むと最短で出会うことができます。（別解として、左下の自転車に乗ってから左側の自動車に乗ると、同じく4分間で出会うことができます）
- 説明
  - では、3分以内に着けない理由を考えてみましょう。
  - 3分では、左側の自動車に着くことはできますが、走らせる時間はありません。そして、自動車の場所には右側にいる相手が3分で着くことはできません。結果として、自動車は使えないことがわかります。
  - 次に自転車を考えると、2人が自転車に乗るために1分かかり、残りの2分では自転車で会うことはできないので、やはり無理なことがわかります。
2021-机-解説
- 考案国：エルサルバドル
- 正解
  - A を3回押して，B を4回押して，C を2回押す
- 説明
  - 「A」ボタンを3回押すと、机1、2、3の高さがそれぞれ40、100、80になります。
  - 次に「B」ボタンを4回押すと、机2、3、4の高さはそれぞれ60、40、40になります。
  - 最後に「C」ボタンを2回押すと、机1、3、4の高さはすべて60ビーバー単位になります。
- 実際のコンピュータでは
  - プログラムを作るときに、条件によってコンピュータに違う動作をさせたいことがあります。
  - そのようなときは、条件文を使うことで、条件によってコンピューターに異なる処理を行わせることができます。
C
2021-クモのキルト-解説
- 考案国：カナダ
- 正解
- 説明
  - クモの巣を観察しましょう。すると、つながっている糸がわかります。
    ・1と3（3と1）
    ・1と5（5と1）
    ・1と6（6と1）
    ・2と4（4と2）
    ・2と7（7と2）
    ・3と6（6と3）
    ・4と6（6と4）
    ・4と7（7と4）
  - これらの場所に「米」の印が置かれているものが正解です。
2021-サルのジャンプ-解説
- 考案国：スロベニア
- 正解
  - サルは、下の絵の紺色の8本の木に飛び移ることができます。
- 説明
  - 公園の木をよく観察して、飛び移れる木に同じ色を付けていくと、上の絵のように6個のグループに分けることができます。
  - サルが黄色に塗られた木から出発した場合、すべての黄色の木に飛び移ることができますが、他の色の木には飛び移ることができません。
- 実際のコンピュータでは
  - ある木から飛び移れる木に線を引くと、下の絵のような線を描けます。
  - 色を付けるほかに、線で結ぶことで、具体的な移動を表現することができます。
  - また、この絵のように点と線で情報を表現することで、問題をコンピュータに入力して解決することが可能になります。
  - 情報を点と線で表すことを「グラフ」にすると言い、問題をコンピュータで扱える形に整理することをモデル化と呼びます。
2021-重ねられた果実-解説
- 考案国：スロベニア
- 正解
- 説明
  - この問題は、次のように考えることができます。
    - まず、父はみかんだけが好きなので、一番最後に起きる父のために、みかんを一番下の箱に入れましょう。
    - 母は娘より前に起きるので、母が取るのは1番上か2番目の箱で、娘が取るのは2番目か3番目の箱です。息子の取る箱は1番目でも2番目でも3番目でも構いません。
  - これらを表にまとめると、起きる順の組み合わせは、次の3つの案が考えられます。
  - この表で2番目を見ると、息子と娘と母の可能性があるため、2番目の箱には3人全員が好きなものを入れる必要があります。それはりんごですね。
  - 次に、1番上の箱を考えると、残った果物はなしといちごですが、母はなしが嫌いなので、1番上の箱には、母と息子が好きないちごを入れる必要があります。そして、残った3番目の箱にはなしを入れましょう。
- 実際のコンピュータでは
  - コンピュータ科学を学ぶときに、データの並ぶ順序を考えることは重要です。また、問題を解くためには、問題の背景情報を理解する必要もあります。この問題では、誰が最初に起きるのか正確にわからない状態でも、問題が解決できるように情報を整理する必要がありました。
  - この問題では、4個の箱の並びを考えるときに、スタックと呼ばれる考え方が使われました。スタックは「後入れ先出し」、つまり「最後に入れたものが最初に取り出される」データ構造です。スタックでは、1番上にあるものにしか取り出すことができません。1番上のものを取り除いて初めて、2番目のものが利用できるようになるのです。スタックはプログラミングの中でよく使われます。
  - この問題では、複数の条件を満たすように、果物の配置がうまくいくような解決策が求められました。しかし、問題にはいくつかの制約条件があり、すべての状況が発生するわけではありません。このような制約のある問題を解くのは、一般的には難しいことが多いです。そのためには、コンピュータプログラムを作成し、それを使っていろいろな組み合わせを試すことで、問題を解決するのが有効な場合があります。
  - コンピュータ科学やプログラミングでは、論理の考え方が重要です。このような論理を理解するための問題を解くことは、コンピュータやプログラムを学び始めたときに、よい練習問題になるでしょう。
  - 解説にあるように、すべての可能性を示す表を作ることは、与えられたデータを並び替えたり順序付けするための良い方法です。論理の組み合わせ（AND、OR、NOT）を使って、どのデータが有用かを判断するブール論理の考え方も役立ちます。この問題のような計算問題を解くことで、ELSE/IFのようなプログラミングにおける条件式も理解できるようになるでしょう。
  - 論理を理解して、論理的にプログラムの命令を実行して問題を解決する方法を理解した後は、多くの変数を持つ問題を解決するために、自分でコンピュータプログラムを書くことができるようになります。そして、スタックを処理するプログラムを書くこともできるようになるでしょう。
2021-トルシェタイル-解説
- 考案国：スロベニア
- 正解
- 説明
  - パッと見ただけでは、どのように考えてよいかがわからないかもしれません。それぞれのタイルについて、タイルの線がどこで交わるかを観察してみましょう。
  - 左のパターンでは、1本の連続した波状の線が見えます。ですから、この模様を作るタイルの線は、曲がっていて、タイルの端の直線のの真ん中でつながっている必要があります。
  - 曲線を使ったパターンは他に1つしかないので、そのパターンを作るためには、曲線を持ったもう1つのタイルを使う必要があります。
  - 残ったタイルのうちの1枚は、隅に暗い色がついています。残りの2つのパターンの角を見てみると、片方のタイルだけが同じ暗い色をしていることがわかります。
- 実際のコンピュータでは
  - この問題では、考案者の人名にちなんで付けられたパターンを扱いました。
  - とてもシンプルな要素を組み合わせて複雑なパターンが作れることは、昔から人々が探求してきました。
  - このようなパターンは、数学やコンピュータ科学の分野で研究され、コンピュータゲームでは迷路や壁の模様などの生成に使われています。