2016年度京都大学特色入試の数学をRで解く【３】

この記事はQiita 数学 Advent Calendar 2015の4日目の記事です。（後付け）

センター（翌日のAdvent Calendarの記事参照）に続いて、入試問題をRでなんとかかんとかするシリーズです。
今回は、京都新聞の記事になっていた問題をRで解く…と言いたいところですが、一般の場合の論証的なことは難しかったので、とりあえず検算します。ただし、小問1と2は実際に解きます。小問3についても、任意の$n,k$に対して必ずこのゲームを終了させられるかの判定結果は返せるようにします。（一階述語論理を用いて任意の変数に対する命題として示していないだけだもん、的な逃げの姿勢です。）

この手の問題って、自分で解いても抜けが無いか不安になりますよね

$n$を$3$以上の整数とし、$k$を自然数とする。表裏の区別のつく$n$枚のコインを用いて$1$人で以下のゲームを行う。
・まず、ゲームの初期状態として、$n$枚のコインを円周上に等間隔に並べる。各コインは表または裏である。
・以下の操作を何回か繰り返す。
操作…並べたコインの中から連続する$k$枚を選び、選んだコインをすべてひっくり返す。
・この操作を何回か行った結果、すべてのコインを表にすることができれば、ゲームを終了する。

【問１】$n=7,k=3$とする。初期状態が図１の状態のとき、このゲームを終了させることができることを示せ。また、すべてのコインを表にするまでに必要な操作の最小回数を求めよ。

【問２】$n=6,k=3$とする。初期状態が図２の状態のとき、このゲームを終了させることはできないことを示せ。

【問３】どのような初期状態であっても必ずこのゲームを終了させることができるための、$n,k$に関する必要十分条件を求めよ。

解答

Rを使うという本題とは直接関係ないですが、一応つけておきました。問題の雰囲気を掴むのに必要な場合はどうぞ。

【問１】

真左から時計周りに頂点を$1,2,3,4,5,6,7$とする。
$i$を中心として3つ連続しているコインをひっくり返すことを$f(i)$と書くとき、$f(3),f(4),f(5),f(6)$を行うとすべて表になる。
$f(i)$によって、表のコインの数は$+1,-1,+3,-3$のいずれかの変化を受けることに注意する。
ゲームが終了する直前に行う操作ではすべてのコインが表に変わる必要があるので、$+3$でなければならない。
そこで、最小手数を2手と仮定すると$+1,+3$という組み合わせでなければならないが、このような組み合わせは存在せず矛盾する。
最小手数を3手とすると、各操作で表のコインの枚数が奇数枚変化することから、表の枚数が偶数になってしまって、やはり矛盾する。よって最小手数は4手。

【問３】

$k$が奇数、かつ$n$と$k$の最大公約数が$1$であることが必要十分条件であることを示す。

まず、$k$を偶数とすると、操作によってコインの偶奇が変わらないので、$n$と偶奇が異なる初期状態を選ぶと、すべて表にはできない。よって少なくとも$k$は奇数である。
そこで、$i$を中心として$k$個連続するコインをひっくり返す操作を同様に$f(i)$と書くことにする。
この操作は可換、すなわち$f(i)$をしてから$f(j)$をしても、$f(j)$をしてから$f(i)$をしても、同じ結果になることに注意する。
また、$f(i),f(i)$と操作をすると、元の状態に戻る。これらの事実から、与えられた初期状態に対して操作が作り出せる状態の数はたかだか$2^n$個である。
いま、コイン1枚をひっくり返す操作を同様の記法で$g(i)$と書くとき、$g(i)$と$f(j)$も可換。
初期状態にコインを並べることは、すべて裏の状態に対して$g(i)$たちを施すことと同義であるから、問題は$f(i)$たちによって、任意のコインの状態を作り出せるか、ということに帰着する。
コインの状態は$2^n$種類存在するので、つまり、上で述べた作り出せる状態の数が、ちょうど$2^n$個であればよい。言い換えれば、異なる操作列で同じ状態に移るものが無ければよい。
特に、すべて裏の状態からすべて表の状態になるような操作列を考えたとき、円の対称性から、このような操作列は回転させて実施しても、すべて表になる。
つまり、$f(i)$たちによる操作列に対して、$f(i+k)$たちによる操作列を考えても、すべて表になる。（$i+k$が$n$を超えるときは、剰余に応じて適宜$i+k$を振りなおすものとして。）
したがって、そのような操作列は、（操作の順序を除いて）$f(1),f(2),...,f(n)$のすべてを行う操作列のただ一つでなければならない。
ここで、$f(1),...,f(n)$すべてを行うと、すべてのコインが$k$回ひっくり返るので、$k$が奇数ならすべて表になる。

さて、$n$と$k$の最大公約数が$m>1$として、$1$から$k$をひっくり返す、$k+1$から$2k$をひっくり返す、…ということを繰り返す。（ただし、この操作の中で$n$を超えた場合は適宜$n$を引き、$n$の剰余の意味で考える。）
この操作を$n/m$回繰り返したところで、$nk/m$はちょうど$n$で割り切れる数になるので、すべてが表またはすべてが裏の状態になる。
$n/m<n$だから、$f(i)$たちすべてを行ってはいないことに注意する。
この操作によって、すべてが裏となる場合には、$f(i)$たちの使っていないものだけを選べば、すべてが表となる操作を作り出すことができる。
したがって、いずれの場合も$f(i)$たちすべてを使わずにすべてが表になる状態を作り出すことができ、$m>1$では終了できないゲームが存在することが分かる。

