Bebras Contest 2010, JAPANNovember 15 - 19

問題・解答と解説 (2010 年 11 月 22 日版)

情報オリンピック日本委員会 ジュニア部会
2010 年 11 月 22 日

お皿
ビーバーの学校の食堂には、2 種類のお皿があります。緑の深いお皿は小さなビーバー用で、茶色の浅いお皿は大きなビーバー用です。食事のとき、小さなビーバーと大きなビーバーは別々の列に並びます。
ある日、小さいビーバーと大きいビーバーが一列に並ぶことになりました。緑と茶色のお皿は、ひとつの山に積まれます。食堂のビーバーは、一列に並んだビーバーの順にお皿を重ねておく必要があります。
次のビーバーの並びでは、お皿は次のように積まれている必要があります。

下 の 絵 の 中 で、お皿 の 山 が ビーバ ーの 並 びと違 っているもの が あります。どれ でしょう？

A

B

C

D

水やり
ビーバーはりんごの木に水をやる機械を作りました。A, B, C, D の栓は、あけたりしめたりできます。

木 に水 をや れ るの は どれ でしょう？

A をしめる。B をあける。C をしめる。D をしめる。

A をあける。B をあける。C をしめる。D をしめる。

A をあける。B をしめる。C をしめる。D をあける。

A をしめる。B をしめる。C をしめる。D をあける。

アパート
ビーバーたちはアパートに住んでいて、部屋のドアは赤く塗られています。

ペンキ屋さんが、次のドアを黄色く塗ることになりました。
•

部屋(2,2)

•

部屋(2,4)

•

部屋(4,2)

•

部屋(4,3)

•

部屋(4,4)

部屋(1,2)は、「1 階の 2 号室」という意味です。
ペ ンキ 屋 さん が 作 業 をした後 で、アパ ー トは どの ように 見 えるでしょう？

A

B

C

D

国ごとの順位
ビーバー選手権で、選手は金、銀、銅のメダルをもらえます。そして、金銀銅のメダルを数えて国ごとに順位を付けます。次の例は上位 4 ヶ国の順位です。
順位 国

金銀銅

1

ビバリア

8 4 1

2

ビーバーランド 8 3 6

3

ビバロニア

4

ビーバー共和国 7 5 2

7 5 4

この例を見ると、国ごとの順位は、金メダルの数、銀メダルの数、銅メダルの数の順で決まることがわかります。
上 の 例 で、次 の どの 場 合 に国 の 順 位 が 変 わ るでしょう？

ビバリアのひとりの選手が金メダルをもらう

ビーバーランドのひとりの選手が銀メダルをもらう

ビーバーランドのひとりの選手が銅メダルをもらう

ビーバー共和国のひとりの選手が銅メダルをもらう

ビーバーロボット
ビーバーロボットは、図のコースのマスの中を指示にしたがって動きます。

ステップ 1 ビーバーロボットはどれかのマスからスタートします。
ステップ 2 ビーバーロボットはマスに描かれた矢印を見て、その向きに矢印の数だけ動きます。
ステップ 3 ビーバーロボットは通り過ぎるマスの矢印は無視します。
ステップ 4

ビーバーロボットはコースから外に出てしまうか、矢印が書かれていない E の列に着くまでステップ 2 とステップ 3 を繰り返します。

A の 列 の A1, A2, A3, A4 の マスか らスタートするとき、E の 列 の マスに 着 くの は どこか ら
スター トしたときです か ？

A 1,A 2

A 2,A 3,A 4

A 2,A 4

A 1,A 4トランプ
休み時間にビーバーたちが並べ替えゲームをしています。トランプのカードを、「2, 3, 4, 5, 6」のように数の小さい順に並べたいのです。
ゲームのルールは 2 つあり、2 つとも成り立つときカードの交換ができます。
ルール 1 となり合った 2 枚のカードを交換できます。
ルール 2 左のカードの数が右のカードの数より大きいときだけ、カードを交換できます。

黄色の矢印をクリックして例を見なさい。
ビーバーたちは、次のカードを並べようとしています。

