問36
頻出度★★☆
プロジェクトの参加メンバが，それぞれ1対1で情報の伝達を行う必要がある。このとき，プロジェクトの参加メンバ数と情報の伝達を行うために必要な経路の数との関係に関する記述として，適切なものはどれか。
平成25年度 春期 ITパスポート試験 問36
テクノロジ系基礎理論 › 応用数学
This question's explanation and your answers so far.
解説
問 36
- ア
正解 When there are x participating members, the number of one-to-one communication paths equals the number of combinations of two different people, that is y＝x(x−1)/2 paths. Counting them directly: 2 members give 1 path, 3 members give 3, 4 members give 6, and 5 members give 10. Following the increase each time one more member joins: 1→2 members adds 1 path, 2→3 members adds 2, 3→4 members adds 3, and 4→5 members adds 4, so the increase itself keeps getting larger. Checking with the formula gives the same result: going from x members to x+1 members adds (x+1)x/2 − x(x−1)/2 ＝ x paths, which equals the number of members x before the increase. You can also think of it this way: the newly added person must connect a path to every one of the existing x members, which leads to the same conclusion. In other words, the larger the original number of participating members, the larger the increase, so ア is appropriate.
Incorrectイ
An increase of only one path happens just when going from 1 member to 2. From 2 to 3 members it increases by 2 paths (1 path → 3 paths), and from 3 to 4 members by 3 paths (3 paths → 6 paths); the increase equals the number of members before the increase. Since the increase is not constant, saying it “always increases by exactly one” is wrong.
Incorrectウ
y＝x! is the factorial of x (1×2×…×x), which grows far larger than the correct relationship y＝x(x−1)/2. When x＝3 it gives 6 (actually 3 paths), when x＝4 it gives 24 (actually 6), and when x＝5 it gives 120 (actually 10), so y＝x! does not hold.
Incorrectエ
If y＝x², then x＝3 would give 9 paths and x＝4 would give 16, but the actual numbers are 3 and 6. x² corresponds to a count that even includes pairing a person with themselves and distinguishing the two directions of a round trip, so it is too large for the number of one-to-one paths. The correct formula is y＝x(x−1)/2, which is about half the size of x².
ここがポイント
- When n people communicate with one another on a one-to-one basis, the number of paths is the number of combinations of two different people: nC2 ＝ n(n−1)/2 paths. It grows rapidly, roughly in proportion to the square of the number of people.
- When the number of people goes from n to n+1, the increase in paths is n (the new member has to connect to all n existing members). The fact that the increase itself grows along with the number of people is why communication cost rises sharply as a project grows in scale.
用語