面白い問題おしえて～な二十二問目©2ch.net

**１３２人目の素数さん転載ダメ©2ch.net** · 2016/05/29(日) 20:27:46.04

**１３２人目の素数さん** · 2017/04/02(日) 09:50:40.40

>>591
いや、>>587に回答したんだが

**１３２人目の素数さん** · 2017/04/02(日) 11:39:01.55

>>589
4手目で{1,3,5}のとき先手必勝じゃね？

**１３２人目の素数さん** · 2017/04/02(日) 12:15:07.22

>>589
やっぱりn=20は無理だ
2手目で{4,5,5}のとき後手は勝てない

**１３２人目の素数さん** · 2017/04/02(日) 12:46:23.59

先手が４に置けば後手は４をすべてなくせる。
先手が５に置けば後手はもう一つの５の同じ所に置けばいい。

**１３２人目の素数さん** · 2017/04/02(日) 13:34:03.64

後手必勝のパターンを合体させたらまた後手必勝
{4}も{5,5}も後手必勝だから{4,5,5}も後手必勝

また、同じパターンを２つ組み合わせたものも後手必勝
例：{3,3,7,7,7,7,10,10,100,100}

1と2だけを偶数個組み合わせたものも後手必勝
例：{1,1,1,2,2,2,2,2}

**１３２人目の素数さん** · 2017/04/02(日) 14:30:56.16

ある配置パターンについて1手の操作は以下のいずれか
(1) 1～3を1つ削除する
(2) 3以上の数のうちの1つから2を引く
(3) 4以上の数のうちの1つから3を引く
(4) 5以上の数のうちの1つから3を引いてそれを2つの自然数に分解する

{}を後手必勝パターンとして、以下の漸化式的なルールで先手必勝か後手必勝かが決まる
・そのパターンから1手でたどり着くパターンのうち1つでも後手必勝があれば先手必勝
・そのパターンから1手でたどり着くパターンが全て先手必勝であれば後手必勝

碁石を置ける場所の個数N毎に後手必勝パターンを全て挙げていくと
N=1：なし
N=2：{1,1}
N=3：{1,2}
N=4：{4},{2,2},{1,1,1,1}
N=5：{1,1,1,2}
N=6：{3,3},{1,1,4},{1,1,2,2},{1,1,1,1,1,1}
N=7：{1,6},{1,2,4},{1,2,2,2},{1,1,1,1,1,2}
以下略
まあ、そんなに簡単に一般的な規則性は見つからないよね

**１３２人目の素数さん** · 2017/04/02(日) 14:50:40.94

>>596
後手必勝パターンと先手必勝パターンを合体させたら先手必勝ってのもいえるな。
（規則性を見出すのには役に立たない知見ばかりだが）

**１３２人目の素数さん** · 2017/04/02(日) 15:33:37.55

>>593
6手目で{1,2},{3,3},{1,1,1,1}のいずれかにできるので後手勝利。
>>594は>>595の通り。

>>586が正しいのであれば、おそらくグランディー数も周期34でループするんだろう。
証明は、計算が面倒なだけで地道にやればできそうだ。
面倒だからやらないが。

**586** · 2017/04/02(日) 17:45:54.94

プログラムは長くないので貼っておく。言語は Python3
周期性は、あるところからある程度周期的なら、それ以降ずっと周期的であることが
帰納法で証明できるね

def mex(s):
　　import itertools
　　for i in itertools.count():
　　　　if i not in s:
　　　　　　return i

g = [0, 1, 1]

