【数セミ】エレガントな解答をもとむ3【2018.10】

**１３２人目の素数さん** · 2018/09/17(月) 01:40:43.02

締切りの過ぎた問題をみんなで議論しましょう。

過去スレ：
1. http://rio2016.5ch.net/test/read.cgi/math/1295154182/
2. http://rio2016.5ch.net/test/read.cgi/math/1476702312/

**１３２人目の素数さん** · 2020/08/07(金) 02:43:57.93

2^(1+1/n)/(2^(1/n) - 1) = 1 + (2^(1/n) + 1)/(2^(1/n) - 1) = 2 ＋ 2/(2^(1/n) - 1)

**１３２人目の素数さん** · 2020/08/09(日) 07:42:58.92

泥臭いやり方以外に解く方法あるのかね？

**１３２人目の素数さん** · 2020/08/09(日) 08:18:55.12

出題2解答
https://i.imgur.com/ngdKGdO.jpg

**１３２人目の素数さん** · 2020/08/09(日) 08:37:42.83

答えも見つけ方もネット見りゃ分かったけど、これしかアプローチが無いのはなんだかなあ

**１３２人目の素数さん** · 2020/08/09(日) 08:57:21.62

>>745はこうか？
https://i.imgur.com/do74soJ.jpg

**１３２人目の素数さん** · 2020/08/09(日) 09:00:12.84

コレ無理数度で解けた人いる？
μ^(x)=inf{ μ | inf {(p/q - x)q^μ | p/q>x }>0 }
μ_(x)=inf{ μ | inf {(x - p/q)q^μ | p/q<x }>0 }
とでもおいて出題2は
μ^(2/(log(2)) > 2
が示されれば十分なのはすぐわかる
ところでμ(x)=max{μ^(x), μ_(x)}はirrationality measureと呼ばれてコレの上からの評価を作るテクニックや結果は色々見つかるんだけど下からの評価、つまり「この無理数はこんないい有理数近似を持ってる」事を示す方の論文はあんまり見つからない
例えば􏰈􏰖 μ(2/log(2))
≦1-(1+ln(3+sqrt(8)))/(1+ln(3-sqrt(8)))
みたいのは出てくるんだけど反対向きが見つからない

**１３２人目の素数さん** · 2020/08/09(日) 09:35:29.14

泥臭いというかなんというか、

自然数kに対して
k<⌈2/(2^{1/n} -1)⌉
⇔ k < 2/(2^{1/n} -1)
(変形中略)
⇔ log(2)/2n < (log(k+2)-log(k))/2

k<⌊2n/log(2)⌋
⇔ k+1 ≦ 2n/log(2)

1/(k+1) < (log(k+2)-log(k))/2 < 1/k
だからどっかで差がつく、でよいのかな

**１３２人目の素数さん** · 2020/08/09(日) 10:42:16.87

大雑把にいうとこんな感じ？
2n/log2-2/(2^(1/n)-1)が「2n/log2の小数部分」よりも小さければ等号は成り立たなくなる。
前者は無限遠でフーリエ変換すると1-log2/(6n)+O(1/n^3)、後者は0,1間の擬似乱数みたいなもの。
だから、あるnで等号にならない確率はlog2/(6n)。この確率はnの桁が1増えると大体1/10倍だけど、
その桁に含まれる数も10倍だから、桁ごとに等号が成り立たないnが発見される確率はさほど変わらず、
だいたいlog2/6(1+1/2+...+1/9)=0.3268。もう少しちゃんと計算すると
log2/6 sum(n=10^k～10^(k+1)-1)1/nのk->∞を計算してlog2log6=0.266で、これ以上下がらない。
1つ桁を増やせば確率0.266で見つかるから、いずれどこかで見つかるよね。

まあ証明問題なら0点だけど、これを手掛かりに反例を1つ見つければ勝ちかな。

**１３２人目の素数さん** · 2020/08/09(日) 10:43:17.65

>>757
間違えた
×フーリエ変換
○テイラー展開

**１３２人目の素数さん** · 2020/08/09(日) 10:58:14.27

>>757
もう一つ訂正で、確率を足算しているから、見つかる確率ではなくその桁に等号が成り立たないnがいくつあるかの平均だな。

**１３２人目の素数さん** · 2020/08/09(日) 12:02:44.68

俺の直感ではもともと不成立
なんだか成り立つように見えて、果てしなく遠い数でようやく反例が見つかる
へたな計算機では誤差が生じて反例の確認すらままならないときた
エレ解の問題としては異端児すぎる

**１３２人目の素数さん** · 2020/08/09(日) 12:37:15.79

>>760
なんだよな
まぁ正則連分数表示を求めるアルゴリズム作って正則連分数近似の中から探すとかにすればややかっこよくなるだけで本質的に計算機で探すしかうまい手が見つからない
irratinality measureがらみなんだけどうえから評価でなくて下から評価であんまり研究が見つからない

**１３２人目の素数さん** · 2020/08/09(日) 16:27:13.36

>>752
n = 777451915729368;
2n/log(2) = 2243252046704767 - 0.0331107460500546… /n,
2/(2^(1/n) -1) = 2243252046704766 + 0.08241378404327… /n
　= coth(log(2)/2n) - 1,
辺々引いて
2/(2^(1/n) - 1) + 1 - 2n/log(2)
　= coth(log(2)/2n) - 2n/log(2)
　= (1/3)(log(2)/2n) - (1/45)(log(2)/2n)^3 + (2/945)(log(2)/2n)^5 - …　(マクローリン)
　= 0.11552453009332422 /n - …

**１３２人目の素数さん** · 2020/08/09(日) 17:15:38.73

>>954
n = 140894092055857794;
2n/log(2) = 406534415799078269 - 0.09254321204766 /n,
2^(1+1/n)/(2^(1/n) -1) = 406534415799078270 + 0.022981318045663 /n
　= coth(log(2)/2n) + 1,
辺々引いて
2^(1+1/n)/(2^(1/n) -1) -1 - 2n/log(2)
　= coth(log(2)/2n) - 2n/log(2)
　= (1/3)(log(2)/2n) - (1/45)(log(2)/2n)^3 + (2/945)(log(2)/2n)^5 - …
　= 0.11552453009332422 /n - …

**１３２人目の素数さん** · 2020/08/10(月) 02:52:35.01

ディリクレのディオファントス近似定理
　|qα-p| < 1/N,　0<q≦N
を改良して
　|qα-p| < 0.11552453/q,　0<q≦N
とできればよいのだが、それはかなり難しいようだ。

α = 1/(2^{1/n} -1) はn次方程式　2x^n - (x+1)^n = 0　の根
つまり n次の代数的数。
これについては次の予想があるので、改良は容易でない。

〔予想〕(Serge Lang)
　αが3次以上の代数的数で、k>1 ならば、
　　|qα - p| < 1/(q･log(q)^k),
　を満たす有理数 p/q は有限個しか存在しない。

**１３２人目の素数さん** · 2020/08/10(月) 16:14:45.55

今月の問題を見てゲンナリしたワタクシ

**１３２人目の素数さん** · 2020/08/10(月) 17:10:25.60

8月号問2から続けて3問似た系統の問題だな。
解き方は全然違うだろうが。

**１３２人目の素数さん** · 2020/08/10(月) 23:28:21.76

きょう出題１に応募したら859番でした。
今月は出題２でがんばろう。

**１３２人目の素数さん** · 2020/08/11(火) 00:33:20.69

でもこういう奴の方がある意味難しい
問題を解けるかどうかなんて解けて当たり前レベル
いかに“面白く”解けるかが問われる

**１３２人目の素数さん** · 2020/08/11(火) 19:10:02.88

確かに
時間をかければ誰でも示せるけどここではまさにエレガントな解答が求められているよね

**１３２人目の素数さん** · 2020/08/11(火) 21:46:40.89

敢えて論争を仕掛けて見るテスト

簡単な問題の解法をあれこれ工夫するのが好きか？
方法問わず難しい問題を解ききることに幸せを感じるか？

俺は後者。後者の問題こそ、思いもよらない解法が生まれやすい
「これしか解法ないだろ」と思って解くんだけど、みんな頭振り絞ってるせいか何通りも解法が出てきて仰天することが多々ある

**１３２人目の素数さん** · 2020/08/11(火) 21:56:17.42

>>770
本音を言うとちょい物足りん

**１３２人目の素数さん** · 2020/08/11(火) 23:06:28.99

>>771
だよね

**１３２人目の素数さん** · 2020/08/12(水) 00:01:12.72

8月号の出題2、この辺
https://oeis.org/A129935
を見ても一番小さい例外は 777451915729368 みたいなんだけど、正しいのだろうか。
>>757の考え方で行くとその数まで例外が無い確率って1.7%ぐらいなんだけど、
見落としはないのかなあ。

**１３２人目の素数さん** · 2020/08/15(土) 03:00:41.98

>>773
検証プログラム作成時

1より大きい無理数αに対し正規連分数の打ち切り近似有理数列ri(α)を
r0(α)=[α]、
r(i+1)(α)=[α]+1/ri(1/(α-[α]))
で定める

補題
任意の奇数iに対しri(α)はαの上からの近似であり、分母がri(α)の分母以下である任意の上からの近似の中で最良である
系
2/(2^(1/n)-1)の天井と2n/(log2)の床が一致しないものが存在するならば、その最小を与えるものはある奇数iについてri(2/log2)の分母として得られる自然数に限られる
主張
奇数iに対し
ri(2/log2)=p/q、
r(i+1)(2/log2)=r/s、
r(i+2)(2/log2)=t/u
とおく
1) qが反例を与えるには(p/q-2/log2)q^2<log2/6が必要である。特に
(p/q-t/u)q^2<log2/6‥①
が必要である
2)qが反例を与えるには(p/q-2/log2)q^2<log2/6-(log2)^3/360/q^2なら十分である。特に
(p/q-r/s+1/q^4)q^2<log2/6‥②
なら十分である
定理
最小の反例はr39(2/log2)の分母である
n= 777451915729368
である
∵) r1(2/log2)=3/1であるがn=1は明らかに反例を与えない
i:3～37である奇数に対し主張の①を満たすものはない
i=39のとき主張の②は満たされる

