shaitan's blog

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

前の記事のタイトルは「インテル入ってる」の方が良かったかなって思った

自作数学問題bot 箱庭数学


2^(n+1)個の自然数をa[1]≦a[2]≦…≦a[2^n]≦b[1]≦b[2]≦…≦b[2^n]とおき、2≦a[2^n]であるとする。
Πa[k]≧a[2^n]≧2 (k=1,2,...,2^n。以下、総和および総積の範囲はこれと同じなので省略する。）。
2≦b[k]であるから、Πb[k]≧2^(2^n-1)b[2^n]≧2^(C[n,0]+C[n,1]-1)b[2^n]=2^nb[2^n]≧Σb[k]。(ただしC[i,j]は二項係数)
これらより、Σa[k]+Σb[k]≦2Σb[k]≦(Πa[k])(Πb[k])。
左側の等号成立にはΣa[k]=Σb[k]が必要である。
ここで、定義よりa[k]≦b[k]であるからこの等号がすべて成立している。
特にa[1]=b[1]≧2なのでΠa[k]≧a[2^n]*a[1]=4>2となり右側の等号は成立しない。
以上からΣa[k]+Σb[k]=(Πa[k])(Πb[k])のときa[2^n]=1、つまり任意のkについてa[k]=1。
従って、2^(n+1)個の自然数の和と積が等しいとき、少なくとも2^n個は1である。

299792458は9桁だったからダメだった

箱庭数学 自作数学問題bot

f(n)を以下のように定義する。
ある自然数nを一の位から3桁ごとに区切り、区切った3桁の数を「位が下だった方から」交互に足し引きしてできた数
例: 9192631770　→　9,192,631,770　→　770-631+192-9=322 なのでf(9192631770)=322。
（問題文の事象Aで計算される値とは符号が変わる場合があることに注意）

以下、mとnを7で割ったあまりが等しいことをm≡nと書くことにする。
「事象A⇔f(N)が7の倍数」に注意すると、f(n)≡nの成立を示せば十分。

n<1000のとき明らか。
n< kのとき成立を仮定し、
k=1000a+b　（0≦b<1000)とおく。
定義および仮定よりf(k)=f(b)-f(a)≡b-a。
また、k=1000a+b=1001a+b-a≡b-aであるからn=kのときも成立。
よって数学的帰納法により任意のnに対しf(n)≡n。

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

自作数学問題bot 箱庭数学

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は任意の自然数)

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

自作数学問題bot 箱庭数学

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は任意の自然数)。

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

自作数学問題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回で終了可能でないので不適。