2015-12-12

専用マグネットバー“くっつくん”は別売り商品です。

shaitan.hatenablog.com

m=nは明らか。
m< nのときm=ga, n=gb, (a< bは互いに素)とおく。
(ga)^n=(gb)^mよりg^(n-m)a^n=b^mだが、aとbは互いに素なのでa=1。
これを代入して両辺のm乗根をとるとg^(b-1)=b。
b>1よりg>1であり、 ${g^{b-1}=\displaystyle\sum_{k=0}^{b-1}\binom{b-1}k(g-1)^k\leq\binom{b-1}0+\binom{b-1}1=b}$ 。
等号成立はb-1=1かつg-1=1のとき、つまり(m,n)=(2,4)のとき。
m>nのときも同様なので、あわせて(m,n)=(2,4),(4,2),(k,k) (kは任意の自然数)

2015-12-11

箱ティッシュの最初に二組取れちゃうのがなんだかもったいない

自作数学問題bot 箱庭数学

(16) n^m=m^n (m、nは自然数)を満たすm、nの組み合わせを求めよ。
— 自作数学問題bot (@mathquestionakt) 2015, 12月 10

m=nは明らか。以下、m< nとする。
x>0で ${f(x)=x^{\frac1x}}$ とおく。f(n)=f(m)となる(m,n)を求めればよい。
${f'(x)=f(x)(\log f(x))'=\dfrac{f(x)}{x^2}(1-\log x)}$ であるから、
f(x)はx< eで単調増加、x>eで単調減少。
従って、f(m)=f(n)であるためにはm< e< nが必要。
このとき、f(n)>n^0=1=f(1)より、m=2。
よって、n^2=2^nなるn(>e)を求めれば良い。
n=4はこの条件を満たす。
x>eでf(x)は単調減少なので、f(n)=f(2)を満たすn>eは高々一つであるから他のnは条件を満たさない。
m>nも同様であるから、以上をまとめて求めるm,nの組み合わせは(m,n)=(2,4)(4,2)(k,k) (kは任意の自然数)。

2015-12-11

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

自作数学問題bot 箱庭数学

(2) n人で席替えをすることを考える。全員が異なる席へ移る確率をP(n)とする時、lim(n→∞)P(n)を求めよ。
— 自作数学問題bot (@mathquestionakt) 2015, 12月 10

席替えはいったん全員が席から立ち、一人ずつランダムに空いている席に座るとしてよい。
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}$ 。
これより、 $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}}$ 。
従って、 $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}$ 。

2015-12-10

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

自作数学問題bot 箱庭数学

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

【定期ツイ】このbotの全問題の解説を掲載しているサイトがあるのでこちらも参考にしてみてください。(このアカウントの管理人とは別の人のサイトです) https://t.co/Su7Gbjn4of https://t.co/gX7cuMg0Du
— 自作数学問題bot (@mathquestionakt) 2015, 12月 7

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

(1) 自然数nについて、n!がn桁になるとき、nの値として考えられる値を全て求めよ。
— 自作数学問題bot (@mathquestionakt) 2015, 12月 6

${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:可愛い

2015-12-01

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

箱庭数学

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回で終了可能でないので不適。

2015-11-30

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

箱庭数学

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

2014-06-28

東大2010年前期理系問題1

箱庭数学数学問題bot

3辺の長さがととの直方体を，長さがの1辺を回転軸として90°回転させるとき，直方体が通過する点全体がつくる立体をとする．
(1)の体積をを用いて表せ．
(2)のとき，の体積のとりうる値の範囲を求めよ．

(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)$ は☆の範囲の任意の値をとりうる．