Random Walker Log's Log

二度と見ない系ログファイル

20151129 京大特色入試と聞いて

b.hatena.ne.jp

京大特色入試というのが行われていたのを、これを見て知った。東工大AOみたいなやつかな?
とりあえずここの記事に書いてあった問題を考えてみた。もうtogetterとかでまとめてる人もいたけどとりあえずメモ。

(1)
表を1、裏を0で表す。また、コインの並びは適当なところでぶつ切りにして横に並べて書くことにする。
0101010
1011010
1011101
0111100
1111111
とすれば4回でできる。表にするコインは4枚だから、全部表にするまでにコインを裏返す総回数は偶数。一度に裏返せるコインは奇数枚だから、終わるまでの操作の回数は偶数。
初期位置を見れば1回で0001111の形にはできないので2回で揃えるのは無理。だから4回が最善手。

(2)
横に並べた6つのコインに、左から順に1,2,...,6と番号をつけてやると、
どのように操作を行っても、番号を3で割った余りが0,1,2の奴が1つずつ裏返される。
ということは、余りが0,1,2のコインのうち、表のコインの枚数をa,b,cとおくと、a,b,cは操作によって必ず1ずつ変化する。
表のコインの枚数の差a-b,b-c,c-aを2で割った余りの3つ組が不変量になる、ということ。
図2の配置を110100と書くとa=2,b=1,c=0だから不変量は(1,1,0)で、作りたい形111111の場合は(0,0,0)だから作れない。

(3)
nとkが互いに素で、かつkが奇数というのが必要十分条件

互いに素でないときは、nとkの最大公約数をdとおくと、(2)と同じようにやれば不変量が作れる。
左から順に1,2,...,nと番号をつけてやれば、
操作によって番号をdで割った余りが0,1,...,d-1の奴がk/d枚ずつ裏返される。
ということは、余りが0,1,...,d-1のコインのうち、表のコインの枚数は、
 k/dが奇数なら1ずつ変化する
 k/dが偶数なら変化しない
なので(2)の3つ組をnつ組にしたものが不変量になる。
100...0のnつ組は111...1と異なるから揃えられない。
互いに素で、かつkが偶数のとき、000...0を111...1にできない。
nはkと互いに素だから奇数なので、000...0を111...1にするには奇数回裏返さなければならないため。

互いに素かつkが奇数のとき、0000000...→1110000...→1111110...のように順番に裏返していくと、
n回操作を行った時点でコインの裏表が全部入れ替わる。
nとkは互いに素だから、ak=bn-1となるような正整数a,bがとれる。
順番に裏返すのをa回やると、
 ある1枚だけ、裏返した回数が1回少ない
という状況がおこる。全部入れ替えと合わせれば、
 ある1枚だけを裏返す
という操作を構成できる。これを使えばどんな初期位置からでも111...1を作れる。


2進法とか使ってトリッキーな不変量を思いついたと思ったら勘違いですごくつらかった。
こういう問題は楽しいっちゃ楽しいんだけど、個人的にはどちらかというと数3の積分ゴリゴリみたいな問題が好きなほうなので、高校の時とか周りが数オリっぽい問題が好きな人ばっかりで肩身が狭かった記憶がある。


(なんかすごい眠い感じの中で書かれたので、捏造された記憶かもしれないし、この解答のようなものも単なる怪文書かもしれない)