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

締切りの過ぎた問題をみんなで議論しましょう。
ただし難易度情報は可。

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

>>21
あなたが頑張れば可能かも

噂をすれば竹内さん

京都大学のガロア祭を頑張るべし

数セミ、エレ解、2021年7月号、1番：離散対数絡みでない？

>>35
なにゆえ？
その心は？

アンカーミス
>>25
なにゆえに？

>>35 には「なぞかけ」を書くこと

なんと！！『数学セミナー』も60周年か。。。素晴らしい！！
戸田アレクシ哲先生もNoteに出場されておったの・・・・

京都大学数学教室主催、ガロア祭をみよ！！
塩田先生の問題は、やはり稠密定理絡みであったか。。。。。
https://www.math.kyoto-u.ac.jp/ja/node/4678

梅雨が明けたら、４分の２の季節は…
いやいや、暑くて茹だこですよ。
今ごろ出題１を出してるのは、たぶんオレだけだろうな。(#1462)

>>31
半月遅れてだしたってこと？なにゆえ？

こう暑いと 閃かないんだよな。
2回軸の本数とkの関係とか…

辺ABを辺CDに移す対称操作、でいいのかな

>>34金子君、そうだ！！

出題2はなんか腹立つな
解釈に余計な時間使う

長文はパス

どちらの方にも解けるって言わなくねー？とは言いたい

文意がハッキリしないなー

はじめの3分間は無解答だったから
　pの値に対して 3≦x<y が１組しかない場合
　sの値に対して 3≦x<y が１組しかない場合
は省いて良かろう。
そのうえで pの値とsの値の対応を考えるかな？

1分でなく3分ってのは期待値を考えろと言ってるんだよねえ
3分過ぎてから突然ってのは？
3分経過後Sが回答しないのを見てPが回答したのか、3分経過後間髪入れずにPが機先を制する形で回答したのか

>>41
SとP逆な

「正統な根拠」とか「この問題はどちらの方にも解けます」とかの文言が確率は絡まないと言ってるようにも思える

コレの系列やろ

en.m.wikipedia.org/wiki/Sum_and_Product_Puzzle

>>43
その場合1分で5万ずつ減る設定どう使う？

>>45
それもそうか
なら「正当な根拠」っていうのはもっともらしい理由くらいの意味と捉えるべきなのかもしれない。
でも「この問題はどちらの方にも解けます」は何だろう。
例えば確率が1/2ずつの解消できない2択があってどうやっても正当な根拠が示せない状況はないですよ、みたいな感じ？

>>46
対等、期待値が同じ、の意味に解さないと話が通らないような
でもそれだとSとPは同時に回答しなきゃいけないような

もうこの問題捨てるか

p=3*大きな素数だった場合ってP氏は50万獲得できんの？

素数×素数の時点で50万ゲトやろ

正しい問題解釈を誰か教えてくれ
スタートラインにも立てない

Xを3以上の自然数の自然数の2元集合の全体とする
Xの部分集合の列Xiが以下で与えられている

X0 = X
X(i + 1) = Xi
＼ { ( u,v ) ∈ Xi | uv = ab, ∀{k,l} ∈Xi ＼{{ u,v}} uv ≠ kl }
＼ { ( u,v ) ∈ Xi | uv = ab, ∀{k,l} ∈ Xi＼{{u,v}} u+v ≠ k+l }

今X3の元{a,b}が

∀{k,l}∈X3 ＼ {{a,b}} kl ≠ ab
∃{k,l}∈X3 ＼ {{a,b}} k+l = a+b

を満たしているとき{a,b}を求めよ

>>48
数学愛好家ならどんなに大きい数でも素数か否か瞬時に判別できるはずだぞ

>>51
そうなる根拠が解らぬ
5万円でも1円でも答えは変わらないのね？

やっぱり問題設定が分からん
逐次情報をやり取りするなら分かるが、1分に1回やり取りしたと考えるのは無理がある

理にかなわない行動をして相手の誤答を誘う心理戦とかありそう

解いたけど、これ計算機使わずにできないだろ？

>>19エレガントナ解答の正解者調べたら
カナダ、シンガポールからの投稿者もあった。
日本人だけど。結構、海外赴任中に購読されておられる
マニアの方もおられるのでは？？
よって、インターナショナルな雑誌と認定。

>>19エレガントナ解答の正解者調べたら
カナダ、シンガポールからの投稿者もあった。
日本人だけど。結構、海外赴任中に購読されておられる
マニアの方もおられるのでは？？
よって、インターナショナルな雑誌と認定。

竹内さん問題分かりづらいよー

出題2の解答キボンヌ

出題2はそもそも題意の解説からぷりーずだな

解答来ないってことは解けなかったんだな誰も、問題文の意味を。

週末まで待て

まだかなまだかな〜♪
エレ解の、オジサンまだかな〜♪

とりあえず問題の定式化はそこまで難しくないやろ
まず集合S(s,n),をそれぞれ「x+y=sである場合S氏か最良の推論をした場合にn回目の挑戦終了時点で残る(x,y)の可能性の集合」と定めたい、P(p,n)も同様に定めたい、どうするか
まず当然S(s,0)、すなわちsの値以外なにも情報がない時点では
S(s,0) = { (x,y) | x\+ y=s }
とするしかないのはいい
P(p,0)も同様
S(s,k-1),P(p,k-1)まで定められたときS(s,k),P(k,p)はどうなるかだけどk-1回目終了時点からk回目終了時点の間でS氏が得た情報は「k回目においてもP氏は(x,y)を特定できなかった」しかないのだからこの情報だけを利用してS(k-1)から除外できる数を除外したものがS(k)になる
すなわち(a,b)∈S(s,k-1)が除外できるのはk-1回目の挑戦でP氏が確定できないもの、すなわちP(ab,k-1)={(a,b)}であるものである
何故ならP(ab,k-1)はk-1回目の挑戦でP氏が最良の推論で絞り込める最小の集合としてすでに定められているので、ココに(a,b)以外の、他の元が入ってないことがP氏がk回目の時点で確定できる条件となる
結局S(s,k)は
S(s,k) = S(s,k-1)＼{(a,b) ∈ S(s,k-1) | P(ab,k-1) = { (a,b) } }
と定められる事になる
P(p,k)も同様に
P(p,k) = P(p,k-1)＼{(a,b) ∈ P(p,k-1) | S(a+b,k-1) = { (a,b) } }
と定められるとわかる
後はコレでP(p,2)は一元集合ではないけどP(p,3)は一元集合となるpを求める問題とわかる

>>65
なぜそうなるのか本当に分からん
1分毎に1度だけ回答機会が与えられるという設定ならまだしも
しかも1分おきに5万円という設定も解答に使わないのであれば、分単位の時間経過はなんの意味ももたないのでは？

互いが相手のことを知らない
＝相手の数学力や論理的思考力の程度が分からない
＝1分待ってみないと相手が考え中なのか解答不能なのか判断できない
と解釈すれば >>65 みたいにnを離散的にとっていいことになる・・・か？

>>67
うーんこの手の問題は両者perfect logicianであることを仮定するからなあ

みんな>>65のように解釈したのかなぁ
それならよくあるSPの会話形式でええじゃないの...
50万から5万ずつ下がり、間違えたら半額が相手に渡るなんていかにも意味有りげな設定は無視していいわけ？
単に1分おきにお互い"無言"のメッセージをやり取りしたってのが題意だというなら繰り返すけどSPの会話形式でエエジャナイカ...

おれはやっぱりT内さんの問題が好きになれんわ
ちと作問が独りよがりに過ぎんかね
みんな楽しめたんならなによりだが、俺はエレガントな解答じゃなくて問題の正しい解釈を見つけるのに9割5分の時間を割くはめになった

もう出題2はいいや
誰か納得いく説明や新解釈があれば話聞きたいけど

出題1は易しい良問で楽しめたよ

3≦x<yなる任意の整数x,yについて頂点(s,x+y)と頂点(p,xy)の間に辺を張った無限単純無向二部グラフGを作る．
Gの次数1の頂点に対応する(人,封筒の数)だった場合は，その人にとってのx,yの候補が1通りなので即答できる．
Gの次数1の頂点を全て除去したグラフをG'とする．
G'の次数1の頂点に対応する(人,封筒の数)だった場合は，その人にとってのx,yの候補は2通り以上ある．
しかしそのうち1通りを除きもしその候補なら相手が即答しているはずであるから，残る1通りを自分が即答すればよい．
以下同様に次数1の頂点がなくなるまでGの頂点を除去しきったグラフをHとする．
S氏,P氏は数学愛好家なので（？）Hを得るまでは一瞬で，ここから期待値を考え始める．

ここまでは考えたんだがHが無限グラフなんでどうにもならん．
せめてx,yに上限があれば……

今ごろ出題１を出してるのは、オレだけかも。(#1495)

>>72
今月の？先月の？

9月号 出題1 (阿賀岡さん)

今ごろて

先月の問２について
同じアイディアが既に出ているかも知れないが具体的にやる。
x,yの組を(x,y)と書く。
p=xyは条件より12以上がわかる。12〜30までのpの候補のうち、
条件を満たす選択肢が2つ以上あるのは、
p=24のとき(3,8)か(4,6)
p=30のとき(3,10)か(5,6)
ここでp=24もp=30もないことを示す。
p=24として、(4,6)だったとする。対応するs=10の選択肢は(3,7)か(4,6)の二つ。
(3,7)の場合p=21となりｐは即答しているので、(4,6)となる。
しかしこの場合sが解答できるので、これもなし。結局p=24のとき(3,8)が解答になる。
するとpが解答できるので(3,8)もなし。以上よりp=24はなし。
p=30であり、(5,6)だったとする。対応するsは11でその候補は
(3,8)か(4,7)か(5,6)となる。(3,8)がないことは上の通り。
(4,7)はpが即答するのでなし。(5,6)となるがこの場合sが解答できるのでなし。
よってp=30のとき(3,10)となるがpが解答できるのでなし。pは31以上である。
（ここまでの考察で数字が与えられていれば3分はかからないと思う。）

今月号の難易度情報もとむ

1は難しい気配がする
2はおそらく簡単

>>78
77だが逆かと思ってた

１出して　２に取りかかる　残暑かな
(難易度情報なし)

九月号はベストセラーで売り切れですね！！西浦先生の記事のせい

俺も西浦さんの記事見たよ
世間のニュースより数セミの方が周知が早かったな

[特集1]
新型コロナウイルスと闘うために数学にできること
102p．1199円
http://www.nippyo.co.jp/shop/magazine/8348.html

8割おじさん (医) ご登場ですか。ご老公に駆り出された？
ところで、ご老公は大丈夫だろうな。

2021年9月号
>予防接種完了時の新型コロナウイルス感染症流行をどのように見通しているか……西浦 博

竹内郁雄
まだ生きてるのか

2番いい問題だな
まだ突破口みつからんのだけど

2番難問

2番言うほどかね
良い問題であることには同意

>>88
ほう。
勇気もらったから粘ってみるわ

やっぱり難問だよこれ

2番答えは解ったが証明はどうしたもんか

じゃあ猛者ども証明よろ

書くか

以下全集合はZの中で考える
集合Aと整数nに対して
A+n := { a+n | a∈A }
とかくとする

定理
0≦a<b<c, Z=∪[ i∈S | { a+i, b+i, c+i }が非交和とする
a,b,cの3進展開が同一の数にならない最小の桁が3^iの桁とする
このときa,b,cの3進展開の3^iの位は全て相異なる

∵) iについての帰納法
あるi0>0においてi<i0で正しいとしてi=i0とする
a≡b≡c≡r (mod 3) (r∈[0,2])とする
a'=[a/3],b'=[b/3],c'=[c/3],S'={ (i+r)/3 | i∈S,r+i≡0(mod 3)}とおけばZ=∪[i∈S']{a'+i,b'+i,c'+i}は非交和となるから帰納法の仮定から主張が従う
i=0の時を考える
Z=∪[ i∈S ] { a+i, b+i, c+i }が非交和とする
0=a,0∈Sとしてよい
Sn = {a+i,b+i,c+i | i ∈ [ cn, cn + c - 1 ] ∩ S }
とおき、さらに
An=(Sn-cn)∩[0,c)、Bn=(Sn-cn-c)∩[0,c)
とおく
このときあるk≧0とl>0で
Bk=[0,c)＼A(k+1),
B(k+1)=[0,c)＼A(k+2)
...
B(k+l-1-1)=[0,c)＼A(k+l)
A(k+l)=Ak
となるものが取れる
SをS-ckに取り替えることによりk=0としてよい
T=∪[0≦n<l]Sn、t=clとおく
Tの最大元はc(l-1)+c-1=t-1以下である
f(x)=x^a+x^b+x^c、g(x)=Σ[i∈T]x^iとおく
f(x)g(x)
=Σ[i∈T]x^i
=Σ[0≦i<t]x^i - Σ[i∈[0,c)＼A0]x^i +Σ[i∈B(l-1)]x^(i+t)
=Σ[0≦i<t]x^i + Σ[i∈B(l-1)]x^i(x^t-1)
≡1+x+‥+x^(t-1) (mod x^t-1)
である
特にf(x)g(x)は1+x+‥+x^(t-1)で割り切れる
またg(x)の次数はt-1以下である
b+cが3の倍数でないとする
このときf(x)の根は1の冪根ではない
実際ζが1の原始m乗根とする時1+ζ^b+ζ^cが0になるのはζ^b、ζ^cが相異なる1の原始3乗根である時に限られる
よってb/(b,m)=c/(c,m)=3である
さらにb/(b,m)+c/(c,m)≡0(mod 3)とならねはならずb,cについての仮定に反する
よってg(x)は1+x+‥+x^(t-1)の根を全て根とするからg(x)=1+x+‥+x^(t-1)で割り切れる
さらにg(x)の次数はt-1以下であったからg(x)=1+x+‥+x^(t-1)である
特に0,b-a∈T⊂Sとなるがbが{a,b,c}+0と{a,b,c}+b-aの両方に含まれることになり仮定に反する

ほれみろ難問じゃねえか

>>93
これ読んで自分が問題を読み間違えていることに気付いた

>>94
元論文当たらずにこの発想にたどり着けた？

コレ論文の元ネタあるん？

元ねた論文詳細希望

出題1って全事象が6^n通りなんだから推移行列どうこう以前に1/5や1/7になるはずなくね
確率を求めよ、にした方が良かったのでは

たしかに。
でもフライング気味…

最近少し時間ができて数学を勉強し直しています。
高校の数学からやり直してますが、せっかくなのでエレ解にも挑戦してみようと思い、とりあえず10月号の出題2を提出しましたが、私にはなかなか難しく、簡潔な回答が思いつきません。

このスレの皆さんは凄いですが、どんな職業の人が多いのか興味があります。

出題2は答えの予想も立つし、証明もそれほど難しくないけど、官名な証明ほ見つからないな

>>102
a=5 のとき
　n回で s≡r (mod 5) となる確率は
　(n-1)回で s≡(r-1) となる確率に１を足して6で割ったもの。
　ここに 0≦r<5
修正ｽﾏｿ.

>>106
真ん中だけ1、真ん中だけcのパターンもある。n<=8だと他にもある。

そうそう
Xの最小値は[3(n-1)/2]
コレはbが1スタートの場合
1c1c...
1111c1111
1111c11111
のタイプが無限系列で出てきてスポラディックな奴
1cc1
11c11c11
が出てくる
答えはコレでいいハズだけど簡明に書くのが難しい

上手い解き方を見つけた人はぜひ書き込んでいただきたい。
俺は場合分けの嵐のような、提出するのをためらう答案になってしまった。

1c11c1もあるかな。

>>111
おっと
そうそう
俺が作った解答はまず
Δ(k) = #{長さkのbの連続部分列に含まれるcの数}
m = min{ k | Δ(k)=1 }
とおく
n-1 = qm + r ( 0≦r≦ m )
とすれば頑張るとm≧3においてX = [ 3(n-1)/2 ]になりうるのは
・q = 1
・q=2, r=0
・( m, q, r ) = (3,2,2)
に絞られる
q = 1 のケースで11111c11111, 11111c111111の無限系列解と1cc1
( q, r ) = (2, 0 )のケースで1c11c1
( m,q,r ) = ( 3,2,2 )のケースで11c11c11
に絞れた
コレで多分全部

今んとこ間違いは見つけてないがエレガントではない解を張ってみる

準備
階差列I(X)を以下(b1,..b(n-1))とする
Δ(k):=#{ b'の中のcの数 | b'はbの連続k項の部分列}
と定める
d(X)=Σ[k]Δ(k)
である
以下b(1)=1の場合を考える
Δ(k)=1であるkがなければd(X)≧2(n-1)である
以下そうでないとする
m=min{ k | Δ(k)=1 }とおく
n-1 = qm + r ( 0 ≦ r < m )
とおく
m=2のときd(X)=[3(n-1)/2]である
以下m≧3とする
条件(❇︎)を
m≧3, d(X)=[3(n-1)/2]‥(❇︎)
とおく
K1 = { k | Δ(k) = 1 }, K2 = { k | Δ(k) ≧ 2 }
とおく

claim1 (❇︎)が成立するには
#K1 ≧ #K2
が必要である
∵) 容易□

claim2 Δ(k)=1のとき b(p+k)=b(p)である
すなわちbは周期mの数列である
∵) Σ[p≦i≦p+k-1]b(i) = Σ[p+1≦i≦p+k]b(i)
によりb(p)=b(p+k)を得る□

