第 10 回 新潟県数学選手権 中学生大会 解答例 (団体) (1) 5 回シャッフルを行うと， 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 6, 1, 7, 2, 8, 3, 9, 4, 10, 5 → 3, 6, 9, 1, 4, 7, 10, 2, 5, 8 → 7, 3, 10, 6, 2, 9, 5, 1, 8, 4 → 9, 7, 5, 3, 1, 10, 8, 6, 4, 2 → 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 のように最初の状態から上下が逆順になるので，もう 5 回繰り返すと元に戻る。よって最初か ら数えて 10 回繰り返すと元に戻る。 (2) 1 5 x 5 n のとき，y = 2x。n + 1 5 x 5 2n のとき，y = 2x − 2n − 1。 (3) (A) で，k = 5, x = 1, y = 1 と置くことにより，25 − 1 = 31 は 2n + 1 で割り切れる。31 は素 数なので，2n + 1 = 31 よって，n = 15。(ちなみにこのとき，25 x を 31 で割った余りは x なの で，全てのカードが元の位置に戻る。) (4) 0 回シャッフル，1 回シャッフル，2 回シャッフル，· · · ，2n 回シャッフルと 2n + 1 通りのシャッ フルによる 1 枚目カードの移動先に注目すると，移動先は 2n 通りしかないので，ある a 回と b 回 (0 5 a < b 5 2n) のシャッフルについて移動先が一致する。それを y 枚目とすると，(A) よ り 2a − y, 2b − y は，2n + 1 で割り切れる。よって，2b − 2a = (2b − y) − (2a − y) も 2n + 1 で 割り切れる。よって，2a (2b−a − 1) は 2n + 1 で割り切れるが，2 と 2n + 1 は，公約数が 1 しか ないので，2b−a − 1 が 2n + 1 で割り切れる。よって，自然数 x (1 5 x 5 2n) 倍することにより 2b−a x − x が 2n + 1 で割り切れ，2b−a x を 2n + 1 で割った余りは x である。よって，(A) より b − a 回のシャッフルで全てのカードが元に戻っていると言える。1 5 b − a 5 2n なので，示さ れた。 (5) シャッフル 1 回により，x 枚目のカードが移動する先を x′ 枚目と書くことにする。自然数 a, b について次が言える。 (∗)「a が b を 2n + 1 で割った余りだと仮定すれば，a′ は 2b を 2n + 1 で割った余りである。」 [証明] (2) より，a′ は 2a あるいは 2a − 2n − 1 に等しい。したがって，2b − a′ は 2(b − a) ある いは 2(b − a) + (2n + 1) に等しい。仮定により，b − a は 2n + 1 で割り切れるから (0 は任意 の自然数で割り切れると考える)，どちらの場合も 2b − a′ は 2n + 1 で割り切れる。1 5 a′ 5 2n なので，a′ は 2b を 2n + 1 で割った余りである。(証明終) さて，1 5 x 5 2n なので，a = x, b = x と置くと (∗) の仮定が満たされ，x′ は 2x を 2n + 1 で 割った余りである。更に，シャッフルで x′ 枚目のカードが x′′ 枚目に移動したとする。a = x′ ， b = 2x と置くと (∗) の仮定が満たされるので，x′′ は 22 x を 2n + 1 で割った余りである。以下同 様に k 回繰り返せば，y は 2k x を 2n + 1 で割った余りであると言える。
© Copyright 2024 ExpyDoc
