問題
，とおく．平面において，を座標とする点から始めて，点列をつぎのような手続きで作っていく．の座標をとするとき，
(イ) のときは，をまたはのどちらかが成りたつように決める．
(ロ) のときは，をによって決める．
このようにするといろいろな点列ができるが，それらについてつぎの問に答えよ．
(1) として可能な点をすべて求め，図示せよ．
(2) をで表わせ．
(3) として可能な点は何個あるか．
方針
和 に注目すると、行列 のどちらを使っても になる。(1)は2回分を直接列挙する。(3)は がしきい値以上である間だけ2択があり、 から までの8回が自由であることを確認する。さらに、各選択列が異なる点を与えることを 座標の二進的な変化量で示す。
解答
{(1) である。まず
であるから、 として可能なのは である。
さらにもう1回操作する。 からは
からは
したがって として可能な点は
である。図示ではこの4点を座標平面に打てばよい。
(2)
とおく。 を用いた場合、 なので を用いた場合も より したがって、どちらを選んでも である。初めは だから (3)
(2)より したがって、 から までは各段階で の2択が可能であり、 以後は に定まる。自由に選べるのは の8回である。
あとは、この 通りがすべて異なる点を与えることを確認する。時刻 で を選ぶと つまり 座標は だけ減る。一方、 を選んだときは 座標は変わらない。
したがって の 座標は、初期値1から、選んだ の時刻に対応する のいくつかを引いた値である。これらの和は二進的に一意に決まるので、異なる選び方は異なる 座標を与える。
最後の2回はどちらも で決まっており、 は異なる点を異なる点へ移す。したがって として可能な点の個数は }