ある難関校でだされた大学入試問題がわかりません。

質問

高校の講義で出された問題なのですが、まったくわからないです。
解法ご存じのかたおられましたら教えて下さい。

　問題　□□□□□□
　　　　　□□□□
　　　　　　　　　　　　　　　　　　　このような枠がある。１から１０までの自然数を各枠の中に１つずつ
　　　　　次の２つの条件を満たすように並べる。
　　　　　１．各段においては、枠の中の数は右に行くに従って大きくなる。
　　　　　２．左から４個の各列においては、下段は上段の数よりも大きい。

　　　　　です。ひたすら数えたところ９０？という数字が出てきたのですが、正しいのかどうかも
　　　　　わかりません。。。こんな解法があるよ！というかた、よろしくお願いします。
　　　　　（それにしてもどこの入試なんでしょうか）

回答No.10

f272 · ベストアンサー

リクエストがあったので「計算だけで出すのなら10C4-10C3で答えは出る」の解説を書いてみる。

問題は，10個の数字を6個と4個に分けて，条件１と条件2を満たすようにすると，並べ方の総数はいくつか？

条件１だけを満たせばよいのであれば，話は簡単で10C４です。なぜなら10個の数字から4個を選んで小さい順に並べると下段ができて，残りの6個の数字を小さい順に並べると上段ができるからですね。

条件1を満たすもののうち，条件２を満たさないものが10C3通りであるということが分かればおしまいですが，これはちょっと面倒です。10C3通りというのは普通に考えると10個の数字から3個を選ぶ方法の数です。言い換えると「10個の数字を7個と3個に分けて条件１を満たすようにするときの並べ方の総数」ですね。実は「(A) 10個の数字を7個と3個に分けて条件１を満たすようにする」のと「(B) 10個の数字を6個と4個に分けて条件１を満たすが条件2は満たさないようにする」のは並べ方の総数は同じになります。それを示すには(A)と(B)に一対一対応があることを示せばよくて，そのためには(A)から(B)への対応が必ず作れて，かつ，(B)から(A)への対応が必ず作れることを示せばよいですね。それでは以下でその対応を作ってみます。

