私は東大実践模試を数十年分集めていて、良問があったので、それを改題したら、自

数学

高校生

解決済み

7年弱前

私は東大実践模試を数十年分集めていて、良問があったので、それを改題したら、自分でも手も足も出ない解けないくらいの難問になってしまいました…。
どなたか詳解をお願いします！！
おそらく問題の難易度としては、東大数学で上位の点数を取る方、、、といったくらいでしょうか…。
以下、その問題をあげますね。

【問題】nを2以上の整数とする.
1, 2, …, nを記入したカードがそれぞれ2枚ずつ, 合計2n枚ある. これらのカードを次の条件(A),(B)を満たすように2枚ずつn組に分ける方法の総数をanとする.
(A) どの組においても, 2枚のカードに書かれた数字は異なる.
(B) どの組についても, 一方の組の2枚のカードに書かれた数字の組合せと他方の組の2枚のカードに書かれた数字の組合せは異なる.
例えば, a2=0, a3=1 , a4=3である.
(1)a5 , a6 をそれぞれ求めよ.
(2) a9 を求めよ.

回答

✨ ベストアンサー ✨

gößt

7年弱前

問題設定を私が取り違えていないか(あと間違った解き方をしていないか)知りたいので、先に答えだけ確認してもいいですかね
(1)は
a₅=12, a₆=70
になりましたがどうでしょうか？

ちなみに
a₉=30016
になりました

hizumi 7年弱前

正解です。ぜひ詳解をお願いします。

gößt 7年弱前

のんびりしている間に正答が出てしまいましたが、一応私の解法も載せておきます

できあがった組分けにおいて、ある数字から始めて、組になっているもう一つの数字を順に辿っていくといつかは元の数字に戻ってきます。このとき、辿った数字を順に並べたものを"ループ"と呼び、数字の個数を"ループの長さ"と呼ぶことにします
例えば、
14 37 23 45 67 26 15
という組分けであれば、ループは
(1,4,5), (3,7,6,2)
の２つがありますね
ただし、(1,4,5)と(4,5,1)のように数字をずらしただけのものや、(1,4,5)と(1,5,4)のように並びをひっくり返したものは同一視します

上に書いた同一視の仕方から分かるように、n個の数字からできる長さnのループの総数はn個の相異なるものを並べる数珠順列の総数に等しいので
(n-1)!/2 個
です

あとはループの長さが3以上でないといけないことに留意しつつ、求める組分けの総数を出来上がるループの長さの組合せに分けて数えます

n=9のとき、ループの組合せは 9, 3-6, 4-5, 3-3-3 の4タイプあります
(i)長さ9
(9-1)!/2=20160
(ii)長さ3と長さ6
₉C₃•(3-1)!/2•(6-1)!/2=5040
(iii)長さ4と長さ5
₉C₄•(4-1)!/2•(5-1)!/2=4536
(iv)長さ3が３つ
{₉C₃•₆C₃•{(3-1)!/2}³}/3!=280
したがって、
a₉=20160+5040+4536+280
=30016
となります

gößt 7年弱前

ちなみに、ループを利用することで漸化式も立てられます

1~n+1までの2(n+1)枚のカードの組分けのうち、1を含むループが長さkになるものは
nCk•k!/2•a[n-k]
(ただし、a₀=1, a₁=0 とします)
通りあるので、
n k!
a[n+1]＝Σ nCk • — • a[n-k]
k=2 2
これを n-k=ℓ とおいて少しいじると
a[n+1]=na[n]+nC₂a[n-2]
が得られます