プリクラ問題２

まる @ps_maru

厳密解－近似解の値です。まだ4が現れてません。4が現れないことがわかればnが十分大の時の厳密解は[n/m[(n-1)/(m-1)]]（[]は端数切り上げ）になりそうですが、これはそのうち現れる予感が……。 #プリクラ問題 pic.twitter.com/WfAM1yJpN1

拡大

○和 @78pple

例によって質問してみたが質問が意味わからんとボコボコにされる予感　math.stackexchange.com/questions/1092… #プリクラ問題

まる @ps_maru

定理「P(kn,km)≤P(n,m)（kは自然数）」を、「P(kn,km)≤P(n,m)（kはkn,kmが自然数であるような任意の正有理数）」、と拡張するのはまだできてません。P(46,25)が6だとしても、なぜ比で決定できるのがちょうど6回までかの意味は未解明。 #プリクラ問題

まる @ps_maru

@298itf P(46,25)が6であった場合にm≦25で解が1～6回のときだけn/mの比の範囲で完全に解が決定できることになるのはわかっています（添付画像の通り）。前者の拡張予想はまだ全然確かめてません。 #プリクラ問題 pic.twitter.com/eqz78nOti0

拡大

まる @ps_maru

4回の場合って初めて詳しく見たけど、4回に関してだけならわりとアルゴリズム的な法則性が見つかりそうな雰囲気はある…。 #プリクラ問題

それでも完全に元の鞘に収まることはない @miliushin

#プリクラ問題 ちょっと気になってる

小金井ささら | ユキちゃんかわいい @kgneissr

(2/3)n≦m＜n⇔P(n,m)=3 って成り立つのかな #プリクラ問題

まる @ps_maru

P(kn,km)≤P(n,m)が有理数へ一般化可能なことが示せさえすれば、4回の場合もアルゴリズムを出すことなく4回って決まります。5,6回のときは、下界がやはり4回でそれぞれ4～5、4～6の範囲までしか絞れないので、アルゴリズム見つけないとつらいです。 #プリクラ問題

小金井ささら | ユキちゃんかわいい @kgneissr

P(n,m)≧P(kn,km)のkを自然数から有理数に拡張するならk≧1という条件が出てくる #プリクラ問題

なれ @nareO7

"Covering Designs on 13 Blocks Revisited "という論文のイントロに、各1≦k≦13に対して、最小の撮影回数がk回となる(n,m)の組を決定したとの記述が　#プリクラ問題

○和 @78pple

仮に予想が正しいと仮定したら、あの表はどこまで埋まるのだろうか #プリクラ問題

○和 @78pple

メキシコのジョージ先生さすがだわ　埋まるかもしれない #プリクラ問題 math.stackexchange.com/questions/1092…

○和 @78pple

【朗報】ジョージ先生がF(46,26),F(47,26)について調べてくれると宣言 math.stackexchange.com/questions/1092… #プリクラ問題

小金井ささら | ユキちゃんかわいい @kgneissr

(47,26)と(47,26)……しらみ潰しだと最悪で (47C26)C5+(47C26)C6+(46C26)C5+(46C25)C6パターンあるぞ……こんなのできるのか…… #プリクラ問題

まる @ps_maru

4回のときのわけかた 123 145 234 235 12345 12678 34567 3458 123456 12789A 345678 34569A #プリクラ問題

まる @ps_maru

4回の時のやり方たぶんわかった！ほぼA:(B1+B2):C=1:(1+1):2になるよう分割し、この異サイズ4グループで(A,B)(A,C)(B1,C)(B2,C)と動く。そのため、解が4の時の比n/mの値の上端の分母は5(上端での実際の比の値は5分の7)になる。 #プリクラ問題

まる @ps_maru

サイズ比が1:k(整数)のグループに分けるのを何回かやる考え方で全てできるとしたら、総当たりをmin関数を用いて動的計画法による厳密な漸化式に落とせる見込みがあるんじゃ？(アイデアがわりと最初の段階に戻りつつある…) #プリクラ問題

小金井ささら | ユキちゃんかわいい @kgneissr

N(m) とは #プリクラ問題

萎れたほうれん草 @bamboofield00

m,n,a,bが自然数でn＞b、(m-1)=anのときF(m.n)=a+F(m-1.n)になる気がするんだが流石に既知かwww #ﾌﾟﾘｸﾗ問題

まる @ps_maru

従来より高速な解法を思いつくために自然数の分割（8=1+1+2+4みたいな）について調べていたのだけど、ja.wikipedia.org/wiki/%E5%88%86… の補助函数の表がプリクラ問題の表とめっちゃ似ている気がする…！ #プリクラ問題

まる @ps_maru

nが十分大ならP(n,m)→[n/m[(n-1)/(m-1)]]は証明されているらしく、その十分大がn≧N(m)(mに依存する整数値)のときと言いかえる場合のN(m)。このN(m)のオーダーを調べられたら…？という感じですね…。 #プリクラ問題

すみたつ @Sumitacchan

m≦l≦nなる任意のlに対し P(n,m)≦P(n,l)P(l,m) ∵n人からl人選んでP(l,m)回でそのl人が互いに誰とも写るようにする。これをP(n,l)回繰り返せばよい。 #プリクラ問題

すみたつ @Sumitacchan

n=m(m-1)+1かつm-1が素数ならP(n,m)=nかな？ #プリクラ問題

小金井ささら | ユキちゃんかわいい @kgneissr

∀l (m≦l≦n) P(n,m)≦P(n,l)P(l,m) 、比の計算に使えそう #プリクラ問題

ラン @gmcgso_kdeuvmt

プリクラ問題の上界表スプレッドシート用の形式で上がってないかな… #プリクラ問題