**１３２人目の素数さん** · 2020/08/15(土) 03:01:14.23

import Data.Ratio

-- 一般化連分数から有理数近似列を作成
fracs bs cs = id
$ map (head.fst)
$ iterate (\([[p,q],[p',q']],n) -> ([[(bs!!n)*p+(cs!!n)*p',(bs!!n)*q+(cs!!n)*q'],[p,q]],n+1))
$ ([[bs!!0,1],[1,0]],1)

rats bs cs = id
$ map (\[x,y] -> x%y)
$ fracs bs cs

-- 1/(log2) の一般化連分数の作成
bs = [1..]
cs = 0:(concat [[k^2,k^2] | k<-[1..]])

-- 有理数近似列から正規連分数の作成
makeRbs ratapxs = let
rcfsMain rs = let
apx1 = truncate $ rs !! 0
apx2 = truncate $ rs !! 1
newrs = map (recip.(+(-(fromInteger $ apx1)))) rs
in if apx1 == apx2
then (apx1:(rcfsMain newrs))
else rcfsMain $ tail rs
in rcfsMain ratapxs

-- 1/(log2) の正規連分数の作成
rbs = makeRbs $ drop 2 $ rats bs cs
rcs = repeat 1

-- 1/(log2) の正規連分数から有理数近似列を作成
rrats = map (*2) $ rats rbs rcs

-- 反例を与えるための必要条件 ind1<(log2)/6 と
-- 反例を与えるための十分条件 ind2<(log2)/6 の
-- 検証
tests = [ (k,ind1,ind2,n) |
k<-[1,3..],
let x = rrats !! k,
let y = rrats !! (k+1),
let z = rrats !! (k+2),
let n = denominator x,
let rn = fromInteger $ n,
let ind1 = fromRational $ (x-z)*rn^2,
let ind2 = fromRational $ (x-y+1/rn^4)*rn^2
]

main = do
mapM_ print $ take 20 $ tests

**１３２人目の素数さん** · 2020/08/15(土) 03:01:34.76

