福島県ジュニア数学オリンピック問題 初歩の情報数学に挑戦しよう

福島県ジュニア数学オリンピック

本稿では、2016年度(平成年度)に実施された福島県ジュニア数学オリンピックの問題のうち、これまで紹介してなかった問題を解説します。この問題は他の問題とはやや異なります。敢えて言えば情報処理の数学に近い問題です。

1.  はじめに

本稿で紹介する問題は平成28年度の問題のうち、これまで紹介してなかった最後の1問です。この問題は確率や情報数学に近い分野の問題です。

福島県ジュニア数学オリンピック問題 初歩の情報数学に挑戦しよう

数や計算、図形などとは異質の問題です。

2.1 問題文

下の図1のようなA,Bの2個のスイッチが付けられた宝箱があります。スイッチを1回押すと,「オン」から「オフ」へ,または「オフ」から「オン」へと必ず変わります。変わったことは,見た目や押した感じではわかりません。 2個のスイッチの状態は,次の1のように4通りです。A,B両方のスイッチの状態が「オン」になったときに宝箱のみだが開き,

それ以外の3通りの状態ではふたは開きません。

図1. 2個のスイッチがついた宝箱

表1.

スイッチA

スイッチB

説 明

オフ

オフ

ふたは開かない

オフ

オン

オン

オフ

オン

オン

ふたが開く

例えば,Aが「オン」,Bが「オフ」の状態のスイッチを,A→B→A→B→… の順でそれぞれ1回ずつ押していくと,下の図2の方法で,合計3回で宝箱のふたを開けることができます。

図2 Aが「オン」,Bが「オフ」のときのふたの開け方

次にA,B,Cの3個のスイッチが付けられた3のような宝箱のふたを開けることを考えます。今,宝箱のふたは閉まっており,スイッチの状態もどのようになっているかわかっていません。3個のスイッチの状態がすべて「オン」になると,宝箱のふたが開きます。このとき,次の設問1,設問2の各問いに答えなさい。

図3 3個のスイッチがついた宝箱

2.1.1 設問1の問題文

宝箱のふたが閉まっているとき,3個のスイッチの状態は,全部で何通りありますか,答えなさい。

2.1.2 設問2の問題文

宝箱のふたが閉まっているとき,スイッチをA→B→C→B→A→B→C→… の順にそれぞれ1回ずつ押していきます。次の各問いに答えなさい。

設問2の1の問題文

スイッチをA→B→C→B→Aの順にそれぞれ1回ずつ,スイッチを押した回数が合計5回のとき,宝箱のふたが開きました。はじめのスイッチの状態はどのようになっていましたか,下の例のように解答欄に示しなさい。

例 「A: オフ、B: オフ、C: オフ」

設問2の2の問題文

スイッチをA→B→C→B→A→…の順にそれぞれ1回ずつ押していきます。宝箱のふたが開くのに、スイッチを押した回数の合計が最も多いときは,合計何回ですか,答えなさい。また,このとき,はじめのスイッチの状態はどのようになっていましたか,上の<例>のように解答欄に示しなさい。

2.2.1 設問1の検討

宝箱のふたが閉まっている場合の3個のスイッチの状態の数を求めます。2にスイッチA、B、Cのすべての組み合わせを示します。ふたが閉まっているのは、3つのスイッチが共にオンの場合を除くすべての場合(7通り)です。

表2.

スイッチAスイッチBスイッチC宝箱の状態

オフ

オフ

オフ

開かない

オフ

オフ

オン

開かない

オフ

オン

オフ

開かない

オフ

オン

オン

開かない

オン

オフ

オフ

開かない

オン

オフ

オン

開かない

オン

オン

オフ

開かない

オン

オン

オン

開く

別解

全ての場合の数は23 = 8 です。

この数から箱が開く場合を引くと、残りは7通りとなります。

2.2.2 問題2.1の検討

  • A、B、C、B、Aの順にスイッチを押してふたが開いたのですから、スイッチAは2回、スイッチBは2回、スイッチCは1回だけおされています。
  • どのスイッチも2回押されるともとに戻るのですから、スイッチAとスイッチBは元の状態に戻っています。
  • スイッチCだけは反転した状態になっているのですから、元の状態は容易にわかります。すなわち、スイッチAはオン、スイッチBもオン、スイッチCはオフでした。
  • 最初のスイッチの状態は、「A: オン、B: オン、C: オフ」です。

