大幅減点の理由をご指摘ください。よろしくお願いします。
Nを正の整数とする。2N個の項からなる数列{a1,a2,…,aN,b1,b2,…b,N}を{b1,a1,b2,a2,…,bN,aN}という数列に並べ替える操作をシャッフルと呼ぶことにする。並べ替えた数列はb1を初項とし、biの次にai、aiの次にb(n+1)が来るようなものになる。また数列{1,2,…,2N}をシャッフルした時に得られる数列において、数kが現れる位置をf(k)で表す。
nを正の整数とし、n=2^(n-1)の時を考える。数列{1,2,…,2N}を2n回シャッフルすると{1,2,…,2N}に戻ることを証明せよ。
前の設問で1≦k≦2Nを満たす任意の整数kに対し、f(k)-2kは2N+1で割り切れることを示しています。この事実を利用すると思い、kをi回シャッフルした時のkが現れる位置をai(k)と置きます。
前の設問より、a1(k)-2k=(2N+1)A1(A1は整数)と置けます。
a1(k)=(2N+1)A1+2k
同様に、a2(k)-2a1(k)=(2N+1)A2(A2は整数)と置けます。
a2(k)=(2M+1)A2+2(2N+1)A1+4k=(2N+1)(2A1+A2)+4k
以下同様に
a3(k)=(2N+1)(4A1+2A2+A3)+8k
a4(k)=(2N+1)(8A1+4A2+2A3+A4)+16k
・
・
・
a2n(k)=(2N+1){2^(2n-1)A1+2^(2n-2)A2+…+A2n}+(2^2n)k
a2n(k)-k=(2N+1){2^(2n-1)A1+2^(2n-2)A2+…+A2n}+(2^2n)k-k
a2n(k)-k=(2N+1){2^(2n-1)A1+2^(2n-2)A2+…+A2n}+(2^n+1))(2^n-1)k
a2n(k)-k=(2N+1){2^(2n-1)A1+2^(2n-2)A2+…+A2n}+(2N+1))(2N-1)k
a2n(k)-k=(2N+1){2^(2n-1)A1+2^(2n-2)A2+…+A2n+(2N-1)k}
a2n(k)-kは2N+1で割り切れます。一方、1≦a2n(k)≦2^n、1≦k≦2^nより、0≦|a2n(k)-k|≦2N-1＜2N+1なので、a2n(k)-k=0より、a2n(k)=kです。
|
No.55387 - 2018/12/02(Sun) 02:17:51
| ☆ Re: 整数問題 / IT | | | > 前の設問で1≦k≦2Nを満たす任意の整数kに対し、f(k)-2kは2N+1で割り切れることを示しています。この事実を利用すると思い、kをi回シャッフルした時のkが現れる位置をai(k)と置きます。
>
> 前の設問より、a1(k)-2k=(2N+1)A1(A1は整数)と置けます。
このA1は各kによっては異なる可能性があります。
それをすべてのkに対して共通のA1が取れると誤解していると、採点者に解釈されたのかも知れません。
採点打ち切り箇所（致命的な間違い・意味不明などでそれ以降は採点しない）、減点箇所、部分点箇所などに採点者がマークしていませんか？
|
No.55396 - 2018/12/02(Sun) 15:27:28 |
| ☆ Re: 整数問題 / 瑠璃 | | | 御回答ありがとうございます。
＞このA1は各kによっては異なる可能性があります。
それをすべてのkに対して共通のA1が取れると誤解していると、採点者に解釈されたのかも知れません。
ここがよくわかりません。一体どのようなことおっしゃっているのでしょうか。a1(k)、a2(k)、a3(k)、…、a2n(k)すべてでA1、A2、A3、…、A2nと添え字を変えてますが、これでは不十分なのでしょうか。
|
No.55404 - 2018/12/03(Mon) 01:22:16 |
| ☆ Re: 整数問題 / らすかる | | | kによってA1,A2,…の値が変わる、という意味です。
なので正確に書けばA1(k),A2(k),…ですね。
|
No.55407 - 2018/12/03(Mon) 02:46:51 |
| ☆ Re: 整数問題 / IT | | | 例えば N=4のときk=1,2,3,4,5,6,7,8について a1(k)-2k がどうなるか調べてみてください
|
No.55411 - 2018/12/03(Mon) 07:20:40 |
| ☆ Re: 整数問題 / 瑠璃 | | | No.55430 - 2018/12/05(Wed) 01:48:49 |
|