claim3 k≦(n-1)-(m-1)に対してΔ(k)=Δ(k-m)である
すなわち最後のm-1項を除いてΔは周期mの数列である
∵) sをb(1)からb(m)までの中のcの数をsとするとき
a∈{ b'の中のcの数 | b'はbの連続k項の部分列}
→a-s∈{ b'の中のcの数 | b'はbの連続k-m項の部分列}
である
何故ならは連続k項の部分列b'の中のcの数がaのとき、その末尾m項を取り除いた部分列の中のcの数はa-sとなる
また
a∈{ b'の中のcの数 | b'はbの連続k-m項の部分列}→a+s∈{ b'の中のcの数 | b'はbの連続k項の部分列}
何故ならは連続k-m項の部分列b'の中のcの数がaのとき、k-m≦(n-1)-(2m-1)であるからb'の前か後ろかのいずれかの方向にm項列の長さを伸ばせる余地がありその伸ばした部分列の中のcの数はsとなる□

claim4 (❇︎)のとき#K1≦#K2+1である
さらに全てのkでΔ(k)≦2である

∵) Δの最初のm-1項と最後のm-1項を取り除いた列を考える
この部分列は初項が1で第2項〜第m項が2以上である周期mの数列である
従ってこの部分列の中でK1に属する項の数は多くともK2に属する項の数より高々1大きい事しか許されない
一方で最初に取り除いた2m-2項にはK2に属する項の数の方がK1に属する項の数より多いかまたは等しい
以上により#K1は高々#K2+1以下である
もしΔ(k)≧3となる項があるとする
n-1が奇数の時は[3(n-1)/2]=3(n-1)/2-1/2であり
d(X)≧1+2#K2+#K1
≧1+3/2#K2+3/2#K1-1/2
=3(n-1)/2+1/2
=[3(n-1)/2]+1
により(❇︎)に矛盾する
n-1が偶数の時は#K1≦#K2となり、[2(n-1)/2]=3(n-1)/2だから
X≧1+2#K2+#K1
≧1+3/2#K2+3/2#K1
=[3(n-1)/2]+1
により(❇︎)に矛盾する□

