・一列の電球                        DD++ 氏

 nとmは、 n≧m≧2 を満たす自然数とします。電球が一定の間隔でn個並んでいて、最初
は各々デタラメに点灯していたり消灯していたりします。それぞれの電球にはスイッチがつい
ていて、1回押すごとに点灯と消灯が切り替わります。

 これらの電球のうち等間隔(隣接するものを選んでも何個かおきでもよい)にm個の電球を
選びそれらのスイッチを押すというのを繰り返して、全ての電球を消灯することを考えます。

 例えば、n=5、m=3、最初の状態が順に 消点消消点 だった場合、

  「1、2、3番目」 、「1、3、5番目」

の順に操作すれば、全ての電球を消灯できます。

 もちろん、「2、3、4番目」 、「3、4、5番目」の順でも全ての電球を消灯できます。

 これについて、以下を考えてください。

(1) mが偶数の場合、任意のnに対して、何度操作しても全ての電球を消灯できない初期状
  態がありえることを証明してください。

(2) m=3の場合、n≧8であれば、どんな初期状態からでも全ての電球を消灯できることを
  証明してください。

  また、n=7の場合に、何度操作しても全ての電球を消灯できない初期状態の一例を示
 してください。

(3) m=5の場合、n≧24であれば、どんな初期状態からでも全ての電球を消灯できること
  を証明してください。

  また、n=23の場合に、何度操作しても全ての電球を消灯できない初期状態の一例を
 示してください。

(4) m=7の場合、どんな初期状態からでも全ての電球を消灯できるようなnの最小値は?

(5) 同じく、m=9の場合は?

(6) m=11、13は飛ばして、m=15の場合は?


 GAI さんからのコメントです。(平成29年5月3日付け)

 (2)の後半は、とりあえず [0,1,0,0,0,0,0] 、[0,0,1,0,0,0,0] 及びこの逆並び(1:点灯部)


 らすかるさんからのコメントです。(平成29年5月4日付け)

 (2)の後半の一般解は、

  「2番目、3番目、5番目、6番目の4つのうちの点灯個数が奇数」

ですね。


(コメント) DD++さんの問題を見て、次の問題と同じ匂いを感じました。

 20枚のトランプが裏になり一列に並べてある。このとき、以下の操作を適当に繰り返す。

(操作) 裏向きのカードを適当に1枚選び裏返す。すぐ右隣のカードも(あれば)裏返す。

 すると、どのようにカードを選んでも、有限回の操作の後にカードはすべて表になることを
示せ。

 この問題は、映画「僕と世界の方程式」の公開に先立ち開かれたイベント

  音と数字で奏でるメロディ♪ 「僕と世界の方程式」 試写会
  (平成29年1月20日 講談社リケジョ主催 JST&日本数学オリンピック財団後援)

で、音楽家の中島さち子さん(数学オリンピック 金メダリスト)から出題されたものである。

 同様の問題として、

 1からnまでの数字の書かれたn枚のトランプをシャッフルし、一番上の数がaならば上から
1番目からa番目までの順番をひっくり返すという操作を繰り返す。すると、必ず有限回の操
作の後に、1が一番上に来て操作が終了することを示せ。
(出典:「ピーター・フランクルの中学生でもわかる大学生にも解けない数学問題集 代数編」
                                              (日本評論社))

 2つとも2進法という概念が解決への糸口で、シンプルな証明が可能らしいです。DD++さん
の問題も2進法が関係するのかな?


 DD++さんからのコメントです。(平成29年5月4日付け)

 他にも、2015年度京大特色入試の3番なんかも近いものがあります。この手の問題は、バ
リエーション豊富なので、探せばいくらでも出てくるかと。

 中島さんの問題は、裏向きを1、表向きを0として全体を二進法で読めば、1回の作業ごと