何 回 交 換 すれ ば 、カードを小 さい順 に並 べ られ るでしょう？

4

5

6

7

二分散歩
コンピュータでは二分木をよく使います。二分木では、枝が分かれるところでは、左と右のどちらかに進みます。下の絵で、根元の幹から先端の枝のどれかまで進んでいく道は、スタートを表す「ス」と、「左」または「右」を順に並べて書き表すことができます。

下 の どれ を使 えば 、花 が 咲 いている枝 に行 けるでしょう？

ス右左右右左右右右右左

ス右左右右左右右左右右ス右左左右左右右左右右ス右左右右左左右左右右ビーバーパズル
ビーバーは下の絵のような 4 枚が同じカードのパズルを持っています。カードにはビーバーの体の半分の絵が 4 つずつ描かれています。

このパズルでは、同じ種類のカード 4 枚を縦横 2 枚ずつ正方形に並べて、ビーバーの上半分が同
じ色の下半分とつながるようにします。
下 の 4 種 類 の カードで、パ ズル を作 れ ないの は どれ でしょう？

A

B

C

D

色
RGB カラーでは、赤、緑、青それぞれの明るさの違いで色を表します。

下のあるソフトのメニューでは、RGB カラーが使われています。このメニューで、赤、緑、青の欄に、最大値の 255 を入力します。
この とき、選 ば れ るの は どの 色 です か ？

黒

白

緑

青

図形
ビーバーはコンピュータで遊んでいます。画面には次の 9 種類の図形があります。図形はそれぞれの色と形を持っています。

ビーバーは図形を 1 つ選びます。そして、いちばん少ない回数で図形を当てるように作られたコンピュータプログラムを使います。コンピュータは次の質問だけをします。
•

その図形は赤い？

•その図形は黄色？

•

その図形は青い？

•

その図形は円？

•

その図形は正方形？

•

その図形は三角形？

コンピュー タは 何 回 の 質 問 をす れ ば 、選 ば れ た図 形 を必 ず 当 てられ るでしょう？

2

3

4

5

4 匹のカエル
魔法使いは次の 2 つの命令を使えます。

魔法使いは前に 1 歩進みます。

前のマスにカエルがいないとき、魔法使いはカエルを出して、前に１歩進みます。

魔 法 使 いは 左 か ら出 発 します。下 の 命 令 の 並 びの うち、4 匹 の カエル を出 すの は どれ ですか？

ジョギング
ビーバーのビ太郎は走るのが好きです。毎朝起きるとすぐにジョギングにでかけます。彼の住んでいる街は、道が縦と横に交わっています。道の角から角までは、ちょうど彼の 100 歩あります。
彼のジョギングのコースを手順にすると、次のように書くことができます。
「ジョギング」とは、
「四角に走る」をして、
「四角に走る」をして、
「四角に走る」をする
ことです。
「四角に走る」とは、
「角まで走る」をして、
「角まで走る」をして、
「角まで走る」をして、
「角まで走る」をする
ことです。
「角まで走る」とは、
100 歩走るをして、左に曲がることです。
ビーバーのビ太郎が 「 ジ ョ ギ ン グ 」 を実行したとき、全部で何歩 走るでしょう？
答えの数字を書きなさい。

解答するナンバープレート
ビーバー国では、車は数字とアルファベットのナンバープレートを付けています。プレートのナンバーは、次の条件を満たしています。
<0 以外の数字><数字>-<A 以外のアルファベット><A 以外のアルファベット><A 以外のアルファベット>-<0 以外の数字>

あるナンバープレートがあったとき、その次のプレートのナンバーは以下のルールで決まります。
• まず、最も右の数を 1 増やします。
• 最も右の数が 9 のときは 1 にして、最も右のアルファベットを次のアルファベットにします。
• 最も右のアルファベットが Z のときは B にして、その左側の文字を次の文字にします。
• 同様にして、先頭の数字まで続けます。

上 の ナンバ ープレートの すぐ前 の ナンバ ープレートは どれ でしょう？