def grundy(n):
　　global g
　　if n < len(g):
　　　　return g[n]
　　for m in range(len(g), n+1):
　　　　s = {g[k] ^ g[m-3-k] for k in range((m-1)//2)} | {g[m-2]}
　　　　g.append(mex(s))
　　return g[n]

#グランディ数
print(list(enumerate(map(grundy, range(100)))))
#後手必勝となるn
print([n for n in range(200) if grundy(n) == 0])
#周期34からはずれるn
print([n for n in range(1000) if grundy(n+34) != grundy(n)]) #[14, 16, 31, 34, 51]

**１３２人目の素数さん** · 2017/04/03(月) 22:30:58.02

【問題】
単位体積の正四面体Tと、Tの内部の点Pを考える。
点Pを通り、Tの4つの面に平行な4枚の平面によって、Tを14個の小片に分割する。
これらの小片のうち四面体でも平行六面体でもない小片すべての体積の和をf(P)とおく。
点PがTの内部を動くとき、f(P)のとる値の範囲を求めよ。

**１３２人目の素数さん** · 2017/04/04(火) 02:14:05.08

>>601
正四面体をOABCとし、
↑OP=x↑OA+y↑OB+z↑OCとすると、
x＞0，y＞0，z＞0，x+y+z＜1
w=1-x-y-z、正四面体の１辺の長さをaとする
14個の小片のうち
１面が元の正四面体の1つの面に含まれる正四面体が4つあり、
　それぞれの１辺はxa,ya,za,wa
１つの頂点を元の正四面体と共有する平行六面体が4つあり、
　それぞれの1つの頂点に集まる3辺の長さの組は
　{xa,ya,za},{ya,za,wa},{za,wa,xa},{wa,xa,ya}
他の6つは正四面体でも平行六面体でもない。

f(P)=1-(x^3+y^3+z^3+w^3)-6(xyz+yzw+zwx+wxy)

まずはここまで

**１３２人目の素数さん** · 2017/04/04(火) 03:52:18.85

0＜f(P)＜3/4
f(P)が0に近づくのはPが正四面体の頂点に近づくとき
f(P)が3/4に近づくのはPが正四面体の各辺の中点に近づくとき

**１３２人目の素数さん** · 2017/04/04(火) 13:33:54.65

>>603
正解
以下解答
http://i.imgur.com/KLnI8Ax.png

**１３２人目の素数さん** · 2017/04/05(水) 20:58:35.12

【問題】
荷造り用のPPバンドを6本用いてセパタクローボールを作ることができる。
この6本の帯の色がすべて異なるとき、異なるパターンのボールは何通りできるか。

※セパタクローは東南アジアの球技であり、使用するボールは準正32面体の形をしている。
3本の帯はすべての箇所で三すくみの関係になっていてほどけず、各帯は大圏コースを通る。
空洞部分は正五角形をしている。
http://i.imgur.com/Q0aK0Vx.jpg

**１３２人目の素数さん** · 2017/04/05(水) 23:36:57.05

>>605
１つのボールの中では、３つのバンドが１点で接する20箇所の重ね方は全て同じなので
６つのバンドが同じ色なら作り方は鏡像の２通り
そのうちの１つを６色のバンドで作ると、１つのバンドに着目して
残りの５本がそのバンドの上に重なる箇所の配置を考えると、５箇所のじゅず順列となるので
4!/2=12通り

よって、鏡像も含め12×2=24通り
（ルール上鏡像が許されないなら12通り）

**１３２人目の素数さん** · 2017/04/14(金) 03:02:25.56

２次元上で、n個の単位円を内部に含むように紐を巻くときの最小の長さを考える。
ただし円は重ならないように。
1個のときは、2π
2個のときは、2π+4
3個のときは、2π+6
4個のときは、2π+8
n=5、6のとき、紐の最小値は？

**１３２人目の素数さん** · 2017/04/14(金) 12:07:46.39

>>607
証明はできてないけど
n=5のとき　2π+10
n=6のとき　2π+8+2√3
かな

**１３２人目の素数さん** · 2017/04/14(金) 15:29:30.16

>>608
正解。n=6のときの答えが自分では思いつかなかった。
発展問題として、2π+2n よりも小さくなる n (≧7)を見つけてみてください。

**１３２人目の素数さん** · 2017/04/14(金) 20:02:42.62

n=7がいきなり答え。
n≧9の長さは難しいね。

**１３２人目の素数さん** · 2017/04/15(土) 02:52:32.89

n≧7 なら、n-1 個の円を円形に並べて内側に１個置けば
2π+2(n-1) にはなる

**１３２人目の素数さん** · 2017/04/15(土) 11:43:17.54

n=9で　2π+12+2√3　より短い方法ってあるのかな？

**１３２人目の素数さん** · 2017/04/15(土) 11:52:23.30

>>612
どんな風に並べたん？

**１３２人目の素数さん** · 2017/04/15(土) 12:02:46.66

n=4のときの見た目って、正方形に積むのと、正三角形状に２つ積むのとで同じ長さだよね？

**１３２人目の素数さん** · 2017/04/15(土) 12:32:38.34

n=7　2π+12
n=8　2π+14
n=9　2π+12+2√3
n=10　2π+16
n=11　2π+14+2√3
n=12　2π+18
n=13　2π+16+2√3
n=14　2π+20
n=15　2π+18+2√3
n=16　2π+22
n=17　2π+16+4√3
n=18　2π+20+2√3
n=19　2π+24
あたりがとりあえずの候補か。
ここから先はかなり混沌としてくる悪寒

**１３２人目の素数さん** · 2017/04/15(土) 12:35:15.39

circle packing問題の解のときに紐の長さも最小になる？

**１３２人目の素数さん** · 2017/04/15(土) 12:36:41.79

>>613
○○○
.○○○
○○○

**１３２人目の素数さん** · 2017/04/15(土) 12:39:46.68

>>616
それは違うと思う

**１３２人目の素数さん** · 2017/04/15(土) 12:52:58.97

TeXとemathでn=4まで描いて疲れた。
http://i.imgur.com/R3kSxbX.jpg

**１３２人目の素数さん** · 2017/04/15(土) 13:32:20.94

n=6まで描いたお。疲れたわ
http://i.imgur.com/vl31LNr.jpg

n=7のときは、正三角形状にぎっしり詰めればええんやね。
n=8のときは？

**１３２人目の素数さん** · 2017/04/15(土) 13:40:01.44

よく考えたら、n=6のときは、もっと短くない？

**１３２人目の素数さん** · 2017/04/15(土) 13:51:37.06

勘違いだった。絵も間違ってるな

**１３２人目の素数さん** · 2017/04/15(土) 14:36:53.04

計算する前に、丸鉛筆と輪ゴムでやってみよう。

**１３２人目の素数さん** · 2017/04/15(土) 15:05:19.95

ちょっくら文房具屋行ってくる

　　　　　　／|
　　　　　_/⌒)A
　　＿／/三///＼＿
　∠＿_∥∥//＿＿_＞
- - -∠◎◎_＞ + - -
ﾆ +-／////ｉﾆ - ﾆ +-
三三三＿三三_三_三三
////////////////////

**１３２人目の素数さん** · 2017/04/15(土) 20:38:18.49

>>615
難しいね

**１３２人目の素数さん** · 2017/04/15(土) 21:10:08.67

n=1　 2π 　　
n=2 　2π+4 　4をたす
n=3　 2π+6 　2をたす
n=4 　2π+8 　2をたす
n=5 　2π+10 2をたす
n=6　 2π+8+2√3 　約1.46をたす
n=7　 2π+12 　　約2.54をたす
n=8　 2π+14 　　2をたす
n=9　 2π+12+2√3 　約1.46をたす
n=10　2π+16 　　　約2.54をたす
n=11　2π+14+2√3 　約1.46をたす
n=12　2π+18 　　　約2.54をたす
n=13　2π+16+2√3 　約1.46をたす
n=14　2π+20 　　　約2.54をたす
n=15　2π+18+2√3 　　約1.46をたす
n=16　2π+22 　　　　約2.54をたす
n=17　2π+16+4√3 　約0.93をたす
n=18　2π+20+2√3 　約2.53をたす
n=19　2π+24 　　　約2.54をたす

**１３２人目の素数さん** · 2017/04/15(土) 23:04:38.87

2.54と書いてあるところは全部0.54な

**１３２人目の素数さん** · 2017/04/15(土) 23:22:01.80

>>620
その図のl_6だと2π+5√(10-2√5)となり、2π+8+2√3より長い。
正解はこんな感じ

**１３２人目の素数さん** · 2017/04/22(土) 19:46:36.56

三辺の辺長が全て有理数で面積が自然数の直角三角形のうち、周長が最小のものを見つけよ。
無理ならば、12より短いものをいくつか見つけよ。

**１３２人目の素数さん** · 2017/04/23(日) 21:38:59.94

>>629
とりあえず１つ見つけた
３辺の長さが 7/2，145/42，97/21
面積 6
周の長さ 81/7 = 11.5714…

**１３２人目の素数さん** · 2017/04/23(日) 21:53:32.00

三角形の３辺も面積も有理数なら、その頂点から対辺に下ろした垂線で
分割される２つの直角三角形の各辺も有理数であることが示せる。
よって、逆に２つの３辺が整数の直角三角形（ピタゴラス数）を組み合わせてできる
３辺が整数で面積も整数の三角形の各辺を、面積の平方因子の平方で割ったものが
求める周長が最小のものの候補となる。

>>630の例は、２つのピタゴラス数
(97,65,72)と(145,17,144)から、前者を2倍に拡大したものと後者を組み合わせて
できる３辺が(147,145,194)の三角形（底辺を147とすると高さ144）を
1/42に縮小したもの

**１３２人目の素数さん** · 2017/04/23(日) 21:56:48.97

それ、直角三角形？

**１３２人目の素数さん** · 2017/04/23(日) 22:35:31.86

あ、直角三角形か…w

まあ、直角三角形という条件を外したものの方が難しそうだからそっちもよろしく。

**１３２人目の素数さん** · 2017/04/24(月) 02:20:25.30

>>629
互いに素なピタゴラス数は、一般に
互いに素で偶奇の異なるm＞nなる自然数の組(m,n)を用いて
(m^2+n^2, m^2-n^2, 2mn)と表される。
よって、３辺の長さがいずれも有理数の直角三角形の３辺は
このm,nと自然数kを用いて
((m^2+n^2)/k, (m^2-n^2)/k, 2mn/k)と表せる
このとき、周長はL=2m(m+n)/k
ここで、面積をS=mn(m+n)(m-n)/k^2とおくと、
k^2=mn(m+n)(m-n)/S
∴ L^2=4Sm(m+n)/(n(m-n))
ここで、m>nより、x=m/n-1（＞0）とおくと
L^2=4S(x+1)(x+2)/x=4S(3+x+2/x)≧4S(3+2√2)
となる。（実際は、等号成立条件x=√2が成り立たないので、等号は成立しない）
なお、面積Sが整数なので、k^2は1またはmn(m+n)(m-n)の平方因子である。
(m,n,k)=(2,1,1)のとき、S=6，L=12となる。
S≧7のとき、L＞√(28(3+2√2))=12.7748…なので、
L≦12となるためには、S≦6であることが必要条件となる。

**１３２人目の素数さん** · 2017/04/24(月) 03:02:36.09

>>634 続き
ある(m,n)に対してLをなるべく小さくするには、Sをなるべく小さくとる必要があるので、
以下k^2はmn(m+n)(m-n)の最大の平方因子とする。
自然数m,nは互いに素で偶奇が異なりm＞nをみたすので、
m, n, m+n, m-nは、どの２つをとっても互いに素な自然数である（証明略）
よって、S=mn(m+n)(m-n)/k^2は、
m, n, m+n, m-nのそれぞれを最大の平方因子で割ったものの積となる。

以下、
(1) m, n, m+n, m-nのいずれも平方数となることがあるか
(2) m, n, m+n, m-nのうちの３つが平方数となり、
　残る１つをその平方因子で割ったものが6以下となることがあるか
(3) m, n, m+n, m-nのうちの２つが平方数となり、
　残る２つをその平方因子で割ったものの積が6となる(m,n)の組のうち、
　2n＜m＜3nとなるものがあるか
を検討していくことになる。

あとは任せた。

なお、(m,n,k)=(2,1,1)以外でSがなるべく小さくなるものを探すと、
例えば(m,n,k)=(16,9,60)とするとS=7となり、そのときL=40/3=13.333…となる。

**１３２人目の素数さん** · 2017/04/24(月) 03:18:14.41

細かいロジックのバグ修正。
>>634 で、
　３辺の長さがいずれも有理数の直角三角形の３辺は
　このm,nと自然数kを用いて
　((m^2+n^2)/k, (m^2-n^2)/k, 2mn/k)と表せる
と書いたが、
実際は、３辺の長さが(m^2+n^2, m^2-n^2, 2mn)の直角三角形の面積が
mn(m+n)(m-n)と自然数となることから、この三角形と相似で面積が自然数、各辺が整数
となる三角形のうち「最も小さいもの」の３辺が、
ある自然数kを用いて上記のように表せる、というのが正解。
（最も小さいという条件がないと、それらをさらに整数倍したものを除外できない）

**１３２人目の素数さん** · 2017/04/24(月) 16:30:07.87

>>629

斜辺を除く二辺が、互いに素なp,qを用いて p/q, 2nq/p と表される時(つまり面積がnの場合)

l^2 = (p/q)^2 + (2nq/p)^2 であるから、
(pql)^2 = p^4 + 4n^2q^4
より、右辺はqの素因数を持たないので、q=1 となる。

同様に、右辺がpの素因数を持つならば2nの素因数でもあるから、小さい数からしらみつぶしに調べるとnの最小値は6とわかる。(3,4,5の三角形)

n≧7 の時、周の長さは少なくとも
2√n + √(2n)
≧2√7 +√14
>12
より大きいので、(3,4,5)の長さ12が最小。

**１３２人目の素数さん** · 2017/04/24(月) 16:32:37.74

>>637
ごめんこれlが整数の場合しか調べてないね吊りたい

**１３２人目の素数さん** · 2017/04/24(月) 20:38:39.79

>>638
　　　　　　　　　　　,　-,　　　
　　　　　　　　　 ,'ヽ,','　　　カッパえびせんやるから落ち着けよ
　　　　　　　　　,'ヽ,','
　　　　　　　　　 ,'ヽ,','
　　　　　　　　　,'ヽ,','
　　　　　　　／)、,,','ヽ
　　　　　　／／　　 }　|`i､
　　　　　　l　`ー‐'" ／　l }
　　　　　　|　　　　　　　／
　　　　　　|　　　　　／

