問題提起
あのね。前々からずーーっと答えが知りたい数学の問題があって。 ①n人のグループがいる ②プリクラ機械には一度にm人しか入れない この場合、全員が必ず他の全員と最低一回は同時に撮影される為には、何回撮影する必要があるか? 実際の事例から考えた問題だけど、自力では解けない。
2015-01-01 22:54:02現段階の進捗状況
#プリクラ問題 の厳密解と上界の表(n≦50, m≦25)(pic.twitter.com/NQZehIdutZ)の改良版。挟み撃ちで厳密解と断定できるところを染めました。 pic.twitter.com/1kI6RYURKf
2015-01-06 01:12:01@hiroko_TB ぼんやり考えていたのですが、理論値は厄介そうなので貪欲的な解法で解を求めてどれほど性能が出るか計算機を回して試してみました。横軸が人数、縦軸が回数です。ほとんど下限値(nC2/mC2)に近い解が得られるようです。 pic.twitter.com/fEwHeVu3YI
2015-01-02 21:33:39仮説:m=3のときの厳密解P(n,3)=[(n/3)[(n-1)/2]] ([]は端数切り上げ) n<100での成立は確認 #プリクラ問題
2015-01-04 18:45:37m=3のとき、(n,解)=(x,y)としてy=x^2/6と近似してみて差を取ってみたの図。この差(紫)を三角関数か何かでさらに近似すればかなり正確に出そう?でももしそれでできるなら既に昔の数学者が求めてるはず……? #プリクラ問題 pic.twitter.com/2c88ahJG2U
2015-01-04 16:41:01@kgneissr 丸めの問題なのでしょうか…。誤差は添付画像の右下の赤線のような感じです。横向き[で囲った3つ組(下も含めれば6つ組)で、3つ目の矢印のところがやや(ほぼ定数値だけ)0寄りという三つ組の繰り返しです。 #プリクラ問題 pic.twitter.com/AGSGbX8K0a
2015-01-04 18:14:39考えの方針など
#プリクラ問題 、今のところ ・nC2 /2mを厳密解だと考えてる人 ・nC2/mC2を厳密解だと考えてる人 ・女学生問題あたりを考えてる人 ・ブロックデザインを考えてる人 みたいに把握レベルがバラバラなので、要点だけ抜き出した「まとめのまとめ」が必要かも
2015-01-04 12:32:47おそらくP(n,m)=[(n/m)[(n-1)/(m-1)]]なんじゃないかというのが大方の見方だけど……でも反例もあるっぽいしなぁ…… #プリクラ問題
2015-01-04 20:07:10#プリクラ問題 このサイトだと上界(というより現時点で見つかっている最小パターン)の一覧が載っているだけで厳密解ではないっぽい ccrwest.org/cover/HIGH.html
2015-01-04 12:06:09以下議論の流れ
n個の中からm個を選ぶ組み合わせで、順序を保存しないのはn!/(m!(n-m)!)でよく出てくるので_nC_rtと書く。 dinop.com/vc/combination…
2015-01-01 22:59:43@hiroko_TB @Lord_HIGE @hthsi @kuma5th ちょっと問題文が違う気がする!それはn個から最大m個を選択するのを繰り返した場合、最短でnのすべての要素を選択できるのは何回かってこと?
2015-01-01 23:32:30あしやまさんのプリクラ問題、(n,m)=(7,5)の時に最小回数が4という時点で、7C5=7!/5!=42がどう頑張っても4にならなさそうだから辛くなってきた
2015-01-01 23:36:19プリクラ問題の難しいのはプリ機で最大m人撮れるときにm以下も許されるから高校の単純な組み合わせの考え方だけでは解けんところかな。
2015-01-01 23:41:35