プリクラ問題

プリクラを最短で撮り終える回数を求める問題(未解決) 条件は以下の通り。 (1)n人がいる (2)プリクラ機には一度にm人しか入れない 続きを読む
40
前へ 1 2 ・・ 42 次へ
hth @hthsi

@faifx @hiroko_TB @inanzu @kuma5th @Lord_HIGE 要はこのように書いた総当たりのマスを最短で埋める方法を見つけるということで良いですね? moby.to/ta261g

2015-01-01 23:50:33
hth @hthsi

あしやまさんのプリクラ問題、総当たりの表を作ると(n*n-1)/2の空白を一度に最高でも(m*m-1)/2箇所しか埋められないと考えると最低でも何回必要なのかがわかる

2015-01-01 23:53:34
いなんず @inanzu

これ直交群使わないととけないような気がしてきた。

2015-01-01 23:53:36
髭伯爵(ぬ) @Lord_HIGE

@hiroko_tb @hthsi @faifx @inanzu @kuma5th n個の要素からm個を取り出して、o個の組み合わせを問題にするのか…

2015-01-01 23:53:56
いなんず @inanzu

i1)互いに直交する要素O0,O1..On=O、On*On=O0、On*O0=0があって、その中から任意のr個を選択し、新しく集合pを作る 2)これをi回施行して、集合p[i]について(n<i)Π(p[n])=O0になる最小のiを求めよ

2015-01-01 23:58:53
いなんず @inanzu

っていうふうに取れるか?

2015-01-01 23:59:03
いなんず @inanzu

nビットの数列があって、mビット個の組み合わせyをi回選んだ時、任意のyのうち2つの要素XORを取った時、最低1個でもビットが残る組み合わせを作った時の最小のiは幾つか?か。

2015-01-02 00:04:37
いなんず @inanzu

って要するに連結区間がある要素を数えりゃいいんだからfloor(n÷(m-1))+1(m>1は条件から自明)で終わりな気がして来た

2015-01-02 00:06:53
あしやまひろこ @hiroko_TB

「要はこのように moby.to/ta261g 書いた総当たりのマスを最短で埋める方法」by @hthsi  はつほさんの考え方が一番近そうなのでご紹介 @hthsi @faifx @inanzu @kuma5th @Lord_HIGE

2015-01-02 00:06:53
いなんず @inanzu

あ、でもそれだと連結はしてるけど必ずしも互いの連絡が取れないか。

2015-01-02 00:09:04
いなんず @inanzu

てそんなことを考えてたら2日になってたよ!

2015-01-02 00:09:45
いなんず @inanzu

なんだかモデル化したらあっさり解けそうだし、数列に含まれている/含まれていないだからようは連結の有る無しを表現できるモデルを定義できれば解けそうに思うけど、たしかにめんどっちい

2015-01-02 00:12:11
hth @hthsi

@hiroko_TB この問題、どうしても「余り」の概念が出てきてしまうので、+-×÷じゃ表現しきれないのでは…

2015-01-02 00:14:43
あしやまひろこ @hiroko_TB

.@hthsi そうかもしれません…。繰り返しになるんですが、自分は数学は高校までしかやっていなくて、実際にプリクラを撮っているときに考えた問題なので、もちろん回答もアプローチもまったくわからないのです……。

2015-01-02 00:17:40
いなんず @inanzu

なんだか普通に情報数理上実用的な問題なきがする>プリクラに集まった時最小の手数でお互い全員をカバーする方法

2015-01-02 00:20:39
遼哉(Ryoya) @ryoya9826

むずかしい!なんだこれ

2015-01-02 00:20:59
hth @hthsi

@hiroko_TB 自分も専攻が数学でないのと確率論ですら独学だもんで余り自信はないです… ですが、少しでも問題をスッキリさせられればと思いました。とても面白い問題だと思います!

2015-01-02 00:21:53
遼哉(Ryoya) @ryoya9826

普通にnCmじゃないかと考えてしまう…

2015-01-02 00:23:38
遼哉(Ryoya) @ryoya9826

@yukanoria もうそんなことは言ってないですw なんや恥ずかしいww いやすばらしいです、ありがとうございます!

2015-01-02 00:25:10
前へ 1 2 ・・ 42 次へ