**１３２人目の素数さん** · 2017/04/24(月) 22:57:42.27

おそらく最もシンプルで、周長もかなり小さい、ある三角形の周長の分母
186
です。629の出題者より。

**１３２人目の素数さん** · 2017/04/25(火) 00:58:15.44

>>634のxを√2に近づければいいんじゃないの？
連分数展開を打ち切って有理近似にすれば。

**１３２人目の素数さん** · 2017/04/25(火) 01:02:34.77

>>640
>>634 >>635の理屈だと
kは186=2*3*31の倍数なので、
m,n,m+n,m-nのうちのいずれかが31^2=961の倍数になるのだが、
それで、各数の平方因子を除いた残りの積が6以下になるというのは
なかなか難しい。

**１３２人目の素数さん** · 2017/04/25(火) 01:06:23.65

>>641
いや、xよりもSを6以下にするのが難しいのですよ。

**１３２人目の素数さん** · 2017/04/25(火) 12:00:01.81

１５１９／４９２，４９２０／１５１９，３３４４１６１／７４７３４８。

**１３２人目の素数さん** · 2017/04/25(火) 12:30:44.66

>>644
m=1681=41^2
n=720=12^2*5
m+n=2401=49^2
m-n=961=31^2
k=747348=41*12*49*31
S=5
L=2009/186=10.801…
ですね。美しい！
（これがL最小だと証明するのは難しそうですね）