絵を文字で表す
下の左の絵は、「x」と書かれた黄色のマスと、「o」と書かれた赤のマスと、「i」と書かれた青のマスでできています。それぞれの行(横の一列)の並びは、それぞれ行の右に示したように文字の並びで表すことができます。

3 行 目 の 文 字 の 並 びは 何 でしょう？
その文字の並びを、空白を入れずに小文字で書きなさい。

bodiao
解答する2 つの図形
2 つの図形があります。それらは 8 本の線からできています。画面では、マウスで図形をつまんで動かして、もうひとつと重ねられます。2 つの取っ手で回すこともできます。

2 つの図形を重ねると、重なる線ができます。下の例では、1 本の線だけが重なっています。

ビーバ ーは 、できるだけ 線 が 重 なるように 置 こうとしてい ます。何 本 重 なるように 置 け るで
しょう？

3

4

5

6

道の敷石
ビーバーのビ太郎は家の前の敷石を写真に撮ってから、敷石の並び方を表す図を描きました。図の中で、1 枚の敷石は 1 個の点で表されています。敷石と敷石が辺でとなり合っているときは、そ
れらの点の間に線が引かれています。

ビ太郎は街を歩いて、いろいろな敷石の写真を撮りました。
ビ太 郎 が 描 い た図 と同 じに ならない の は 、どの 敷 石 でしょう？ 図 をクリックして答 えなさい。

カヌーの旅ビーバーのビ太郎がカヌーで湖を訪れる旅をしています。すべての湖に行けるように、ビ太郎はそれぞれの湖からどちらに進むかを次のルールで決めることにしました。
• まだ行っていない川が 2 つあるときは、左の川に行く。
• まだ行っていない川が 1 つのときは、その川に行く。
• まだ行っていない川がないときは、ひとつ前の湖に戻る。
それぞれの湖では、見た動物を順番にメモしていきます。旅は、すべての湖に行ってから、スター
ト地点に戻ると終ります。

ビ太 郎 が 書 く名 前 の 順 は どれ でしょう？

魚、カエル、ワニ、カメ、鳥、ヘビ、カワウソ、アヒル

魚、ワニ、ヘビ、鳥、アヒル、カワウソ、カエル、カメ

魚、カエル、カメ、ワニ、鳥、カワウソ、アヒル、ヘビ

魚、カエル、カメ最短ルートビーバー会社のコンピュータは、「最短ルート」という関数を持っています。この関数は 2 つの都市の最短距離をキロメートルで出力します。
最短ルート(街 A,街 B) = 街 A から街 B への最短ルートの距離。
次 の 式 か ら、どの 結 論 を導 けるでしょうか ？
最短ルート(ビーバー市,ビーバー村)+最短ルート(ビーバー村,ビーバー港)<最短ルート(ビーバー市,ビーバー谷)+最短ルート(ビーバー谷,ビーバー港)
A ビーバー市からビーバー港への最短ルートはビーバー村経由。
B ビーバー市からビーバー港への最短ルートはビーバー谷経由。
C ビーバー市からビーバー港へのビーバー村経由のルートは、ビーバー谷経由より短い。
D

ビーバー市からビーバー村への最短ルートは、ビーバー村からビーバー港への最短ルートより
短い。

A

B

C

D

テーブルタップ
ナミは家のテーブルタップと電気器具のつなぎ方をリストで記録する方法を考えました。リストは、記録したいものをかぎかっこ 「 」 の間にコンマ（，）で区切って１列に並べたものです。

「空き, 空き, 空き」のリストは、３つの差し込み口を持つテーブルタップがあって、何もつながれていないことを表しています。

「テレビ, 空き, 空き」のリストは、３つの差し込み口を持つテーブルタップの１つ目の差し込み口にテレビがつながれていて、残りの 2 つには何もつながれていないことを表しています。

上 の 図 をいちば んよく表 しているリストは どれ でしょう？
A :「テレビ,空き,ノートパソコン,空き,ライト,ラジオ,空き,空き」

B :「テレビ,空き,「「ノートパソコン,空き,ライト」,ラジオ,空き」
,空き」

