◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】 必ずいる。
背理法で証明する。
いないとすると最大の挨拶数はｎ−1回だからｎ人の挨拶数がすべて異なる組み合わせは
０，１，．．．，ｎ−１ のただ１とおりである。
最大のn-1回挨拶した人：Aと、その他の人(n-1人)に分けると、その他の人はもう一回Aとは挨拶できないと同時に全てAと一回ずつ挨拶しており、Aの存在を無視しても同じである。
よって問題はｎ-1人の問題に還元される。
以上繰り返すとｎ=2 に還元され、この二人の挨拶数が異なることは無い。
よって、必ず同じ挨拶数の人がいる。
【問題２】 起こりうる。
人数をｎ＝１０１、検査グループ数をｇ＝１１、
最大挨拶数をｍ＝９ とし、背理法で証明する。
ある挨拶の組み合わせで、どの検査グループにも挨拶済みがいるとする。
この時、少なくとも１人の挨拶数がｍ回であるとしてよい｡
もし最大がｍ未満なら、ｍ回の人が現れるまで挨拶をしても、やはりどの検査グループにも挨拶済みがいるからである。
このときｎ人を ｍ回挨拶した１人：Ａ と
Ａと挨拶したｍ人のグループ：Ｂと
その他のｎ−ｍ−１人のグループ：Ｃの３つに分ける。
すると ＡとＣのみからなるｇ人の検査グループにも少なくとも一組挨拶済みのペアがいる。
ただし、ＡはＢグループとのみ挨拶しているから、
結局Ｃのグループ内のｇ−１人の検査グループ内に少なくとも１組挨拶済みがいる。
Ｃ内の１人の挨拶数は前と同様にｍ回としてよく、
問題は ｎ＝ｎ−ｍ−１、ｇ＝ｇ−１、ｍ＝ｍ の問題に還元できる。
以上を繰り返すと最終的に
ｎ＝１０１→９１→８１→７１→６１→５１→４１→３１→２１→１１
ｇ＝ １１→１０→ ９→ ８→ ７→ ６→ ５→ ４→ ３→ ２
ｍ＝９
の問題となる。
１１人から任意の２人が挨拶済みであるということは、全てのペアが挨拶していることである。
即ち１人１０回挨拶している。
これはｍ＝９と矛盾する。
よって起こりうるといえる。
【問題３】 ２２８組
全人数をｎとします。
ｎ＝６０の場合の最小ペア数（＝Ｍ）をあたえる挨拶パターンにおいて、
最も多く挨拶した人の一人をAとし、その挨拶数をｍAとします。
そこで、このAが入らない８人組を考えると、
A以外の５９人がＭ−mA回の挨拶をしている状態で、任意の８人組において挨拶をしたペアがいる必要があります。
よって、mAはなるべく小さい方が有利であり、小さくて損になることはない。
一方最大の挨拶数を７とすると問題２の方法で破綻することがわかるので、
mA＝８としてよい。
ｎ＝５９に対しても最大７回は破綻するのでｍB＝８。
以上を繰り返すと、ｎ＝５６でｍ＝７は破綻しなくなります。
さらに繰り返すと下記の列が得られ、ｍの総合計は
４×(１から８までの和)＋３×(１から７までの和)＝２２８
になります。よって２２８ペアが最小です。
n =60 59 58 57 56 55 54 53 52 51 50 49 … 43 42…36 35…29 28…22 21… m = 8 8 8 8 7 7 7 7 7 7 7 6 … 6 5… 5 4… 4 3… 3 2…具体的には、ｎをなるべく同じ人数の７(=8-1)グループに分け、各グループ内では全員が挨拶済みであれば条件を満足します。
すなわち ６０＝４×９＋３×８ なので
４×9C2＋３×8C2＝２２８
は最小値に一致しています。
【おまけ】
ｎ人のグループをそれぞれＡ，Ｂとする。
問題となる３人組は互いに知り合いなので、ＡまたはＢからだけではできない。
すなわち、Ａから隣接２人とＢから任意に１人 またはＡ⇔Ｂしたものである。
背理法により証明する。
少なくとも１組だけ異なる挨拶があるとする。
この場合、Ａのグループ間とＢのグループ間で異なる挨拶が必ずあり、これを
Ａ１-Ａ２ と Ｂ１−Ｂ２ とする。図１参照。
するとここで問題となる３人組は
A1-A2-B1、A1-A2-B2、B1-B2-A1、B1-B2-A2
の４つである。
条件を満足する挨拶言葉の組み合わせは B1-B2の順番を無視すると図１の一通りである。
図中 赤線はA1-A2の挨拶言葉、青線はB1-B2間の挨拶言葉とする。
図から判る様に、A1-B1間は赤で A1-B2間は青である。
もしＢグループ間の挨拶言葉が全部同じなら
A1-B3は赤、A1-B4は青に限られ以下、赤青は交互に現れなければならない。
ところがｎは奇数であるため一周してくると偶奇性が矛盾する。
よって、Ｂグループ内は（全てが同じ挨拶言葉）ではない。
Ａグループも同様である。
以上より各グループ内連絡網に 図２のような挨拶言葉が変わる部分がある。
これをA1-A2-A3、B1-B2-B3 とする。
そしてこの間の挨拶の可能性を考えると、図２に示す２通りが残る｡
これらは対称であり、実質１とおりである。
なお灰色線は赤でも青でも良いことを表す。
先の証明と同様 A1-A2ないしA2-A3を中心軸としてＢグループ側間が同じ挨拶言葉（色）が続くと偶奇性が合わず矛盾する。
よって、途中で挨拶言葉はさらに連絡網のなかで沢山変わらなければならい。
しかし、その変化点でも図２と同じ状況であるから、
A1-A2ないしA2-A3を中心軸としたＡ−Ｂ間の挨拶の偶奇性は維持され、一周すると矛盾する。
よって仮定は誤りであり、２ｎ組みの挨拶言葉は全部同じである。
【出題者のコメント】
解答ありがとうございます。
２ヶ月以上も解答がなかったので、とても嬉しいです。
すべて正解です。
しかも、どれもとても解り易く思えます。
【問題１】は「鳩の巣箱の原理」を利用しても以下のように証明できます。
ｎ人の参加者おのおのに挨拶した人数を申告してもらうと、
０人〜(ｎ−１)人のｎ通りの内のいずれかを得ます。
それを集計すると最大ｎ種類の挨拶人数があるように思えますが、
０人とｎ−１人の申告が同時に存在することはありえません。
よって、ｎ人の参加者の集計では高々ｎ−１種類の挨拶人数しかありません。
ｎ人のおのおのがそのいずれかに属するので、どうしても何処かの挨拶人数には２人以上がいなければなりません。
【問題２】,【問題３】は各参加者をそれぞれの点に２人で交わす挨拶を２点を結ぶ線にするとグラフ理論になります。
ただし、同一の２点間を結ぶ線は２本以上はないものとします。
【問題２】を一般化させると、ｍｎ＋１個の各点の間では以下の(１),(２)のいずれかが成立します。
（１）ｍ個以上の点と線で結ばれている点が少なくとも１個存在する。
（２）あるｎ＋１個の点同士の間では互いにどの点とも線で結ばれていない。
【問題３】を一般化させると、次のようになります。（テュランの定理）
互いにどの２点も線で結ばれていない点の最大集団があり、その集団の点の個数が高々ｎ個である時、
それらを含むｍｎ＋ｒ(０≦ｒ＜ｎ)個の点の間では、２点を結んだ線は少なくとも
ｒm+1Ｃ2＋(ｎ−ｒ)mＣ2 本存在する。