shaitan's blog

長文書きたいときに使う．

本文と無関係なブログタイトルって見るたびに謎だったんだけど腑に落ちた。

自作数学問題bot 箱庭数学


席替えはいったん全員が席から立ち、一人ずつランダムに空いている席に座るとしてよい。
k番目に座る人をp(k)、その人が最初に座っていた席をs(k)、その席が空いていないことをa(k)と書く。
p(i) (i≦m)が最初と異なる席に座っている、という条件付のa(k)の確率をQ(i;j,n)と書く。
ここで、対称性よりQ(i;j,n)のj依存性はjがiより大きいかi以下かの二通りしかない。
Q(i;i,n)とQ(i;i+1,n)の大小関係を考える。
p(i)が座る前の状態ではa(i)とa(i+1)の確率は等しい。p(i)はs(i)には座らないがs(i+1)には座る可能性があるため、p(i)が座った後はa(i)の確率よりa(i+1)の確率のほうが大きい。
すなわちQ(i;i,n)＜Q(i;i+1,n)。
ここで、p(i)が座った後に空いていない席はi個であるから、i=iQ(i;i,n)+(n-i)Q(i;i+1,n)。
従ってQ(i;i+1,n)＞i/n。
よって、p(i) (i≦k)が全員異なる席に移っている状態で、p(k+1)がランダムに座ったときにs(k+1)に座らない確率q(k)は
{q(k)=Q(k;k+1,n)+(1-Q(k;k+1,n))\dfrac{n-k-1}{n-k}=\dfrac{Q(k;k+1,n)-1}{n-k}+1>1-\dfrac1n}。
これより、{\displaystyle P(n)=\prod_{k=1}^nq(k)>\left(1-\dfrac1n\right)^n\to\dfrac1e\quad(n\to\infty)}。
さて、Q(i+1;1,n+1) (i＜n)は、p(1)が座った後、この人および座った席を無視すればQ(i;i+1,n)と等しい。
ここで、{Q(i;i+1,n)=Q(i+1;1,n+1)<\dfrac{i+1}{n+1}}であることに気をつけると、
{q(k)=\dfrac{Q(k;k+1,n)-1}{n-k}+1<1-\dfrac1{n+1}}。
従って、{\displaystyle P(n)=\prod_{k=1}^nq(k)<\left(1-\dfrac1{n+1}\right)^n\to\dfrac1e\quad(n\to\infty)}。
はさみうちの原理により{\displaystyle\lim_{n\to\infty}P(n)=\frac1e}。

のってぃーちゃんのツイートが可愛かったので

自作数学問題bot 箱庭数学

のってぃーのっとちゃん*1(@knottyknot)のRTで自作数学問題bot(@mathquestionakt)の存在を知った。
解答もある。


ということなので、別解を考えることにします。

{f(n)=\dfrac{n!}{10^{n-1}}}とおく。
f(1)=1であり、n>1で{f(n)=\dfrac n{10}f(n-1)}より、
n<10でf(n)< f(n-1)、n≧10でf(n)≧f(n-1)。
従って1以外に1≦f(n)<10を満たすnは連続する数となる。
さて、22!を評価する（註１）。
{22!=2^{19}\cdot3^9\cdot5^4\cdot7^3\cdot11^2\cdot13\cdot17\cdot19}であり、
{7^2=49<50=5\cdot10}
{7\cdot11=77<80=2^3\cdot10}
{11\cdot13<12^2=2^4\cdot3^2}
{17\cdot19<18^2=2^2\cdot3^4}
なので、{22!<2^{28}\cdot3^{15}\cdot5^5\cdot10^2=2^{23}\cdot3^{15}\cdot10^7}。
さらに、{3^5=243<256=2^8}であるから、{22!<2^{47}\cdot10^7}。
ここで、{2^{50}=1.024^5\cdot10^{15}}<1.2\cdot10^{15}である（註２）から、{f(22)<\dfrac{12}8=\dfrac32<10}。
よって{f(21)=\dfrac{10}{22}f(22)<\dfrac{10\cdot3}{22\cdot2}<1}、
また、{f(24)=\dfrac{23}{10}\cdot\dfrac{24}{10}f(22)<\dfrac{23\cdot24\cdot3}{10\cdot10\cdot2}<10}。
今度は下から評価する。{7\cdot11=77>75=3\cdot5^2}であり、{49=50(1-0.02), 11\cdot13>12^2(1-0.02), 17\cdot19>18^2(1-0.02)}に注意して、
{22!>2^{18}\cdot3^{16}\cdot10^8(1-0.02)^3}。
{3^4=81>80=2^3\cdot10}であるから、{22!>2^{30}\cdot10^{12}(1-0.02)^3=\bigl((1+0.024)(1-0.02)\bigr)^3\cdot10^{21}>10^{21}}。
これよりf(22)>1, f(25)=2.5*2.4*2.3*f(22)>2.5*2*2*1=10。
以上を総合して、求めるnは1, 22, 23, 24である。