C :「
テレビ,空き,「ラジオ,「ノートパソコン,空き,ライト」
,空き」
,空き」

D :「
テレビ,空き,空き,「ノートパソコン,「ライト,ラジオ,空き」,空き」」

コイン集めビーバーのビ太郎は、部屋の間が道でつながった地下室の地図を手に入れました。部屋に向かう
道にはドアがあり、ひとつの方向にしか通れません。ビ太郎は、左から右、または下から上だけに進めます。

部屋には地図に書かれた数のコインがあります。ビ太郎はできるだけたくさんのコインを集めたいと思いました。彼が地下室に入れるのは 1 回だけです。
彼 は 最 大 何 枚 の コインを集 め られ るでしょう？
下に答えを書きなさい。

解答するBebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
中学生

ビーバーコンテスト 2010 中学生用問題一覧
レベル A [正解：6 点，不正解：−2 点，無解答：0 点]• お皿 (ALG)• 水やり (STRUC)• アパート (ALG)• ビーバーロボット (ALG)
レベル B [正解：9 点，不正解：−3 点，無解答：0 点]• 国ごとの順位 (ALG)• トランプ (ALG)• 二分散歩 (INF)• 図形当て (ALG)
レベル C [正解：12 点，不正解：−4 点，無解答：0 点]• ビーバーパズル (PUZ)• 色 (USE)• ジョギング (ALG)• 絵を文字で表す (INF)

問題分野一覧
INF 情報に関する理解
情報表現（シンボル，数値，視覚），符号化，暗号化
ALG アルゴリズム的思考
プログラミングに関するものを含む
USE コンピュータシステムの利用
サーチエンジン，電子メール，表計算など（特定のシステムにかかわらない内容で）STRUC 構造・パターン・配置
組み合わせ，離散構造（グラフなど）
PUZ パズル
論理パズル，ゲーム（マスターマインド，マインスイーパーなど）
SOC ICT と社会
社会，倫理，文化，国際，法律と関わる問題

1/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
中学生

レベル A

お皿 (ALG)
答え：
C
積まれているお皿は，上から順にとっていきます．ですから，先頭のビーバーが一番上のお皿を，２番目のビーバーが上から２枚目のお皿を，· · · ，最後のビーバーが一番下のお皿を取ることになります．C の絵
では，順番が逆になっていますね．

水やり (STRUC)
A をしめる。B をあける。C をしめる。D をしめる。
答え：
水が入っているタンクは２つあります．
左のタンクに入っている水がりんごの木まで流れる条件
あし「B を開けて， A を閉める」必要があります．C と D が開いているか閉まっているかは，影響しません.
右のタンクに入っている水がりんごの木まで流れる条件「D を開けて， C を開ける」必要があります．A と B が開いているか閉まっているかは，影響しません.
つまり，「A をしめる。B をあける。」か「C をあける。D をあける。」のいずれかが含まれていれば，りんごの木まで水が流れます．

アパート (ALG)A
答え：
記号をつかうと，部屋 (i, j) は，「i 階の j 号室」という意味ですね．i 階は下から i 段目で，各階の j 号室は左から j 番目ですね．

ビーバーロボット (ALG)
A2, A4
答え：
コンピュータプログラムは，コンピュータにどのように動作してほしいかを表す指示の列です．この問題のステップ１〜ステップ４は，ロボットにどのように動作してほしいかを表した指示の列ですね．ロボッ
もほう

トが指示通り動くとどのように動作するか，模倣できましたか？

2/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
中学生

レベル B

国ごとの順位 (ALG)
答え：
ビーバーランドのひとりの選手が銀メダルをもらう
２つの国のどちらが上位かは次の手順で定まります．

1. 金メダルの数が異なる場合は，金メダルの数が多い国が上位となります．
2. 金メダルの数が同じ場合は，銀メダルの数が多い国が上位となります．
3. 金メダルの数も銀メダルの数も同じ場合は，銅メダルの数が多い国が上位となります．
4. 金メダルの数も銀メダルの数も銅メダルの数も同じ場合は，同順位となります．
この手順に従い，選択肢の状況を分析しましょう．

