ITパスポート 2013年 春期 問36

参加メンバと情報伝達経路の関係【ITパスポート 解説】

正解の理由

解法ステップ

1. 問題の意味を整理する：1対1の情報伝達は「2人1組のペア」を数えること。
2. 組合せの考え方を使う：$x$ 人から 2 人を選ぶパターン数は $\left(\genfrac{}{}{0ex}{}{x}{2}\right)$。
3. 組合せを式にすると $y=\frac{x(x-1)}{2}$。
4. 増分を見る：1人増やしたときの差を計算して $x$ であることを確認する。
5. 以上より、「増分は元の参加メンバが多いほど大きくなる」という ア が正しい。

• $x=3$ のとき $y=\frac{3\cdot 2}{2}=3$（AB, AC, BC）
• $x=4$ のとき $y=\frac{4\cdot 3}{2}=6$ 増分は $6-3=3$ で、元の人数 $x=3$ と一致します。

選択肢別の誤答解説

• ア: 正しい。増分が元の参加メンバの数 $x$ に等しいため、元の人数が多いほど増分も大きくなる。
• イ: 誤り。参加メンバが1人増えても経路が必ず1つ増えるわけではなく、増える経路数は元の人数 $x$（例：3→4 のときは3つ増える）。
• ウ: 誤り。$x!$（階乗）は「$x$ 人を並べる順列の数」であり、全員を並べる順序を数える値。1対1の経路数とは関係がない。
• エ: 誤り。$x^2$ は「自己を含む順序付きのペア（自分→自分を含む）」の数に近い値ですが、今回の問題（順序を区別せず、自分自身とのやり取りは含めない）とは合致しない。正しくは $\frac{x(x-1)}{2}$。

よくある誤解

1. 「順序を区別する（A→B と B→A を別とする）場合」と混同する
   • 順序を区別するなら経路数は $x(x-1)$ になります（$A\to B$ と $B\to A$ を別とする）。今回の問題は通常「1対1のつながり」を問うので順序を区別しません。
2. 「階乗（$x!$）を使えばよい」と考える
   • 階乗は「並べ方」の数で、ペアの数を求めるのには使わない。用途が違います。
3. 「自分と自分のやり取り（自己ループ）を含める」と誤って数える
   • 自己ループを含めると $x^2$ に近い値になるが、通常の1対1の情報伝達では自分→自分は考慮しません。

補足コラム

• 覚え方のコツ：新しく来た1人は「既にいる全員」全員と1対1でつながる必要があるので、増分は「既にいる人数」になる、とイメージすると分かりやすいです。つまり、0+1+2+...+(x-1) の和が $\frac{x(x-1)}{2}$（三角数）。
• グラフ理論の言葉で言えば、参加者を頂点とする完全グラフ K_x の辺の数が $\left(\genfrac{}{}{0ex}{}{x}{2}\right)$ です。
• 順序を区別する（向きのある通信を別とする）場合：$y=x(x-1)$。電話の呼び出し元・先を区別する場面など。

def paths(x):
    return x*(x-1)//2

for x in range(1,6):
    print(x, paths(x))
# 出力: 1 0, 2 1, 3 3, 4 6, 5 10

FAQ