(B)から(A)への対応はどちらかというと簡単です。
たとえば(B)として(234567,1890)を考えてみます。
なおなるべく簡潔に表すように(上段の数字,下段の数字）としています。また10の代わりに0と書いています。
この例では1列目が2と1で条件２を満たしません。このとき，下段1列目の１を上段に移動すれば(A)として(1234567,890)が出来ます。一般的に言えば
1列目から(m-1)列目までは条件2を満たし，m列目で初めて条件２を満たさないとき，下段1列目からm列目の数字を上段に移し，上段1列目から(m-1)列目の数字を下段に移します。これで(B)から(A)への対応が得られます。

(A)から(B)への対応はまったく逆にすれば出来るのですが，言葉で言おうとするとちょっと面倒です。
上段1列目が1であれば，それを下段に移します。
(1BCDEFG,HIJ)→(BCDEFG,1HIJ)
上段1列目が1でなく上段2列目が3であれば，上段2列目までを下段に，下段1列目までを上段に移します。
(23CDEFG,1IJ)→(1CDEFG,23IJ)
上段1列目が1でなく上段2列目が3でなく上段3列目が5であれば，上段3列目までを下段に，下段2列目までを上段に移します。
(245DEFG,13J)→(13DEFG,245J)
(345DEFG,12J)→(12DEFG,345J)
上段1列目が1でなく上段2列目が3でなく上段3列目が5でなく上段4列目が7であれば，上段4列目までを下段に，下段3列目までを上段に移します。
(2467EFG,135)→(135EFG,2467)
(2567EFG,134)→(134EFG,2567)
(3467EFG,125)→(125EFG,3467)
(3567EFG,124)→(124EFG,3567)
(4567EFG,123)→(123EFG,4567)
上段1列目が1でなく上段2列目が3でなく上段3列目が5でなく上段4列目が7でない，ということはありえません。(その理由は考えてね)

以上で(A)と(B)に一対一対応があることが分かりますから，その並べ方の個数は同じで10C3となることが分かりました。

補足

しっかり考えてみたところ、よくわかりました！
目からうろこが落ちたような感じです！
こんなことを思いつくなんてすごすぎます。。。
都会の予備校とかで教えておられるんでしょうか。。。
うちは田舎なのでなんか不安になってきました。。。

回答No.9

potatorooms

友だちと考える機会があるなら、最初に回答された方の図を、方眼紙に書き出してみましょう。
また、質問にある□の２行に、上、下と名をつけ、回答の図の方眼のＡとＢ以外の空いた四隅に、上、下をあてはめましょう。

そのうえで、方眼紙のＡからＢへの道筋を１つ例として辿ってみて、その道筋が、質問のどういうパターン（数字の札をどうあてはめたケースか）を描いてみるといいです。
方眼の中の書かれていない場所が、なぜ、書かれていないのかを、理解できる可能性があるかと思います。

ちなみに、テストの時に、思いつけないと解けない方法は、オススメしませんが、センスを磨くには良い例だと思いますよ。

回答No.8

f272

> じゃあコンビネーションは使えないと言うことですか。
> あとは場合分けなんですね！

No.3で書かれているように，場合を分けて考えるほうがたぶん考えやすいのだろうが，
計算だけで出すのなら10C4-10C3で答えは出る。解説を書いても理解できないと言われそうなので書かないが...

補足

いいえ。死ぬ気で理解するようにしますから、書いてくださいませ。
自分が理解できなかったら友達とみんなで考えますから。
是非お願いします。

回答No.7

potatorooms

複雑に見える事象を見える形に整理することかと。

回答No.6

potatorooms

追加ね。
場合の数での、数え上げの解法は、センスが必要です。最初の回答者さんの内容を答案に書けば、多分満点をもらえますよ。説明すべきことはきちんと説明されています。
もし、この説明で理解できないなら、この解法は取らない方が良いです。私が理由を詳しく書いてもおそらくピンとこないままだと思います。

補足

そうですか。ちょっと考えてみます。そのやり方で大丈夫なのですか。
センスというのはこういう風に読み替える事が必要ということですか？

回答No.5

potatorooms

ヒントだけで良いですよね。

｜Jが１０のとき
｜残りの９個の枠は何でもいいです。よって９C3で求まります。８４通りです。

これ、間違いです。回答者さんが勘違いしている、または、質問者さんの出題がダメのどちらかです。
私が書いたように、残りの枠は何でもよいわけではありません。たとえば、下の枠に、１、２、３、１０　と入ると、２の条件「左から４個の各列～」は満たしません。
この回答の場合、「左から４番「目」の列」だけが、下が上より大きいという条件になっています。「各列」すべてが条件を満たすのなら、最初の回答者さんの答えは、数え上げの解法の見本です。
場合分けの解法で解答を作る場合は、私が書いた内容を確認してみてください。

補足

じゃあコンビネーションは使えないと言うことですか。
あとは場合分けなんですね！

回答No.4

akeshigsb

まず上の列を左からAからFとします。下の列はGからJです。
するとJは８，９，１０のいずれかになります。
仮にJが７と仮定するとしたら下の列は最大値が７ということになりますね。
上の列には８、９、１０があります。すると、Dには８が入り２の条件を満たしません。よってJは８，９，１０のいずれかになります。

Jが８のとき
必然的にEFに９，１０が入ります。（下の段は最大値８の仮定ですし、数字が大きければ右側なんで）
残りのA～D、G～Iに関してはどんな数字が入ってもいいです。（もちろん右側になれば大きくなります）
よって７C3で求まります。残りの７個の数字からG～Iを選び出す、順番は考慮せず選んだもののなかから小さいものを左にしていけばいいです。すると７C３=３５通りになります。

Jが９のとき
上と同じように考えFは１０に固定されます。
Jが９であり、それより大きい１０がFに固定されることでDは何でもよくまた他の箇所も何でもよくなります。よって残りの８個の数字からG～Iを選ぶ８C3で求めります。８C３=５６通り。

Jが１０のとき
残りの９個の枠は何でもいいです。よって９C3で求まります。８４通りです。

以上の合計の１７５通りです。
計算が間違ってるかもしれませんが解法は一番楽で
分かりやすいんでないでしょうか？
なんか一橋や横国もしくは旧帝大の若干簡単めか、地方国立大の合否を分けるレベルの問題と思います。
（２）なんかは「上はN個、下はN－２このときの場合は何通りかを求めよ」なんてものかもしれません。

Jが８～１０しか入らないとわかれば比較的簡単な問題でありALL or NOTHING　問題です。
（そこに気付けば簡単、気付かないと０点な問題。）
ご参考までに。

ちなみに７C3などの表記がありますが本来はCが大きめな表記です。（コンビネーションの略です）

補足

お返事遅れました。教えてくださってありがとうございます。
ちなみに下記の９０とおり、と書いておられる方の解法はどう
思われますか？わたしはいまいちよくわからないのですが。。。

回答No.3

potatorooms

自然数１～１０が書かれたカードを並べていくと考えて良いですね。

１．各段においては、枠の中の数は右に行くに従って大きくなる。

ということは、１～１０のカードを、右から順に並べていく、という単純作業です。ＯＫですか？
並べる際に、上か下に置く、という２パターンがあるだけです。
でね、下に置く、という動作の代わりに、１～１０並んだカードから、４枚を抜き取る、という動作に変えてみましょう。

そうすると、１０枚のカードから４枚のカードを抜き取る場合の数は？　という問題に変わります。ＯＫですか？
最初の１枚は、１０通り、次の・・・で、
（１０×９×８×７）　÷　（１×２×３×４）　ですね。
これが並べるすべてのパターン。

２．左から４個の各列においては、下段は上段の数よりも大きい。

で、今度は、カードを４枚取る代わりに、×を打つことにしますね。×でないカードは呼びにくいので○にしましょう。
そうすると、×を打つカードの右側には既にある×の数以上のカードがないとダメ、ということになります。
最初の×は２番目以降。２番目の×は４番目以降、３番目の×は６番目以降、４番目の×は８番目以降についていれば良いだけです。４番目の×がつくのは８番目～１０番目のカードだけと決まっているので、各々場合分けすると手作業でだせます。（ダメなケースの方を考えることで計算でもだせますが）

補足

お返事遅れました。教えてくださってありがとうございます。
皆さんに同じようなこと書いて住みませんが、
ちなみに下記の９０とおり、と書いておられる方の解法はどう
思われますか？わたしはいまいちよくわからないのですが。。。
.

回答No.2

potatorooms

条件は書いてあるけど、問題は書かれていない気がするのですが。

補足

確かに。。。すみません。
並べ方の総数を求めよ、です。
よろしくお願いします。

回答No.1

f272

こんな感じ。
A点からB点に進みながら，枠に1から10まで順に数字を書く。
A点からB点までどのような経路で進んだかが，枠に書かれる数字の組み合わせの種類に対応する。
下に行くときは，1段目の左から順にに数字を書く。
右に行くときは，2段目の左から順にに数字を書く。
下には6回，右には4回しか進めないことや，図に線の書いていない経路を進めないのはこの問題の条件から明らか。

A点からB点までの最短経路の数は小学生でも分かるように，経路上に書いてある数字で上と左の数字を足し算すればよい。

補足

ありがとうございます。
上にも書きましたが、問題を書き忘れていました。
並べ方の総数を求めよ、です。よろしくお願いします。