こうすりゃ割といい解出せそうっていう手順を一般化して出来たのがこちらの表(比較すると盛大にこけている) #プリクラ問題 docs.google.com/spreadsheets/d…
2015-01-06 19:57:37#プリクラ問題 もすっかり大人しくなりましたが、懲りずに表(n≦"99", m≦25)をアップします。現人神ジョージ先生の解答を待ちましょう。 pic.twitter.com/5q3p1seCUa
2015-01-07 00:07:35#プリクラ問題 m≧(2/3)n だと3回、m≧(3/5)nだと4回……だったか 推移定理よりm≧n(2/3)^k だとP(n,m)≦3^k
2015-01-07 01:30:03【プリクラ問題の拡張】n次元単体Nに含まれるm次元単体をいくつ選んで集合Aとすれば、Nに含まれる任意のp次元単体がいずれかのAの要素に含まれるか。(n≧m≧p) #プリクラ問題
2015-01-07 02:02:32プリクラ問題の厳密解一覧見てたけど、n=2mで全部6回になってるのは気づきやすいけど、(3,5)以降のフィボナッチペア(F_n-1,F_n)が全部((21,34)まで)4回になってるの面白い #プリクラ問題
2015-01-07 09:12:07ちなみにリュカ数ペア(リュカ数:2,1で始めてフィボナッチ数列ルール適用)では、(3,1),(4,3),(7,4)が例外で、(11,7),(18,11),(29,18)の三つは4回だな #プリクラ問題
2015-01-07 09:40:20でもフィボナッチもリュカも回数4から得られるものは少なくて、両者とも隣接する数の比が黄金比に近づくから、回数4になるペアはn=m(1+√5)/2周辺に存在するという予想ぐらい #プリクラ問題
2015-01-07 09:50:26昨日気付いたことの延長として、特定のk,mではn=km(m-1)+1のときP(n,m)=kn (下限と一致)が予想される #プリクラ問題
2015-01-07 10:22:56どう考えてもこれなんだよなあ。境界は微妙に違うかもしれないけど。 #プリクラ問題 pic.twitter.com/9Vd8PcAvrr
2015-01-07 10:32:26この境界が大体1.1倍程度でふらふらしてるから、この境界の増加倍率の相乗平均とったら先の境界を予測できるんじゃなかろうか。(等比数列で予測) #プリクラ問題
2015-01-07 10:35:23プリクラ問題、雰囲気が分割数とかなり似ているのに、分割数は動的計画法でできてプリクラ問題は動的計画法の導入すらまだできないのはなぜなのか……。 #プリクラ問題
2015-01-07 13:20:25ちょっとアルゴリズム変えてみたら平均的に悪くなった気がする #プリクラ問題 docs.google.com/spreadsheets/d…
2015-01-07 15:59:01とても特別な例だけど(9,4)だけ1回減った…それぞれ特別な場合分けをしなきゃ一意に定まらないような気がしたのでお仕舞にする #プリクラ問題
2015-01-07 16:02:02組み合わせ表を上から埋めていく戦略を取れば再帰的に回数が求められるのは分かったけど、戦略自体が全く効率よくなかったオチ #プリクラ問題
2015-01-07 17:09:45