**１３２人目の素数さん** · 2017/04/25(火) 12:50:11.88

ご名答。640で想定していたものは、将にそれです。
ですが、最小ではありません。有理数として表現するのは、事実上不可能ですが、
具体的な計算法がはっきりしているいるもので、それより小さい周長のものの存在も確認していますし、
コストと時間さえかければ、もっと小さいものも、見つかるでしょう。
この問題、周長の下限はありますが、最小は無いと思われます。

**１３２人目の素数さん** · 2017/04/25(火) 13:02:03.47

＞有理数として表現するのは、事実上不可能ですが
それは、恐ろしい桁数になるということですね((((；ﾟДﾟ))))
それより周長の小さい例の面積は全て５なのですか？

**１３２人目の素数さん** · 2017/04/25(火) 13:10:14.49

派生した問題
m,nをm＞nなる自然数とするとき、m, n, m+n, m-nがいずれも平方数になることはないことを証明せよ

（各辺が有理数で面積1の直角三角形は存在しない、という話です）

**１３２人目の素数さん** · 2017/04/25(火) 14:35:35.38

>>647
面積6で周長12未満のものを確認してます。
ただし、最もシンプルなものでも分母分子共に1500桁を超えてます。

**１３２人目の素数さん** · 2017/04/25(火) 14:40:39.24