註１：
なぜ唐突に22なのかということの説明。
問題を見た感じ、結構きつい評価しないといけないっぽいし、なにより底が10なのでめんどくさそう。
というわけでひたすら計算することになるんだろうが、とりあえず見積もる。
Stirlingの公式より{\log(n!)\approx n\log\left(\dfrac n e\right)}+\dfrac12\log(2\pi n)でこれがn-1とnの間ってのが条件。
第一項からnは10eより小さく、このとき第二項は1程度。
{\log\left(\dfrac ne\right)\approx\dfrac{n-2}n\approx 0.9\approx\log8}ってことは2.7*8=21.6あたりを調べればよさそうだ！
実はStirlingの公式はぐぐったんだけども、さすがにn!が(n/e)^nくらいってことは覚えてる（ln(n!)=Σln(k)≒∫ln(x)dx=n*ln(n)-nなので）し、もうすこしちゃんと評価（lnが下凸なので台形近似でたぶんいける）すれば簡単な計算でそこそこの精度は出せるはず。

註２：
ここでなんか面倒な計算が出てしまって悩ましい。
{\displaystyle1.024^5<\left(1+\dfrac1{40}\right)^5=\sum_{k=0}^5\binom5k\dfrac1{40^k}<1+\dfrac18+\sum_{k=2}^5\binom52\dfrac1{40^2}<1+\dfrac6{40}=1.15}とでもするのが素直かと思ったが、ここで
{\displaystyle\left(1+\dfrac1{40}\right)^{40}=\sum_{k=0}^{40}\dfrac{40!}{k!(40-k)!40^k}<\sum_{k=0}^{40}\dfrac1{k!}<1+\sum_{k=1}^{40}\dfrac1{2^{k-1}}<3}より、{\left(1+\dfrac1{40}\right)^5<3^{\frac18}<1.8^{\frac14}<1.2}というのもなかなか楽しげでは？

*1:可愛い

京大特色入試と聞いて、を読んで、を書いて

箱庭数学

shaitan.hatenablog.com

問題の画像は新聞のなのでそのうち消えそうだと思って保存しとこうかと思ったけどぐぐったら書き写してる人見つけたのでいいや。
一応ざっと書いておくと、n個のコインを円周上に並べ、連続するk個をひっくり返す操作を行ってすべて表にすると終了、ってやつ。

問2と1は別解にするために無理やり変な解き方した感じなんだが、
2のほうでボツにしたアイデアも一応書いておこう。

【問2】
「図2が終了可能」⇔「図2に1回操作を行った110000が終了可能」。
必要な操作の最低回数が4回以上のとき、
M[i],M[i+3],M[j]を含む（jとiは3を法に合同でない）が、
これらの操作はM[j+3]と結果が同じなので、
それに変更するとより少ない回数で終了可能なので最小性に反する。
よって必要な操作の最低回数は3回以下。
110000だとひっくり返す総数が偶数回であることが必要なので終了可能ならば2回でできる。
ここで1回操作するのは6通りあるがこれらいずれも残り1回で終了可能でないので不適。

京大特色入試と聞いて、を読んで

箱庭数学

nloglogn.hatenablog.com


いつもの別解です。
なんかちゃんとした答案を書けなくなってるので概略のみ。コインの番号とかいい感じになってると思って下さい。


【問3】
操作の順序は関係なく、同一の操作の回数も偶奇しか関係ない。n種の操作のそれぞれを高々一回行うかどうかの2^n通りの一連の操作だけ考えればよい。
初期状態は2^n通りなので、「終了させられない初期状態が存在する」と「同一の初期状態を終了させる相異なる一連の操作A,Bが存在する」が同値。
さらに「その前後で状態が変化しないような一連の操作C（何の操作もしないものを除く）が存在する」とも同値（AとBのXORがC）。
Cは隣接した二枚のコインを裏返す回数の偶奇が等しいことが必要なので、i番目のコインからi+k-1番目のコインをひっくり返す操作（M[i]とする）が含まれるとすれば、M[i+k],M[i+2k],...,M[i+(n/m-1)k]も含まれる(mはkとnの最大公約数)。
これらn/m回の一連の操作を行うことをN[i]と書くと、CはN[i]を組み合わせた一連の操作である。
m>2のとき、N[0]とN[1]は相異なり、いずれもすべてのコインをk/m回ずつひっくり返す操作なのでAとBの条件を満たす。
m=1のとき、N[i]はどれも同じ(以下、単にNと書く)なので、Cが存在するとしたらNである。
Nはすべてのコインをk回ずつひっくり返す操作なので、kが偶数ならばこれはCの条件を満たし、kが奇数ならば満たさない。

以上をまとめて、求める必要十分条件はkが2nと互いに素であること。