に、より小さい整数になるので、2^n-1 回以内に値が0すなわち全て表になります。

 もっとも、この問題の場合は右からk枚目が裏ならk点を加算としてやれば n((n+1)/2 回以
内というよりよい結果が得られるので、二進法が本質かといえば、どうでしょうね。

 ピーター氏の問題は、k と書かれたカードが上から k 枚目以外にあれば 2^k 点加算、と
すれば、一番上が1ではない任意の状態から1回の操作で点数が減少するので、同じ状態
に戻ることはなく、また状態は有限通りなので、いずれ一番上に1がある状態に到達する、
でいいと思います。

 私のは、2進法よりも剰余が役に立つ系ですね。


 りらひいさんからのコメントです。(平成29年5月4日付け)

 とりあえず、ごく一部分だけ力技でやったので、できた範囲だけ書き込んでみようと思いま
す。残る部分はまだ考え中です。

(1) mが偶数の場合、任意のnに対して、何度操作しても全ての電球を消灯できない初期状
  態がありえることを証明してください。


 1回スイッチを押したときに点灯している電球の個数がどう変化するかを考えると、mが偶
数の場合は、点灯している電球の個数が偶数個変わる。

 すなわち、最初に点灯している電球の数が奇数個だと、何回スイッチを押しても奇数個点
灯していることになり、全消灯することはない。

(2) m=3の場合、n≧8であれば、どんな初期状態からでも全ての電球を消灯できることを
  証明してください。


  また、n=7の場合に、何度操作しても全ての電球を消灯できない初期状態の一例を示
 してください。


 前半部分だけですが…。

 n≧8とする。

 「1,4,7番目」「4,5,6番目」「5,6,7番目」を操作すれば、1番目のみを消灯できる。

 操作する場所をすべて右にひとつずつずらせば、2番目のみを消灯できる。

 1番目のみの消灯手順と2番目のみの消灯手順と「1,2,3番目」を操作すれば、3番目のみを
消灯できる。

 2番目のみの消灯手順と3番目のみの消灯手順と「2,3,4番目」を操作すれば、4番目のみを
消灯できる。

 …

 n-2番目のみの消灯手順とn-1番目のみの消灯手順と「n-2,n-1,n番目」を操作すれば、n
番目のみを消灯できる。

 これらを組み合わせれば、どんな初期状態からでもすべての電球を消灯できる。

(3) m=5の場合、n≧24であれば、どんな初期状態からでも全ての電球を消灯できること
  を証明してください。

  また、n=23の場合に、何度操作しても全ての電球を消灯できない初期状態の一例を
 示してください。


 前半部分だけですが…。

 n≧24とする。

 「1,6,11,16,21番目」「6,7,8,9,10番目」「7,8,9,10,11番目」「16,17,18,19,20番目」「17,18,19,20,21
番目」を操作すれば、1番目のみを消灯できる。

 操作する場所をすべて右にひとつずつずらせば、2番目のみを消灯できる。

 操作する場所をさらに右にひとつずつずらせば、3番目のみを消灯できる。

 操作する場所をさらに右にひとつずつずらせば、4番目のみを消灯できる。

 1番目のみの消灯手順と2番目のみの消灯手順と3番目のみの消灯手順と4番目のみの消
灯手順と「1,2,3,4,5番目」を操作すれば、5番目のみを消灯できる。

 2番目のみの消灯手順と3番目のみの消灯手順と4番目のみの消灯手順と5番目のみの消
灯手順と「2,3,4,5,6番目」を操作すれば、6番目のみを消灯できる。

 …

 n-4番目のみの消灯手順とn-3番目のみの消灯手順とn-2番目のみの消灯手順とn-1番目
のみの消灯手順と「n-4,n-3,n-2,n-1,n番目」を操作すれば、n番目のみを消灯できる。

 これらを組み合わせれば、どんな初期状態からでもすべての電球を消灯できる。

(4) m=7の場合、どんな初期状態からでも全ての電球を消灯できるようなnの最小値は?

 m=3やm=5の場合と同様にすれば、少なくとも n≧48 では可能です。それより小さいも
のはまだわかりません。


 GAI さんからのコメントです。(平成29年5月4日付け)

 りらひいさん、素晴らしい手順を見つけましたね。理論を追って進めてみました。(→参考


 らすかるさんからのコメントです。(平成29年5月4日付け)

 GAI さんの、

S=[0,0,0,0,1,0,0,0]について、
F(1,4,7)、F(2,3,4)、F(1,2,3)、F(2,5,8)、F(3,4,5)、F(2,3,4)、F(1,4,7)、F(2,3,4)、F(1,2,3)、F(6,7,8)、F(5,6,7)


という手順には、F(1,4,7)、F(2,3,4)、F(1,2,3)が2〜3個あるので、それぞれ2個ずつ削除して、

 F(2,5,8)、F(3,4,5)、F(2,3,4)、F(6,7,8)、F(5,6,7)

でいいですね。

[0, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 1, 1, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0]

の5手になります。


 DD++さんからのコメントです。(平成29年5月4日付け)

 5手と見せかけて、 F(2,5,8)、F(2,4,6)、F(4,6,8) の3手で終わります。


 らすかるさんからのコメントです。(平成29年5月4日付け)

 では問題。m=3で、[0, 1, 0, 1, 0, 0, 0, 0] は最短何手でしょうか。


 DD++さんからのコメントです。(平成29年5月4日付け)

 6手ですかね。

 (1,2,3)、(1,4,7)、(2,4,6)、(2,5,8)、(3,4,5)、(6,7,8) など。

 n=8、m=3 で最短手数が最長になるパターンの1つですかね。7手かかるパターンもあるの
かな?


 らすかるさんからのコメントです。(平成29年5月4日付け)

 DD++さん、その通り6手です。最短7手以上になるパターンはありませんでした。

 255通りのうち、

12通りが最短1手 、48通りが最短2手 、86通りが最短3手 、75通りが最短4手
30通りが最短5手 、4通り(00001010、00011000、01000010、01010000)が最短6手

です。


 りらひいさんからのコメントです。(平成29年5月4日付け)

 らすかるさんが示した

 (2)の後半の一般解は、
  「2番目、3番目、5番目、6番目の4つのうちの点灯個数が奇数」


を参考にして、ようやく理解が進みました。

(2) m=3の場合、n≧8であれば、どんな初期状態からでも全ての電球を消灯できることを
  証明してください。


  また、n=7の場合に、何度操作しても全ての電球を消灯できない初期状態の一例を示
 してください。


 後半部分について、

 2,3,5,6番目の電球をグループAとする。1回スイッチを押したときにグループAにある点灯し
ている電球の個数がどう変化するかを考えると、変化しないか2個増えるか2個減るかのい
ずれかである。

 よって、最初にグループAで点灯している電球の数が奇数個だと、何回スイッチを押しても
グループAでは奇数個点灯していることになり、全消灯することはない。

(3) m=5の場合、n≧24であれば、どんな初期状態からでも全ての電球を消灯できること
  を証明してください。

  また、n=23の場合に、何度操作しても全ての電球を消灯できない初期状態の一例を
 示してください。


 後半部分について、

 4,5,9,10,14,15,19,20番目の電球をグループAとする。1回スイッチを押したときにグループA
にある点灯している電球の個数がどう変化するかを考えると、変化しないか2個増えるか2個
減るかのいずれかである。

 よって、最初にグループAで点灯している電球の数が奇数個だと、何回スイッチを押しても
グループAでは奇数個点灯していることになり、全消灯することはない。

(4) m=7の場合、どんな初期状態からでも全ての電球を消灯できるようなnの最小値は?

 m=7、n=47とする。k≡6または0 (mod 7) を満たすk番目の電球をグループAとする。1回ス
イッチを押したときにグループAにある点灯している電球の個数がどう変化するかを考えると、
変化しないか2個増えるか2個減るかのいずれかである。

 よって、最初にグループAで点灯している電球の数が奇数個だと、何回スイッチを押しても
グループAでは奇数個点灯していることになり、全消灯することはない。

 mが奇素数ならば同じようにしていけるわけですね。

 mは奇素数とする。n=m^2-2のとき、k≡-1または0 (mod m) を満たすk番目の電球をグル
ープAとすると、最初にグループAで点灯している電球の数が奇数個だとすべての電球を消
灯できない。

 n≧m^2-1ならば、どんな初期状態からでもすべての電球を消灯できる。


 さて、次は合成数について考えないと・・・。


 GAI さんからのコメントです。(平成29年5月4日付け)

 m=3で、[0, 1, 0, 1, 0, 0, 0, 0]は最短6手。
 (1,2,3)、(1,4,7)、(2,4,6)、(2,5,8)、(3,4,5)、(6,7,8) など。


 この「など」に相当する他の操作スイッチを探していたら、

 (1,2,3)、(1,4,7)、(2,3,4)、(2,5,8)、(4,5,6)、(6,7,8)

あるいは、 (1,3,5)、(1,4,7)、(2,5,8)、(3,5,7)、(5,6,7)、(6,7,8)

などでも達成できる。

(2,3,4)&(4,5,6)≡(2,4,6)&(3,4,5)
(1,3,5)&(3,5,7)&(5,6,7)≡(1,2,3)&(2,3,4)&(4,5,6)
(1,2,3)&(2,3,4)&(3,4,5)≡(1,3,5)

 このことは、2つや3つの操作の固まりを他の等間隔の操作に変換可能なために生じる現
象なのですね。(出現する数字が偶数個なら消して確認すればよい。)

 [0,0,0,0,1,0,0,0]が僅か3手で達成出来ることは驚きでした。

 ゲームとしては、電球7個で3つのスイッチが面白そうです。らすかるさんの不可能条件さえ
前もって知っておけば、ある人には可能問題、ある人には不可能問題を即座に作成してやら
せるイジワルができそうです。


 りらひいさんからのコメントです。(平成29年5月8日付け)

 ちょっと進展しました。

(5) 同じく、m=9の場合は?

 n=77のとき不可能で、n=78のとき可能なので、どんな初期状態からでもすべての電球を
消灯できるようなnの最小値は、n=78

(6) m=11、13は飛ばして、m=15の場合は?


 少なくとも、n=216のときは不可能で、n=220のときは可能になるので、nの最小値は、217
から220までのどれかになると思うのですが、まだ答えまでたどり着けていません。


 とりあえず、次のことは言えそうです。

 pを奇素数、eを1以上の整数として、m=p となるとき、

 n≦p2e−pe-1−1 のときは、すべての電球を消灯できない初期状態が存在し、
 n≧p2e−pe-1 のときは、どんな初期状態からでもすべての電球を消灯できる。


 DD++さんからのコメントです。(平成29年5月9日付け)

 出題した私の方では、m=p*q 型までは一般式をつかんでいます。しかし、m=45 のように
少なくともどちらかが平方以上になるもの、m=105 のように3種以上の素因数からなるもの
については私にもわかっていません。追いつかれるまであと少し……。


 りらひいさんからのコメントです。(平成29年12月20日付け)

 以前、途中であきらめていた問題を再度考えました。

(6) m=11、13は飛ばして、m=15の場合は?


 n=217 のとき不可能であり、n=218 のとき可能であるため、n の最小値は218

#時間を置くと、以前気付かなかったことに気付くことってありますよね。

 mが二種類の素因数を持つ場合は次のようになりそうです。

 p、q を奇素数、e、f を1以上の整数として、m=pe*qf となるとき、

 n≦(pe*qf)2-(p+q-1)*pe-1*qf-1-1 のときは、

   すべての電球を消灯できない初期状態が存在

 n≧(pe*qf)2-(p+q-1)*pe-1*qf-1   のときは、

   どんな初期状態からでもすべての電球を消灯できる。


 以下、工事中!



                         投稿一覧に戻る