あ、面積4,3,2,1で、例のような三角形は存在しないという事の確認でしたら、その通りですね。^^

**１３２人目の素数さん** · 2017/04/25(火) 21:27:21.76

>>650
「それより周長の小さい」は、>>644の例より周長の小さい、というつもりでした。
面積6なら、周長＞√(24(3+2√2))=11.8271…なので、>>644の例より短くはなりませんね。
それでも12未満の例が存在する（しかも分母子が1500桁以上…）というのはすごい話です。

面積4以下がないのなら、すぐわかる周長の下界は√(20(3+2√2))=10.7966…ということですか。
実際の下限もここになるのでしょうね。すでに相当近い値ですが。

**１３２人目の素数さん** · 2017/04/25(火) 23:14:13.14

面積がnで、三辺有理数の直角三角形は、楕円曲線　y^2=x^3-n^2 x　上の有理点と
対応させることができます。（詳細は「合同数」をググってください。）
楕円曲線上に有理点が見つかると、その点上での接線を考え、その接線と、楕円曲線
との交点を見つけることで、別の有理点を見つけることができます。
つまり、一つの三辺有理数の直角三角形が見つかると、面積が同じ別の形状の
三辺有理数の直角三角形が見つかると言うことになります。
この方法を具体的に実行し、三角形の三辺に置き換えると、次の恒等式として顕れます。

{(a^2-b^2)/(2c)}^2 + {2abc/(a^2-b^2)}^2 = {(a^4+6a^2b^2+b^4)/(2(a^2-b^2)c)}^2
ただし、a^2+b^2=c^2

(a,b,c)=(3,4,5)、あるいは、(3/2,20/3,41/6)　からスタートして
a'=(a^2-b^2)/(2c)
b'=2abc/(a^2-b^2)
c'=(a^4+6a^2b^2+b^4)/(2(a^2-b^2)c)
という変換を順次行うことで、(ループしない限り)、
無数の「面積が同一の三辺有理数の直角三角形」を見つけ続けることができます。
以上が出題の背景でした。

**１３２人目の素数さん** · 2017/04/26(水) 01:19:04.71

>>651
なるほど、同じ面積の各辺が有理数長の直角三角形の系列が漸化式によって順次生み出されるなら
有理数として計算しなくても、実数値として漸化式を計算していけば、
（その計算の精度の問題に目を瞑ると）周長が小さいケースがいつ出現するかを探ることができる
ということだったのですね。（1500桁とかどんなスパコンで計算してるのかと思った^^）
ざっとExcelのシートで計算したところ、
S=5では(3/2,20/3,41/6)を１番目とすると、>>644の例は２番目にいきなり出現するのですね。
で、周長がそれを下回る例は40番目ぐらいに出現（10.7971…）。ただし、誤差の蓄積の影響は不明。
S=6では(3,4,5)を１番目とすると、7番目に11.8368…というのが出現します。これが>>649の話ですね。

周長の下限が√(20(3+2√2))と言えるには、楕円曲線y^2=x^3-25x上に有理点が稠密に存在すると言えれば
よいのかな？その辺の議論はよくわからないので…

**１３２人目の素数さん** · 2017/04/26(水) 13:00:05.96

p=18428872963986767525.
q=4433082615462019402.
m=p^2.
n=6q^2.
k=(mn(m^2-n^2)/6)^(1/2).
a=(m^2-n^2)/k=
318497209829094206727124168815460900807
/81696716359207757071479211742813520050.
b=2mn/k=
980360596310493084857750540913762240600
/318497209829094206727124168815460900807.
c=(m^2+n^2)/k=
129247578911342274421755561174058897934715352348544627081785824806803920030001
/26020176212606586320464365557466481663803361400079403341276573868591555680350.

**１３２人目の素数さん** · 2017/04/27(木) 03:05:04.92

>>654
面積が6になるのは、(3,4,5)から始まる系列だけではないということですね。
他にも、(4653/851,3404/1551,7776485/1319901) m=2738, n=529 から始まる系列とかもあるようです。
面積6でLが12未満となるLの分母最小の例は>>654なんですかね。

**１３２人目の素数さん** · 2017/04/27(木) 15:40:58.17

ちなみに、>>654の例が出現する系列の出発点は
a=3122541453/2129555051 (=(m^2-n^2)/k)
b=8518220204/1040847151 (=2mn/k)
c=18428872963986767525/2216541307731009701 (=(m^2+n^2)/k)

m=3292336658=2*(13*3121)^2
n=2754885169=(73*719)^2
m+n=3*(17*19*139)^2
m-n=(97*239)^2
k=2216541307731009701=13*17*19*73*97*139*239*719*3121

であるようです。mとnのうち偶数の方が、4で割って2余る数となると、それ以上遡れないので。
>>654の例は、その系列の２番目です。

