1551：グラフ？

問題1551

ある村のどの少年についても、その少年の知り合いの少女たちはすべてお互いに知り合っています。
また、それぞれの少女について、彼女の知り合いの中では少女の数より少年の数の方が多くなっています。この村の少年の数は少女の数以上であることを示せ。
























































解答

・わたしの

女性の知り合いのいない女性が1人でも、男性は一人以上を知っている。
女性を一人知っている女性が一人でもいれば、男性を二人以上知っている。この二人の男性は上の男性にはなりえない。この男性二人が同じ女性だけを知っているとしたら、もう一人の女性はまた別の男性を二人以上知ってることになる。男性二人がそれぞれ二人の女性を知っているとしても、題意は満たされるが、そのときは男女の数は同数。
一般に、k 人の女性をしっている女性が一人でもいると、しってる男性の数はk+1 人以上いる。
そのうちの女性の一人でもそのk+1人の男性の一人でも知らないなら、もう一人新たな男性を知っていることになる。つまり、k+1 人の男性が同じ k+1 人の女性を知っているときに限り、男女の数は同数となり、k+1人が知り合い同士の女性のうちの一人でもそれらの男性が知らないとしたら、その女性がしってる新たな男性がもう一人いることになる。
これは、いずれのk 人においても言えるので、女性の数と同じかそれ以上の男性がいることに他ならない。

これでいいかなあ・・・？ ^^;
急患で起こされて、すぐ眠れなくなったので考えてみたけれど。。。ただ今、朝の4時過ぎ・・・^^;v

・友人のもの

少女が1人もいなければ問題ありません。少女が1人いたとすればその少女の知り合いの少年が少なくとも1人はいます。この2人を除いても同じ条件が成り立っていることがわかります。同じことを繰り返していくと、最後に少女が1人もいなくなります。

こんなにすっきり言えるの...
いまいちピンと来ない私...^^;