ベンジャミン問題解説(小学５年生・６年生)

• A

  2019-ネコ-解説

  • 考案国：カナダ
  • 正解
    • 
  • 説明
    • 元の図
    • 正解はこの図の通りです:
      
      いちばん左に茶色の猫を移すために1番目と4番目の猫を交換すると、1番目は正しい猫になりますが、2番目と3番目と4番目の猫の位置が違っているため、もう1回の交換で3匹を正しい位置に動かすことは不可能です。
    • 元の図の左から1番目と3番目の猫が交換され、2番目と4番目の猫が交換された場合、結果はこのようになります:
      
    • 元の図の左から2番目と3番目の猫が交換され、3番目と4番目の猫が交換された場合、結果はこのようになります:
      
    • 元の図の左から1番目と4番目の猫が交換され、3番目と4番目の猫が交換された場合、結果はこのようになります:
      
  • 実際のコンピュータでは
    • この問題は、「データの交換（スワップ）」のみを使用したアルゴリズムを扱っています。2つのデータを交換するスワップ操作は、コンピューターの処理で多く使われる技術です。猫をコンピュータのメモリに保存されたデータと考えると、この問題はメモリ内で2つのデータの場所を変更する問題と考えることができます。

  2019-交差点-解説

  • 考案国：ルーマニア
  • 正解
    • 
  • 説明
    • 家に帰るためには、最後の交差点は上矢印である必要があります。また、最初の矢印は、左向きだとループになってグルグル回って抜けられなくなるため、右向きになります。その結果、2つ目の交差点は左向きであることがわかります。
  • 実際のコンピューターでは
    • 問題を解決する手順のことをアルゴリズムといいます。問題を解決するためには、正しい操作を順番に行う必要があります。この問題では、交差点に矢印の標識を置いて処理を進める方向を指示する必要がありました。ゴールに到達するためのコースは複数あることもありますし、ループに入って抜けられなくなることもあります。これはアルゴリズムが終了せずずっと計算を続けてしまうことに相当します。

  2019-不思議な紙-解説

  • 考案国：韓国
  • 正解
    • 
  • 説明
    • それぞれの絵は次のように色の上に描かれます。

      A	B	C	D
      4色	2色	3色	4色

      色の数を見るとわかるように、Cだけが3色です。
  • 実際のコンピュータでは
    • この問題では場所によって隠れた色が変わりました。
      実際のコンピュータでは、複数の画像を重ねたように見えるレイヤーを表示しています。各レイヤーの画像は混合して表示されます。
    • 絵を描くためのペイントソフトでは、レイヤーの順序を変更したり、一部のレイヤーを薄くして後ろの画像が見えるようにしたりできます。これは透明度と呼ばれます。
    • Webサイトを見ると、背景画像、色、テキストなどの、多くのものが互いに重なり合っていることがわかります。これらを正しく表示するには、表示する順番が重要です。この順番はz-indexやZオーダーなどと呼ばれます。
