解3(2)-2016年京都大学特色入試の類題の解答

さて……

問3(2)の解説を始めますが，この問題の解説は(1)以上に長くなります．

読者の方々は覚悟を持って読んでください．

筆者が特色入試の問題を読んだとき，「任意の初期配置でカードに書かれた整数を１にできる？そんなことありえるの？」が第一声でした．

組合せの問題で任意の状態を考えるとなると，気分が萎えますよね．

(2)は難度Dです．

この問題のポイントは，問3を紹介する記事でも書いたように，連続して並ぶk枚を選ぶときに生まれる性質です．

解3(1)の解説で用いたx(1),x(2),...,x(n)をここでも使います．

まず，有限回の操作をしてもすべてのカードに１と書かれた状態にすることができない初期状態が生じるとき，n,kはどんな値になっているでしょう？

恐らく，最初に思いつくのはnがkの倍数になっているときでしょう．

これが一番考えやすい条件です．

……では，「nがkの倍数」という条件を緩和して，「nとkが１以外の公約数を持つ」となったら，有限回の操作後にすべてのカードに１と書かれた状態にできない初期状態は生じるでしょうか？

そこで，次のようにx(1),x(2),...,x(n)をグループ分けします．

G(1),...,G(g)は集合です．

こうしてグループ分けしたときに操作を行うとどうなるでしょう？

……実は，操作を一度行うとそれぞれのグループでk/g枚のカードの数が書き換わります．

当たり前の事実ですが，これがこの問題を解くカギとなります．

なぜなら，各グループの要素の数は等しく，その上操作を行うと各グループで同数のカードの数が書き換わるという事実がとても重要なのです．

極端な例を考えてみましょう．

x(1)=a,x(2)=x(3)=...=x(n)=1で，n=6,k=2としましょう．このとき，g=2です．aはいくつでもいいです．

このとき，一回の操作を行うとそれぞれのグループで２枚のカードの数が書き換わります．

しかし，何度操作を行ってもG(1)とG(2)の全要素を同時に1にすることはできません．

実際に実験してみるとわかります．

同様に，x(1)=a,x(2)=x(3)=...=x(n)=1,n=n'g,k=k'gで，g≥2のとき何度操作を行ってもG(1)とG(2)の全要素を同時に1にすることはできません．

これが解答の指針になります．

すなわち，nとkが１以外の公約数を持つならば，有限回の操作をしてもカードすべての数字を1にすることができない初期配置が存在すると予想できます．

そして，もう１つ別のグループ分けを考えてみましょう．

このときも先ほどと同様に，操作を一度行うとそれぞれのグループでk/g枚のカードの数が書き換わります．

このときについても極端な例を考えてみましょう．

x(1)=a,x(2)=x(3)=...=x(n)=1で，k=6,a=4としましょう．すると，g=2です．nはいくつでもいいです．

そして，G(1)の要素の数をi，G(2)の要素の数をi'とします．

このとき，一回の操作を行うとそれぞれのグループで６枚のカードの数が書き換わります．

操作をu回行ったとします．

すると，各グループは合計6u枚のカードに操作が行われます．

そして，G(1)のカードをすべて１にするためには合計で1+4si枚のカードに対して操作が行われる必要があります（sは整数）．

同様に，G(2)のカードをすべて１にするためには合計で4ti'枚のカードに対して操作が行われる必要があります（tは整数）．

これらはどちらも3uに等しいので，1+4si=4ti'となります．

しかし，これを満たすs,tは存在しませんので，このa,kの条件下ではすべてのカードを１にすることはできません．

同様にして，aとkが互いに素でなければ，有限回の操作をしてもカードすべての数字を1にすることができない初期配置が存在するとよそうできます．

以上の２つの場合を見てきましたが，

• nとkが互いに素ではない
• aとkが互いに素ではない

とき，すべてのカードを１にすることはできないと予想できます．

では逆に，これら以外のときは任意の初期配置ですべてのカードを１にすることができるのでしょうか？

……結論から言うとできます．

それを示すには次の補題が必要になります．

これは，解3(1)で示した次の補題から示せます．

解3(1)で示した補題は，m,pを互いに素な整数としても成り立ちます．証明は全く同じなので，各自で確認しましょう．

そこで，任意の整数nに対してkm≡nとなるkが存在するので，n=1として整数lを用いてkm=lp+1と表されます．

よって，任意の互いに素なm,pに対してmk-pl=1を満たすk,lが存在する．

ここで，m=a,p=bとする．

すると，任意の整数tに対してa(k+tb)-b(l+ta)=1が成り立つので，m,nに関する不定方程式am-bn=1は無限個の解を持つ．

したがって，今回示したい補題は示されました．

この補題が十分性を示すうえで重要になります．

それでは，以下解答．

解答中のGCD(p,q)は，pとqの最大公約数を意味します．

★解答★

★★★★

こうして問3(2)は解けました．

いやぁ……長かったですね．

(3)も同じくらい長いかと思いますが，ぜひ最後までお付き合いください．