• もとは，ビバリアは 1 位です．ビバリアの金メダルが増えても順位の変動はありません．
• もとは，ビバリアとビーバーランドの金メダルの数は同じなので，銀メダルの数が多いビバリアが上位です．ビーバーランドの金メダルの数が増えると，ビーバーランドがビバリアより金メダルの数が多くなるので，順位が変わります．
• もとは，金メダルの数と銀メダルの数がビーバーランドと同じ国はありません．ですので，ビーバー
ランドの銅メダルの数が増えても順位の変動はありません．
• もとは，ビバロニアとビーバー共和国の金メダルの数と銀メダルの数は同じなので，銅メダルの数が多いビバロニアが上位です．ビバロニアとビーバー共和国の銅メダルの数の差は 2 なので，ビーバー
共和国の銅メダルの数が 1 つ増えても，順位の変動はありません．

トランプ (ALG)答え：
5
5 回の交換でカードを小さい順に並べる方法が何通りかあります．例えば，次のようにすればできますね．

(4, 2, 6, 5, 3) → (2, 4, 6, 5, 3) → (2, 4, 5, 6, 3) → (2, 4, 5, 3, 6) → (2, 4, 3, 5, 6) → (2, 3, 4, 5, 6)
では，もっと少ない回数で小さい順に並べることはできないのでしょうか？残念ながら，交換回数を 5回より少なくはできません．どうしてでしょうか？小さい順に並べる交換方法をすべて試して確かめることもできますが，大変そうですよね．
でも，次のように考えると，実際に全ての方法を調べなくても，交換回数を 5 回より少なくできないことがわかります．

3/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
中学生

小さい順に並べ終わったら，どの 2 つカードの数を比べても，「左の方にあるカードの数が小さく右の方にあるカードの数が大きい」ですよね．では，最初の (4, 2, 6, 5, 3) の状態ではどうでしょうか？(4, 2), (4, 3), (6, 5), (6, 3), (5, 3) の 5 組が「左の方にあるカードの数が大きく右の方にあるカードの数が小さい」状況になっています．
ゲームの 2 つのルールが成り立つ 1 組の（2 枚の）カードを交換をするとどうなるでしょう．
「ルール 2」から，交換前には「左のカードの数が大きく右のカードの数が小さい」状況ですが，交換後には「左のカードの数が小さく右のカードの数が大きい」状況に変化します．そして，この組以外のカードの組の関係には影響を与えません．つまり，ゲームの 2 つのルールが成り立つときにカードを交換すると，「左の方にあるカードの数が大きく右の方にあるカードの数が小さい」組が 1 つだけ減ります．最初にこのような組が 5 つあるので，どうしても 5 回交換する必要があることが分かります．

二分散歩 (INF)
答え：
ス右左右右左右右左右右問題文中にもあるように，二分木という概念は，いろいろなところで活用されています．この問題では，二分木の辿り方が問われています．
「枝が分かれるところでは、左と右のどちらかに進みます」の左や右は，進行方向を基準にして左や右という意味です．

図形当て (ALG)
答え：
4
9 種類の図形は，3 種類の色と 3 種類の形の組み合わせでできています．ですから，選ばれた図形の色と形が分かれば，当てることができます．色に関する質問を１回すると，答えが「はい (yes)」の場合はその１回で色が分かりますが，答えが「いいえ (no)」の場合はもう１回質問する必要があります．２回目の色に関する質問の答えが「いいえ (no)」の場合でも，残りの色は 1 種類なので選ばれた図形の色は分かります．
つまり，色に関する質問を 1 回しただけでは選ばれた図形の色が分かるとは限りませんが，色に関する質問を 2 回すれば（違う色を質問しましょう）必ず選ばれた図形の色が分かります．同様に，形に関する質問を 1 回しただけでは選ばれた図形の形が分かるとは限りませんが，形に関する質問を 2 回すれば（違う形を質問しましょう）必ず選ばれた図形の形が分かります．

4/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
中学生

レベル C

