# [算數] 哈佛錄取考 1 題數學題

昨天偶然在 YT 看到的，似乎是哈佛的錄取考試（？）。
標題：Can you Pass Stanford University Admission || Simplification Interview

題目是求解：
$$\left(\dfrac{\sqrt{24}}{\sqrt{30}+\sqrt{6}}\right)^{24}$$

方法不少，但省（筆算）計算量的方法意外不多。

底下的做法會直接以化簡後的形式來做計算。

$$\dfrac{\sqrt{24}}{\sqrt{30}+\sqrt{6}} =
\dfrac{2}{\sqrt{5}+1} =
\dfrac{\sqrt{5}-1}{2}$$

底下解答，不想暴雷可以先暫停 :slightly_smiling_face:

## Method 1

Let $x=\dfrac{\sqrt{5}-1}{2}.$

可以先簡單求出 $x^2 = \dfrac{\sqrt{5}-1}{2} \times \dfrac{2}{\sqrt{5}+1} =
\dfrac{\sqrt{5}-1}{\sqrt{5}+1}$.

因爲這個形式數字還小，可以考慮直接三次方計算 $x^6$ :
$$x^6 = \left(\dfrac{\sqrt{5}-1}{\sqrt{5}+1}\right)^3=
\dfrac{8\sqrt{5}-16}{8\sqrt{5}+16}=\dfrac{\sqrt{5}-2}{\sqrt{5}+2}$$

再來是關鍵，我們可以發現有理化時分母會化成 1 （非必要，但省了些小麻煩），故
$$x^6 = \dfrac{\sqrt{5}-2}{\sqrt{5}+2}\cdot\dfrac{\sqrt{5}-2}{\sqrt{5}-2}=\color{red}{9-4\sqrt{5}}$$

右邊紅色的部分是分子==平方==後的結果。
發現了嗎？下一次我們計算 $x^{12}$ 時，分子剛好就是紅色的部分。
而分母剛好是分子==共軛==，因此平方時，分子分母都不用重算了，只需要有理化：
$$ x^{12} = \dfrac{\color{red}{9-4\sqrt{5}}}{9+4\sqrt{5}}=
(81+80)-2\cdot36\sqrt{5}=\color{blue}{161-72\sqrt{5}}$$

再一次的，右邊藍色是下一次的分子（和共軛後的分母）。
因此計算完最後的有理化就可以得到答案
$$ x^{24} = \dfrac{\color{blue}{161-72\sqrt{5}}}{161+72\sqrt{5}}=
(161^2+72^2\cdot5)-2\cdot161\cdot72\sqrt{5}=51841-23184\sqrt{5}$$

## Method 2

因爲 $\dfrac{\sqrt{5}-1}{2}$ 剛好是 $x^2+x-1=0$ 的其中一根。

可以利用餘式定理求出 $x^2+x-1$ 的餘式並帶入 $x=\dfrac{\sqrt{5}-1}{2}$.

>Note: 以 $x^2=-x+1$ 做降階。

基本上 ++24 階可以一次降完++。

但因爲這裏空間有限，示範怎麽一邊部分降一邊求解高階式的餘式。例如目標 $x^{12}$ :
$$\begin{array}{rr|ccccccc}
& & 1 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0\\
&1& & &1&-1&2&-3&5&-8&13&-21&34&-55&89\\
-1&& &-1&1&-2&3&-5&8&-13&21&-34&55&-89\\\hline
& & 1 &-1&2&-3&5&-8&13&-21&34&-55&89&\bf-144&\bf89
\end{array}$$

因此 $x^{12}=(x^2+x-1)P(x)-144x+89$。

平方後得到
$$\begin{array}{rcl}
x^{24}&=&(x^2+x-1)Q_1(x)+(-144x+89)^2\\
&=&(x^2+x-1)Q_1(x)+144^2-144\cdot89\cdot2x+89^2
\end{array}$$

再把餘式降到 1 階
$$\begin{array}{rcl}
x^{24}&=&(x^2+x-1)Q_1(x)+144^2(1-x)-144\cdot89\cdot2x+89^2\\
&=&(x^2+x-1)Q_2(x)-2x\cdot144\cdot161+(144^2+89^2)
\end{array}$$

帶入 $\left(\dfrac{\sqrt{5}-1}{2}\right)^{24}=(144^2+89^2+144\cdot161)-(144\cdot161)\sqrt{5}=51841-23184\sqrt{5}$

## Method 2'

其實 method 2 做除法時，就可以發現係數會呈現==正負交替的 Fibonacci 數列==。

假設 $\left\{ \begin{array}{rl}F_0=&1\\ F_1=&1\\ F_{n+2}=&F_{n+1}+F_n\end{array} \right.$

可得到
$$\begin{array}{rl}
x^{24} &= (x^2+x-1)Q(x)+F_{22}-F_{23}\cdot x\\
&= (x^2+x-1)Q(x)[phone]x
\end{array}$$

帶入後就和 method 2 相同了。

兩個方法本質上相同，但 method 2' 變成以大量加法取代 3 位數乘法。哪種比較好就見仁見智。