9

There is a question in TAOCP vol 1, in "Notes on Exercises" section, which goes something like:

"Prove that 13^3 = 2197. Generalize your answer. (This is a horrible kind of problem that the author has tried to avoid)."

Questions:

  1. How would you actually go about proving this ? (Direct multiplication is one way, another way could be using formula of (a+b)^3). Does the solution requires using some method that will allow us to make some kind of generalization ?

  2. What is the generalization here ?

  3. Why is this a horrible kind of problem ?

  4. What are some other kind of similar horrible problems that you are aware of ?

Appreciate any answers.

P.S. I apologize if the statement of problem above makes it look like a homework problem, but its not. Request people to not tag this as a homework problem, so that more people can give answers.

4

3 に答える 3

3

彼はおそらくペアノの公理から始めてそれを証明しているのではないかとほのめかしていると思います。次に整数を作成し、13 ^ 3=2197がべき乗の定義から生じる自然で論理的な結論であることを正式に示します。

一般化して、aとbが与えられた場合、整数c、つまりa^bが存在することを示すことができます。

ほとんどの人がそれを面白くないと思うので、これは恐ろしい種類の問題です。

同様の種類の問題は、分析のコースで見つけることができます（いくつかの非常に興味深いものもあります）。

于 2009-10-05T11:32:58.673 に答える
2

最初は次のように考えていました:
n 3 = n * n * n
log n (n 3 ) = log n (n*n*n)
log n (n 3 ) = log n (n) + log n (n) +ログn (n)
3 = 1 + 1 + 1
3 = 3

これは、対数恒等式を使用する点でかなり循環しているように見えますが、アルゴリズムの研究で私がどこにいるのかを考えると、奇妙なことに慰めになりました。

于 2013-01-08T05:19:00.500 に答える