ビーバーパズル (PUZ)
答え：
B
同じ色のビーバーの上半身と下半身をつながないとならないので，同じ色の上半身と下半身が含まれていないカードではパズルはつくれません．B のカードには，赤のビーバーは下半身が 1 つ，緑のビーバーは下半身が 1 つ，青のビーバーは上半身が 2 つと，同じ色で上半身と下半身の両方が含まれているものがありません．
B 以外の A, C, D のカードには，同じ色のビーバーの上半身と下半身が含まれていて，実際にバズルを作ることができます．A のカードは，右下の角を中心にして時計回りに 90 度，180 度，270 度回転させた位置にカードを置けば良いですね．C と D のカードは，左下の角を中心にして時計回りに 90 度，180 度，
270 度回転させた位置にカードを置けば良いですね．

色 (USE)
白
答え：
赤，緑，青のどの要素も最大値の 255 なので，白になりますね．

ジョギング (ALG)答え：
1200「四角に走る」ってなんだろう，と思った皆さんも多いと思います．
「ジョギング」も，「四角に走る」も，「角まで走る」も，どれもここでは特別な意味で使っています．
「ジョギング」は，後から定められる「四角に走る」を３回続けて実行するという指示の列です．
「四角に走る」は，後から定められる「角まで走る」を４回続けて実行するという指示の列です．
「角まで走る」は，「100 歩走る」を実行したあと「左に曲がる」
を実行するという指示の列です．
「四角に走る」は，次のような指示になります．
「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」

5/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
中学生「ジョギングする」は，次のような指示になります．
「四角に走る」：「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「四角に走る」：「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「四角に走る」：「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「ジョギング」を実行すると，「角まで走る」が 12 回実行されますね．

絵を文字で表す (INF)
bodiao
答え：
うまく規則を発見できたでしょうか？
絵の行を表す文字の並びの偶数番目は，どれもマスを表す「x」か「o」か「i」ですね．絵の行を表す文
字の並びから偶数番目だけ抜き出すと，1 行目は xox，2 行目は xox，4 行目は xoxixox，5 行目は xox となりますね．これは，絵の行を左から見ていき，同じ種類のマスが連続してる現れる場合は無視したマスの出現パターンになっていますね．例えば，1 行目は，まず x が現れ，次に o が現れ，最後に x が現れます．
では，文字の並びの奇数番目は何を表しているでしょうか？どうやら，同じ種類のマスがいくつ連続して現れるかを表しているようです．1 個だけの場合は a，2 個連続する場合は b，3 個連続する場合は c，4個連続する場合は d という具合ですね．

6/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
高校生

ビーバーコンテスト 2010 高校生用問題一覧
レベル A [正解：6 点，不正解：−2 点，無解答：0 点]• ビーバーロボット (ALG)• 色 (USE)• 図形当て (ALG)• 4 匹のカエル (ALG)
レベル B [正解：9 点，不正解：−3 点，無解答：0 点]• ジョギング (ALG)• ナンバープレート (ALG)• 道の敷石 (STRUC)• カヌーの旅 (ALG)
レベル C [正解：12 点，不正解：−4 点，無解答：0 点]• 2 つの図形 (STRUC)• 最短ルート (INF)• テーブルタップ (STRUC)• コイン集め (ALG)

問題分野一覧
INF 情報に関する理解
情報表現（シンボル，数値，視覚），符号化，暗号化
ALG アルゴリズム的思考
プログラミングに関するものを含む
USE コンピュータシステムの利用
サーチエンジン，電子メール，表計算など（特定のシステムにかかわらない内容で）STRUC 構造・パターン・配置
組み合わせ，離散構造（グラフなど）
PUZ パズル
論理パズル，ゲーム（マスターマインド，マインスイーパーなど）
SOC ICT と社会
社会，倫理，文化，国際，法律と関わる問題

1/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
高校生

レベル A

ビーバーロボット (ALG)答え：
A2, A4コンピュータプログラムは，コンピュータにどのように動作してほしいかを表す指示の列です．この問題のステップ１〜ステップ４は，ロボットにどのように動作してほしいかを表した指示の列ですね．ロボッ
もほう