【問2】
ある一連の操作とN[0]とN[1]のXORをとったものは異なる一連の操作でありいずれも結果は同じ。
N[1]とN[2]の場合、N[2]とN[0]の場合も同様なので、終了させられる初期状態は高々2^6/4=16通り。
以下、終了させられる初期状態を列挙する。
すべて表の状態およびすべて裏の状態（2通り）
すべて表の状態からM[i]を行ったもの（6通り）
すべて表の状態からM[i]とM[i+1]を行ったもの（3通り）
すべて表の状態からM[i]とM[i+2]を行ったもの（3通り）
すべて表の状態からM[i],M[i+1],M[i+2]を行ったもの（2通り）
これらは相異なり、図2はこれらのいずれとも異なるので終了させられない。

【問1】
7と3は互いに素なので終了できる。
(a)必要な操作の最小回数は高々7回。
(b)1回の操作により、隣り合うコインの表裏が異なるようなコインの隙間は高々2だけ増減するが、
初期状態はそのような隙間が6箇所あるので3回以上の操作が必要。
(c)リンク先と同様の議論により偶数回である。
(d)6回で終了できるのは連続する3枚のコインのみが表の状態であり、所与の初期状態とは異なる。
以上より4回。


問２の別アイデアはこちら。
shaitan.hatenablog.com

東大2010年前期理系問題1

箱庭数学 数学問題bot 
3辺の長さがaとbとcの直方体を，長さがbの1辺を回転軸として90°回転させるとき，直方体が通過する点全体がつくる立体をVとする．
(1)Vの体積をa,\ b,\ cを用いて表せ．
(2)a+b+c=1のとき，Vの体積のとりうる値の範囲を求めよ．

(1)
長さがbの1辺に垂直な平面で切った図形は，半径\sqrt{a^2+c^2}，中心角\dfrac\pi2の扇型にa,\ cを隣辺とする直角三角形を2つつけたものであるから，面積は\dfrac\pi4(a^2+c^2)+ac．
従ってVの体積はb\left\{\dfrac\pi4(a^2+c^2)+ac\right\}.
(2)
a+c=x,\ |a-c|=yとおくと0\leq y< x<1であり，体積W(x,y)はW(x,y)=(1-x)\left\{\dfrac\pi8(x^2+y^2)+\dfrac{x^2-y^2}4\right\}．
\pi>2よりy^2の係数は正であるからW(x,y)< W(x,x)．
相乗平均≦相加平均の関係より，W(x,x)=\pi(1-x)\left(\dfrac x2\right)^2\leq\pi\left\{\dfrac{(1-x)+\frac x2+\frac x2}3\right\}^3=\dfrac\pi{27}であり，等号成立はx=\dfrac23．
W(x,y)は体積であり0でないことと合わせて0< W(x,y)<\dfrac\pi{27}…☆が必要．
ここで，W(x,y)はx,\ yに関して連続であり，W(0,0)=0,\ W(\frac23, \frac23)=\frac\pi{27}であるからW(x,y)は☆の範囲の任意の値をとりうる．

東大2001年前期文系問題1

箱庭数学 数学問題bot 
白石180個と黒石181個の合わせて361個の碁石が横に一列に並んでいる．
碁石がどのように並んでいても，次の条件を満たす黒の碁石が少なくとも1つあることを示せ．

その黒の碁石とそれより右にある碁石をすべて除くと，残りは白石と黒石が同数となる．
ただし，碁石が1つも残らない場合も同数とみなす．

左からn個までの碁石のうち黒石であるものの数から白石であるものの数を引いた値をa_nとおく．
a_0=0-0=0なので「a_{k-1}\leq0ならばa_k\leq0」が常に成立すればa_{361}\leq0だがa_{361}=181-180=1より矛盾．
よってa_{k-1}\leq0かつa_k>0なるkが存在するが，a_nは1ずつ増減するのでa_{k-1}=0,\ a_k=1．
このとき，k番目の石は条件を満たす黒石である．

東大2000年前期理系問題1

箱庭数学 数学問題bot 
AB=AC, BC=2 の直角二等辺三角形ABCの各辺に接し，ひとつの軸が辺BCに平行な楕円の面積の最大値を求めよ．

適当なkを選び，この図形をBC方向にk倍，BCと垂直方向に\dfrac1k倍すれば楕円が円に移るようにする．
この円をOとおくと，Oの面積はもとの楕円の面積に等しい．
この変換で△ABCは円Oを内接円とする二等辺三角形Tに移り，Tの面積は△ABCの面積つまり1に等しい．
Oの半径r，Tの周長をsとおくと\dfrac{rs}2=1．
Tの三辺の長さをx,y,zとおくと，ヘロンの公式と相乗平均≦相加平均より1=\dfrac{\sqrt{s(s-2x)(s-2y)(s-2z)}}{4}\leq\dfrac{\sqrt s}4\cdot\sqrt{\left(\dfrac s3\right)^3}= \dfrac{s^2}{12\sqrt3}=\dfrac1{3\sqrt3r^2}.
等号成立はx=y=zのときで，このとき最初に施した変換と逆の変換を施せば確かに題意を満たす楕円が存在する．
従って求める面積の最大値は\pi r^2の最大値に等しく，\dfrac\pi{3\sqrt3}=\dfrac{\sqrt3}9\pi．