プリクラ問題２

まる @ps_maru

P(7,3)=7は3+2*2、P(13,4)=13は4+3*3。 補助関数を導入。定義：H(p,q)≡(p人q組に分かれていて、既に同じ組の人同士では済んでいる状態からp人ずつ選んで撮るときの最小回数) このとき、次のことが成立。（続） #プリクラ問題

まる @ps_maru

（承前） 定理：H(p,p)=p^2 定理：P(m(m-1)+1,m)=H(m-1,m-1)+m ここでm(m-1)+1≡1or3(mod6)より、後者の定理はシュタイナー系の定理「P(2,3,n)が重複組なし⇔n≡1or3(mod6)」と類似し、一般化を期待。 #プリクラ問題

ラン @gmcgso_kdeuvmt

m=3の縦の周期性ってわかったりしないかな #プリクラ問題

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

そういえばP(kn,km)≦P(n,m)のkの自然数から有理数への一般化、反例あるしだめっぽい #プリクラ問題

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

あれ？ m=3の時の厳密解って P(n,3)=[(n/3)[(n-1)/2]] ([]は端数切り上げ) で確定でいいんだよね？ #プリクラ問題

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

下界P(n,m)≧[(n/m)[(n-1)/(m-1)]]、式を見れば明らかだけど、mが大きくなると(n-1)/(m-1)が整数より僅かだけ大きくなる (=繰り上げされる幅が大きくなる) パターンが出てくる #プリクラ問題

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

そしてn/m×繰り上げられた整数 の形になるから、n/mに比例して繰り上げ幅が更に拡大していく そんなわけで、n,mが大きくなると下界はnC2/mC2=n(n-1)/m(m-1)からの差が目立つようになってくる #プリクラ問題

まる @ps_maru

( ˘⊖˘) 。o(とりあえず補助関数を導入しようとしたものの、これが正解なのかはわかりません……) #プリクラ問題

あしやまひろこ @hiroko_TB

#プリクラ問題 のまとめ、二つ目作ろうと思いますがどうですか？

ゴンちゃんに叱られる @gon_25_25

23時まで #プリクラ問題 見る

ゴンちゃんに叱られる @gon_25_25

とりあえずP(16,4)の書き出しは意外にすぐ終わった #プリクラ問題

萎れたほうれん草 @bamboofield00

繰り上げ部のサイズとか比較してみたらなんとかなるかもとか思ったけど論拠皆無だし誰かやってみて #ﾌﾟﾘｸﾗ問題

まる @ps_maru

画像の定理12,13が知られており、 n=m(m-1)+1 (m-1は素数)⇒P(n,m)=nの定理は、定理13でq=m-1 (m-1は素数), k=2としたときのP(m(m-1)+1,m)=m(m-1)+1の場合だ！ #プリクラ問題 pic.twitter.com/9HARnn86Es

拡大

まる @ps_maru

@Sumitacchan 一般化は、先行研究で証明されているらしい、定理「qが素数冪、kが正整数のとき、P((q^(k+1)-1)/(q-1),q+1)=(q^(k+1)-1)/(q^2-1)*(q^k-1)/(q-1)」だと思われます…。 #プリクラ問題

まる @ps_maru

今までわかっていること ・NP困難である ・素数列が登場する ・解が1～15のときの全ての(n,m) ・m=2,3,4のときの全ての(n,m) ・m=5のときのn≦280のときの全ての(n,m)と、n≧281でnが4の倍数+1のときの全ての(n,m) #プリクラ問題

まる @ps_maru

今までわかっていることその2 前ツイートの他に、添付画像の定理も判明している。 #プリクラ問題 pic.twitter.com/OqXoWlHuvp

拡大

まる @ps_maru

@nareO7 mathoverflow.net/questions/1920… Caro and Yuster(中略): Covering Graphs: The Covering Problem Solved, JCTA 83 (2) 273–282, 1998.です。 #プリクラ問題

まる @ps_maru

今まで示したり予想してきたことのほとんどは先行研究に載っているので、まず今までの論文のReview論文的なのをまとめる必要がある気がします……。それと、全員が最新の情報を把握するのって難しいですね……(タグやTogetherだけでは厳しい？)。 #プリクラ問題

すみたつ @Sumitacchan

#プリクラ問題 、P(n,m)の値よりもどのようにグループを構成すればよいかに興味がある

すみたつ @Sumitacchan

p,p+1がどちらも素数の冪であるとする。P(p(p+1)^n+1,p+1)は下限と一致する？？？ #プリクラ問題

すみたつ @Sumitacchan

pとp+1がどちらも素数の冪ならばP(p(p+1)^n+1,p+1)=(p(p+1)^n+1)p(p+1)^(n-1)という予想、プリクラ数の文献(ツイッター)値がn≦99までだから妥当性が調べられない #プリクラ問題

まる @ps_maru

定理 定理12と定理13の組は全て重複がない解になる。 予想 「重複がない解になる(その解をシュタイナー系でS(2,m,n)と表す)⇔選び方がCyclicである」が成立。 #プリクラ問題

まる @ps_maru

予想 重複がない解になるP(n,m)に対し、P(n+1,m)=P(n,m)+ceiling(n/(m-1))が成立。(∵重複がないところに1人増えたら、P(n,m)をした後に純粋にその人と他の人がceiling(n/(m-1))回で撮っていった場合が最小になる。) #プリクラ問題

まる @ps_maru

@ps_maru いくつか調べてるけどこの予想今のところ成立してる。というか厳密解表で厳密解とわかってる部分になってるｗｗ先行研究ｗｗ #プリクラ問題

○和 @78pple

ジョージ先生が熊になっとる... #プリクラ問題