ロッカー問題を、プログラムで解いてみる

はじめに

皆さん、こんにちは。
今回は、ロッカー問題について、プログラムで解くという記事を書きたいと思います。
ロッカー問題を知っている人にも、知らない人にも、参考になれば幸いです。

ロッカー問題とは

皆さんは、ロッカー問題をご存知でしょうか？
ロッカー問題とは、以下のルールによって開け閉めしたロッカーが、最終的にどうなっているか？という問題になります。

（１）1番から100番までの、番号が振られたロッカーがある
（２）1番から100番までの、ゼッケンを着た人がいる
（３）ゼッケンを着た人達が、1番から順番に、自分のゼッケン番号で割り切れる番号のロッカーを、開け閉めする
（４）ロッカーは最初全て閉まっており
（５）ロッカーの開け閉めは、開いていれば閉め、閉まっていれば開ける、という操作とする

イメージ的には、以下。

ちなみに、この問題は、大手外資系証券会社などの採用面談などで聞かれたりするそうです。

先に結論

この問題は、解ける人はパッと解けるんだそうです。
紙もペンも使わずに。

答えは、「√を取ると整数が得られる番号のロッカーだけが開いており、他は閉まっている」となります。
なぜならば、この問題において、ロッカーの開け閉め回数は、ロッカー番号の約数の数と合致し、かつ、ある整数が2乗された数は約数が奇数である為です。

ちなみに、私はこの問題を最初に問われた時に、パッとは答えられませんでした。
また、答えを聞いても、ピンと来ませんでした。
そもそも、整数を2乗した値の約数が奇数だという法則性を、知らなかった為です。
尚、その法則性は、割と常識なようです。
ですが、更なる質問「なぜ約数が奇数なのか？」という問いに答えられる人はいませんでした。

プログラムで解いてみる

その後、気になったので、色々と掘り下げてみることにしました。
先ずは、プログラムで解いてみて、傾向を見ます。

問題を解くプログラムは以下です。

import numpy as np

locker = np.zeros([100], dtype=np.bool)

for member_i in range(100):
   zekken_no = member_i + 1
   for locker_i in range(100):
       locker_no = locker_i + 1
       if ((locker_no % zekken_no) == 0):
           locker[locker_i] = (not locker[locker_i])

print('open locker is')
print(np.where(locker)[0] + 1)

そして、プログラムの出力結果は以下。

open locker is
[ 1 4 9 16 25 36 49 64 81 100]

確かに、整数の2乗の番号を持つロッカーが開いているようです。
いや、面白いですね。

約数を調べてみる

次に、約数を調べるプログラムを書いてみました。

import numpy as np

access_zekken = [[] for i in range(100)]

for member_i in range(100):
   zekken_no = member_i + 1
   for locker_i in range(100):
       locker_no = locker_i + 1
       if ((locker_no % zekken_no) == 0):
           access_zekken[locker_i].append(zekken_no)

print('access zekken (約数)')
for locker_i in range(100):
   print('    locker_%03d : ' % (locker_i + 1), end='')
   print(access_zekken[locker_i])

出力結果は以下。

