<style>
body[style],
body[style *= "background-color: #f3f3f3"]{
background-color: #f3f3f3 ! important;
}
</style>
# NCPC 2018 初賽 Problem C - Partition an Integer
###### tags: `程設專題`
:::spoiler partition of 11
```
lcm
11 = 9 + 1 + 1 --- 9
= 8 + 2 + 1 --- 8
= 7 + 3 + 1 --- 21
= 7 + 2 + 2 --- 14
= 6 + 4 + 1 --- 12
= 6 + 3 + 2 --- 6
= 5 + 5 + 1 --- 5
= 5 + 4 + 2 --- 20
= 5 + 3 + 3 --- 15
```
:::
## 題目
$n$ 是一個大於 $2$ 的正整數，給定 $n$，找出三個正整數 $(a, b, c)$，滿足 $n=a+b+c$ 且 $𝑙𝑐𝑚(𝑎,𝑏,𝑐)$ 最小。
$2 < n \le 2^{31}$
## 符號定義
- Partition(拆分)：
- When $a+b+c=n$, $(a,b,c)$ is a partition of n.
- $f(n)$：
- $f(n)=(a,b,c)$ when $(a,b,c)$ is the optimal partition of n.
## 觀察
$\forall n \in \Bbb N \land n >2$
#### $lcm(f(n))$ 上界
1. $n$ is odd
$n = 2k + 1 = 1 + k + k\\
\Rightarrow lcm(f(n)) \le lcm(1,k,k) = k = \dfrac{n-1}{2}$
2. $n$ is even
$n = 2k + 2 = 2 + k + k\\
\Rightarrow lcm(f(n)) \le lcm(2,k,k) \not= k = \dfrac{n-2}{2}$
$\because lcm(2,k,k) =
\begin{cases}
2k,\quad k\text{ is odd}\\
k,\quad k\text{ is even}\\
\end{cases}$
- $n$ is a multiple of 2 but is NOT a multiple of 4
$\begin{split}
n &= 2(2k') + 2\\
&=4k'+2\\
&= 2 + 2k' + 2k'\\
\end{split}$
$lcm(f(n)) \le lcm(2, k',k') = \dfrac{n-2}2$
- $n$ is a multiple of 4
$\begin{split}
n &= 2(2k' -1) + 2\\
&= 4k'\\
&= k' + k' + 2k'\\
\end{split}$
$lcm(f(n)) \le lcm(k',k', 2k') = \dfrac{n}2$
#### $lcm(f(n))$ 下界
if $n$ is a multiple of 3
$\Rightarrow n = k + k + k\\
\Rightarrow f(n) = (k, k, k), lcm(f(n)) = k$
### 小結
$\dfrac n3 \le lcm(f(n)) \le \dfrac n2$
## Solution in $O(n^2)$
### Idea
WLOG, let $a \le b \le c \Rightarrow lcm(a,b,c) \ge c$
Let $k = lcm(a,b)$
$lcm(a,b,c) = lcm(lcm(a,b), c) = lcm(k,c)$
if $lcm(a,b,c) = lcm(k,c) = c \Rightarrow k|c$
### Pseudocode
```cpp=
f(n):
(A,B,C) = (∞,∞,∞)
for (c = n-2;c >= n/3;c--):
for (b = c, a = n-b-c; a <= b; a++, b--):
if (a <= 0 || c % a != 0) continue;
k = lcm(a,b)
if (c % k == 0):
if c < C:
(A,B,C) = (a,b,c)
break;
return (A,B,C)
```
ref. [wiki LCM](https://zh.m.wikipedia.org/zh-tw/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8)
## output
:::spoiler result of $n < 50$
```
3: 1 1 1
4: 1 1 2
5: 1 2 2
6: 2 2 2
7: 1 3 3
8: 2 2 4
9: 3 3 3
10: 2 4 4
11: 1 5 5
12: 4 4 4
13: 1 6 6
14: 2 6 6
15: 5 5 5
16: 4 4 8
17: 1 8 8
18: 6 6 6
19: 1 9 9
20: 4 8 8
21: 7 7 7
22: 2 10 10
23: 1 11 11
24: 8 8 8
25: 5 10 10
26: 2 12 12
```
```
27: 9 9 9
28: 4 12 12
29: 1 14 14
30: 10 10 10
31: 1 15 15
32: 8 8 16
33: 11 11 11
34: 2 16 16
35: 7 14 14
36: 12 12 12
37: 1 18 18
38: 2 18 18
39: 13 13 13
40: 8 16 16
41: 1 20 20
42: 14 14 14
43: 1 21 21
44: 4 20 20
45: 15 15 15
46: 2 22 22
47: 1 23 23
48: 16 16 16
49: 7 21 21
50: 10 20 20
```
:::
### Lemma 1
::: info
**Lemma 1. (Optimal Partition for Primes)**
$f(p) = (1,b,b) = (1,\dfrac{p-1}2,\dfrac{p-1}2)$, where $p \ge 3$ and $p$ is a prime number.
:::
**Pf. (by contradiction)**
Suppose that $(1+2x,b-x,b-x)$ is a *better* partition of $p$ where $x,b-x\in\Bbb N$
such that $lcm(1+2x,b-x,b-x) < lcm(1,b,b) = b$
$lcm(1+2x,b-x,b-x) = lcm(1+2x,b-x) < b\Leftrightarrow 1 + 2x \mid b-x$
Let $b-x=(1+2x)k$, $k \in \Bbb N$
$\begin{split} \\
p &= (1+2x) + (1+2x)k + (1+2x)k \\
&= (1+2x)(1+2k) \Rightarrow p \text{ is not a prime number}
\end{split}$
Therefore $(1,b,b)$ is the optimal partition for $p$.
### Lemma 2
$\begin{split}
R &= R_1 + R_2 + R_3\\
&= dr_1 + dr_2 + dr_3,\ d \mid r_1 \land d \mid r_2 \land d \mid r_3\\
&= d(r_1 + r_2 + r_3)\\
&= d\cdot r
\end{split}$
:::info
**Lemma 2.**
When $R$ has optimal partition $(R_1, R_2, R_3)$, then
$f(R)=d \cdot f(r)$
where $R = d\cdot r$ and $d$ is a common factor of $r_1, r_2$ and $r_3$.
:::
**Pf. (by contradiction)**
Suppose there exists a partition $(r_1',r_2',r_3')$ such that $lcm(r_1',r_2',r_3') < lcm(r_1,r_2,r_3)$ then by assumption we have
$lcm(r_1',r_2',r_3') < lcm(r_1,r_2,r_3)$
$\Rightarrow d \cdot lcm(r_1',r_2',r_3') < d \cdot lcm(r_1,r_2,r_3)$
$\Rightarrow lcm(dr_1',dr_2',dr_3') < lcm(dr_1,dr_2,dr_3)$
$\Rightarrow(dr_1',dr_2',dr_3')$ is a better partition for $R$, a contradiction.
:::warning
When $R=d\cdot r$, we know $f(R)\Rightarrow d\cdot f(r)$
ex.
$\begin{split}
f(24) &= (8,8,8)\\
&= 8\cdot (1,1,1)\\
\Rightarrow f(3) &= (1,1,1)
\end{split}$
How about $d\cdot f(r)\Rightarrow f(R)$?
ex.
$\begin{split}
f(4) &= (1,1,2)\\
6\cdot f(4) &= 6\cdot(1,1,2)\\
6\cdot f(4) &= (6,6,12)\\
f(24) &\not= (6,6,12)
\end{split}$
:::
### Formula Derivation
For $n\ge 3$, if $n$ has an optimal partition
$\begin{split}
f(n) &= (n_1, n_2, n_3)\\
&= d(n_1', n_2', n_3')\\
\end{split}$
where $d$ is a common factor of $n_1', n_2'$ and $n_3'$.
Let $p$ be a prime number, $p \ge 3$, where $p = n_1'+n_2'+n_3'$.
By **Lemma 2**, $f(n) = d\cdot f(p)$ where $f(p)$ is the optimal partition of $p$.
By **Lemma 1**, we obtain that $f(p) = (1,b,b)$ where $b=\dfrac{p-1}2$.
Then
$\begin{split}
f(n) &= d\cdot f(p)\\
&= d\cdot(1,b,b)\\
&= (d,bd,bd)
\end{split}$
$\Rightarrow f(n)$ must be in form $(d,bd,bd)$ where $\begin{cases}
d = \dfrac np,\\
b = \dfrac{p-1}2.
\end{cases}$
$\begin{split}
lcm(d, bd, bd)&= bd\\
&= \dfrac{p-1}2 \cdot \dfrac np\\
&= \dfrac n2\cdot(1-\dfrac1p)
\end{split}$
$\because\dfrac n2$ is a constant,
$\therefore$ minimize $p$ cause the minial $lcm(d, bd, bd)$.
### Conclusion
$\forall n = p\cdot d$
$\because$ choose $p=2$ is illegal
$\therefore$ rewrite $n = 2^k\cdot x$ where $x$ is odd.
Thus, $\forall n = 2^k\cdot x ,x \not= 1$
$f(n) = 2^k\cdot f(x)$
Def. $f(1) = (\dfrac14, \dfrac14, \dfrac12)$
$f(x)=\begin{cases}
(1, \dfrac{x-1}2, \dfrac{x-1}2)&, &x \in \text{prime numbers}\\
\dfrac xp\cdot f(p)&, &x \notin \text{prime numbers} \land x \not= 1, p\text{ is the smallest prime factor of } x\\
(\dfrac14, \dfrac14, \dfrac12)&, &x=1
\end{cases}$
Sign in with Wallet
Connect another wallet