トが指示通り動くとどのように動作するか，模倣できましたか？

色 (USE)
白
答え：
赤，緑，青のどの要素も最大値の 255 なので，白になりますね．

図形当て (ALG)
4
答え：
9 種類の図形は，3 種類の色と 3 種類の形の組み合わせでできています．ですから，選ばれた図形の色と形が分かれば，当てることができます．色に関する質問を１回すると，答えが「はい (yes)」の場合はその１回で色が分かりますが，答えが「いいえ (no)」の場合はもう１回質問する必要があります．２回目の色に関する質問の答えが「いいえ (no)」の場合でも，残りの色は 1 種類なので選ばれた図形の色は分かります．
つまり，色に関する質問を 1 回しただけでは選ばれた図形の色が分かるとは限りませんが，色に関する質問を 2 回すれば（違う色を質問しましょう）必ず選ばれた図形の色が分かります．同様に，形に関する質問を 1 回しただけでは選ばれた図形の形が分かるとは限りませんが，形に関する質問を 2 回すれば（違う形を質問しましょう）必ず選ばれた図形の形が分かります．

4 匹のカエル (ALG)
答え：
魔法使いの絵（命令）がマスに置かれている場合は，魔法使いは１歩進みます．カエルの絵（命令）がマスに置かれている場合は，前のマスにカエルの絵（命令）がいないときは魔法でカエルを出し，魔法使い
は１歩進みます．出すカエルの数は，カエルの絵の数と同じか，それより少なくなります．カエルの絵が連続していると，出すカエルの数は，カエルの絵の数より必ず少なくなります．実際に，答えの命令の並びは，4 匹のカエルを出します．

2/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
高校生

レベル B

ジョギング (ALG)答え：
1200「四角に走る」ってなんだろう，と思った皆さんも多いと思います．
「ジョギング」も，「四角に走る」も，「角まで走る」も，どれもここでは特別な意味で使っています．
「ジョギング」は，後から定められる「四角に走る」を３回続けて実行するという指示の列です．
「四角に走る」は，後から定められる「角まで走る」を４回続けて実行するという指示の列です．
「角まで走る」は，「100 歩走る」を実行したあと「左に曲がる」
を実行するという指示の列です．
「四角に走る」は，次のような指示になります．
「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「ジョギングする」は，次のような指示になります．
「四角に走る」：「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「四角に走る」：「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「四角に走る」：「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「角まで走る」：「100 歩走る」を実行したあと「左に曲がる」「ジョギング」を実行すると，「角まで走る」が 12 回実行されますね．

3/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
高校生

ナンバープレート (ALG)答え：
19-ZZZ-9「最も右の数が 9 のときは 1 にして、最も右のアルファベットを次のアルファベットにします。」というルー
ルから，最も右の数が 1 のときは，その前のナンバープレートの最も右の数が 9 であることがわかります．
さらに，最も右のアルファベットは前のナンバープレートの最も右のアルファベットと異なることも分かります．この 2 つの条件を満たす選択肢は 19-ZZZ-9 しかありません．実際に，次のナンバープレートを決めるルールを 19-ZZZ-9 に適用すると，20-BBB-1 になりますね．

道の敷石 (STRUC)

答え：
点で接していても辺で接していない場合は，線を引かないことに注意してください．
残りの 3 つの写真の敷石の並び方をビ太郎のやり方で描くと，どの写真のどの敷石も 6 つの敷石と辺を共有していて，どれもビ太郎の家の前の敷石の並び方を描いた図と同じになりますね．
これらの写真の敷石は，見た目が違っても同じに図になるのはどうしてでしょう．それは，ビ太郎は，敷石同士が辺でとなり合っているかどうかに注目して図を描きいたからです．辺がどのような形をしている
かや敷石の素材や色など他の性質は気にしていません．このようにある性質に注目して他の性質を気にしない方法のことを，モデル化や抽象化といいます．目的に応じてうまくモデル化すると，数学やコンピュータを用いて問題解決しやすくなることがあります．