逆に、$n$と$k$の最大公約数を1とすると、同様の操作を続けることで、1つだけ表または1つだけ裏の状態を作り出すことができる。
（$mk$を$n$で割った余りが$1$になるような数が必ず存在する為。）
このとき、$f(i)$たちすべてを使えば表になることを利用して、必ず1つだけ表の状態を作り出すことができる。
この状態を生む手順を$G(1)$とするとき、はじめの操作の起点を$i$にして得られる操作を$G(i)$とすれば、$G(i)$によって$i$だけを表にすることができるので、$G(i)$たちを組み合わせれば任意の状態を再現できる。
従って、$k$が奇数、かつ$n$と$k$の最大公約数が1であることが必要十分条件となる。

※これ、実はコインの表裏というのが2で割った剰余に対応していて、$i$を$f(i)$に移す線形写像を考えたとき、その行列式が2で割った剰余の意味で1になるかどうか、ということに他なりません。$f(i)$たちをすべて使う操作列を足すことが、補集合を取ることとほとんど同じ意味なんですよね。そういう意味で、この証明の内容は、実は標数2の場合の線形写像の基底への具体的な写像の対応を与えているのと一緒なんですね。
この辺、どこまで丁寧に書くかですが、実際のテストでは、乱雑でも上の解答ぐらいのことを書いておけばいいんじゃないかなー。。。他の問題に使うべき時間もありますし。たぶん。

【問２】

真上から時計周りに頂点を$1,2,3,4,5,6$とする。$f(1),f(5)$は2だけ表の状態になるが、問３で示したことにより、1枚だけ表の状態は、すべてが表/すべてが裏の状態から遷移できない。

※問２って、どういう意図の誘導なんでしょうか。。。互いに素であるか否かに気付け、という意味なのか。あるいは、単にできない場合の具体例をいじって色々感じろ、ということなのか。

検算

そうだ京都行こう.R

library(plyr)
library(tidyr)

# k奇数のみ
ItsSoKyotoLetsGo <- function(n = 7,k = 3,default = c(1,3,6)){
  f <- list()
  for(i in 1:n){
    f[[i]] <- (i-(k%/%2)):(i+(k%/%2))
    f[[i]] <- n - ((- f[[i]]) %% n)
  }
  l <- matrix(0,2^n,n)
  for(i in 1:n){
    l[,i] <- c(rep(i,2^(i-1)),rep(0,2^(i-1)))
  }
  
  x <- list()
  ans <- list()
  minVal <- 1000
  for(i in 1:(2^n-1)){
    x[i] <- (c(gather(as.data.frame(f[l[i,]]))[,2], default) %>% count())[,2] %% 2 %>% sum()
    if(x[i] == n && minVal > sum(l[i,]>0)){
      ans <- list()
      ans[1] <- i
      minVal <- sum(l[i,]>0)
    } else if(x[i] == n && minVal == sum(l[i,]>0)){
      ans[length(ans) + 1] <- i
    }
  }
  ans[["min"]] <- minVal
  ans
}

今更ながら、$f(i)$の定義が激しくイマイチですね。せめて$i$から$i+k$にしておけばよかったのか…
関数名はGoogle先生に尋ねた結果なので、もし何か変だったら先生のせいです。。

【問１】

$2^7$通りの全ての場合について試して、全てが表になる場合を出します。まあ、操作0の場合は試さなないんですが。

n=7

> ItsSoKyotoLetsGo()
[[1]]
[1] 68

$min
[1] 4

68と言われても手順が分かりませんが、関数の中で作っているl[i,j]の中身を見てみると、l[68,] = 0 0 3 4 5 6ということで、$f(3),f(4),f(5),f(6)$を実行せよということでした。

【問２】

$2^6$通りの全ての場合について試して、全てが表になる場合が無いことを示します。

n=6

> ItsSoKyotoLetsGo(n=6)
$min
[1] 1000

※ナンバリングが真上からではないので、ちょっとずれていますが、形は同じなので問題はありません。

【問３】

この問題は、小さい$n$や$k$への検算に留めます。検算の方法としては、普通に解いた時に少し述べている、線形写像が単射になることを用いて直接計算します。具体的には行列式です。
$n=10,k=9$なんかが特徴的で、どちらも複数の素因数を持ちますが、ちゃんと全て表にできますね。まあ、全部表にしてから9枚ひっくり返せば明らかに1枚だけひっくり返す手順が確立されるので、その意味では自明なんですが。。。

for(n in 1:10){
  for(k in 1:n){
    a <- c(rep(1,k), rep(0,n))[1:n]
    A <- a %*% t(a)
    for(i in 1:n){
      A[,i] = c(a[i:n],a[1:i])[1:n]
    }
    print(paste(n,k,round(det(A)) %% 2))
  }
}

出力

[1] "1 1 1"
[1] "2 1 1"
[1] "2 2 0"
...
[1] "10 8 0"
[1] "10 9 1"
[1] "10 10 0"

Rを使って解こうとすると、問１と問２の方が問３よりも易しいですね。
向き不向き、ということですかね。

この問題が「報道」されているという事に関しては、メディアなどを通じて興味を持って貰えたとすれば、宣伝という意味で有効な戦略になるのではないかな、と思いました。