https://put3y19ea1n0r9er.hatenablog.com/entry/2020/03/05/223003

自作問題です．解答は下部に載せました．

問題

行ベクトル $A \left( 0 , 0 \right) = \left [ a_1 \left( 0 , 0 \right) , a_2 \left( 0 , 0 \right) , \ldots , a_{n} \left( 0 , 0 \right) \right ]$ とする．ここで， $a_i \left( 0 , 0 \right)$ は自然数であり， $1 \leq a_i \left( 0 , 0 \right) \leq n$ である．また， $i \neq j$ ならば $a_i \left( 0 , 0 \right) \neq a_j \left( 0 , 0 \right)$ とする．以下の方法で， ${ \displaystyle A \left( 0 , 0 \right) }$ から順番に成分を取り除いていく．

操作１： ${ \displaystyle A \left( 0 , 0 \right) }$ の $1 + a_1 \left( 0 , 0 \right)$ 列の成分を取り除く．ただし， $1 + a_1 \left( 0 , 0 \right) \gt n$ となる場合は， $1 + a_1 \left( 0 , 0 \right) - n$ 列の成分を取り除く．

操作２：操作１で取り除いた成分の列番号を $k$ とおく．新たな行ベクトルを

$A \left( 0 , 1 \right) = \left [ a_1 \left( 0 , 1 \right) , a_2 \left( 0 , 1 \right) , \ldots , a_{n-1} \left( 0 , 1 \right) \right ]$

とおく．ここで，

${ \displaystyle a_{1} \left( 0 , 1 \right) = a_{k+1} \left( 0 , 0 \right) }$

${ \displaystyle a_{2} \left( 0 , 1 \right) = a_{k+2} \left( 0 , 0 \right) }$

$\ldots$

${ \displaystyle a_{n-k} \left( 0 , 1 \right) = a_{n} \left( 0 , 0 \right) }$

${ \displaystyle a_{n-k+1} \left( 0 , 1 \right) = a_{1} \left( 0 , 0 \right) }$

$\ldots$

$a_{n-1} \left( 0 , 1 \right) = a_{k-1} \left( 0 , 0 \right)$

とする．

操作３： ${ \displaystyle A \left( 0 , 1 \right) }$ の $1 + a_1 \left( 0 , 1 \right)$ 列の成分を取り除く．ただし， $1 + a_1 \left( 0 , 1 \right) \gt n -1$ となる場合は， $1 + a_1 \left( 0 , 1 \right) - \left( n -1 \right)$ 列の成分を取り除く．

操作４：操作３で取り除いた成分の列番号を $l$ とおく．新たな行ベクトルを

$A \left( 0 , 2 \right) = \left [ a_1 \left( 0 , 2 \right) , a_2 \left( 0 , 2 \right) , \ldots , a_{n-2} \left( 0 , 2 \right) \right ]$

とおく．ここで，

${ \displaystyle a_{1} \left( 0 , 2 \right) = a_{l+1} \left( 0 , 1 \right) }$

${ \displaystyle a_{2} \left( 0 , 2 \right) = a_{l+2} \left( 0 , 1 \right) }$

$\ldots$

${ \displaystyle a_{n-1-l} \left( 0 , 2 \right) = a_{n-1} \left( 0 , 1 \right) }$

${ \displaystyle a_{n-1-l+1} \left( 0 , 2 \right) = a_{1} \left( 0 , 1 \right) }$

$\ldots$

$a_{n-2} \left( 0 , 2 \right) = a_{l-1} \left( 0 , 1 \right)$

とする．

操作５：以下，同様の操作を $A \left( 0 , n \right) = \left [ \ \right ]$ を得るまで繰り返す．

操作１～操作５によって ${ \displaystyle A \left( 0 , 0 \right) }$ から取り除いた成分を，取り除いた順番が早い順に第１列から並べた行ベクトルを

$A \left( 1 , 0 \right) = \left [ a_1 \left( 1 , 0 \right) , a_2 \left( 1 , 0 \right) , \ldots , a_{n} \left( 1 , 0 \right) \right ]$

とおく． $A \left( 1 , 0 \right)$ に対して同様の操作を行うことで， $A \left( 2 , 0 \right)$ を得る．以下同様にして $A \left( m , 0 \right)$ を得る．

このとき， $A \left( m , 0 \right) = A \left( m + 1, 0 \right)$ を満たす行ベクトル $A \left( m , 0 \right)$ は各 $n$ に対してただ一つしか存在しないことを示せ．

解答：

題意を満たす行ベクトルは，

$A \left( m , 0 \right) = \left [ n , n-1 , \ldots , 2, 1 \right ]$

ただ一つである．

証明： ${ \displaystyle a_1 \left( m , 0 \right) \neq n }$ とすると， ${ \displaystyle a_1 \left( m , 0 \right) \neq a_1 \left( m + 1, 0 \right) }$ となるが，これは題意を満たさない．よって， ${ \displaystyle a_1 \left( m , 0 \right) = n }$ である．このとき， ${ \displaystyle a_2 \left( m , 0 \right) \neq n - 1 }$ とすると， ${ \displaystyle a_2 \left( m , 0 \right) \neq a_2 \left( m + 1, 0 \right) }$ となるが，これは題意を満たさない．よって， ${ \displaystyle a_2 \left( m , 0 \right) = n -1 }$ である．以下同様に， ${ \displaystyle a_i \left( m , 0 \right) = n + 1 - i }$ であるから，題意を満たす行ベクトルは，

$A \left( m , 0 \right) = \left [ n , n-1 , \ldots , 2, 1 \right ]$

ただ一つである．

発売日: 2015/03/28
メディア: おもちゃ＆ホビー