2.2.3 問題2.2の検討

  • 本格的に問題に取り組むなら、この問題におけるスイッチの変化規則を把握しなければなりません。
    • ABCB ABCB ABCB ABCB ….と「ABCB」のサイクルを繰り返します。
    • Bはこのサイクルの途中で状態を反転させますが、サイクルの終わりで元の状態に復帰します。
    • Aはこのサイクルの最初に状態を反転させると、サイクルの終わりまでその状態に保持します。次のサイクルの最初で元の状態に復帰し、当該サイクルが終わるまでその状態を保ちます。すなわち、2サイクルを周期に変化を繰り返すのです。
    • Cはこのサイクルの最初に状態を反転させると、サイクルの終わりまでその状態に保持します。次のサイクルの最初で元の状態に復帰し、当該サイクルが終わるまでその状態を保ちます。すなわち、2サイクルを周期に変化を繰り返すのです。
  • 箱が空くのに最も多くのスイッチ操作が必要な場合を求めるには、スイッチAとスイッチCが最初の状態に復帰するのに2サイクルかかることを利用しなければなりません。
    • その場合とは、ABCB ABCの場合です。この操作でどのスイッチもオンになるための条件は、スイッチの初期設定時様態は、「A: オン、B: オフ、C: オン」でなければなりません。

2.2.4 設問2.2の別解1

スイッチの操作は、ABCB  ABCBと推移します。

  • 1回目のスイッチ操作Aをした場合の各スイッチの操作回数は1,0,0です。
    • Aのスイッチは反転しますが、BとCのスイッチは変化しません。
  • 2回目のスイッチ操作Bをした場合の各スイッチの操作回数は1,1,0です。
    • AとBのスイッチは反転しますが、Cのスイッチは変化しません。
  • 3回目のスイッチ操作Cをした場合の各スイッチの操作回数は1,1,1です。
    • A,B,Cのすべてのスイッチの状態が反転します。
  • 4回目のスイッチ操作Bをした場合の各スイッチの操作回数は1,2,1です。
    • AとCのスイッチは反転し、Bのスイッチは初期状態に復帰します。
  • 5回目のスイッチ操作Aをした場合の各スイッチの操作回数は2,2,1です。
    • AとBのスイッチは初期状態に復帰し、Cのスイッチは反転します。
  • 6回目のスイッチ操作Bをした場合の各スイッチの操作回数は2,3,1です。
    • Aのスイッチは初期状態に復帰し、BとCのスイッチは反転します。
  • 7回目のスイッチ操作Cをした場合の各スイッチの操作回数は2,3,2です。
    • AとCのスイッチは初期状態に復帰し、Bのスイッチは反転します。
  • 8回目のスイッチ操作Bをした場合の各スイッチの操作回数は2,4,2,です。
    • すべてのスイッチの操作回数が偶数なのですべてのスイッチは初期状態に復帰します。

7回目のスイッチ操作で玉手箱の蓋が開くためのスイッチの初期状態は、「A:オンもB:オフ、C:オン」でなければなりません。

2.2.5  設問2.2の別解2

  • 表3のような表を使って設問2を解くことを考えます。上段の各列はスイッチの初期設定値です。000から111まであります。
  • 左から順にA,B,Cのスイッチに対応しています。0はスイッチがオフ、1はスイッチがオンであることを示します。
  • 111は既に箱は開きますので問題の対象になりません。
  • 縦軸はスイッチの操作の順を表しています。操作したばかりのスイッチは赤字で示しています。

表3. 表を使った解法

   初期値

操作

000

001

010

011

100

101

110

111

A

100

101

110

111

000

001

010

0

AB

110

111

100

1

010

011

000

ABC

111

2

101

011

010

001

ABCB

3

111

001

000

011

ABCBA

4

101

100

111

ABCBAB111

110

5

ABCBABC

6

111

  • 初期値が101の場合はスイッチ操作がABCBABCの7工程で箱が開きます。

3. 問題の価値

  • 2回押すと元の状態に戻るスイッチがトグルスイッチ(Toggle Switch)です。
  • 2進数の1桁も似たような性質があります。以下に0から15までの整数の2進数表示を挙げます。

表4

10進数2進数10進数2進数

0

0000

8

1000

1

0001

9

1001

2

0010

10

1010

3

0011

11

1011

4

0100

12

1100

5

0101

13

1101

6

0110

14

1110

7

0111

15

1111
  • 情報処理の世界では、複雑な処理の工程を何桁かの2進数で表示し、「その値がいくらの時は何を処理する」というルールを決めてききプログラムをつくります。本稿の問題は3桁の2進数が111の時にふたを開かせる仕組みだったのです。

4. まとめ

高校や大学の数学になると、虚数、複素数、行列、微積分、微分方程式など扱う対象が広がると共に、問題の捉え方や扱い方、計算技法などが多彩になります。小学校高学年の算数や中学課程の数学ではそれらが使えないので、素朴な方法で立ち向かわねばなりません。大学生でも社会人でも考える訓練になります。

本稿では、希望者だけが受験する福島県教育委員会主催の数学ジュニアオリンピック問題から、數や計算、方程式、図形などの問題とは異質の情報数学の分野の問題を紹介しました。

コメント

タイトルとURLをコピーしました