問36
頻出度★★☆
プロジェクトの参加メンバが，それぞれ1対1で情報の伝達を行う必要がある。このとき，プロジェクトの参加メンバ数と情報の伝達を行うために必要な経路の数との関係に関する記述として，適切なものはどれか。
平成25年度 春期 ITパスポート試験 問36
テクノロジ系基礎理論 › 応用数学
この問題の解説と、これまでの解答の記録です。
解説
問 36
- ア
正解 参加メンバが x 人のとき、1 対 1 の伝達経路は異なる 2 人の組合せの数に等しく、y＝x(x−1)/2 本になる。実際に数えると 2 人で 1 本、3 人で 3 本、4 人で 6 本、5 人で 10 本である。ここで 1 人増えるときの増分を追うと、1 人→2 人は 1 本、2 人→3 人は 2 本、3 人→4 人は 3 本、4 人→5 人は 4 本となり、増分そのものが大きくなっていく。式で確かめても、x 人から x+1 人になったときの増分は (x+1)x/2 − x(x−1)/2 ＝ x で、増える前のメンバ数 x に等しい。新しく加わった 1 人は既存の x 人全員と経路を結ぶ必要がある、と考えても同じ結論になる。つまり元の参加メンバが多いほど増分は大きくなるので、アが適切である。
不正解イ
増分が 1 本で済むのは 1 人→2 人のときだけである。2 人→3 人は 2 本 (1 本→3 本)、3 人→4 人は 3 本 (3 本→6 本) と増えていき、増分は増える前のメンバ数に等しい。増分は一定ではないので「必ず一つ増加する」は誤り。
不正解ウ
y＝x! は x の階乗 (1×2×…×x) で、正しい y＝x(x−1)/2 より大きくなりすぎる。x＝3 では 6 (実際は 3 本)、x＝4 では 24 (実際は 6 本)、x＝5 では 120 (実際は 10 本) となり、y＝x! は成り立たない。
不正解エ
y＝x² だと x＝3 で 9 本、x＝4 で 16 本になるが、実際は 3 本と 6 本である。x² は自分自身との組合せや往復の向きの違いまで数えた値に相当し、1 対 1 の経路数としては過大。正しくは y＝x(x−1)/2 で、これは x² のおよそ半分の大きさになる。
ここがポイント
- n 人が互いに 1 対 1 で連絡するときの経路数は、異なる 2 人の組合せの数 nC2 ＝ n(n−1)/2 本。人数の 2 乗にほぼ比例して急増する。
- n 人から n+1 人に増えたときの経路の増分は n 本 (新メンバが既存の n 人全員と結ぶ)。増分自体が人数とともに大きくなることが、プロジェクト規模拡大でコミュニケーションコストが跳ね上がる理由である。
用語