[rentwi.hyuki.net]

a≠b≠cは書き方としてよくないように感じます。a≠bとb≠cが成り立っているからといってa≠cが成り立つとは限らないですから。≠では推移律が成り立たない。

#数学の問題 文字が1,2,3のいずれかを表しているとして「a≠b≠c≠d≠e」を満たすパターンは何通りあるか。

こういう問題に出会ったときは、例を作ってみて、自分が問題を理解しているか確かめるのがいいですね。「例示は理解の試金石」ですから。「1≠2≠1≠3≠2」のように具体的に書いてみると何かに気づくかも(気づかないかも)。

次に「小さな数で試してみる」のもいいですね。例えば「a≠b」だけでやってみるわけです。1≠2, 1≠3, 2≠1, 2≠3, 3≠1, 3≠2 の6通り。次に「自分のやったことを振り返ってみる」と6通りは3×2として計算できそうかな?…などなど。

ここまで考えてくると、与えられた問題は少しの工夫で解けそう。さらには文字が1,2,3,...,mのいずれかであり、a₁≠a₂≠...≠anの場合にはどうなるかという一般化もできそうですね。

いただいたリプにもありましたが、隣り合った場所を別の色で塗る塗り分け問題に言い換えたりするのも楽しそうです。

n個の数が与えられたとき、そのすべてが等しいことを判定するアルゴリズムはO(n)ですよね。ではそのすべてが互いに異なることを判定するアルゴリズムのオーダーは?

2016-10-28 (Fri) 22:58:04