ITパスポート 2009年秋期問46

問題文

あるプロジェクトの関係者6人が、それぞれ1対1で情報の伝達を行う必要があるとき、情報の伝達を行うために必要な経路の数は少なくとも幾つになるか。

🖊️ 解答を隠して解いてみる

選択肢

ア：6

イ：9

ウ：15（正解）

エ：30

🔒 解説は解答すると表示されます

あるプロジェクトの関係者6人がそれぞれ1対1で情報の伝達を行う必要があるとき、情報の伝達を行うために必要な経路の数は少なくとも幾つになるか。【ITパスポート解説】

正解の理由

理由の要点は「1対1の組み合わせ」を数えることです。6人のうち2人を選んで行う通信1つが1経路です。誰A→誰Bのように向き（誰が話すか）は区別せず、「AとBの組み合わせ」は1つと数えます。したがって、6人から2人を選ぶ組み合わせの数を求めればよく、その値は15になります。

解法ステップ

考え方：6人の中から2人を選ぶ組み合わせの数を求めます。順序（AとBかBとAか）を区別しません。
一般式：n人のときの「2人組」の数は組合せの公式で $_{n} C_{2} = \frac{n ( n - 1 )}{2}$ です。
n=6を代入： $_{6} C_{2} = \frac{6 \times 5}{2} = 15$
よって必要な経路は15本です。

補助的に直感的説明：各人が残り5人と通信できるので「6×5=30」通りに見えますが、AとBのペアはA→BとB→Aの2回数えられているため、2で割って15になります。

選択肢別の誤答解説

ア: 6
誤り。これは「各人につき1つだけ経路を用意する」と解釈した場合の数ですが、問題は「それぞれ1対1で情報の伝達を行う必要がある」すべての組み合わせをカバーする必要があるため不十分です。
イ: 9
誤り。9は例えば「何らかの誤った組合せの数え方」や「3対3のペアを想定」など間違った分割に基づく結果です。6人から2人を選ぶ正しい組合せは15であり、9とは一致しません。
ウ: 15（正解）
正しい。上記の通り $_{6} C_{2} = \frac{6 \times 5}{2} = 15$ で求まります。
エ: 30
誤り（ただし意味の違いで正解になり得る場合あり）。30は「順序を区別して数える」場合の数です。つまり「AがBに伝える経路」と「BがAに伝える経路」を別のものと数えると $6 \times 5 = 30$ になります。問題文が順序を区別していない（1対1の経路＝AとBの組み合わせ）と読むのが通常です。

よくある誤解

「向き（誰→誰）を区別する」
受験者がよくするミスは、A→BとB→Aを別物と考えて30を選ぶことです。問題文の「1対1で情報の伝達を行う必要がある」とは通常「AとBの関係が必要」という意味で、向きは区別しません。
「1人につき1本だけで済む」と考える
「ア:6」を選んでしまう人は、各人が1本の経路を持てばよいと誤解します。実際は誰と誰が直接やり取りするか、すべての組み合わせを用意する必要があります。

補足コラム

この問題は「ハンドシェイク問題（握手の問題）」として知られる古典的な組合せの問題です。パーティで互いに一度ずつ握手をするときの総握手回数も同じ公式で求められます。一般に「n人の間で2人ずつの対を作る数」は

_{n} C_{2} = \frac{n ( n - 1 )}{2}

で表されます。

また、ネットワーク設計の文脈では、点（人）同士を直結するリンク（経路）を無向グラフの辺として考えると、辺の本数がちょうどこの組合せ数になります。もし通信が一方向のみでパスが分かれるなら有向辺を考え、個数は

n (n - 1)

になります。

簡単なプログラム例（Python）：

import math

n = 6
pairs = n * (n - 1) // 2
print(pairs)  # 15

FAQ

Q1. 「向きがある場合」と「向きがない場合」の区別はどう判断する？
A1. 問題文に「AがBに送る」など向きを示す語が無ければ、通常は向きを区別しません。向きがあるなら「〜から〜へ」といった表現や「送信者と受信者を区別する」と明記されます。

Q2. 一般に人数が増えたらどう計算する？
A2. 公式

_{n} C_{2} = \frac{n ( n - 1 )}{2}

を使います。例えば10人なら

\frac{10 \times 9}{2} = 45

です。

Q3. なぜ順序を区別しないときに2で割るのか？
A3. AとBのペアはA→BとB→Aの2通りで数えられているため、重複分を取り除くために2で割ります。

関連キーワード: 組合せ、組み合わせの公式、コンビネーション、ハンドシェイク問題、二者間通信、ネットワークトポロジー、組合せ数の計算

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

ITパスポートを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！