| For All Solvers
OMC174 (for experts)

OMC174(C)

 1,2,,1001, 2, \ldots, 100 の番号のついた頂点を用意し,番号の和が 101,103,105101, 103, 105 のいずれかである頂点の間に辺を張ることで(無向)グラフ GG を構成すると,GG は図1のようになる.ただし図1において, a2n1=4n3,a2n=1044n,b2n1=4n1,b2n=1024n(n=1,2,,25)a_{2n-1}=4n-3,\quad a_{2n}=104-4n,\quad b_{2n-1}=4n-1,\quad b_{2n}=102-4n\quad (n=1, 2, \ldots, 25) である.スコアが 77 となるような 77 枚のカードの選び方は,頂点の個数が 77,辺の本数が 77 である GG の誘導部分グラフに対応し,その誘導部分グラフを図1の頂点の位置関係で考えたときの形は図2の (i)~(v) のいずれかである(それぞれ回転や反転したものも含む).
 (i) は連結な 66 頂点の位置で場合分けして考えれば 91×2+90×45=423291\times 2 + 90\times 45=4232 通り.また (ii)~(v) については反転および回転を考えると (ii) は 182182 通り,(iii), (iv), (v) は 184184 通りずつとわかる.
 以上より,求める場合の数は 4966\bm{4966} 通り.

誘導部分グラフとは  もとのグラフからいくつかの頂点を選ぶとき,それらの頂点の間の辺の有無がもとのグラフと一致する部分グラフを誘導部分グラフと呼ぶ.

figure 1

解説YouTube

解説YouTubeが存在しません.