• B

  2019-動物-解説

  • 考案国：インドネシア
  • 正解
    • 
  • 説明
    • 正解はCです。虫はカエルに食べられてしまいます。
      他の絵はすべての生き物が平和に共存できます。
  • 実際のコンピュータでは
    • この問題を解決するには、オオカミとキツネの両方に食べられてしまう鶏など、複数の動物に狙われる動物に注目します。そして鶏が安全になるかどうかを確認します。すべての動物が安全なことを確信できるまで、いちばん強い動物から順番に試して行きましょう。
    • コンピュータ科学では、これは「制約充足問題」と呼ばれます。 制約充足問題の解は、「すべての変数が、示された制約を満たしている」状態になることです。この問題では「すべての動物が、捕食者の隣にいないという制約を満たしている」ことに相当します。

  2019-雪だるまの帽子-解説

  • 考案国：リトアニア
  • 正解
    • 
  • 説明
    • 正解はEです。
      いちばん上の帽子をいちばん左の雪だるまにかぶせ、残ったいちばん上の帽子を次の雪だるまにかぶせるように順に帽子をかぶせていったときに、雪だるまの大きい順にそれぞれ大きい順に帽子がかぶせてあるかを考えましょう。
  • 実際のコンピュータでは
    • この問題では、帽子を上から順に取り出し、雪だるまに左から順にかぶせました。このように、2つのデータを1個ずつ順に対応させることをマッピングと呼びます。
    • 帽子を1個ずつ置くときは、最初に置いたものが下になり、取り出すときはいちばん最後に置いた上のものから取り出します。このように「最後に置いたものから順に取り出す」データの構造をスタックと呼びます。
    • 帽子は、新しいものを下に入れていくことで、上から順に置くこともできます。この場合のように「最初に置いたものから順に取り出す」データの構造をキューと呼びます。
    • この問題の雪だるまも、「右から到着して、早く着いたものから順に帽子をかぶって左に出ていく」ように動く場合はキューとして考えることができるでしょう。

  2019-飾りつけ-解説

  • 考案国：ハンガリー
  • 正解
    • 
  • 説明
    • 正解はBです。
      Bでは、テーブルクロスの色が毎回変わり、3種類の花がすべて使われています。
      AとDでは、テーブルクロスの色が隣と同じものがあります。
      Cでは、2種類の花が使われていて、1種類でも3種類でもありません。
  • 実際のコンピュータでは
    • コンピュータでは、複数の条件を満たしているかどうかを調べる論理演算は重要です。ANDは2つの条件を満たしているかを調べる論理積です。ORは少なくともどちらかの条件を満たしているかを調べる論理和です。
      この問題では、「1種類の花か3種類の花が使われている」という論理和（OR）と、「テーブルクロスが交互に並べられていて、1種類か3種類の花が使われている」という論理積（AND）が組み合わされて使われていました。
      このような問題を解くことで、論理的思考を向上させることができます。

  2019-ビーバーコイン-解説

  • 考案国：スイス
  • 正解
    • 
  • 説明
    • 最適な解は「8ビーロが1枚、4ビーロが1枚、1ビーロが1枚」です。
      16ビーロでは大きすぎます。8ビーロを使うと残りは5ビーロで、いちばん近いのは4ビーロです。そうすると残りは1ビーロで、2ビーロだと大きすぎるので1ビーロを使います。
  • 実際のコンピュータでは
    • コンピュータではさまざまな種類のデータを扱います。この問題では数を表す数値データを扱いました。
      数値を表すときは、13の例だと「8を1枚、4を1枚、1を1枚」のほかに、「4を3枚、1を1枚」や「4を2枚、2を2枚、1を1枚」「1を13枚」などさまざまな表現ができてしまいます。
      これでは表現があいまいになってしまうため、「最も少ない枚数のコインで表す」というルールを加えることで、「8を1枚、4を1枚、1を1枚」という最適な表現に決まるようにしています。
• C

  2019-スカーフ制作機-解説

  • 考案国：リトアニア
  • 正解
    • 
  • 説明
    • 正解はAです。
      図の上の中央にある草は続けて現れることができますが、図の下の中央にある木の枝は繰り返すことができないことに注意しましょう。また、図の出口の青い花から、入口の紫の花に戻ることはできません。
  • 実際のコンピュータでは
    • この問題のように、入口から矢印をたどりながら「今どこにいて、次はどこに移る」を繰り返して出口に行けるかを表す図をオートマトンまたは状態遷移図と呼びます。
    • オートマトンは、プログラムが文法通りに書かれていることを確認したり、PCやスマートフォンで入力された文字を日本語に変換する処理、電卓で数式が正しいことを確認する処理などで利用されています。
    • たとえば、多くの電卓では「12+3=」を入力すると正しく計算が行われますが、「12++3=」はエラーになって計算されません。これは電卓の中に「数字の繰り返しと、演算記号と、数字の繰り返しと、最後に＝」を表すオートマトンが定義されているため、正しい数式かどうかをチェックできているのです。

  2019-お皿-解説

  • 考案国：ロシア
  • 正解
    • 「3回」
  • 説明
    • この問題では、3枚のお皿を移動する必要があります。大きな皿の4枚目を入れるには中くらいの皿を1枚動かす必要があり、そのためには小さな皿を1枚動かす必要があるからです。
      
  • 実際のコンピュータでは
    • 大きさの順に並んでいるデータの中に新しいデータを加えるときは、コンピュータもこの問題と同じようにデータを扱います。
    • コンピュータの処理は高速ですが、コンピュータが扱うデータの数が数億個のように多いときには、すべてのデータを1個ずつずらす処理はさすがのコンピュータでも時間がかかってしまいます。
    • そこでコンピュータ科学者は知恵を絞って効率のよい工夫を考えます。全部で100万枚のお皿がある場合でも、今回の問題のようにお皿の種類が3種類しかない場合には、たった3枚のお皿を動かすだけで新しいお皿を適切な場所に入れることができるのです。

  2019-二重駐車-解説

  • 考案国：ドイツ
  • 正解
    • 「Iの車」
  • 説明
    • Iの車を出すためには、Nの車を動かす必要があります。そのためには、左と右のどちらの方向にもOとMの車があるため、最初にOかMの車を動かしてから、次にNの車を動かす必要があります。
  • 実際のコンピュータでは
    • この問題を考えるときに、コンピュータはすべての車について、可能性をひとつひとつ調べていくかもしれません。このような「しらみつぶし」の調べ方はブルートフォース（総当り検索）と呼ばれます。
    • 車の効率のよい駐車方法は多くの研究が行われています。駐車中の車を自動的に最適な場所に移動させるシステムも研究されています。

（ベンジャミン問題に戻る）