access zekken (約数)
locker_001 : [1]
locker_002 : [1, 2]
locker_003 : [1, 3]
locker_004 : [1, 2, 4]
locker_005 : [1, 5]
locker_006 : [1, 2, 3, 6]
locker_007 : [1, 7]
locker_008 : [1, 2, 4, 8]
locker_009 : [1, 3, 9]
locker_010 : [1, 2, 5, 10]
locker_011 : [1, 11]
locker_012 : [1, 2, 3, 4, 6, 12]
locker_013 : [1, 13]
locker_014 : [1, 2, 7, 14]
locker_015 : [1, 3, 5, 15]
locker_016 : [1, 2, 4, 8, 16]
locker_017 : [1, 17]
locker_018 : [1, 2, 3, 6, 9, 18]
locker_019 : [1, 19]
locker_020 : [1, 2, 4, 5, 10, 20]
locker_021 : [1, 3, 7, 21]
locker_022 : [1, 2, 11, 22]
locker_023 : [1, 23]
locker_024 : [1, 2, 3, 4, 6, 8, 12, 24]
locker_025 : [1, 5, 25]
locker_026 : [1, 2, 13, 26]
locker_027 : [1, 3, 9, 27]
locker_028 : [1, 2, 4, 7, 14, 28]
locker_029 : [1, 29]
locker_030 : [1, 2, 3, 5, 6, 10, 15, 30]
locker_031 : [1, 31]
locker_032 : [1, 2, 4, 8, 16, 32]
locker_033 : [1, 3, 11, 33]
locker_034 : [1, 2, 17, 34]
locker_035 : [1, 5, 7, 35]
locker_036 : [1, 2, 3, 4, 6, 9, 12, 18, 36]
locker_037 : [1, 37]
locker_038 : [1, 2, 19, 38]
locker_039 : [1, 3, 13, 39]
locker_040 : [1, 2, 4, 5, 8, 10, 20, 40]
locker_041 : [1, 41]
locker_042 : [1, 2, 3, 6, 7, 14, 21, 42]
locker_043 : [1, 43]
locker_044 : [1, 2, 4, 11, 22, 44]
locker_045 : [1, 3, 5, 9, 15, 45]
locker_046 : [1, 2, 23, 46]
locker_047 : [1, 47]
locker_048 : [1, 2, 3, 4, 6, 8, 12, 16, 24, 48]
locker_049 : [1, 7, 49]
locker_050 : [1, 2, 5, 10, 25, 50]
locker_051 : [1, 3, 17, 51]
locker_052 : [1, 2, 4, 13, 26, 52]
locker_053 : [1, 53]
locker_054 : [1, 2, 3, 6, 9, 18, 27, 54]
locker_055 : [1, 5, 11, 55]
locker_056 : [1, 2, 4, 7, 8, 14, 28, 56]
locker_057 : [1, 3, 19, 57]
locker_058 : [1, 2, 29, 58]
locker_059 : [1, 59]
locker_060 : [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
locker_061 : [1, 61]
locker_062 : [1, 2, 31, 62]
locker_063 : [1, 3, 7, 9, 21, 63]
locker_064 : [1, 2, 4, 8, 16, 32, 64]
locker_065 : [1, 5, 13, 65]
locker_066 : [1, 2, 3, 6, 11, 22, 33, 66]
locker_067 : [1, 67]
locker_068 : [1, 2, 4, 17, 34, 68]
locker_069 : [1, 3, 23, 69]
locker_070 : [1, 2, 5, 7, 10, 14, 35, 70]
locker_071 : [1, 71]
locker_072 : [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]
locker_073 : [1, 73]
locker_074 : [1, 2, 37, 74]
locker_075 : [1, 3, 5, 15, 25, 75]
locker_076 : [1, 2, 4, 19, 38, 76]
locker_077 : [1, 7, 11, 77]
locker_078 : [1, 2, 3, 6, 13, 26, 39, 78]
locker_079 : [1, 79]
locker_080 : [1, 2, 4, 5, 8, 10, 16, 20, 40, 80]
locker_081 : [1, 3, 9, 27, 81]
locker_082 : [1, 2, 41, 82]
locker_083 : [1, 83]
locker_084 : [1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84]
locker_085 : [1, 5, 17, 85]
locker_086 : [1, 2, 43, 86]
locker_087 : [1, 3, 29, 87]
locker_088 : [1, 2, 4, 8, 11, 22, 44, 88]
locker_089 : [1, 89]
locker_090 : [1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90]
locker_091 : [1, 7, 13, 91]
locker_092 : [1, 2, 4, 23, 46, 92]
locker_093 : [1, 3, 31, 93]
locker_094 : [1, 2, 47, 94]
locker_095 : [1, 5, 19, 95]
locker_096 : [1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96]
locker_097 : [1, 97]
locker_098 : [1, 2, 7, 14, 49, 98]
locker_099 : [1, 3, 9, 11, 33, 99]
locker_100 : [1, 2, 4, 5, 10, 20, 25, 50, 100]

こちらも確かに、整数の2乗の番号を持つロッカーは、約数の数が奇数になっているようです。

約数を観察してみると、2乗の数の約数が奇数である理由が分かった

約数を観察してみると、以下のことが分かりました。
ある数について、約数をリストアップしようとすると、小さい数から大きな数までが抽出されるのですが、必ず「n番目に小さな約数」と「n番目に多いな約数」とがセットになっているのです。
尚、この約数のセットは、掛け合わせると、元の数と合致します。

例えば、数字の99で言えば、以下の感じです。

  - 1番目
      - 小さな約数：1
      - 大きな約数：99
      - 1 ✕ 99 = 99
  - 2番目
      - 小さな約数：3
      - 大きな約数：33
      - 3 ✕ 33 = 99
  - 3番目
      - 小さな約数：9
      - 大きな約数：11
      - 9 ✕ 11 = 99

しかし、整数の2乗の値については、この法則性が崩れます。
というのも、ちょうど真ん中の大きさの約数ペアが、その数字同士となる為です。

例えば、数字の81で言えば、以下の感じです。

  - 1番目
      - 小さな約数：1
      - 大きな約数：81
      - 1 ✕ 81 = 81
  - 2番目
      - 小さな約数：3
      - 大きな約数：27
      - 3 ✕ 27 = 81
  - 3番目
      - 小さな約数：9
      - 大きな約数：9
      - 9 ✕ 9 = 81

最後の約数のペアが、同じ数字のペアなので、ユニークな数字の数としては、カウントが1つ減ってしまいます。
そんな訳で、整数の2乗の値は、約数が奇数となってしまう訳です。

どうでしょうか？
直感的に、分りやすくはないでしょうか？
いやー、やはり、デバッグは大事だなと思いました。

おわりに

ここまで読んでくださった方、ありがとうございました。
ロッカー問題に関する自己満の記事ですが、私と同じ様に腑に落ちる肩がいらっしゃれば幸いです。🙇笑