楕円曲線上の有理点の系列には、有限個の生成元しかないそうですが、
y^2=x^3-36xの場合は、ここまで出てきた３つを含め、全部でいくつの生成元があるのでしょうね。

**１３２人目の素数さん** · 2017/04/27(木) 19:29:02.13

n個の自然数 a1, a2, …, an が
f = 1/a1 + 1/a2 + …+ 1/an < 1
を満たしながら変化するとき、fの最大値を求めよ

**１３２人目の素数さん** · 2017/04/28(金) 00:36:48.24

>>657
いわゆる「欲張り法」でとっていくと、
b_0=1，b_{n+1}=b_n*(b_n + 1)という数列
{1,2,6,42,1806,…}
を考えて、
a_n = b_{n-1} + 1 とすると
f = 1/a_1 + 1/a_2 + 1/a_3 + … + 1/a_n
　= (b_n - 1)/b_n
となります。
n=1から順にfの値は
1/2，5/6，41/42，1805/1806，3263441/3263442，…
という感じです。
ただ、これが最大だという理由は自分には全然見つかってません。
なお、上記数列{b_n}はここ https://oeis.org/A007018 にあります。きれいな一般項の表記はない模様。

**１３２人目の素数さん** · 2017/04/28(金) 06:34:08.24

>>658
> いわゆる「欲張り法」でとっていくと、

ｋｗｓｋ！

**１３２人目の素数さん** · 2017/04/28(金) 10:41:56.69

>>659
１から、単位分数を順次引いていくというプロセスを考え、
ステップごとに残った値から（全部は取らない範囲で）最大の単位分数をとっていく。
最初は1 - 1/2 = 1/2
次は1/2 - 1/3 = 1/6
以下1/6 - 1/7 = 1/42，1/42 - 1/43 = 1/1806，…
という具合です。

元々は、任意の有理数をエジプト式分数（異なる単位分数の和）に展開する際の手法で
Wikipediaの「エジプト式分数」の項には「強欲算法」と紹介されてます。
そっちは、ぴったりその数にするのが目的なので、残りが単位分数ならそれで終わりですが、
今回は１にしてはいけないので、全部取らない範囲でなるべく大きく取る、
つまり、残りが1/nなら、1/(n+1)を取ればよいことになり、1/(n(n+1))が残ります。

今回の問題は>>658で正解のような気がするので、だれか証明よろしく。

**１３２人目の素数さん** · 2017/04/28(金) 12:26:14.09

>>657
そもそも最大値があるのかどうかも一応確かめてみる

(定理)
任意の正の実数r,任意の自然数nについて、
f= 1/a_1 + 1/a_2 + …+ 1/a_n < r
を満たすfは最大値を持つ。

(証明)
(i)n=1 の時
省略

(ii)ある自然数mについて、n=mの時 rがどんな値でも成り立っていると仮定する。
n=m+1 の時、反例となるrが存在すると仮定すると、
各 k=1,2,…,n に対して自然数列 {a_ki}_i (ただし a_1i≦a_2i≦…≦a_ni)が存在して
1/a_1i + 1/a_2i + … + 1/a_ni → r (i→∞)
となる。

liminf(a_1i) が存在するのでこれを b とおくと、
{a_ki} の部分列 {b_ki} が取れて
1/b_2i + … + 1/b_ni < r - 1/b
かつ左辺の極限が右辺になるものが取れるが、これはn=mの場合についての仮定と矛盾。
背理法よりn=m+1の場合も成り立つ。

数学的帰納(以下略)

**１３２人目の素数さん** · 2017/04/28(金) 12:30:14.28

>>661
ちょい訂正

誤：1/a_1i + 1/a_2i + … + 1/a_ni → r (i→∞)

正：1/a_1i + 1/a_2i + … + 1/a_ni < r かつ左辺の極限が右辺

**１３２人目の素数さん** · 2017/04/28(金) 17:41:49.04

1/a_1+…+1/a_n < 1 の右辺をどんな数に変えても欲張り法でいいのかなと思ったけど
そんなことはなかった

1/a_1+1/a_2 < 0.451 の場合を考える。
欲張り法だと a_1=3 で、
1/3 + 1/8 = 0.458…
1/3 + 1/9 = 0.444…
なので a_2=9, このとき 1/a_1 + 1/a_2 = 0.444…
一方 1/4 + 1/5 = 0.45 なので、欲張り法では最大にならない。

**１３２人目の素数さん** · 2017/04/28(金) 18:50:12.91

>>661
それだと、fが最大値を持つことではなく、
fの上限がrとならないことを証明しているように見えるのですが…。
上限がrではなく、なおかつ最大値を持たないケースが排除できていない気がします。

＞n=m+1 の時、反例となるrが存在すると仮定すると、
の後、

fは上に有界なので上限を持ち、それをRとすると

というような記述を挟んで、以下rをRに置き換えるべきでは。

それと、
＞1/b_2i + … + 1/b_ni < r - 1/b
＞かつ左辺の極限が右辺になるものが取れるが、
とありますが、
bはinf(a_1i)の極限であってa_1iの極限ではないので、
「左辺の極限が右辺になるものが取れる」とかは言えないと思います。

