プリクラ問題2

#プリクラ問題 の続き これまでの経緯はこちら http://togetter.com/li/765312 条件は以下の通り。 (1)n人がいる 続きを読む
6
前へ 1 2 3 ・・ 13 次へ
ラン @gmcgso_kdeuvmt

こうすりゃ割といい解出せそうっていう手順を一般化して出来たのがこちらの表(比較すると盛大にこけている) #プリクラ問題 docs.google.com/spreadsheets/d…

2015-01-06 19:57:37
○和 @78pple

#プリクラ問題 もすっかり大人しくなりましたが、懲りずに表(n≦"99", m≦25)をアップします。現人神ジョージ先生の解答を待ちましょう。 pic.twitter.com/5q3p1seCUa

2015-01-07 00:07:35
拡大
小金井ささら | ユキちゃんかわいい @kgneissr

#プリクラ問題 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
ガガドス @___chicken

通常のプリクラ問題はp=2としたとき。 #プリクラ問題

2015-01-07 02:01:46
ガガドス @___chicken

まぁグラフつかって説明したほうがわかりやすいんだろうけどカッコ悪そうだった(( #プリクラ問題

2015-01-07 02:02:15
ガガドス @___chicken

【プリクラ問題の拡張】n次元単体Nに含まれるm次元単体をいくつ選んで集合Aとすれば、Nに含まれる任意のp次元単体がいずれかのAの要素に含まれるか。(n≧m≧p) #プリクラ問題

2015-01-07 02:02:32
ふるやん @furuya1223

プリクラ問題の厳密解一覧見てたけど、n=2mで全部6回になってるのは気づきやすいけど、(3,5)以降のフィボナッチペア(F_n-1,F_n)が全部((21,34)まで)4回になってるの面白い #プリクラ問題

2015-01-07 09:12:07
ふるやん @furuya1223

(n,m)だから逆か。(F_n+1,F_n)で4回だな #プリクラ問題

2015-01-07 09:13:28
ふるやん @furuya1223

ちなみにリュカ数ペア(リュカ数:2,1で始めてフィボナッチ数列ルール適用)では、(3,1),(4,3),(7,4)が例外で、(11,7),(18,11),(29,18)の三つは4回だな #プリクラ問題

2015-01-07 09:40:20
ふるやん @furuya1223

でもフィボナッチもリュカも回数4から得られるものは少なくて、両者とも隣接する数の比が黄金比に近づくから、回数4になるペアはn=m(1+√5)/2周辺に存在するという予想ぐらい #プリクラ問題

2015-01-07 09:50:26
すみたつ @Sumitacchan

昨日気付いたことの延長として、特定のk,mではn=km(m-1)+1のときP(n,m)=kn (下限と一致)が予想される #プリクラ問題

2015-01-07 10:22:56
ふるやん @furuya1223

どう考えてもこれなんだよなあ。境界は微妙に違うかもしれないけど。 #プリクラ問題 pic.twitter.com/9Vd8PcAvrr

2015-01-07 10:32:26
拡大
ふるやん @furuya1223

この境界が大体1.1倍程度でふらふらしてるから、この境界の増加倍率の相乗平均とったら先の境界を予測できるんじゃなかろうか。(等比数列で予測) #プリクラ問題

2015-01-07 10:35:23
ふるやん @furuya1223

P(kn,km)=P(n,m)と思ったけど違うのか。じゃあだめじゃん #プリクラ問題

2015-01-07 11:23:13
まる @ps_maru

プリクラ問題、雰囲気が分割数とかなり似ているのに、分割数は動的計画法でできてプリクラ問題は動的計画法の導入すらまだできないのはなぜなのか……。 #プリクラ問題

2015-01-07 13:20:25
むいにゃん♥ @mui_nyan

あれ?解けた気がする。(気がするだけ) #プリクラ問題

2015-01-07 15:58:11
ラン @gmcgso_kdeuvmt

ちょっとアルゴリズム変えてみたら平均的に悪くなった気がする #プリクラ問題 docs.google.com/spreadsheets/d…

2015-01-07 15:59:01
ラン @gmcgso_kdeuvmt

とても特別な例だけど(9,4)だけ1回減った…それぞれ特別な場合分けをしなきゃ一意に定まらないような気がしたのでお仕舞にする #プリクラ問題

2015-01-07 16:02:02
渡久地 信之 @palfem_kleet

そういえば,P(5n,2n)(n>=1)は10と9の繰り返しっぽいけどどっかに反例あるかなー? #プリクラ問題

2015-01-07 16:37:22
まる @ps_maru

modの問題は自主解決しました #プリクラ問題

2015-01-07 16:52:20
むいにゃん♥ @mui_nyan

組み合わせ表を上から埋めていく戦略を取れば再帰的に回数が求められるのは分かったけど、戦略自体が全く効率よくなかったオチ #プリクラ問題

2015-01-07 17:09:45
前へ 1 2 3 ・・ 13 次へ