読者です 読者をやめる 読者になる 読者になる

理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

京都大学の特色入試数学からつらつらと~その2~

Exam Math

前回の続きです.濃い目の2問が続きます.

第3問 コインのパズル

f:id:miwotukusi:20160214214937p:plain
f:id:miwotukusi:20160215014258p:plain
図は,ちょっと回転させたりしたものを描いてみました.

一部で,数学五輪級の問題だと言われた問題です.確かに,易しくはありません.
(1)左端にある表のコインに注目すると,線対称に表裏が並んでいることがわかります.ですので,ひっくり返せるパターンは限られてきます(線対称となるものは考えなくて良い).とすると,自ずと表にする手順が導き出せます.そして,それよりも少ない回数ではできないことも示さなければなりません.これがなかなか面倒くさい.
たとえば,左端のコインから時計回りに(表,裏,表,裏,裏,表,裏)と並んでいますが,これを(1,0,1,0,0,1,0)と表すことにします.すると,最小(と思われる)4回の操作は
 (1,0,1,0,0,1,0) 初期状態
→(1,1,0,1,0,1,0) 1回目
→(1,1,1,0,1,1,0) 2回目
→(1,1,1,1,0,0,0) 3回目
→(1,1,1,1,1,1,1) 4回目

と表されます.
ここで,コインに(a,b,c,d,e,f,g)と名前を付けておきます.そして,1回目としてひっくり返すコインを「b,c,dの3枚」「c,d,eの3枚」…と順にとってみると,1回目でとりうるパターンは以下のとおりとなります.
 「a,b,cの3枚」ならば,(0,1,0,0,0,1,0)
 「b,c,dの3枚」ならば,(1,1,0,1,0,1,0)
 「c,d,eの3枚」ならば,(1,0,0,1,1,1,0)
 「d,e,fの3枚」ならば,(1,0,1,1,1,0,0)
 「g,a,bの3枚」ならば,(0,1,1,0,0,1,1)

残りの2パターンは,すでにあるパターンと線対称になることから不要です.これで,1回ではできないことは明らかですし,2回でもできないこともわかります.さらに,2回目終了時,3回目でできる構成(連続した3枚だけが裏になっているパターン)はとれないので,結果3回以下ではできないと結論付けられます.


さて,最小となった4回の操作について,この数字の羅列を「縦」に見てみると,
・はじめ裏だったコイン(b,d,e,g)は,1回もしくは3回ひっくり返されている.
・はじめ表だったコイン(a,c,f)は,0回もしくは2回ひっくり返されている.

ということがわかります.「それぞれのコインがひっくり返される回数の総和」と「k×(k枚をひっくり返した回数)」が等しくなるということは当たり前といえば当たり前なのですが,意外と書き出せない内容だったりします.
そして,(3)では「ねらった1枚のコインだけをひっくり返す(残りのn-1枚のコインはもとの状態になる)」という操作ができるかを考えていきます.これはk=1ならなんてことないですが,k≧2となるとそれなりの条件が必要になってきます.そして,これができれば,裏となっているコインだけに,この操作を使いまくることで,すべてを表にできるわけです.
少し言い換えれば,

  • ねらった1枚のコインは,奇数回だけひっくり返され,
  • 残りのn-1枚のコインは,偶数回だけひっくり返される.

ということができるかを調べていくことになります.コインや石を扱うようなパズルでは,「必勝パターン」が存在するものがありますが,この問題もその類です.そして,その必勝パターンを使える条件を見つけだすことになります.


第4問 点列の存在有無(距離空間)

f:id:miwotukusi:20160214215000p:plain

 |x_n - x_m| + |y_n - y_m|は,「マンハッタン距離」と呼ばれる格子点間にて定義される距離になります.アメリカ映画(特に刑事もの)で,「2ブロック先で爆発!」というような言い回しがありますよね.たとえば,1ブロックの間隔が100メートルだったとしたら,その距離は 100|x_n - x_m| + 100|y_n - y_m|メートルと書けるわけです.
和式にいうならば,京都や奈良の「碁盤の目」での距離になります.


さて,(条件2)を少し書き換えてみると,
  \displaystyle{ \frac{1}{100} |n-m| -1 \leqq |x_n - x_m| + |y_n - y_m| }
 
となります.点列の間隔(n-m)が大きくなったら,点列間の距離もそれなりに離れているようになってね.という条件になります.
n-m=1000ならば,その点列間の距離は9以上に,n-m=100000ならば,その点列間の距離は999以上にならなければならないということです.P_1(x_1,y_1)P_{100001}(x_{100001},y_{100001})との間でもですし,P_{10000}(x_{10000},y_{10000})P_{110000}(x_{110000},y_{110000})との間でも成り立たなければなりません.
どうも
「このような点列:{Pn}はnが大きくなるにつれて,どんどんと離れていく(P_1から遠ざかっていく)ような配置にならなければならない」
ようです.スタート地点から離れるほど,どんどん遠ざかっていく.わたしの中では,ちょうど宇宙の膨張(ハッブルの法則)のようなイメージになっています.


