『画像処理』

【問題】

V(0,0) = (1)
V(1,0) = (1, 1)
V(1,1) = (1,-1)

V(n+1,i) = (V(n, i), V(n, i))
　0 ≦ i ＜ 2n

V(n+1,i) = (V(n,i-2n), -V(n,i-2n))
　2n ≦ i ＜ 2n+1

と 2n次元ベクトル V(n, i)
　(0 ≦ n, 0 ≦ i ＜ 2n) を定義する。

n = 3 の時を、1 を □、-1 を ■ で表すと、

V(3, 0) = □□□□□□□□
V(3, 1) = □■□■□■□■
V(3, 2) = □□■■□□■■
V(3, 3) = □■■□□■■□
V(3, 4) = □□□□■■■■
V(3, 5) = □■□■■□■□
V(3, 6) = □□■■■■□□
V(3, 7) = □■■□■□□■
となる。

一般に i ≠ j ならば、V(n, i) と V(n, j) の内積は ０ である。

【問題１】

内積が ０ になることを示せ。

上の n = 3 の場合、置換
(0, 4, 6, 2, 3, 7, 5, 1) → (0, 1, 2, 3, 4, 5 ,6, 7) により並べかえると

V(3, 0) = □□□□□□□□
V(3, 4) = □□□□■■■■
V(3, 6) = □□■■■■□□
V(3, 2) = □□■■□□■■
V(3, 3) = □■■□□■■□
V(3, 7) = □■■□■□□■
V(3, 5) = □■□■■□■□
V(3, 1) = □■□■□■□■
という形になる。
この並べ方だと、下にいくほど 1 から -1 あるいは -1 から 1 に変わる回数が増えていく。
また、左上から右下への対角線を軸にして、線対称になっています。

【問題２】

一般にどのような置換でこのように並べかえることができるか。

　解答用紙はこちらです。　【寄せられた解答】

　◆図形問題へもどる

　数学の部屋へもどる