ホーム >> 組合せ >> 登山家の休憩
hide or visible

方針・考え方

論証力と思考力を必要とする問題です.登山家が山登りをする問題ですが,休憩のみが問題となっていることに注意してください.また,個々の休憩の長さ等もあまり重要なことではありません.ただ,同時刻に休憩をとっていた登山家の人数に焦点が当たっています.

さて,何も制約をつけずに考えようとするとこの問題はs複雑すぎるので,まずはある程度制約を加えて考えてみましょう.たとえば,結論を否定して$3$人以上の登山家が同時に休憩を取ることがなかったとしてみましょう.こうすると状況が比較的簡単になり,考えやすくなります.以上の考察から背理法で攻めることにします.

より簡単な問題

上の問題が難しすぎる場合は,本質的にあまり変わらないより簡単な次の問題にチャレンジしてみてください.

 ある日,$3$人の登山家が山登りをしていた.どの登山家も山を登りきるまでにちょうど$1$回休憩をとった.また,どの$2$人の登山家についても同時に休憩をとっている時があった.このとき,$3$人が同時に休憩をとっている時があることを示せ.

この問題は,少し考えればすぐに直感的にわかると思います.

背理法

さて,もとの問題について考えてみましょう.$3$人以上の登山家が同時に休憩を取ることがなかったと仮定します.つまり,同じ時間帯には多くても$2$人の登山家しか休憩をとっていない状況を考えます.このとき,どの$2$人の登山家についても同時に休憩をとっている時があるという条件から,$2$人の登山家が同時に休憩をとった回数は合計$_9 \mathrm{C}_2=36$回以上となります.すると,登山家の延べの休憩回数は$37$回以上でなければなりません.以下,その理由を説明しましょう.

延べの休憩回数

初めて$2$人の登山家が同時に休憩をとったとすると,このとき$2$人目以降の登山家が休憩をとったことになります.次に$2$人の登山家が同時に休憩を取るためには,$1$人以上の登山家が休憩をやめて,$3$人目以降の登山家が休憩をとったときのみに起こります.同様に,$n$回目に$2$人の登山家が同時に休憩を取るためには$n+1$人目以降の登山家が休憩をとらないと起こりえません.したがって,登山家の延べの休憩回数は$37$回以上でなければなりません.

しかし,登山家の延べの休憩回数はちょうど$36$回なのでこれは矛盾です.よって,少なくとも$3$人の登山家が同時に休憩をとっている時があったことになります.


個人的には計算力よりも論証力の方が何かと重要な気がします.