(1,0.1111111111111111,1.1428571428571428,1)
(3,0.28125,0.3074276462254604,9)
(5,0.2157303370786517,0.37955514726065,96)
(7,0.5604534005037783,0.778657718283889,445)
(9,0.1838388515860153,0.2907375803451737,794)
(11,1.0174722211315717,1.2252482805588467,4319)
(13,0.1773551664467339,0.19461297624934124,25469)
(15,0.6869730361965083,1.0463959311459805,287209)
(17,0.13674228263475482,0.18821662431664307,418079)
(19,0.7335370174413465,1.1584026182264542,3057423)
(21,1.0170018170613446,1.2245661504073762,8336111)
(23,0.19155865628150245,0.21960325986464296,24590254)
(25,1.4623220085717246,1.5494690343620314,385107953)
(27,0.2731271551989445,0.28278157095101175,6847196937)
(29,0.8922736690121698,1.6110001975243693,200557046245)
(31,1.1787446582422778,1.287114621424387,449541554817)
(33,0.210010870755119,0.23465044264678134,2669611999270)
(35,0.2248455561686892,0.40858063754648183,25423560120208)
(37,0.7271910471480607,0.7842187311800556,113071214541301)
(39,3.29262416686285e-2,3.524736840949706e-2,777451915729368)

**１３２人目の素数さん** · 2020/08/16(日) 02:41:58.19

>>774
コード間違ってた
1/log2正規連分数の打ち切り近似を2倍しても2/log2の正規連分数の打ち切り近似にはならん
コード直したらn=777451915729368はi=35での上から評価だった

import Data.Ratio

-- 一般化連分数から有理数近似列を作成
fracs bs cs = id
$ map (head.fst)
$ iterate (\([[p,q],[p',q']],n) -> ([[(bs!!n)*p+(cs!!n)*p',(bs!!n)*q+(cs!!n)*q'],[p,q]],n+1))
$ ([[bs!!0,1],[1,0]],1)

rats bs cs = id
$ map (\[x,y] -> x%y)
$ fracs bs cs

-- 2/(log2) の一般化連分数の作成
bs = 2:[2..]
cs = [0,2,1]++((concat [[k^2,k^2] | k<-[2..]]))

-- 有理数近似列から正規連分数の作成
makeRbs ratapxs = let
makeRbsMain rs = let
apx1 = truncate $ rs !! 0
apx2 = truncate $ rs !! 1
newrs = map (recip.(+(-(fromInteger $ apx1)))) rs
in if apx1 == apx2
then (apx1:(makeRbsMain newrs))
else makeRbsMain $ tail rs
in makeRbsMain ratapxs

-- 2/(log2) の正規連分数の作成
rbs = makeRbs $ drop 10 $ rats bs cs
rcs = repeat 1

-- 1/(log2) の正規連分数から有理数近似列を作成
rrats = rats rbs rcs
--rrats = map (*2) $ rats rbs rcs

-- 反例を与えるための必要条件 ind1<(log2)/6 と
-- 反例を与えるための十分条件 ind2<(log2)/6 の
-- 検証
tests = [ (k,ind1,ind2,n) |
k<-[1,3..],
let x = rrats !! k,
let y = rrats !! (k+1),
let z = rrats !! (k+2),
let n = denominator x,
let rn = fromInteger $ n,
let ind1 = fromRational $ (x-z)*rn^2,
let ind2 = fromRational $ (x-y+1/rn^4)*rn^2
]

main = do
mapM_ print $ take 18 $ tests

**１３２人目の素数さん** · 2020/08/16(日) 02:42:30.06

(1,0.1111111111111111,1.125,1)
(3,0.2571428571428571,0.3584995251661918,9)
(5,0.3645833333333333,0.5745868183338909,35)
(7,0.24181360201511334,0.2751801401822668,96)
(9,0.21822607876241706,0.22524981315418816,794)
(11,0.18275732576857484,0.19461297624934124,25469)
(13,0.15236871728780266,0.1584026182320683,418079)
(15,0.4463335352290383,0.8061415376018488,10975455)
(17,0.18006122736094865,0.21960325986464296,24590254)
(19,0.5385099766993894,0.5494690343620313,136566069)
(21,0.24775175562084492,0.3293483999092869,6847196937)
(23,0.36333931797114377,0.5706953927377529,27637329632)
(25,0.5300370170033072,0.6110001975243692,76064791959)
(27,0.6450755494730714,0.8217786553560967,574033809103)
(29,0.210010870755119,0.23465044264678134,2669611999270)
(31,0.2533250635740805,0.2900654933452463,25423560120208)
(33,0.5163505675436897,0.6960546827950139,200718868962394)
(35,3.29262416686285e-2,3.404729100026536e-2,777451915729368)

**１３２人目の素数さん** · 2020/08/17(月) 14:49:48.49

>>752 と一致したが････
エレガントとは思えませぬ。。。

**１３２人目の素数さん** · 2020/08/17(月) 15:11:38.97

>>779
存在するか？
なんだからそりゃ反例一個あげれば終わりでしょ？
>>774-778は>>773へのレスだよ
ホントにn<777451915729368までに解が存在しないか一個ずつ計算したらいかに計算機でも辛い
連分数のテクニック使わないとn=777451915729368が最小の反例は計算機使っても苦しいと思う

**１３２人目の素数さん** · 2020/08/18(火) 07:54:22.81

最良性が必要ってところが良くわからん

**１３２人目の素数さん** · 2020/08/20(木) 03:00:33.43

きょう出題２に応募したら869番でした。
今月は出題３でがんばろう（？）

**１３２人目の素数さん** · 2020/08/22(土) 00:19:25.54

そうなんだ

**１３２人目の素数さん** · 2020/08/26(水) 23:33:21.11

>>636
2020年3月号出題２
(別解)
n=7L かつ成分の中に1～7がL個ずつ現れるもの全体をAとする。
スターリングの公式から
　#A = (7L)!/(L!)^7 ～ k･(7^n)･n^(-3)･exp(-4/n),
　k = (√7)/(7/2π)^3 = 3.658504
ここで 0<c<7 とすると、じゅうぶん大きいnについて
　#A > c^n,
∴ c<7 で成立。

**１３２人目の素数さん** · 2020/08/26(水) 23:43:42.05

>>607 >>613-614
2020年4月号出題２

〔定理2〕
Sがn点のとき、これ以上線が曳けなくなるまでに
　min{ [2n/5], [3(n-1)/7] } 本の線が必要。
〔系〕
n≠1,3,8 の場合は　[2n/5] 本の線が必要。

**１３２人目の素数さん** · 2020/08/27(木) 00:25:19.89

