青い留置線・改頭の体操

どうやら漫画紹介blogになりつつあるという現実

2024.11.24

[PR]

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

2024/11/24 (Sun) 07:47:34 ▲top

2008.09.25

#121

某氏のネットラジオで思い出したけど、今年の高校生クイズ。
今年は従来の高校生クイズと異なり、「知力の対決」をテーマにクイズだけのガチバトルとなりました。
いや、難しいのなんのって！
とにかく知識の量と推理力で差がついたって感じですね。

そんな中、ちょっと毛色が違ったのが準決勝の問題。
1問目はピーター・フランクル氏が、かつて数学オリンピックで出題されたという問題を持ってきました。
確か、こんな問題だったような。

1～90の整数の中から5個の整数を選ぶとき、どの2個も隣り合わないような選び方は何通りあるか？

制限時間は20分。
この放送の中で、僕が解けた唯一の問題です（汗
皆様も、ちょっとお考えください…。

答え。
勿論解答に至る過程はいくつもありますが、多分一番計算量が少ないと思われるのを示してみます。
フリップを見る限り、正解したチームはこの方法で解いていたはず。

90個の中から5個の整数を選ぶ方法を、次のように具体的に考えます：
まず、1～90の数字が書かれた表を用意します。

1	2	3	4	5	…	89	90
					…

そして、選ばれた数字には「○」を、選ばれなかった数字には「×」を記入していきます。
↓こんな風に。

1	2	3	4	5	…	89	90
×	○	×	×	○	…	○	×

すなわち「90個の数字から5個を選ぶ方法」は、「5個の○と85個の×を一列に並べる方法」と言い換えることができるわけです。
「選ばれたどの2つの数字も隣り合わない」というのは、「どの○も隣り合わない（○と○の間には必ず×が1個以上入る）」と言い換えられます。【☆】

並べる方法として、まず85個の×を最初に並べておきます。
その後5個の○を、×と×の間（もしくは両端）に置いていくことにします。
置くことができるスペースは、全部で86個。
○は2個以上隣り合ってはならないので、1個のスペースには○を最大1個までしか置けません。

このルールに従って○を5個置くということは、すなわち86個のスペースの中から○を置く位置を5個選ぶことに相当します。
86個の中から5個を選ぶ、ということですから、あとは公式が使えます。
（公式に関しては高校の数学の教科書とかを見てくださいｗ）

86C5 = (86×85×84×83×82)／(5×4×3×2×1) = 34826302通り

数学オリンピックの問題とは言うものの、【☆】まで思いつけばあとは高校数学でよく見る問題になります。
難関大受験レベルの高校生にとっては、別段難しいことでもないかも。
あとは、あきらめずに掛け算すれば答えは見えてきますｗ

2008/09/25 (Thu) 00:20:04 雑記 Trackback() Comment(0) ▲top

トラックバック

トラックバックURL：

カレンダー