2012年10月25日
プリクラ撮影での最適化
1ヶ月前、個人的な記録でメモしてたんですが、ジュニカレ的(ブログ、ツイッター)には放置していたことに気づきました。1ヶ月前の記録と回想です。
ある高校生から(9月7日の夜)質問がありました。「13人いて4人ずつプリクラ撮りたいんですけど、必ず全員と撮るには(最小で)何枚でいけますか?」と。」これは部活を引退する生徒が、効率よく写真撮影をしたいという自然な欲求から生まれた疑問でした。
この問題は(酔いが醒めながら)10分程度でメールで回答していたのですが、その後の経過についてです。
─9月8日─
昨晩の問題。「13人の人がいて、4人ずつプリクラを撮っていきます。全員が、すべての人と一緒に写っているよう(一緒に写っていない人がいないように)するとき、なるべく枚数を少なくするにはどうしたら良いか?」
高校の数学(大学入試)ではこのパターンの問題って見たことがない。しかし実際にはこのパターンで思考にはいることはあるよな、という感想。問題をくれた女子高生は、部活引退の際の記念撮影を効率よく済ませたいという欲求から質問をくれたようでした。
(ちなみに基本問題であるのは13人の人から4人グループを選ぶ場合の数は?とか・・。これだと13C4=13*12*11*10/4*3*2*1=715通り。でも今回のプリクラの問題はこんなことを聞いているわけではない。。)
この問題は、紙とペンと上手い思考があれば、きっちりと解けます。13通りですし、解は以下の例のみ(他の組み合わせだと13通りに収まらないはず)です。
1 2 3 4
1 5 6 7
1 8 9 10
1 11 12 13
2 5 8 11
2 6 9 12
2 7 10 13
3 5 9 13
3 6 10 11
3 7 8 12
4 5 10 12
4 6 8 13
4 7 9 11
しかし問題なのは、13人を6人ずつ撮影するとどうなるか???とりあえず9回(9通り)撮影をすれば十分だという解答例は分かったけれど、13人のうち3回撮影する人もいれば、5回撮影する人もでてきてしまう。それに問題を解くときにうまい解法(アルゴリズム)が浮かんでなくて、成り行き的に解いてしまっています。理想的には6回?でいけるんじゃないか!?という計算はしたのですが、解答例がまだありません。。誰か上手いこと8回以下の解答例があれば是非!!!!!
ちなみに数学と世間の好奇心をつなぐような問題はいくつかあって、よく知られているのは「囚人のジレンマ」「モンティホール問題」とかあります。でも自分的には、「プリクラ問題の最適化(勝手に名前付けた)」のほうが面白いと思います。しばらく考えますので、お知恵を・・・。
(これからビールがぶ飲みします。)
─9月17日─
グラフ理論のテキストを眺めてたら、少しずつ一般化の道筋が。グラフにして多角形の頂点、対角線の数を考えています。あまりが出るときをどう切り抜けるか、具体的な解(組合せ)をどう求めるかで考え中。
─9月18日─
n人いてr人ずつプリクラを撮るとき、その総枚数を"n_S_r"と表記することにする。(Pが既に使われているので、仕方なくSに。Sは撮影=ショットみたいな感じで。)
まず、基本として「1人あたりが撮影される写真の枚数」は(n-1)/(r-1)で表せる。例えば、"13人で4人ずつなら"=1人あたり12/3枚=4枚。
で、本題の"n_S_r"はn(n-1)/r(r-1)で表すことができる。例えば、13人で4人"13_S_4"=(13・12)/(4・3)=13枚。いくつか確かめてみたけど、この式でいけると思う。
で、次の問題は「13人で6人ずつ撮影するとき」のように、割り切れないとき考えるかという問題。さらに、「具体的な組み合わせを書き下す」にはどう考えるとうまくいくかという問題。
─10月25日─
で、現在は1ヶ月前から放置したままです。あまりが出るときの考え方について、表計算ソフトでnとrを変化させながら表にして、眺めています。プログラミングが得意な人にやって組んでもらいたいけど、なんにしても数え上げるアルゴリズムが。。。また暇をみて考えます。
こんなことがあったな、というお話でした。
ある高校生から(9月7日の夜)質問がありました。「13人いて4人ずつプリクラ撮りたいんですけど、必ず全員と撮るには(最小で)何枚でいけますか?」と。」これは部活を引退する生徒が、効率よく写真撮影をしたいという自然な欲求から生まれた疑問でした。
この問題は(酔いが醒めながら)10分程度でメールで回答していたのですが、その後の経過についてです。
─9月8日─
昨晩の問題。「13人の人がいて、4人ずつプリクラを撮っていきます。全員が、すべての人と一緒に写っているよう(一緒に写っていない人がいないように)するとき、なるべく枚数を少なくするにはどうしたら良いか?」
高校の数学(大学入試)ではこのパターンの問題って見たことがない。しかし実際にはこのパターンで思考にはいることはあるよな、という感想。問題をくれた女子高生は、部活引退の際の記念撮影を効率よく済ませたいという欲求から質問をくれたようでした。
(ちなみに基本問題であるのは13人の人から4人グループを選ぶ場合の数は?とか・・。これだと13C4=13*12*11*10/4*3*2*1=715通り。でも今回のプリクラの問題はこんなことを聞いているわけではない。。)
この問題は、紙とペンと上手い思考があれば、きっちりと解けます。13通りですし、解は以下の例のみ(他の組み合わせだと13通りに収まらないはず)です。
1 2 3 4
1 5 6 7
1 8 9 10
1 11 12 13
2 5 8 11
2 6 9 12
2 7 10 13
3 5 9 13
3 6 10 11
3 7 8 12
4 5 10 12
4 6 8 13
4 7 9 11
しかし問題なのは、13人を6人ずつ撮影するとどうなるか???とりあえず9回(9通り)撮影をすれば十分だという解答例は分かったけれど、13人のうち3回撮影する人もいれば、5回撮影する人もでてきてしまう。それに問題を解くときにうまい解法(アルゴリズム)が浮かんでなくて、成り行き的に解いてしまっています。理想的には6回?でいけるんじゃないか!?という計算はしたのですが、解答例がまだありません。。誰か上手いこと8回以下の解答例があれば是非!!!!!
ちなみに数学と世間の好奇心をつなぐような問題はいくつかあって、よく知られているのは「囚人のジレンマ」「モンティホール問題」とかあります。でも自分的には、「プリクラ問題の最適化(勝手に名前付けた)」のほうが面白いと思います。しばらく考えますので、お知恵を・・・。
(これからビールがぶ飲みします。)
─9月17日─
グラフ理論のテキストを眺めてたら、少しずつ一般化の道筋が。グラフにして多角形の頂点、対角線の数を考えています。あまりが出るときをどう切り抜けるか、具体的な解(組合せ)をどう求めるかで考え中。
─9月18日─
n人いてr人ずつプリクラを撮るとき、その総枚数を"n_S_r"と表記することにする。(Pが既に使われているので、仕方なくSに。Sは撮影=ショットみたいな感じで。)
まず、基本として「1人あたりが撮影される写真の枚数」は(n-1)/(r-1)で表せる。例えば、"13人で4人ずつなら"=1人あたり12/3枚=4枚。
で、本題の"n_S_r"はn(n-1)/r(r-1)で表すことができる。例えば、13人で4人"13_S_4"=(13・12)/(4・3)=13枚。いくつか確かめてみたけど、この式でいけると思う。
で、次の問題は「13人で6人ずつ撮影するとき」のように、割り切れないとき考えるかという問題。さらに、「具体的な組み合わせを書き下す」にはどう考えるとうまくいくかという問題。
─10月25日─
で、現在は1ヶ月前から放置したままです。あまりが出るときの考え方について、表計算ソフトでnとrを変化させながら表にして、眺めています。プログラミングが得意な人にやって組んでもらいたいけど、なんにしても数え上げるアルゴリズムが。。。また暇をみて考えます。
こんなことがあったな、というお話でした。
Posted by juniorcollege at 12:00│Comments(0)
│何でもないこと