claim5 Δ(i) = Δ(i+1) = 1のときb(i+1)〜b(n-1)とb(1)〜b(n-i-1)は全てb(1)に等しい

∵) b(i+1) = b(1) = b(i+2)=...=b(n-i-2)=b(n-1)=b(n-i-1)である□

claim6 q≧2で(❇︎)が満たされるのはbが
b:1c11c1
b:11c11c11
のいずれかの場合である

∵) #K1≦#K2+1でΔの全ての項は1か2,n-1≧2mだからΔは
・(m-1個の2)12(m-1個の1)
・(m-1個の2)1221(m-1個の1)
の形しか許されない
前者のときΔ(m+2)=Δ(m+3)=1によりb(1)〜b(m-2), b(m+3)〜b(2m)は全て等しく、Δ(m)=1からb(m),b(m+1)もコレらに等しい
すなわちb(k)はb(m-1),b(m+1)を除いて全てb(1)に等しい
b(1)〜b(m)の中のcの個数とb(m+1)〜b(2m)の中のcの個数は等しいのでb(m-1)=b(m+2)である
さらにそれはb(3)〜b(m+2)の中のcの個数にも等しいからここに第m-1項は入ることができないのでm-1<3となりm=3を得る
よってbは
1c11c1
である事が必要である
コレは(❇︎)を満たす
後者のときΔ(m+3)=Δ(m+4)=1によりb(1)〜b(m-1), b(m+4)〜b(2m+2)は全て等しく、Δ(m)=1からb(m+1),b(m+2)もコレらに等しい
すなわちb(k)はb(m),b(m+3)を除いて全てb(1)に等しい
b(1)〜b(m)の中のcの個数とb(m+3)〜b(2m+2)の中のcの個数は等しいのでb(m)=b(m+3)である
さらにそれはb(4)〜b(m+3)の中のcの個数にも等しいからここに第m項は入ることができないのでm<4となりm=3を得る
よってbは
11c11c11
である事が必要である
コレは(❇︎)を満たす□

