玉入れ問題に関する話② (1996年 東大理系・後期)

画像に alt 属性が指定されていません。ファイル名: 1996_7.jpg

 前記事の兵庫医大( https://wp.me/pbB1S2-Lh )に続いて「玉入れ問題」に関する内容で、各小問(1)(2)(3)(4)は前問の(a)(d)(c)(b)のケースに相当します。

 箱の数こそ前問より少ないですが玉の数が一般の正の整数に拡張されており、特に後半部分の(3)及び(4)については一筋縄ではいきません。

(1)の解答

k = 1, 2, …, nに対し、番号kの玉の行き先はそれぞれ3通りであるので3n通り

 前問における(a)と同じパターンに相当し、考え方も同様です。

(2)の解答

 前問における(d)のパターンであり、重複組み合わせの考え方に基づいてn個の玉(〇)と2つの仕切り(|)の並べ替え問題に帰着させることが可能です。よって、求めるべき組み合わせの総数は以下の通りです。

n+2C2 = {(n+2)(n+1)}/2 通り

(3)の解答

 前問における(c)のパターンに相当しますが、ここから難易度が上がります。

 前問では先に(b)のパターン(箱、玉いずれも区別しない)を先に考えて、そこから改めて玉を区別して考えました。しかし本問のように玉の数が一般のnに拡張された場合は、(b)の総数を求める方が却って大変であり前問のような戦略は使えません。

 そこで箱も玉も区別されている(1)の結果に着目し、そこから箱が区別できなくなった場合と比較する戦略を取ります。

全ての玉が1つの箱に入っている場合
 箱が区別されている場合は、玉が全て入っている箱の選び方で3通り存在するが箱が区別出来ない場合は1通り。

玉が入っている箱が2つ以上の場合
 箱が区別できる場合は(1)の結果と余事象を考える事で3n-3通り存在するが、玉の分け方は同じで箱の種類のみが異なる3!通りについては、箱の区別を無くすことで同一視出来る為、箱が区別できない場合(3n-3)/6通りとなる。

よってこれらを足し合わせて 1 + (3n-3)/6 = (3n+3)/6 通り

 類題経験がない場合、この着想に至るのは中々難しいと思われます。なお前問の問題の場合は箱の数が6個と多いため、箱も玉も区別されている状態から考えようとすると却って苦戦します。

 このように「玉を区別し、箱を区別しない」という同じ条件設定であっても、玉や箱の数によって最良の解法が変わってくることもこの手の問題の特徴です。

(4)の解答

 前問における(b)のパターンに相当します。前問はあり得る玉の分け方を全て書き出す戦略で比較的簡単に解決しましたが、6の倍数という制約があるとはいえ玉の数が一般化されている本問では通用しません。

 本問ではまず答えとなる場合の数をA通りと置き、入っている玉の個数が等しい箱の数によって場合分けを行います。

3つの箱に入っている玉の数が等しい場合
 n = 6mより3つの箱に区別の出来ない玉が各々2m個ずつ入ることになる。このような入れ方は1通り

2つの箱に入っている玉の数が等しく、残りは異なる場合
 3つの箱にそれぞれk, k, 6m-2k個の玉が入っていると考える事が出来る。kは0以上の整数であり、更に6m-2kも0以上の整数である事を考えるとkは0≦k≦3mを満たす整数となる。但しk = 2mのときは3つの箱に入っている玉の数が全て等しくなるため、求める場合の数は(3m+1)-1 = 3m通り

3つの箱に入っている玉の数が互いに異なる場合
 余事象を考える事でA-3m-1通り

 このままではAが残ったままですが、ここで上記の場合分けと(2)の結果を比較して考えます。

3つの箱に入っている玉の数が等しい場合
 箱は区別されていてもやはり1通り

2つの箱に入っている玉の数が等しく、残りは異なる場合
 3つの箱が互いに区別できる場合は、同じ数の玉が入った箱の選び方として3C2 = 3通りを考える必要がある為、3m x 3 = 9m通り

3つの箱に入っている玉の数が互いに異なる場合
 3つの箱が互いに区別できる場合は、箱の選び方として3! = 6通りを考える必要がある為、6(A-3m-1)通り

 一方で(2)の結果にn = 6mを代入すると、上記場合分けの総数は(3m+1)(6m+1)通りとなります。従ってAに関する以下の一次方程式を解くことで本問は解決です。

1+9m+6(A-3m-1) = (3m+1)(6m+1) ⇔ A = 3m2+3m+1 通り

 以上のように入っている玉の個数が等しい箱の数の場合分けが重要となりますが、これはn = 6mの時に限り綺麗な議論が出来ることに注意が必要です。

コメント

 (1)と(2)については内容は標準的であり、ここまでは完答が必須と言えます。(3)以降は場合分けをしながら(1)及び(2)の結果と比較する必要があり、類題経験の無い受験生にとってはかなりの発想力が要求されます。

 前問の兵庫医大の記事と比較すると分かる通り、玉の数が具体的な数値から一般のnに拡張されると問題の難易度は一気に上がります。

玉入れ問題と分割数

 実の所箱も玉も区別しないパターンについては、玉の入れ方の総数を分かり易い形で一般化することは現在においても達成されていないようです。

 箱も玉も区別しない玉入れ問題は、分割数(自然数を順番を除き1つ以上の自然数の和として表現する方法の総数)と密接に関与しており、自然数nに対する分割数p(n)は以下の式で与えられるとされています(wikipediaより引用)。

{\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }{\sqrt {k}}\,A_{k}(n)\,{\frac {d}{dn}}\left({\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left[{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}\right]\right)}


 自分でもよくわからずwikipediaから引用しているだけなのですが、これだけでも玉入れ問題が如何に数学の難解な部分と繋がっているかを実感させられます。

 

投稿者: matsubushi

趣味で数学など

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。