12月家の歌声



  • ヨーロッパヤマネ(hazel dormouse)の12月家のお話です。
    12人の姉妹は町のイベントに参加することになりました。
    12人揃って歌を歌う予定です。
    0_1522505515954_舞台 - コピー.png
    特設会場には、上の図のように長方形の舞台にL字の観客席が設けられ
    下図のように舞台を上から見た時、縦は4列横3列に並びます。
    図では縦列をそれぞれA,B,C,Dとし、横列をそれぞれ1,2,3と振ってあります。
    0_1522505552378_12月家並び - コピー.png
    12月家の姉妹は12人すべて背の高さが違うので、できるだけ皆の顔がどちら側の観客からも見えやすいように、
    各縦列では一列目から三列目まで順に背が高くなるように
    各横列ではA列からD列まで順に背が高くなるように並ぶことにしました。

    つまり
    A-1<A-2<A-3
    B-1<B-2<B-3
    C-1<C-2<C-3
    D-1<D-2<D-3

    A-1<B-1<C-1<D-1
    A-2<B-2<C-2<D-2
    A-3<B-3<C-3<D-3

    のようにします。
    たとえば背が低い方から順に①~⑫とすると
    0_1522505579587_12月家並び2 - コピー.png
    このような順に並ぶことができますね。
    では問題です

    【問題】
    このような条件に合うような並び方は何通りあるでしょう。
    ノート(紙)とペンだけで答えを出してみてください。
    検算のためにプログラムを組んで計算しても構いませんが、あくまでも検算として使用して下さい。

    回答は即時OKです。

    4月8日(日)午後10時までに正解が出ない場合は解答を発表します。
    特に期限を設けません。
    正解が出なかった場合、議論が尽きたころに正解を発表します。
    数値が1つに定まった回答は隠す機能を使ってください。
    だいたいこの範囲などの考え方はオープンでOKです。(4/1修正&追記)
    解答発表後にプログラムを組めない出題者に代わって、どなたかプログラムで検算をお願いします。(無茶ぶり)



  • @マーモセット さん
    (^^♪

    (^^♪祝

    場合の数を考えるのが大変です
    10!からどう減らせるのか考えて見ます。
    すこし取り込み中<私のBlogに理由が書いてあります。>ですので
    考え始めるのは水曜日くらいからになります。(;'∀')



  • @riffraff さん
    回答お待ちしています♪

    ちょっと面倒な問題なので、1週間では時間が短いかと思いましたが、取りあえず目安があったほうが、よいかと思い期限を決めました。
    もう少し時間が欲しいという意見があれば延長可です。
    さっぱりわからないという人は、だいたいこれくらいになるだろうという大雑把な回答でも歓迎です。


  • Global Moderator

    @マーモセット さん

    もう少し時間が欲しいという意見があれば延長可です。

    こんなお便りが寄せられています:

    ・12人のヤマネっこたちを新たに描くには、とても時間が足りません(挿絵係)


  • Global Moderator

    もし並び方に制約がなければ、12!≒4.8億とおりの並び方がありますね。一方、もし背の高さどおりに一列に並ぶ必要があるなら、1とおりですね。今回の問題の答えはこの間のどこかです(笑

    1 < 解 < 4.8億

    少し制約を増やし、A,B,C,Dのそれぞれの列だけで背の高さ順になる場合には、まず12人を3人ずつに分け、それぞれのグループ内で背の高さ順が1とおりあります。ということは、単純に3人ずつに分ける方法の場合の数になります。これは、

    12!/3!/3!/3!/3! = 369600

    とおりです。1,2,3のグループで見た場合には、

    12!/4!/4!/4! = 34650

    とおりです。実際には両方のグループ分けで同時に制約があるので、解は、

    1 < 解 < 34650 < 369600 < 4.8億

    この範囲にありそうです。



  • @ソム さん

    ・12人のヤマネっこたちを新たに描くには、とても時間が足りません(挿絵係)

    挿絵まで期待できるのですね。
    楽しみです\(^o^)/
    期限は設けないで議論が尽きたころにします。

    1 < 解 < 34650 < 369600 < 4.8億
    この範囲にありそうです。

    だいぶ範囲が狭まってきましたね。
    皆さんがこの問題を解く時『どんな考え方で進めていくか』をお聞きするのが楽しみです。
    頑張ってくださ~いヽ(^o^)丿


  • System

    先頭記事が更新されました。


  • Global Moderator

    今度は、下限側を攻めてみたいと思います。

    0_1522546922773_12month_consert.png

    図の線で切ってグループわけしてやると、もし集団内の最も背の低いひとでも、その左下のグループの人たちより背が高くなっていれば、条件を満たします。しかし、必ずしもそうである必要はないので、これは、実際よりも強い制約になります。下限側の値です。

    このときの場合の数は、1! 2! 3! 3! 2! 1! = 144 になるので、

    144 < 解 < 34650

    この範囲にありそうです。



  • @ソム さん

    144 < 解 < 34650
    この範囲にありそうです。

    ドキッ(◎_◎;)
    だいぶ近づいてきましたね。
    私が想定していた解法とは別方向からの攻めになっていますが、どこまで範囲が狭められるか、今後がますます楽しみです。



  • これが使えないかと考え始めました

    0_1522567304391_junjo.jpg
    相対的大小は順序のしばり、タイは制約外です



  • @riffraff さん
    お絵かき回答が期待できそうですね。

    私の解法もお絵かきになります。
    問題文を読んだ瞬間、すぐに気づいた人もいらっしゃるかも。
    (ちょっとヒント出し過ぎ(°O゜)☆\(^^;) バキ!)


  • Global Moderator

    小さい問題を考えて見ました。2x2の編成だと単純すぎるので、2x3、計6人です。

    本題と同じように上限・下限を見積もると、

    1!2!2!1 < 解 < 6!/3!/3!
    4 < 解 < 20

    これなら全可能性をノートとペンでチェック可能です。まず「上限」の20通りを全て列挙し、そのうち、最終条件を満たすものに○を付けました。

    1 2 3
    4 5 6
    ------
    1 2 4
    3 5 6
    ------
    1 2 5
    3 5 6
    ------
    1 2 6
    3 4 5
    ------
    1 3 4
    2 5 6
    ------
    1 3 5
    2 4 6
    ------
    1 3 6
    2 4 5
    ------
    1 4 5
    2 3 6
    ------
    1 4 6
    2 3 5
    ------
    1 5 6
    2 3 4
    ------
    2 3 4
    1 5 6
    ------
    2 3 5
    1 4 6
    ------
    2 3 6
    1 4 5
    ------
    2 4 5
    1 3 6
    ------
    2 4 6 ○
    1 3 5
    ------
    2 5 6 ○
    1 3 4
    ------
    3 4 5
    1 2 6
    ------
    3 4 6 ○
    1 2 5
    ------
    3 5 6 ○
    1 2 4
    ------
    4 5 6 ○
    1 2 3
    ------
    

    4 < 解 = 5 < 20

    となり、意外と見積もりの下限に近かったです。「下限」の制約で弾いたのは、

    4 5 6 ○
    1 2 3
    

    だけです。


  • Global Moderator

    小さい問題を見て気づいたのですが、左下隅と右上隅は1,6で確定ですね。例えば、6が右上隅以外にあると、その右か上の人が必ず居ます。するとその人は必ず6より小さいのでルール違反になります。同じ理由で、左下隅は1が確定です。

    するとこの場合の上限の見積もりはもっと小さくできて、

    4 < 解 < 6

    になります。4C2 * 4C2 = 6 です(nCm は、n個からm個を選ぶ場合の数)。同じように計算すると、12月家の場合には、

    10C3 * 7C4 * 3C3 = 4200 なので、

    144 < 解 < 4200

    の範囲になりそうです。



  • @ソム さん

    小さい問題を考えて見ました。2x2の編成だと単純すぎるので、2x3、計6人です。

    出題者にとってドキドキするような鋭い発想ですね。
    この問題もこうした小さいスケールでの解法を応用したものです。



  • @マーモセット さん

    現状報告です

    0_1522586802568_pale.jpg
    この4パターンのようです
    3から10をどう入れるか(;'∀')



  • @riffraff さん

    Re:現状報告です

    こうやって見ると、残りが入るパターンは少なそうに見えますが、@ソム さんの計算でも144以上にはなるので、ここから詰めていくのもまだ難所がありそうですね。

    ただ、@riffraff さん、@ソム さんの考え方の流れを見ていると、想定解よりも簡単に答えが出てきそうで、ヒヤヒヤしています。


  • Global Moderator

    @マーモセット さん

    一見、簡単そうに思えましたが、難しいです。かといって、コンピューターで全数探索しないと解けないだろうと思うほどでもないです。工夫でなんとかなりそうな期待が持てる、絶妙なバランスだと思います。



  • @ソム さん
    楽しんでいただけているようでよかったです。
    この問題は、ある方法をちょっと工夫することで答えが出せますが、計算で出せるかどうかは知りません。(無責任ですみません)



  • マーモセットさん、御出題を有り難うございます。

    脳ミソしびれそうです(快

    追伸
    tan of arccos of tan of arccos of sin of arctan of sqrt of 145
    が答えです (嘘



  • @Hannibal さん
    回答をお待ちしています。
    私の勘では、@Hannibal さんはすでに「ある方法」には気付かれているかも(#^.^#)


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.