**１３２人目の素数さん** · 2017/04/28(金) 22:00:00.87

一つ目を決めて残りが最大になるようにとる。
一つ目は有限通り考えればいいので最大はある。

**１３２人目の素数さん** · 2017/04/28(金) 22:00:08.46

任意の正の実数rと自然数nについて、
有限自然数列a_1～a_nが
a_1≦a_2≦…≦a_n，1/a_1+1/a_2+…+1/a_n < r
かつ
a_n = 1または1/a_1+1/a_2+…+1/(a_n - 1) ≧ r
を満たすとき、その数列a_1～a_nを極大解と呼ぶものとする。
（極大解は、a_nのみの変更でfをよりrに近づけることができないような例とも言える）

そのとき、極大解が有限個しか存在しないことを示せば、fの最大値の存在は自明だし、
有限個しかないこともほぼ自明。

**１３２人目の素数さん** · 2017/04/28(金) 22:50:22.38

a1≦a2≦…≦an とすると、a1≧n+1 のときは、f≦n/a1≦n/(n+1) <1 となるから、a1は、2≦a1≦n+1 についてのみ調べればよい。
a1を固定すれば、同様にしてa2も有限個について調べればよく、結局、a1～an有限個の組み合わせだけ調べればよいことになるから、最大値は存在する。

欲張り法で求めた解が最大値かどうかは、自明ではないが、証明方法は分からない。

**１３２人目の素数さん** · 2017/04/29(土) 11:55:07.74

>>664
１つ目の指摘は確かにその通りだった。サンクス
上限を新たにRとおけばここは解決しそうだな

二つ目だけど、
{a_ki}のうち a_1i=b を満たすiだけ取り出して並べた数列を{b_ki}としたら解決すると思う

**１３２人目の素数さん** · 2017/04/29(土) 13:37:58.68

>>668
「a_1i=b を満たすi」が無限に存在する保証はないし、
「liminf(a_1i) が存在するのでこれを b とおく」という設定をやめて
無限に存在するa_1iを１つ選んでbとすることにしても、そんなものが存在する保証はないし、
そもそも、
＞1/b_2i + … + 1/b_ni < r - 1/b
＞かつ左辺の極限が右辺になるものが取れる
ことと、
1/b_2i + … + 1/b_niの最大値が存在しないことは無関係
（必要条件であっても十分条件ではない）
なので、矛盾なんか導けない。

**１３２人目の素数さん** · 2017/04/29(土) 14:07:00.35

>>669
そうか？
a_1i≦a_2i≦…となるように定めてるから、
もし a_1i がliminfを持たない(つまりlim(a_1i)=∞)とすると、
1/a_1i + 1/a_2i + … + 1/a_ni
≦1/a_1i + 1/a_1i + … + 1/a_1i
=n/a_1i
が、i→∞で0に飛んでくことになっておかしい。

二つ目も、必要条件だけで大丈夫じゃないかな
実際、前者から後者が導けるわけだし、そこでn=mの仮定と矛盾が生じる

**１３２人目の素数さん** · 2017/04/29(土) 23:37:51.98

>>669
まず先に謝っとくと、「矛盾なんか導けない」ってことはないですね。>>668の後半は間違い。
bとなるa_1iが無限に存在するなら、r - 1/bより小さい範囲での最大値が存在しないと言えるから、
矛盾は導けますね。すみません。

で、前半の話だが、
＞a_1i がliminfを持たない
ということを言っているのではなく、a_1iの最小値が存在し、なおかつそれが有限回数しか出現しない
可能性があるという話をしてます。だから、b=liminfa_1iとすると、無限列が作れない場合がある。
で、a_1iのうち無限に出現するものが存在することは、{a_ki}_iが無限列であるということと
a_1iのとりうる値の範囲の制約（R-fが0に収束するという仮定なので、それがある値以下になる時を考える）
から言えるので、そのa_1iをbとすれば、めでたく矛盾は導ける。

（が、そのa_1iのとりうる値の範囲の制約についての議論をした時点で、>>666 >>667あたりの議論が
できてしまうので…）

**１３２人目の素数さん** · 2017/04/30(日) 01:42:50.22

シルベスター数列とか、カーティスの定理とかでググってみると…
証明はされてるけど難しいもののようですな。
当方ギブアップ

**657** · 2017/04/30(日) 16:43:49.45

有名な難問だったのか。知らんかったわ。
ならば解くのは無理だね。

**１３２人目の素数さん** · 2017/04/30(日) 22:38:42.35

無理とも限らないんじゃない？
俺には無理だけど。

**１３２人目の素数さん** · 2017/04/30(日) 22:59:51.18

おいらには解けない

**１３２人目の素数さん** · 2017/04/30(日) 23:10:53.78

調べてみたらオイラーが解いてるってオチじゃないよね？
芸風が違うものね。

**１３２人目の素数さん** · 2017/04/30(日) 23:19:33.43

青空学園のホームページに載ってたわ

**１３２人目の素数さん** · 2017/05/01(月) 03:00:31.10

カーティスさんの記事はここで閲覧できる
http://www.jstor.org/stable/2299023?seq=1#page_scan_tab_contents
この記事に先行して、一般化した問題を日本のTakenouchiという人物が発表してたみたいな話が
記事の最後に書いてある。まだちゃんと読んでないけど。