コレらは(❇︎)を満たす□

claim7 q=1の時(❇︎)が成立するのは
b: (m-1個の1)c(m-1個の1)
b: (m-1個の1)c(m-2個の1)
b: (m-2個の1)c(m-1個の1)
b: 1cc1
のいずれかの場合である

∵) K2は[1,m-1]を含むからK2の元数は少なくともm-1元ある
よって#K1≧#K2のためにはn-1≧2m-2が必要であり、よってr=m-2,m-1のいずれかが必要である
さらにいずれの場合にもK2=[1,m-1]、K1=[m,n-1]である
特にΔ(m)=Δ(m+1)=1が必要である
よってΔは
・(m-1個の2)(m個の1)
・(m-1個の2)(m-1個の1)
のいずれかの形しか許されない
前者のときΔ(m)=Δ(m+1)=1によりb(1)〜b(m-1), b(m+1)〜b(2m-1)は全て等しい
よってbは
(m-1個の1)c(m-1個の1)
である事が必要である
コレは(❇︎)を満たす
後者のときΔ(m)=Δ(m+1)=1によりb(1)〜b(m-2), b(m+1)〜b(2m-2)は全て等しい
b(m-1)=b(m)=cかつm≧4とするとbは11ccの形の連続部分列を含むので11,1c,ccの形の連続部分列をも含みΔ(2)≧3となって矛盾する
よってb(m-1)=b(m)=cとなるのはm=3の時に限られる
以上によりbは
b:(m-1個の1)c(m-2個の1)
b:(m-2個の1)c(m-1個の1)
b:1cc1
である事が必要である□

11月の出題2がえらく簡単に思えるが何か勘違いしているかな。

今ごろ出題2の解答を出してるのはオレだけかも (#1600)
ちょっと複雑…

今回は出題1の方が難しくね？

うむ。
きのう出した出題1の解答　 (#1614)
きょう出した出題1の解答　(#1615)

>>120
コレ他の人の解答もみれんの？
hp見てもそれらしきリンクないけど