> [time=Fri, Oct 27, 2023 2:31 PM]

# 算幾不等式

[toc]

## 證明

**Statement.** Let $a_1,a_2,\dots,a_k \in \mathbb N$, denote $A,G$ as the arithmetic mean and geometric mean of $a_1,a_2,\dots,a_k$,respectively. Then $A \ge G$

**Proof.**
> Claim: $k = 2^n, n \in \mathbb{N}$, the inequality hold

Proof of claim: let $n = 1$, then by $(\sqrt{a_2}-\sqrt{a_1})^2 \ge 0$, we have $\frac{1}{2}(a_1+a_2) \ge \sqrt{a_1a_2}$. Hence the claim hold.

Suppose at some value of $n$, this claim hold, namely,
$$A=\frac{a_1+a_2+\dots+a_{2^n}}{2^n} \ge \left(a_1a_2\dots a_{2^n}\right)^{1/2^n}=GM$$
Then, for case $n+1$
$$\begin{align} \\
A & = \frac{a_1+a_2+\dots+a_{2^n}+a_{2^n+1}+\dots+a_{2^n+1}+a_{2^{n+1}}}{2^{n+1}} \\
&= \frac{1}{2}\left(\frac{a_1+a_2+\dots+a_{2^n}}{2^n}\right) + \frac{1}{2}\left(\frac{a_{2^n+1}+\dots+a_{2^n+1}+a_{2^{n+1}}}{2^n}\right)\\
& \ge \sqrt{(a_1a_2\dots a_{2^n})^{1/2^n}}\cdot \sqrt{(a_{2^n+1} a_{2^n+2} \dots a_{2^{n+1}})^{1/2^n}} \\
&=\left(a_1a_2\dots a_{2^{n+1}} \right)^{1/{2^{n+1}}} = G
\end{align}$$
Therefore, AM-GM ineq. hold for $k$ as a power of two.

---

For cases where $k \in \mathbb{N}$, choose $n$ such that $2^n \ge k$.
$$\begin{cases}
A = \frac{a_1 + a_2 + \dots + a_k}{k} \\
G = (a_1 a_2 \dots a_k)^{1/k} \\
\end{cases}$$
Consider a true-by-claim inequality, $$\frac{(a_1+a_2+\dots +a_k)+ (a_{k+1} + a_{k+2} + \dots + a_{2^n})}{2^n} \ge (a_1 a_2\dots a_k a_{k+1} a_{k+2} \dots a_{2^n})^{1/2^n}$$
Take $A = a_{k+1} = a_{k+2} = \dots = a_{2^n}$, we have
$$\begin{align}
\frac{a_1+a_2+\dots + a_k + (2^n-k)A}{2^n} & \ge (a_1 \dots a_k A^{2^n-k})^{1/2^n} \\
\implies A & \ge (a_1 \dots a_k)^{1/2^n} A^{1-{k/2^n}} \\
\implies A & \ge G \text{, by simplification}
\end{align}$$
Q.E.D.

### Remark
這邊，我們有GM <= AM
同樣的，在線性代數我們也有類似表述：
給定方陣$A$, 以及$\lambda \in \sigma(A)$令$$\alpha(\lambda) = \text{dim}(\cup_k {N\left( (\lambda I - A)^k \right) })$$
為代數重數，以及$$g(\lambda) = \text{nullity}(\lambda I - A)$$
為幾何重數，則$$g(\lambda) \le \alpha(\lambda)$$，即 Geometric Multiplicity <= Algebraic Multiplicity

## 應用

分塊算法，sqrt tree, Mo's algorithm 等等都是使用算幾不等式來選分塊的大小，來獲得 $O(\dots \sqrt{n})$ 的複雜度。

## *離散版* 算幾不等式

題目如下：

https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/description/

給你一個正整數 $n$，要求 $\prod a_i$ 的最大值，其中 $a_1 + \dots + a_k = n,\, a_i\in \mathbb{N}, k \in \mathbb{N}$, $k\in \mathbb{N}, k \not = 1$

For generality, 這邊先假設 $k$ 可以等於 $1$
從感性而言，按照傳統的算幾不等式，我們知道把 $n$ 拆成一樣的數字，可以最大化 product
所以可以假設把 $n$ 拆成 $k$ 個一樣的數字，此時乘積為 $\left(n\over k\right)^k$

微分可得
$${d\over dx}\left(n\over k\right)^k = \left(k\log\left(n\over k\right)\right)\left(n \over k\right)^k \left(\log\left(n\over k\right)-1\right) = 0$$

然後通靈（他是最大值而非最小值的部分）得 $k = {n\over e}$ 時取得最大值 $e^{n\over e}$。這也就是說把數字拆成 $e$ 是最好的。

從理性而言，題目要求我們只能拆成整數，所以上述的討論全然無意義！

所以面對這種題目，我們就只能分情況討論了，嗎？注意到，$e = 2.71827 \approx 3$
所以猜測盡可能把 $n$ 拆成一堆 $3$ 是最好的，得到如下

**Theorem.** 假設 $m$ 是 $n$ 除 $3$ 的餘數。
* 如果 $m = 0$ 則 $n = 3 + \dots + 3$ 為最優拆分。
* 如果 $m = 1$ 則 $n = \underbrace{3 + \dots + 3}_{(n-4)/3} + 4$ 為最優拆分。
* 如果 $m = 2$ 則 $n = \underbrace{3 + \dots + 3}_{(n-2)/3} + 2$ 為最優拆分。

比方說 $14 = 3+3+3+3+2, 2\cdot 3^4 = 162$

**Proof.**

* $n$ 的最優拆分中，不包含 $1$ 的數字
proof : 乘 $1$ 沒有幫助

* $n$ 的最優拆分中，不包含大於 $4$ 的數字
proof : 假設拆分中有 $a\ge 5$ 不妨把 $a$ 再拆成 $3(a-3)$，則顯然有 $3a-9 > a$，因為 $a > {9\over 2}$，因此得到嚴格更優的拆分。

至此，我們知道 $n$ 的最優拆分只會有 $2$, $3$, $4$
因為 $4$ 有最優拆分 $2 + 2$，所以可以把 $4$ 排除，即某個最優拆分只包含 $2, 3$

那麼到底該把 $n$ 拆成多少 $2$ 多少 $3$ 呢？首先從算幾，大概知道不會像是什麼拆成 5 個 2, 17 個 3 這種怪組合，而是盡可能偏好一種數字。至於要偏好哪個數字，不妨把剛剛的函數拉來看。$f(x)$ 是把 $5$ 等分拆成 $x$ 的乘積。


直觀理解來看，的確，因為 $2$ 比 $3$ 更遠離 $e$ 所以儘管是從函數圖像上看，拆成一堆 $2$ 不會更好。

最後得到如此結論：拆成一堆 $3$，有剩就留兩個 $2$ 或一個 $2$，取決於 $n$ 除 $3$ 餘幾。

因為要求 $k \not= 1$ 所以 $n$ 很小時，還是一定得拆，所以要做特判的。

class Solution {
public:
    int cuttingBamboo(int n) {
        if (n<=3) return n-1;
        int m = n % 3;
        if (m==0) return fastpow(3,n/3);
        else if (m==1) return modmul(4,fastpow(3,(n-4)/3));
        return modmul(2,fastpow(3,(n-2)/3));
    }
};