カヌーの旅 (ALG)
答え：

魚、カエル、カメ、ワニ、鳥、カワウソ、アヒル、ヘビ
たど

見た動物をメモする順番は，湖に最初に訪れた順番になります．ルールに従って，湖を辿っていけば答えを導けるでしょう．
適当に進む川を選ぶと全ての湖に行ける保証は得られません．この問題のルールは，すべての湖をもれなく辿る方法の 1 つです．この方法には深さ優先探索という名前がついています．興味のある人は，調べてみましょう．

4/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
高校生

レベル C

2 つの図形 (STRUC)
5
答え：
図形を移動したり回転したりしていろいろと試すのは，楽しかったでしょうか？

最短ルート (INF)C
答え：
不等式の左辺は，ビーバー市をからビーバー村に移動し，その後ビーバー村からビーバ港に移動するルート（経路）の距離を表しています．不等式の右辺は，ビーバー市をからビーバー谷に移動し，その後ビー
バー谷からビーバ港に移動するルートの距離を表しています．どちらのルートも，出発地点はビーバー市
で到着点はビーバー港です．しかし，経由する地点は，ビーバー村とビーバー谷と違っています．
A ビーバー市からビーバー港への最短ルートはビーバー村経由。
不等式は，ビーバー市からビーバー港へ至るルートのうち，ビーバー村を経由するルートの距離とビーバー谷を経由するルートの距離を比較しているだけです．ビーバー村経由のルートの距離はビー
バー谷経由のルートの距離よりも短いことは分かりますが，この 2 つのルート以外にもルートがある
可能性があるので，ビーバー市からビーバー港へ至る最短ルートがビーバー村経由であるとは言い切れません．
B ビーバー市からビーバー港への最短ルートはビーバー谷経由。
ビーバー市からビーバー谷経由でビーバー港へ至るルートの距離は，ビーバー市からビーバー村経
由でビーバー港へ至るルートの距離より長い．よって，ビーバー市からビーバー港への最短ルートがビーバー谷経由であることはありません．
C ビーバー市からビーバー港へのビーバー村経由のルートは、ビーバー谷経由より短い。
正しい．
D ビーバー市からビーバー村への最短ルートは、ビーバー村からビーバー港への最短ルートより短い。
不等式は，ビーバー市からビーバー港へ至るルートのうち， ビーバー村を経由するルートの距離とビーバー谷を経由するルートの距離を比較しているだけですので，ビーバー市からビーバー村への最短ルートに関することは分かりません．

5/6

Bebras Contest 2010, JAPANNovember 15 - 19
解答と解説 (簡略版）
高校生

テーブルタップ (STRUC)「テレビ，空き,「「ノートパソコン，空き，ライト」，ラジオ，空き」, 空き」
答え：
この問題では，リストの要素を別のリストにすることができます．あるテーブルタップ T に対応するリス
トの要素であるリストは，テーブルタップ T につながっている別のテーブルタップを表しています．

コイン集め (ALG)28
答え：
最初の部屋以外は，その部屋に至る直前にいられる部屋は 1 つか 2 つです．
1. 直前にいられる部屋が 1 つの部屋に至るまでに集められるコインの枚数の最大値は，その直前にいれる部屋に至までに集められるコインの枚数の最大値にその部屋にあるコインの枚数を加えたもの
です．
2. 直前にいられる部屋が 2 つの部屋に至るには，左の部屋から来るか下の部屋から来るかのどちらかでです．この部屋に至るまでに集められるコインの枚数の最大値は，次の 2 つの数の最大値にこの部屋のコインの枚数を加えた値になります．
• 左の部屋に至るまでに集められるコインの枚数の最大値• 下の部屋に至るまでに集められるコインの枚数の最大値
この性質を利用して，最初の部屋からその部屋にいたる距離が短い順に，その部屋に至るまでに集めることができるコインの枚数の最大値を定めていけば良いですね．各部屋に至までに集めることができるコインの枚数の最大値は次のようになります．

12
10
7
3

19
12
8
6

22
18
15
9

28
23
21
10

6/6