握手会における社交的な人数の最大値問題

Table of Contents

AHSME 1978

AHSME 1978

Problem

$N = {x \vert x \in \mathbb Z, x \geq 3}$と定義する. ある部屋に$N$人の人がいる. この部屋の自分を除くすべての人と握手したことある人を社交的な人, そうでない人を社交的ではない人と呼ぶことにする. 社交的でない人が少なくとも1人いるとき, 社交的な人の人数として考えられる最大値はいくつか？

解答

部屋にいる人をそれぞれ$a_1, a_2, \cdots, a_n$とする. この内, 社交的でない人を一般性を失うことなく$a_1$とすると, 少なくとも$a_1$はだれかと握手しておらずその人を$a_2$とする. このとき, $a_2$も社交的でない人となるので, 社交的な人は高々 $N- 2$人となる.

従って, 最大値は$N- 2$人.

Share Buttons
Share on:

Feature Tags
Leave a Comment
(注意：GitHub Accountが必要となります）

握手会における社交的な人数の最大値問題

組合せ論 3/N

AHSME 1978

CONTENTS