数学A 場合の数 問題 48 解説

方針・初手

辺を4本消した後に残る図形を、5点を頂点、残った辺を辺とするグラフとして見る。

もとの辺は10本なので、4本消すと残る辺は6本である。また、三角形が残るとは、その3頂点を結ぶ3本の辺がすべて残っていることに対応する。

解法1

まず、消した後に残った辺について考える。

点 $X$ から出る残った辺の本数を $d(X)$ とする。残った辺は6本であり、各辺は両端の2点で1回ずつ数えられるから、

$$ d(A)+d(B)+d(C)+d(D)+d(E)=2\cdot 6=12 $$

である。

もしすべての点について、出る辺が高々2本であるならば、

$$ d(A)+d(B)+d(C)+d(D)+d(E)\leqq 2\cdot 5=10 $$

となり、上の式に反する。

したがって、出る辺が3本以上ある点が少なくとも1つ存在する。これで(1)が示された。

次に、(2)を数える。三角形が1個も残らないように、残った6本の辺からなるグラフを考える。

(1)より、出る辺が3本以上ある点が存在する。その点を $X$ とする。

もし $X$ から出る辺が4本ならば、$X$ は他の4点すべてと結ばれている。このとき、他の4点の間に1本でも辺が残っていれば、$X$ とその辺の両端で三角形ができる。よって他の4点の間には辺が残らない。しかしこの場合、残る辺は $X$ から出る4本だけで、残る辺が6本であることに反する。

したがって、三角形が1個も残らない場合、ある点 $X$ から出る辺の本数はちょうど3本である。

$X$ と結ばれている3点を $Y,Z,W$、$X$ と結ばれていない残りの1点を $T$ とする。三角形が残らないためには、$Y,Z,W$ の間に辺が1本も残っていてはならない。なぜなら、たとえば $YZ$ が残っていると、$X,Y,Z$ で三角形ができるからである。

残る辺は全部で6本であり、このうち $X$ から出る3本は

$$ XY,\ XZ,\ XW $$

である。残り3本は $Y,Z,W$ の間には置けないので、必ず

$$ TY,\ TZ,\ TW $$

でなければならない。

よって、残る図形は、5点を

$$ {X,T},\quad {Y,Z,W} $$

に分け、異なる組に属する2点をすべて結んだ形である。

この形は、2点からなる組を選べば一意に決まる。したがって、その数は

$$ {}_5 \mathrm{C}_{2}=10 $$

である。

残る6本の辺が決まれば、消す4本の辺も一意に決まるので、(2)の答えは

$$ 10 $$

通りである。

次に、(3)を数える。三角形 $ABC$ だけが残るためには、まず辺

$$ AB,\ BC,\ CA $$

はすべて残っていなければならない。

残る辺は全部で6本なので、これら3本以外に、次の7本

$$ AD,\ AE,\ BD,\ BE,\ CD,\ CE,\ DE $$

のうち3本を残すことになる。

三角形 $ABC$ 以外を作らないように、この3本の選び方を数える。

まず、辺 $DE$ が残らない場合を考える。このとき、残す3本は

$$ AD,\ BD,\ CD,\ AE,\ BE,\ CE $$

の中から選ぶことになる。

しかし、$D$ から $A,B,C$ へ向かう3本のうち2本以上を残すと、$ABC$ の辺と合わせて、$ABD,ACD,BCD$ のいずれかの三角形ができる。同様に、$E$ から $A,B,C$ へ向かう3本のうち2本以上を残しても、$ABE,ACE,BCE$ のいずれかの三角形ができる。

6本のうち3本を選ぶ以上、$D$ 側または $E$ 側のどちらかで2本以上選ばれる。よって $DE$ を残さない場合は不可能である。

したがって、$DE$ は必ず残る。

残り2本は、$D$ から $A,B,C$ のどれかへ向かう辺1本と、$E$ から $A,B,C$ のどれかへ向かう辺1本でなければならない。

さらに、同じ文字に向かう2本、たとえば $AD$ と $AE$ を同時に残すと、$A,D,E$ で三角形ができる。したがって、$D$ と結ぶ点と $E$ と結ぶ点は異なっていなければならない。

$D$ と結ぶ点は $A,B,C$ の3通りであり、$E$ と結ぶ点はそれと異なる2通りである。よって選び方は

$$ 3\cdot 2=6 $$

通りである。

したがって、三角形 $ABC$ だけが残るような4本の辺の消し方は

$$ 6 $$

通りである。

最後に、(4)を数える。

ちょうど1個の三角形だけが残るとき、その残る三角形は、5点から3点を選んで作る三角形のいずれかである。三角形の選び方は

$$ {}_5 \mathrm{C}_{3}=10 $$

通りである。

(3)より、残る三角形を1つ固定したとき、その三角形だけが残るような消し方は6通りである。

ちょうど1個だけ残る三角形は一意に決まるので、重複はない。したがって、求める数は

$$ 10\cdot 6=60 $$

通りである。

解説

この問題では、線分の交わり方ではなく、「どの2点間の辺が残っているか」だけを見ることが重要である。

(1)は、残った辺の本数を次数の総和で数える典型的な処理である。残った辺が6本あるため、次数の総和は12になる。5点すべての次数が2以下では総和が10以下になってしまうので、次数3以上の点が必ず存在する。

(2)では、三角形を作らない6本の辺の形を決定することが核心である。三角形を作らないまま6本を残すには、5点を2点と3点に分け、異なる組の間だけをすべて結ぶ形に限られる。

(3)では、三角形 $ABC$ を固定して、残すべき追加の3本を数えるのがよい。辺 $DE$ が残らないと、$D$ 側または $E$ 側で2本以上の辺を残すことになり、必ず余分な三角形ができる。したがって $DE$ を残すことが本質である。

答え

(1)

出る辺が3本以上ある点が少なくとも1つ存在する。

(2)

$$ 10 $$

通り。

(3)

$$ 6 $$

通り。

(4)

$$ 60 $$

通り。