**１３２人目の素数さん** · 2017/05/02(火) 16:22:01.08

【アリクイはアリを食べる
アリクイをアリも食べる
千万年そうしてきた♪♪】
さて、問題です。アリとアリクイは互いに捕食しあっています。それぞれ個体数をx、yとする。時刻tとし、それぞれの個体数の変化を次の方程式でモデル化した。
dx/dt=2x-y
dy/dt=2y-x
時刻０においてx=200,y=100の場合、一方の個体が0となる最初の時刻を計算せよ。

**１３２人目の素数さん** · 2017/05/02(火) 19:22:18.62

水木一郎によると、アリクイは死んだら食われるそうだから、
dy/dt=2y-x の -x は違うような気がするけどな。
dy/dt=2y(t)-y(t-1) とか？

>>679 を解いてみると、
x = f(t)x0 + g(t)y0,
y = g(t)x0 + f(t)y0,
f(t) = {e^t + e^(3t)}/2,
g(t) = {e^t - e^(3t)}/2.
なので、先に 0 になるのは y で
そのとき t = (1/2)log((x0+y0)/(x0-y0)).
x0 = 200, y0 = 100 ならば、t = log√3.

**１３２人目の素数さん** · 2017/05/02(火) 19:22:49.43

>>679
z=x+y dz/dt=z log(z)=t+C z=Ce^t
z(0)=300 z=300e^t
dx/dt=3x-300e^t
x=ue^(3t) dx/dt-3x=e^(3t)du/dt
du/dt=-300e^(-2t) u=150e^(-2t)+C1
x=150e^t+C1e^(3t)
x(0)=200 y(0)=100 x=50e^t(e^(2t)+3) y=50e^t(-e^(2t)+3)

**１３２人目の素数さん** · 2017/05/03(水) 02:25:40.09

ロトカ・ヴォルテラの方程式みたいだな
数理生物学の

**１３２人目の素数さん** · 2017/05/03(水) 04:51:03.60

こっちは線型だから、はるかに簡単だよ。

**１３２人目の素数さん** · 2017/05/03(水) 08:25:28.29

nを自然数とする。以下のすべての条件を満たす自然数の組(a1,a2,・・・,an,b1,b2・・・,bn)の個数を求めよ。
•n≧a1≧a2≧・・・≧an≧1
•n≧b1≧b2≧・・・≧bn≧1
•a1≧b1,a2≧b2,・・・,an≧bn
•a1≠1,a2≠2,・・・,an≠n
•b1≠1,b2≠2,・・・,bn≠n

**１３２人目の素数さん** · 2017/05/03(水) 11:05:46.07

n 次元ユークリッド空間 Rn の 2 点 A = (a1, a2, . . . , an) と B = (b1, b2, . . . , bn) の距離はd(A,B)=√{(a1 －b1)^2 +(a2 －b2)^2 +···+(an －bn)^2}
で定義されている.次の条件を満たす n(n + 1) 個の点からなる Rn の部分集合 S が存在することを示せ.
(条件) S の任意の異なる 2 点間の距離は 1 または √2 である.

**１３２人目の素数さん** · 2017/05/03(水) 11:06:37.89

>>684
自然数の組a=(a_1,…,a_n), b=(b_1,…,b_n)に対して
a_1≧b_1,a_2≧b_2,・・・,a_n≧b_nが成り立つことをa≫bと書く

n=2のとき
・(2,1)≫(2,1)
のみ

n=3のとき
・(3,3,2)≫(3,3,1)
・(3,3,2)≫(3,1,1)
・(3,3,1)≫(3,1,1)
・(3,1,1)≫(2,1,1)
の4組

**１３２人目の素数さん** · 2017/05/03(水) 11:56:24.86

>>686
正解だと思います。ちなみに近大数学コンテストの昨年の問題です

**１３２人目の素数さん** · 2017/05/03(水) 12:11:38.86

いや、間違えてたｗ

n=3のとき
(3,3,2), (3,3,1), (3,1,1), (2,1,1)
が>>684の一つ目のaに対する条件を満たしてるから
bのとり方を考えたら全部で10通りだ

**１３２人目の素数さん** · 2017/05/03(水) 12:22:49.79

>>688
あ...

**１３２人目の素数さん** · 2017/05/03(水) 13:26:17.86

>>684
(2n-1)!(2n-2)! / (n+1)!n!(n-1)!(n-2)! かな？

**１３２人目の素数さん** · 2017/05/03(水) 14:34:12.72

>>685
n=2ですでに無理なのだが…
何か問題を読み違えてるのかな

n=2のとき、Sの要素のうちある２点P1,P2の距離が1だとすると、
他のSの候補となりうる点は8つしかない。
（P1,P2と組み合わせて、３辺が(1,1,1)(1,1,√2)(1,√2,√2)の三角形を作る点）
その8点のうち、同時にSに含まれうるのは、最大でも2点しかないので、
Sの要素の数は高々4個。（正方形を形成する）

面白い問題おしえて～な 二十二問目©2ch.net

面白い問題おしえて～な二十二問目©2ch.net