１２月家の歌声
-
ヨーロッパヤマネ（hazel dormouse）の12月家のお話です。
12人の姉妹は町のイベントに参加することになりました。
12人揃って歌を歌う予定です。
特設会場には、上の図のように長方形の舞台にL字の観客席が設けられ
下図のように舞台を上から見た時、縦は4列横3列に並びます。
図では縦列をそれぞれA,B,C,Dとし、横列をそれぞれ1,2,3と振ってあります。
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-3A-1＜B-1＜C-1＜D-1
A-2＜B-2＜C-2＜D-2
A-3＜B-3＜C-3＜D-3のようにします。
たとえば背が低い方から順に①～⑫とすると
このような順に並ぶことができますね。
では問題です【問題】
このような条件に合うような並び方は何通りあるでしょう。
ノート（紙）とペンだけで答えを出してみてください。
検算のためにプログラムを組んで計算しても構いませんが、あくまでも検算として使用して下さい。回答は即時ＯＫです。
4月8日（日）午後１０時までに正解が出ない場合は解答を発表します。
特に期限を設けません。
正解が出なかった場合、議論が尽きたころに正解を発表します。
数値が1つに定まった回答は隠す機能を使ってください。
だいたいこの範囲などの考え方はオープンでOKです。（4/1修正＆追記）
解答発表後にプログラムを組めない出題者に代わって、どなたかプログラムで検算をお願いします。（無茶ぶり）
-
@マーモセット さん
(^^♪(^^♪祝
場合の数を考えるのが大変です
10！からどう減らせるのか考えて見ます。
すこし取り込み中＜私のBlogに理由が書いてあります。＞ですので
考え始めるのは水曜日くらいからになります。(;'∀')
-
@riffraff さん
回答お待ちしています♪ちょっと面倒な問題なので、１週間では時間が短いかと思いましたが、取りあえず目安があったほうが、よいかと思い期限を決めました。
もう少し時間が欲しいという意見があれば延長可です。
さっぱりわからないという人は、だいたいこれくらいになるだろうという大雑把な回答でも歓迎です。
-
-
もし並び方に制約がなければ、１２！≒４．８億とおりの並び方がありますね。一方、もし背の高さどおりに一列に並ぶ必要があるなら、１とおりですね。今回の問題の答えはこの間のどこかです（笑
1 < 解 < 4.8億
少し制約を増やし、Ａ，Ｂ，Ｃ，Ｄのそれぞれの列だけで背の高さ順になる場合には、まず１２人を３人ずつに分け、それぞれのグループ内で背の高さ順が１とおりあります。ということは、単純に3人ずつに分ける方法の場合の数になります。これは、
12!/3!/3!/3!/3! = 369600
とおりです。１，２，３のグループで見た場合には、
12!/4!/4!/4! = 34650
とおりです。実際には両方のグループ分けで同時に制約があるので、解は、
1 < 解 < 34650 < 369600 < 4.8億
この範囲にありそうです。
-
@ソム さん
・１２人のヤマネっこたちを新たに描くには、とても時間が足りません（挿絵係）
挿絵まで期待できるのですね。
楽しみです＼(^o^)／
期限は設けないで議論が尽きたころにします。1 < 解 < 34650 < 369600 < 4.8億
この範囲にありそうです。だいぶ範囲が狭まってきましたね。
皆さんがこの問題を解く時『どんな考え方で進めていくか』をお聞きするのが楽しみです。
頑張ってくださ～いヽ(^o^)丿
-
先頭記事が更新されました。
-
今度は、下限側を攻めてみたいと思います。
図の線で切ってグループわけしてやると、もし集団内の最も背の低いひとでも、その左下のグループの人たちより背が高くなっていれば、条件を満たします。しかし、必ずしもそうである必要はないので、これは、実際よりも強い制約になります。下限側の値です。
このときの場合の数は、1! 2! 3! 3! 2! 1! = 144 になるので、
144 < 解 < 34650
この範囲にありそうです。
-
@ソム さん
144 < 解 < 34650
この範囲にありそうです。ドキッ(◎_◎;)
だいぶ近づいてきましたね。
私が想定していた解法とは別方向からの攻めになっていますが、どこまで範囲が狭められるか、今後がますます楽しみです。
-
これが使えないかと考え始めました
相対的大小は順序のしばり、タイは制約外です
-
@riffraff さん
お絵かき回答が期待できそうですね。私の解法もお絵かきになります。
問題文を読んだ瞬間、すぐに気づいた人もいらっしゃるかも。
（ちょっとヒント出し過ぎ(°O゜)☆＼(^^;) バキ！）
-
小さい問題を考えて見ました。２ｘ２の編成だと単純すぎるので、２ｘ３、計６人です。
本題と同じように上限・下限を見積もると、
1!2!2!1 < 解 < 6!/3!/3!
4 < 解 < 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だけです。
-
小さい問題を見て気づいたのですが、左下隅と右上隅は１，６で確定ですね。例えば、６が右上隅以外にあると、その右か上の人が必ず居ます。するとその人は必ず６より小さいのでルール違反になります。同じ理由で、左下隅は１が確定です。
するとこの場合の上限の見積もりはもっと小さくできて、
4 < 解 < 6
になります。4C2 * 4C2 = 6 です（nCm は、n個からm個を選ぶ場合の数）。同じように計算すると、１２月家の場合には、
10C3 * 7C4 * 3C3 = 4200 なので、
144 < 解 < 4200
の範囲になりそうです。
-
@ソム さん
小さい問題を考えて見ました。２ｘ２の編成だと単純すぎるので、２ｘ３、計６人です。
出題者にとってドキドキするような鋭い発想ですね。
この問題もこうした小さいスケールでの解法を応用したものです。
-
@マーモセット さん
現状報告です
この4パターンのようです
３から10をどう入れるか(;'∀')
-
@riffraff さん
Re:現状報告です
こうやって見ると、残りが入るパターンは少なそうに見えますが、@ソム さんの計算でも144以上にはなるので、ここから詰めていくのもまだ難所がありそうですね。
ただ、@riffraff さん、@ソム さんの考え方の流れを見ていると、想定解よりも簡単に答えが出てきそうで、ヒヤヒヤしています。
-
@マーモセット さん
一見、簡単そうに思えましたが、難しいです。かといって、コンピューターで全数探索しないと解けないだろうと思うほどでもないです。工夫でなんとかなりそうな期待が持てる、絶妙なバランスだと思います。
-
@ソム さん
楽しんでいただけているようでよかったです。
この問題は、ある方法をちょっと工夫することで答えが出せますが、計算で出せるかどうかは知りません。（無責任ですみません）
-
マーモセットさん、御出題を有り難うございます。
脳ミソしびれそうです（快
追伸
tan of arccos of tan of arccos of sin of arctan of sqrt of 145
が答えです （嘘
-
@Hannibal さん
回答をお待ちしています。
私の勘では、@Hannibal さんはすでに「ある方法」には気付かれているかも(#^.^#)
