印象に残っている授業

印象に残っている授業がある。
その授業は「総合的な学習の時間」の中で行われていた気がする。

パズルやクイズの中から規則性を見つけ出して、パズルのタネ、
すなわちアルゴリズムを見つけ出すというものだった。

毎週違ったパズルが出てきて、そのタネを見つけだすのがとても楽しかった。

クイズ：数字当てゲームのタネを見つけ出す

回答者は、0から99までの数値を想像する
出題者は、0から99までの50個の数字が書かれた問題用紙を7枚出してくる
回答者は、想像した数値が問題用紙中にあった場合、問題用紙の1つめの数値を足す
これを全ての問題用紙に対して行うと、それが想像した数値となる

確か問題用紙は一番下に挙げた通りだったと思う。

回答：当時を振り返って

それぞれの用紙の最初の数値が明らかに怪しい。
何せ1, 2..64と等倍に増えていく。

次に、それぞれの紙に書いてある数値を並び替えると

1枚目は1, 3, ..
2枚目は2, 3, .., 6, ..
3枚目は4, 5, 6, 7, .., 12, ..

何やらパターンが見えてきた。
最後の紙に至っては普通に数字が並んでいるだけだ。
N枚目の紙では数値が2^(N-1)から始まっており、
2^(N-1)個置きに数字が並んだり飛んでいたりする。

ただし、ノーヒントでわかったのはここまでだった気がする。

その後、2進数というものを先生から教わった。
2進数では桁数と共に1, 2, 4, .., と等倍に増えていき、
しかも0か1のどちらかしかない。

ここまできて、N枚目に書いてある数値は、2進数表記にした際のN-1桁目が1となる数値の集合だったことがわかった。

検証用のJavaScirptコード

N+1毎目の問題用紙を生成し、該当する数値が存在する場合は先頭の要素を足す。
配列のシャッフルは省いたが、先頭要素は同じなので、回答への影響は無い。
正しく動いているようなので、当時の回答も正しいことがわかる。

function make_array(n) {
    var res = []; 
    for (var i = 0; i < 100; i++) 
        if (i & (1 << n)) res.push(i);
    return res;
}

function check(n) {
    var res = 0;
    if (make_array(0).indexOf(n) != -1) res += make_array(0)[0];
    if (make_array(1).indexOf(n) != -1) res += make_array(1)[0];
    if (make_array(2).indexOf(n) != -1) res += make_array(2)[0];
    if (make_array(3).indexOf(n) != -1) res += make_array(3)[0];
    if (make_array(4).indexOf(n) != -1) res += make_array(4)[0];
    if (make_array(5).indexOf(n) != -1) res += make_array(5)[0];
    if (make_array(6).indexOf(n) != -1) res += make_array(6)[0];
    console.log(res == n); 
}

for (var i = 0; i < 100; i++) check(i);

問題用紙

大体こんな感じだっただろうか。
先頭要素以外がシャッフルされている。

1枚目

1, 33, 91, 57, 23, 83, 19, 37, 3, 87, 49, 39, 13, 79, 21, 51, 47, 41, 15, 75, 89, 85, 81, 77, 65, 99, 59, 63, 27, 17, 93, 45, 71, 61, 25, 31, 7, 9, 35, 29, 97, 73, 5, 95, 43, 11, 67, 69, 53, 55

2枚目

2, 42, 95, 19, 26, 87, 27, 35, 10, 59, 86, 71, 7, 79, 43, 75, 55, 15, 94, 62, 90, 18, 54, 3, 91, 31, 39, 50, 23, 74, 51, 63, 11, 78, 14, 67, 47, 99, 22, 58, 6, 82, 98, 66, 70, 34, 83, 38, 30, 46

3枚目

4, 12, 60, 47, 95, 20, 14, 86, 94, 44, 23, 13, 30, 39, 28, 6, 93, 45, 21, 71, 84, 62, 68, 85, 61, 53, 37, 52, 31, 36, 70, 63, 78, 46, 7, 22, 55, 79, 38, 76, 87, 54, 77, 15, 69, 5, 29, 92

4枚目

8, 14, 77, 76, 75, 61, 12, 88, 9, 40, 41, 63, 26, 74, 24, 73, 31, 45, 10, 91, 72, 93, 57, 43, 47, 28, 92, 27, 56, 44, 11, 60, 25, 94, 78, 58, 42, 95, 89, 59, 30, 13, 29, 62, 46, 15, 90, 79

5枚目

16, 52, 88, 80, 56, 17, 62, 58, 51, 83, 63, 18, 57, 27, 84, 29, 59, 92, 48, 82, 54, 89, 86, 60, 95, 30, 49, 26, 87, 20, 81, 22, 21, 85, 94, 23, 55, 61, 31, 19, 90, 93, 53, 91, 24, 50, 25, 28

6枚目

32, 98, 60, 56, 43, 57, 46, 62, 37, 35, 97, 39, 63, 40, 61, 52, 34, 99, 50, 53, 96, 49, 45, 59, 47, 55, 54, 58, 51, 41, 33, 38, 36, 48, 42, 44

7枚目

64, 75, 82, 87, 70, 68, 97, 77, 95, 91, 92, 78, 71, 65, 69, 93, 89, 85, 90, 98, 67, 76, 99, 72, 79, 84, 66, 96, 88, 86, 80, 94, 73, 81, 74, 83