>>622
2020年5月号出題２

〔補題〕
Xは問題の条件を満たす。{x_k}は単調増加としてよい。
　x_1<････<x_k<････<x_n,
このとき　k=1,2,････,n に対して
　x_1 + x_2 + ････ + x_k ≧ 2^k - 1,
(略証)
　{x_1,x_2,････,x_k} の部分集合は（空集合も含め）2^k 個ある。
要素の和は0以上の整数で、題意により互いに相異なる。
∴　最大のものは上記のとおり。　　(終)

　y_0 = 0
　y_k = Σ[j=1,k] (x_j - 2^{j-1}) = Σ[j=1,k] x_j - 2^k + 1,
とおけば、補題により
　y_k ≧ 0,　　　　　　(*)
これを使って
(2 - 2^{1-n}) - Σ[k=1,n] 1/x_k = Σ[k=1,n] (2^{1-k} - 1/x_k)
　= Σ[k=1,n] (x_k - 2^{k-1})/(2^{k-1}･x_k)
　= Σ[k=1,n] (y_k - y_{k-1})/(2^{k-1}･x_k)
　= Σ[k=1,n-1] y_k･(2_{k+1} - x_k)/(2^k･x_k･x_{k+1}) + y_n/(2^{n-1}･x_n)
　≧ 0,

(*)　x_j - 2^{j-1} ≧ 0 は不成立。
　　反例　n=4,　X = {3,5,6,7}

**１３２人目の素数さん** · 2020/08/27(木) 00:52:54.35

>>653-656
2020年6月号出題１

〔命題〕
nから始めて操作(1)(2)で１に辿り着かない条件は次のいずれか。
① 3の倍数
② すべての桁が奇数
③ 順不同で {1,1,1,4} または {1,1,1,8}
④　②,③を満たす数を、繰上りなしに何回か2倍して得られるもの

これらが１に辿り着かないことの確認は難しくない。
しかし逆は、次の補題を使っても難しい････

〔補題〕
　①～④を満たさないnを、うまく桁を入れ替えてから2で割れば
　②を満たさないようにできる。

**１３２人目の素数さん** · 2020/08/29(土) 02:08:57.84

>>785　訂正

×　　[ … ]　　これは floor(x)
○　　ceiling(…)

**１３２人目の素数さん** · 2020/09/06(日) 15:52:46.57

>>787
工夫と根気を試されてたな

**１３２人目の素数さん** · 2020/09/06(日) 15:59:37.41

出題2の3だけど、自然な構成では本質的に平方数が顔を出す。如何に不自然にするかがポイントらしいが、何のためにこんなことしなきゃならんのか分からなくなってきて落ち込んでる

**１３２人目の素数さん** · 2020/09/06(日) 16:03:12.56

エレガントな問題を来月に期待しよう
時弘先生や岡本先生の問題がやってくる季節

**１３２人目の素数さん** · 2020/09/09(水) 23:07:45.05

それは楽しみだ

**１３２人目の素数さん** · 2020/09/10(木) 07:14:35.69

>>791
時弘先生と岩沢宏和だったな。
岩沢の確率本には、他の本が書かないようなことが載っていて、個人的にはかなり面白い。

**１３２人目の素数さん** · 2020/09/10(木) 23:59:35.12

>>782
きょう出題１に応募したら941番でした。
今月は出題２でがんばろう。

**１３２人目の素数さん** · 2020/09/11(金) 02:21:07.75

2020年9月号

■出題１
やり方は色々ありそうですが、ストレートに計算してもできる。
bの方が平方根の形だから、aaを計算する。
　p = (7√11 + 3√3)^{1/3},
　q = (7√11 - 3√3)^{1/3},
とおくと pq = 8 で,
　p と qq, q と pp　が同類項にまとまるのがミソ。

aa = {7√11 + 8(p+q)}^2
　= 49･11 + 16(7√11)(p+q) + 64(p+q)^2
　= 16{(7√11)p+4qq} + 16{(7√11)q+4pp} + 49･11 + 128pq
　= 16p{7√11 + (1/2)q^3} +16q{7√11 + (1/2)p^3} + 539 + 1024
　= 24p(7√11 - √3) + 24q(7√11 + √3) + 1563
あとは3乗を計算する。
　= bb,
これと a>0, b>0 から a=b を示す。

出題：渋川元樹（略してシブキ？）

**１３２人目の素数さん** · 2020/09/11(金) 02:39:58.44

2020年9月号

■出題２ (1)
　A = √(N+1) + √(N - 1/2) + √(N - 1/2),
　B = √(N-1) + √(N + 1/2) + √(N + 1/2),
のとき
　3√N > A > B
を示す問題。（N = 333^2)

左側は　(二乗平均) > (相加平均)　で簡単。

右側は
　A - B = {√(N+1) - √(N-1)} - 2{√(N+1/2) - √(N-1/2)}
　　　　= 2/{√(N+1) + √(N-1)} -2/{√(N+1/2) + √(N-1/2)}
　　　　> 0,

∵　√(N+1/2) + √(N-1/2)　>　√(N+1) + √(N-1),
(略証)
　√(N+x) はxについて上に凸だから
　　√(N+1/2)　>　(3/4)√(N+1) + (1/4)√(N-1),
　　√(N-1/2)　>　(1/4)√(N+1) + (3/4)√(N+1),
　　辺々たす。
または
　{√(N+1/2) + √(N-1/2)}^2 - {√(N+1) + √(N-1)}^2
　= 2{N + √(NN -1/4)} - 2{N + √(NN-1)}
　= 2{√(NN -1/4) - √(NN-1)}　> 0,