(条件3)はわかりやすいです.
まずは,|x|+|y|=100というグラフを描いてみて下さい.きれいな形(回転させた正方形ですが,以後「ひし形」と呼びます)が浮かび上がりますよね.そのような「枠」の中に,点列が必ず存在するという条件です.上の表現を借りれば,「ある点(a,b)から東西南北へ100ブロック進むまでに必ずヤツらがいる」とも言えますし,ひし形の中心を点列(x_n,y_n)にとって考えることもできます.街(格子点)のどこに居ても,ある程度近いところにヤツら一味がいることを要請しており,もう少し言い換えると
「このような点列は,第一象限内である程度均等に存在しなければならない.」

ことを表しています.

f:id:miwotukusi:20160214233310p:plain


としたときに,これら2つの条件を満たす点列は存在するのでしょうか?という問いです.チョ~感覚的ですが,
均等に配置しようとすると,必ずどこかで「折り返してくる」必要がある.でも,折り返してしまうと,どんどん遠ざかるという条件が満たせなくなってしまう.
となり,どうも「存在しない」となりそうです.ただ,存在しないということを示すのは,確かに難しそうです.


ここでちょっと唐突ではありますが,第一象限内のすべての点を表すような点列を考えてみます.すると,以下のようなものが挙げられます.
Q1(1,1)
Q2(1,2), Q3(2,1)
Q4(1,3), Q5(2,2), Q6(3,1)

この点列は,まさしく群数列です.第p群は,x_n+y_n=p+1の直線上の格子点(x座標とy座標の和が一定となる点の集まり)として与えられます.このようにすると,第一象限内のすべての格子点を書き出す(覆い尽くす)ことができます.

【小問】この群数列の「第p群の第q番目」となる点の座標を表しなさい.

右辺の項を定数倍すれば,点列を等間隔で均等にばらまくことができます.たとえば,100倍すると,
Q'1(100,100)
Q'2(100,200), Q'3(200,100)
Q'4(100,300), Q'5(200,200), Q'6(300,100)

というように,全体では縦横100ごとに配置された点列を生み出すことができます.乗ずる数を変えれば,点の間隔を自在に変えられ,均等に第一象限内に点をばらまくことができます.何か使えそうな感じはするのですが,ピンときていません.こういう考え方もあるよ.ぐらいにとらえてもらえればと思います.

f:id:miwotukusi:20160214234746p:plain


上では,条件2を2点間の距離に関する条件として書きましたが,
 |n-m| \leqq 100 \cdot (|x_n-x_m| + |y_n-y_m|) + 100 \\
n - \{ 100 \cdot (|x_n-x_m| + |y_n-y_m|) + 100 \} \leqq m \leqq n + \{ 100 \cdot (|x_n-x_m| + |y_n-y_m|) + 100 \}

と変形することで,
「点Pn(x_n,y_n)を固定し,その点を中心としたひし形をとるとき,そこに含まれている点Pm(x_m,y_m)の個数を与えている」

ととらえることもできます*1.「点Pnから一定の距離の中に,どのくらいの数の点列が存在するのか」を表してくれます.
たとえば,

  • P_nを中心とした縦・横ともに2のひし形には,|n-m| \leqq 100 \cdot 1 + 100 = 200より,P_{n-200}からP_{n+200}が含まれていることになります.
  • P_nを中心とした縦・横ともに2000のひし形には,|n-m| \leqq 100 \cdot 1000 + 100 = 100100より,P_{n-100100}からP_{n+100100}が含まれていることになります.

これらPmを中心としたひし形も用いて,もとの大きなひし形を覆いつくすことができるか(できないだろぉ~)ということを示すことで,矛盾を引き出すことができます*2

この問題が一番難しいのではないでしょうか?矛盾を引き出すために,与えられた条件を図形的に読み解き切る必要があり,さらに自分で別の数列や特定の範囲(ひし形)といった枠を作らないといけません.試行錯誤の先の発想力を問う問題だったんでしょうね.


前半の2問と後半の2問で、ちょっと問題の色合いが違いますね。前半の2問程度であれば,通常の2次試験で出てきてもおかしくないのかなと思います.

*1:|x_n-x_m| + |y_n-y_m|が点P_nと点P_mの距離を与えているから

*2:ひし形を巨大にすると,覆いつくせなくなることがわかります