あるいは
　g(x) = √(N+x)　とおき
　A - B = {g(1) + 2g(-1/2)} - {2g(1/2) + g(-1)}
　　= (1/4) g '''(r)　　　　　　　　(平均値の定理)
　　= (3/32)(N+r)^{-5/2}
　　> 0,

**１３２人目の素数さん** · 2020/09/11(金) 03:01:43.50

2020年9月号

■出題２
(2)　√2 + √z ≒ y
となる自然数 y, z を見つける問題。

　xx - 2yy = -1　ならば
　(xx +5 -4x)/2 = yy + 2 - (2√2)y - 2(x-y√2)
　= (y-√2)^2 + 2/(x+y√2),
∴　√2 + √{(xx +5 -4x)/2} = y + 1/{(x+y√2)(y-√2)} + … ≒ y,

　xx - 2yy = 1　ならば
　(xx +3 -4x)/2 = yy + 2 - (2√2)y - 2(x-y√2)
　= (y-√2)^2 - 2/(x+y√2),
∴　√2 + √{(xx +3 -4x)/2} = y - 1/{(x+y√2)(y-√2)} + … ≒ y,

なお「ペル方程式」
　xx - 2yy = (-1)^n
の解は
　x = {(1+√2)^n + (1-√2)^n}/2,
　y = {(1+√2)^n - (1-√2)^n}/(2√2),
で与えられる。

(3)
　工夫すれば色々できそう。

出題：阿賀岡

**１３２人目の素数さん** · 2020/09/12(土) 18:16:36.22

〔出題２〕
集団の人数やその友人関係は任意で、あらゆる可能性がある。
集団の人数とその友人関係、f(n) が一つ与えられたとき、
それに応じて
　「条件」をみたすように役員（定員なし）を選出する
ことが可能か？
ってことだろうな…

**１３２人目の素数さん** · 2020/09/13(日) 12:21:17.16

>>798
そうとしか読めんだろ。
役員0人は許されるのか？とは思ったが。

**１３２人目の素数さん** · 2020/09/19(土) 15:30:15.99

fの定義域が正の整数だから役員0人はだめってことなんだろうな

**１３２人目の素数さん** · 2020/10/06(火) 12:24:18.39

むずかしい

**１３２人目の素数さん** · 2020/10/11(日) 15:37:14.38

出題2完答できた人いる？
出題1は時弘先生の割には簡単だったか？

**１３２人目の素数さん** · 2020/10/12(月) 20:50:21.15

2020年10月号

■出題1
　たしかに易しめだが…
漸化式
　x ' = x(1-y) + yz,
と 0<y<1 から
　min{x,z} ≦ x ' ≦ Max{x,z}
はすぐ出る。（埼玉大学?）

この後のやり方は色々ありそうですが
線形問題に直すのもあり(？)
漸化式は
　↑x ' = (1-b)↑x + b↑z,
　↑y ' = (1-c)↑y + c↑x,
　↑z ' = (1-a)↑z + a↑y,
↑x/a = ↑y/b = ↑z/c　ならば、重心は変わらない。
　1-r ≦ {a,1-a,b,1-b,c,1-c} ≦ r,
なるrをとれば　△XYZ は縮小率 r 以下で縮小する。
n→∞ で　X｡Y｡Z｡の重心に収束する。
　出題：時弘哲治

**１３２人目の素数さん** · 2020/10/13(火) 21:13:34.02

>>803
スマートですな
絶対値の極限を考える方法もある
簡単過ぎもせず、エレガントな解答を競うにはうってつけの良問か

さて出題2
（1）はいいとして（2）は難しい
（3）に届かなかった人が多いと予想

**１３２人目の素数さん** · 2020/11/07(土) 20:23:16.93

締切ホルモンでラストスパート

**１３２人目の素数さん** · 2020/11/09(月) 15:13:17.19

反転幾何使うと何でもエレガントになる説

**１３２人目の素数さん** · 2020/11/11(水) 01:21:41.21

2020年11月号

■出題１
　⊿ABC が △A｡B｡C。よりずっと大きい場合、
それをさらに相似拡大すると、不成立？
相似縮小も含むと解すべきか？

(補正案)
⊿ABC を正三角形でない任意の三角形とする。
このとき、平面Π上の正三角形△A｡B｡C。と点P の組で、以下の条件
「 PA｡, PB｡, PC。の長さが辺BC, CA, AB の長さと順に等しい。」
をみたすものがただ二組（点PがΓの内側、点PがΓの外側、一組ずつ）存在する。

■出題2
　(i)　円周角の定理（とその逆）から出るらしい。
　　　P_ij 以外の交点(Q_ij)が ⊿ の内部か外部か周上かで場合分け。
　(ii)　お手上げ（反転幾何とか使うのかな？）

**１３２人目の素数さん** · 2020/11/11(水) 02:10:51.15

11月号出題１
　BC=a, CA=b, AB=c, ⊿ABC=S とおく。

・点PがΓの内側にある組
　2辺が b,c 挟角が∠A + 60°の三角形を描く。
　第二余弦定理より、対辺は　L = √{(aa+bb+cc + (4√3)S)/2},
　同様の3つの⊿の頂角の和は　∠A + ∠B + ∠C + 180°= 360°
∴　これら3つの⊿を組合せると、一辺 L の△になる。

・点PがΓの外側にある組
　2辺が b,c 挟角が |60° - ∠A| の三角形を描く。
　第二余弦定理により、対辺は　L' = √{(aa+bb+cc - (4√3)S)/2} > 0,
　同様にして、2つの⊿の頂角の和が、他の⊿の頂角。
∴　上記2つの⊿から他の⊿を引くと、一辺 L' の△が残る。

唯一性はどう示すか･･･

**１３２人目の素数さん** · 2020/11/11(水) 02:40:01.79

⊿ABCの各内角が120°より小さいとき、
フェルマー点をFとすれば
　L = AF + BF + CF = min{AQ+BQ+CQ | Q∈Π}
らしい。

文献
１．デボーヴ（M.Desboves）『平面幾何學研究法』増補6版, 冨山房 (1929)
　　　　　吉田好九郎譯　p.24
２．アメリカの数学オリンピック（USAMO 1974 [5]）

３．数セミ増刊「数学の問題」第２集, 日本評論社 (1978)
　●110　解説　図２

**１３２人目の素数さん** · 2020/11/12(木) 01:42:52.40

所与の3辺の比に対しPは正三角形の2辺で決まる2つのアポロニウス円の交点だから高々2点

**１３２人目の素数さん** · 2020/11/13(金) 17:51:16.89

チョト一般化してみた。

〔類題〕
⊿ABC を正三角形でない任意の三角形とする。
このとき、平面Π上の⊿A｡B｡C。と点Pの組で、以下の条件
「∠A｡, ∠B｡, ∠C。は所与の値。
　PA｡, PB｡, PC。の長さが辺BC, CA, AB の長さと順に等しい。」
をみたすものが二組存在する。

**１３２人目の素数さん** · 2020/11/13(金) 18:33:37.80

辺長が a'= BC sin(A｡), b'= CA sin(B｡), c'= AB sin(C｡) である三角形の
頂角を α,β,γ　面積を S' = S(a',b',c') とする。

・点PがΓの内側にある組
　2辺が AB, BC 挟角が β + ∠B。の三角形を描く。
　第二余弦定理などより、対辺は　2R sin(B｡)
ここに
　(2R)^2 = {sin(A｡)cos(A｡)BC^2 + sin(B｡)cos(B｡)CA^2 + sin(C｡)cos(C｡)AB^2 + 4S'}/{sin(A｡)sin(B｡)sin(C｡)},
　同様の3つの⊿の頂角の和は　180°+ 180°= 360°
∴　点Pの周りにこれらの⊿を並べれば、題意をみたす⊿A｡B｡C。になる。

・点PがΓの外側にある組
　2辺が AB, BC 挟角が |β - ∠B｡| の三角形を描く。
　第二余弦定理などより、対辺は　2R* sin(B｡),
ここに
　(2R*)^2 = {sin(A｡)cos(A｡)BC^2 + sin(B｡)cos(B｡)CA^2 + sin(C｡)cos(C｡)AB^2－4S'}/{sin(A｡)sin(B｡)sin(C｡)},

　同様にして、2つの⊿の頂角の和が、他の⊿の頂角。
　点Pの周りにこれらの⊿を重ねれば、題意をみたす⊿A｡B｡C。が残る。

[面白スレ３３．528-530]

**１３２人目の素数さん** · 2020/11/14(土) 03:23:42.84

出題文に「三次元への拡張など」とあるけど、どうするのかな？

(正4面体ではない) 任意の4面体ABCDから4つの距離a,b,c,dを取出す。(*)
このとき、正四面体 A｡B｡C｡D｡と点P の組で、以下の条件
「PA｡, PB｡, PC｡, PD｡が a,b,c,d に順に等しい。」
をみたすようなものが何組ある････とか

*) たとえば、頂点Aの対面BCDの周長をaとする(??)

**１３２人目の素数さん** · 2020/11/14(土) 11:31:59.47

>>813
それもアポロニウスの3円（球）を考えれば良さそう

**１３２人目の素数さん** · 2020/11/14(土) 21:30:06.74

>>812
面積で表わすなら
⊿A｡B｡C。= (1/2)(2R)^2 sin(A｡)sin(B｡)sin(C｡)
　= (1/2){sin(A｡)cos(A｡)BC^2 + sin(B)cos(B｡)CA^2 + sin(C｡)cos(C｡)AB^2 ± 4S'},
　S' = S(a' ,b', c')
かな

**１３２人目の素数さん** · 2020/11/19(木) 20:35:31.41

>>811
辺長が B'C'= BC･sin(A｡), C'A'= CA･sin(B｡), A'B'= AB･sin(C｡) である三角形の
頂角を ∠A'=α, ∠B'=β, ∠C'=γ とする。

・点PがΓの内側にある組
　辺C'A' の外側に、内角 A｡,B｡,C。の三角形を貼り付け、C'A'D' とする。
　∠D' = B。
　A'D' = CA･sin(C｡),　B'A' = AB･sin(C｡),　∠B'A'D' = α+A｡,
　B'C' = BC･sin(A｡),　C'D' = CA･sin(A｡),　∠B'C'D' = γ+C｡,

二辺が CA, AB で挟角が α+A。の三角形の対辺は x = B'D'/sin(C｡),
二辺が AB, BC で挟角が β+B。の三角形の対辺は y,
二辺が BC, CA で挟角が γ+C。の三角形の対辺は z = B'D'/sin(A｡),
　同様にして　x/sin(A｡) = y/sin(B｡) = z/sin(C｡)　(= 2R)
　これら3つの⊿の頂角の和は　180°+ 180°= 360°
　点Pの周りにこれらの⊿を並べてできる、辺長 x,y,z の⊿は題意をみたす。

・点PがΓの外側にある組
　辺C'A' の内側に内角 A｡,B｡,C。の三角形を貼り付け、C'A'E' とする。
　∠E' = B。
　A'E' = CA･sin(C｡),　B'A' = AB･sin(C｡),　∠B'A'E' = |α-A｡|,
　B'C' = BC･sin(A｡),　C'E' = CA･sin(A｡),　∠B'C'E' = |γ-C｡|,

二辺が CA, AB で挟角が |α-A｡| の三角形の対辺は x = B'E'/sin(C｡),
二辺が AB, BC で挟角が |β-B｡| の三角形の対辺は y,
二辺が BC, CA で挟角が |γ-C｡| の三角形の対辺は z = B'E'/sin(A｡),
　同様にして　x/sin(A｡) = y/sin(B｡) = z/sin(C｡)　(= 2R*)
　2つの⊿の頂角の和が、他の⊿の頂角。
　点Pの周りにこれらの⊿を重ねて残る、辺長 x,y,z の⊿は題意をみたす。

**１３２人目の素数さん** · 2020/12/07(月) 21:12:51.62

今更だけど10月号出題2の小問2と3解けた人いる？

**１３２人目の素数さん** · 2020/12/12(土) 22:33:04.01

思いもよらんかった

**１３２人目の素数さん** · 2021/01/08(金) 22:36:34.17

必ず相異なる点に収束するってところがみたせねえ

**１３２人目の素数さん** · 2021/01/09(土) 09:57:05.36

締切過ぎた
今月はパズル感が強めだったな

**１３２人目の素数さん** · 2021/01/09(土) 20:47:31.03

「A｡, B｡, C。が平面上の相異なる3点としたとき････」

だから　↑AB, ↑BC, ↑CA を不変にすれば

「点列 {A_n}, {B_n}, {C_n} は相異なる3点に収束する」んぢゃね？

一方で　「自明な漸化式を含まない」とあるから、

ABCの重心は別の点（例えば原点）に近付く希ガス

**１３２人目の素数さん** · 2021/01/09(土) 21:04:02.72

････というのは問２の⊿DEFの話でした。ｽﾏｿ

問１の方は ↑AB を一定しておいて、

　C_{n+1} = 2B_n - A_n

とかやるのかな

**１３２人目の素数さん** · 2021/01/10(日) 17:06:28.31

問2は三角形じゃなきゃだめかね？
全点x_i＝0, y_i＝i の相異なる6点から開始したらどうしようもなかろ？

**１３２人目の素数さん** · 2021/01/10(日) 20:19:56.31

「下図を得るような漸化式を…」と言ってて、その図では⊿なんだが…

６点が共線の場合も含む、と広く解釈するか
D｡, E｡, F。は⊿とする、と限定するか

**１３２人目の素数さん** · 2021/01/10(日) 22:05:16.01

一般には三角形になるんだけど、初期値によっては三角形にならないMがある。どんな初期値でも三角形になるか？823の例だと流石に無理だよね、って話

**１３２人目の素数さん** · 2021/01/13(水) 22:27:07.20

６点が共線の場合も含むと解釈すると、それを悪用していつでも共線化してしまう点列が問１と同様に作れてしまう
さすがにそれはなあと思う

**１３２人目の素数さん** · 2021/01/15(金) 00:41:35.87

>>826
問題を曖昧にして解答者の間口を拡げたとは考えられないか？考えられないかそうだよな
でも823は三角形にできんでしょ？こんな例はつまらんけど

**１３２人目の素数さん** · 2021/01/15(金) 00:49:03.78

ケーキカットは単純なロジックパズルで簡単だった
罠でもあったかな

**１３２人目の素数さん** · 2021/01/17(日) 05:08:41.58

２月号　出題２
　「ピタゴラス三角形」だと仰せなんだから
　上図の3行目は b=104, 4行目は c=157 と解するんだろうね。

(御老公はエクセルを使われないらしい…)

**１３２人目の素数さん** · 2021/01/17(日) 14:17:08.89

本当だ。間違ってるね。

**１３２人目の素数さん** · 2021/01/19(火) 00:52:17.75

「上の例のような8点の組」が (;(a,b)を交換した点も含む）必要は無い
に一票…

**１３２人目の素数さん** · 2021/01/20(水) 07:42:24.82

(a,b)交換しないなら a≒b もペル方程式も関係ないな…

**１３２人目の素数さん** · 2021/01/21(木) 07:42:11.57

「ピタゴラス三角形の一般的表現」て複素数の2乗みたいな式？

「レオナルド・ピサノの恒等式」とかいう

**１３２人目の素数さん** · 2021/01/25(月) 05:25:10.22

今月号の出題１は、10進数に限らず、一般化できそうだな。

**１３２人目の素数さん** · 2021/01/31(日) 23:17:48.78

出題2の円の中心は原点以外だよな？

**１３２人目の素数さん** · 2021/02/01(月) 13:56:17.53

う～む
出題文には「同一円周上に････」とあるだけで、中心の位置には言及してないが。

たとえば
　(a,b) = (63,16)　(60,25)　(56,33)　(52,39)　(39,52)　(33,56)　(25,60)　(16,63)
の８点は　原点を中心とする円周 (半径 c=65) 上にあるから
「正確に同一円周上には乗っていません」という条件に反してて
ダメだろうな....orz

**１３２人目の素数さん** · 2021/02/01(月) 17:37:53.67

「上の例のような」という条件に反してるんじゃない？

**１３２人目の素数さん** · 2021/02/01(月) 22:38:49.19

原点でいいなら簡単過ぎるし、2つの図は明らかに原点中心じゃないからな

**１３２人目の素数さん** · 2021/02/06(土) 18:38:21.05

そして解けない
もう原点中心でいいかなって

**出題１** · 2021/02/09(火) 04:42:51.84

一般化して、h進法で考える。
φ(t)をオイラーのトーティエント関数、
tが素数pのs乗で割り切れ、かつs+1乗で割り切れないとき
s=v(p:t)と書くことにする。
kはn^mをh進数で表記したときの桁数である。
log(x)は底がhの対数である。

任意の正の整数mに対して、
n^M≡n^m (mod h^k) M＞mをみたすMが存在するための、n,hの条件を考える。

hを以下のように書く
h=(nの素因数からなる積)・(nの素因数以外の素数からなる積)。
ここで、(nの素因数からなる積)=a、(nの素因数以外の素数からなる積)=bと置く。
Nを正の整数、とすると、
フェルマー・オイラーの定理より、n^{m+φ(b^k)・N}≡n^m　(mod b^k)
がいえる。

a=1のとき
M=m+φ(b^k)・Nとおくと、n^M≡n^m　(mod h^k)がいえる。

以降、a＞1とする。

aの任意の素因数pに対して、v(p:n^m)≧v(p:a^k)となるとき
明らかに、n^{m+φ(b^k)・N}≡n^m≡0　(mod a^k)
がいえる。
よって、M=m+φ(b^k)・Nとおくと、n^M≡n^m　(mod h^k)がいえる。

aのある素因数p'に対して、v(p':n^m)＜v(p':a^k)となるとき
v(p':n^M),v(p':a^k)＞v(p':n^m)より、n^Mとn^mは、mod a^kで等しくない。
(ただし、Mはmより大きな整数とする。)
したがって、n^M≡n^m　(mod h^k)とはいえない。

**出題１** · 2021/02/09(火) 04:50:47.18

以上を踏まえて、以下のようになる。

n＜hのとき
aの任意の素因数pに対して、v(p:n)≧v(p:a)となるとき
mlog(n)=log(n^m)≧log(h^{k-1})=(k-1)log(h)より
m＞(k-1){log(h)/log(n)}≧k-1よりm≧k-1+1=kがいえるから、
aの任意の素因数pに対して、
v(p:n^m)=m・v(p:n)≧k・v(p:a)=v(p:a^k)がいえるから、
>>840より、任意の正の整数mに対して、n^M≡n^m　(mod h^k)をみたす
整数M＞mの存在ががいえる。

aのある素因数p'に対して、v(p':n)＜v(p':a)となるとき
m=1のとき、任意の2以上の整数Mに対して、n^Mとnはmod h^kで合同にならない。
したがって、n^M≡n^m　(mod h^k)とはいえない。

n≧hのとき
aのある素因数p'に対して、v(p':n)≦v(p':a)となるとき
klog(h)=log(h^k)＞log(n^m)=mlog(n)より
k＞m{log(n)/log(h)}≧mよりk＞mがいえるから、
aのある素因数p'に対して、
v(p':a^k)=k・v(p':a)＞m・v(p':n)=v(p':n^m)がいえるから、
>>840より、n^M≡n^m　(mod h^k)とはいえない。

**出題１** · 2021/02/09(火) 06:47:02.97

n≧h、a＞1かつ、aの任意の素因数pに対して、v(p:n)＞v(p:a)となるとき
この場合は、上記のような一般論を展開するのは難しいです。

ただ、hがsquare freeの場合以下のように議論できます。

h^(s-1)≦n＜h^sをみたす整数sをとる。
aの任意の素因数pに対して、v(p:n)≧sとなるとき
h^(k-1)≦n^m＜h^(sm)よりk＝k-1＋1≦sm
がいえるから、
v(p:n^m)=m・v(p:n)≧sm、v(p:h^k)=kv(p:h)=kより
aの任意の素因数pに対して、v(p:h^k)≧v(p:h^k)がいえるので
>>840より、任意の正の整数mに対して、n^M≡n^m　(mod h^k)をみたす
整数M＞mの存在ががいえる。

aのある素因数p'に対して、v(p':n)＜sとなるとき
m=1のとき、任意の2以上の整数Mに対して、n^Mとnはmod h^sで合同にならない。
したがって、n^M≡n^m　(mod h^k)とはいえない。

**１３２人目の素数さん** · 2021/02/09(火) 23:59:34.65

出題2はまぁヒントというか縛りというかの意味がわかれば一瞬やな
1個目の例
中心　119+120i = (12+5i)^2
4点　153+104i = (13+4i)^2
　　 133+156i = (13+6i)^2
　　 85+132i = (11+6i)^2
　　 105+88i = (11+4i)^2
2個目の例
中心　240+238i = (17+7i)^2
4点　225+272i = (17+8i)^2
　　 253+204i = (17+6i)^2
　　 207+244i = (16+7i)^2
　　 275+252i = (18+7i)^2

どちらも中心α^2で4点が(α+ρ)^2, (α+ρi)^2, (α-ρ)^2, (α-ρi)^2, の形
このタイプで例1はρ=1+i、例2はρ=1
ρとして1+2iとか使っていいならρ=2+iも使えば簡単に8点作れるけど、多分禁止なんでしょう
となると例のようにy=xについて取り替えるしかない
それが許されるのは中心α^2が実部＝虚部に近くないとダメ
一例目ではy=x+1, 二例目ではy=x-2
つまりα=x+yiとおいてα^2=x^2-y^2+2xyiが実部＝虚部+k上にあるのは(x^2-y^2)-2xy = kの時だけどコレはペル方程式の形してるから基本解×基本単数^(2n)の形の解を無限に持つ

**１３２人目の素数さん** · 2021/02/10(水) 01:22:49.80

なるほど。4点ずつ同一円周に近づけて x⇔y ですか。
でも円の中心は |x-y| ≧1 ですから、
2つの円の中心は √2 以上離れてますよね。(傾き-1)
そうすると円周もそのぐらい離れるような････

4点ずつが同一円周にかなり近い、ということが却って、
8点が同一円周に近づくのを難しくする希ガス。

>>833
そのとおり。

**１３２人目の素数さん** · 2021/02/10(水) 07:39:28.87

>>844
まぁとは言え例示されてる例がその方法で作ってる8点で「このようにして作れ」なんだからしょうがないと思いますけどねぇ？
もちろんそれ以外の方法で実際に「同一円周上にない8点と中心“もどき”で“半径もどき”の差が0に近づく例」を見つけられればいいですけど
多分一松先生の気持ちとしてはy=x±constに件の格子点が無限にある事とかも気づいて下さいねっぽいのに、それをガン無視するのもどうなんだろうという気もする

**１３２人目の素数さん** · 2021/02/10(水) 15:25:12.43

その方法で「8点の組が、いくらでも正確に同一円周上の点列に近づく」例が見つかるのかなぁ。

**１３２人目の素数さん** · 2021/02/11(木) 20:46:23.10

P((α+ρ)^2) 　　　|α| >> |ρ|
とし、中心を
Q((1+ε)α^2),　　ε>0 (あとで決める)
とすると
|PQ|^2 = |(α+ρ)^2 - (1+ε)α^2|^2
　= |2αρ + (ρ^2 - εα^2)|^2
　= |2αρ|^2 + 2(|ρ|^2 - ε|α|^2)(αρ'+α'ρ) + |ρ^2 - εα^2|^2
ここで ε = |ρ/α|^2 とおくと中項が消えて
　= |2αρ|^2 + |ρ^2 - εα^2|^2
　≦ |2αρ|^2 + (|ρ|^2 + ε|α|^2)^2
　= |2αρ|^2 + 4|ρ|^4,

∴　|2αρ| ≦ |PQ| ≦ |2αρ| + |ρ^3/α|,

|ρ| を固定して |α| を大きくすれば、
いくらでも正確に同一円周上の点列に近づく。

**１３２人目の素数さん** · 2021/02/12(金) 00:12:11.80

OPが最大になるのは ρ/α>0 のとき
　P：　(1+√ε)^2 α^2,　　　････　遠日点
OPが最小になるのは ρ/α<0 のとき
　P：　 (1-√ε)^2 α^2　　　････　近日点
その中点
　Q：　(1+ε) α^2.

**１３２人目の素数さん** · 2021/02/13(土) 01:06:26.00

その2点の距離を直径2Rとすると
　R = (2√ε)|α|^2 = |2αρ|
∴　その2点は近地点でござる。

**１３２人目の素数さん** · 2021/02/13(土) 23:06:41.87

αとρの偏角の差δを使えば…
　δ = arg(ρ/α),
　ρ = α (√ε) e^{iδ},
と表わせるから
　P (α+ρ)^2 = {α (1 + (√ε) e^{iδ})}^2,
　Q (1+ε)α^2,

|PQ|^2 = |2αρ|^2 + |ρ^2 - εα^2|^2
　　= |2αρ|^2 + |(εα^2) (e^{2iδ} - 1)|^2
　　= |2αρ|^2 + |ρ|^4・| e^{iδ} - e^{-iδ} |^2
　　= |2αρ|^2 + |ρ|^4・| 2i sinδ |^2
　　= |2αρ|^2 + |ρ|^4・4 (sinδ)^2,

|2αρ| ≦ PQ ≦ |2αρ| + (|ρ|^3/|α|) (sinδ)^2,