# 背景

「幾個瓶蓋換幾瓶水」印象中是國小數學資優題。而這一題是「三個空瓶換一瓶可樂」與「可額外借一空瓶」。

在 UVA 的題庫中，還有更多此類型的題目（滑到最下面）。這一類題本質是尋找公式解並證明。

# 題解


先講結論：

:::danger
Method 2 的圖其實是倒果為因。結論告訴我們：不管買了多少瓶可樂，先借一個瓶子再說。
:::

---

## 想法 1 - 基本解法

我們重頭開始思考，參考 Method 1 的圖，流程如下：

1. 起初買了==有 8 個可樂==，假想我們全部都喝完了，因此留下 8 個空瓶。
- 6 個空瓶換 ==2 瓶新可樂==，剩下 2 個空瓶不能換，留給下一輪
2. 再次喝完 2 瓶可樂，結算共有 4 個空瓶
- 3 個空瓶換 ==1 瓶新可樂==，剩下 1 個空瓶不能換，留給下一輪
3. 最終輪，喝完 1 瓶可樂，結算共有 2 個空瓶
- 跟別人借 1 個空瓶子，湊成 3 個再換 ==1 瓶新可樂==

因此累計共 $8 + (2 + 1) + 1 = 12$ 瓶可樂。參考程式碼如下：

---

int cnt = n;
while (n >= 3)
{
    cnt += n / 3;
    n = n / 3 + n % 3; 
}
		
// 剩下兩種可能
if (n == 1)
    cout << cnt << '\n';
if (n == 2)
    cout << cnt + 1 << '\n';

---

## 想法 2 - 是否為偶然巧合

上面的程式碼即可完成本題答案需求，只是現在我想要知道，哪些數字需要借 1 空瓶。稍微修改程式碼：

int origin = n;
int cnt = n;
while (n >= 3)
{
    cnt += n / 3;
    n = n / 3 + n % 3; 
}

// 誰需要借瓶子？
if (n == 2)
    cout << origin << '\n';

測試完畢，我們發現**若 n 為偶數**，則需要借瓶子。那就可以參考 Method 2 的圖，一開始就借瓶子。（很顯然，在任何階段借瓶子都會得到一樣結果）

於是有另一種解法：

if (n % 2 == 0) // 可寫可不寫
n++;

int cnt = n;
while (n >= 3)
{
    cnt += n / 3;
    n = n / 3 + n % 3; 
}

cout << cnt << '\n';

事實上，**若 n 為奇數**，借瓶子也不影響結果（最後必剩下兩個空瓶子，再還給別人 1 空瓶即可）。這就是我開頭講的結果論。

---

## 想法 3 - cola 的量（公式解）

前面都是討論「步驟過程」，現在關注「實際的 cola 量變化」，圖表如下：

| 買 n 瓶 | 最多可喝 m 瓶 | m - n |
| ----- | -------- | ----- |
| 11 | 16 | 5 |
| 12 | 18 | 6 |
| 13 | 19 | 6 |
| 14 | 21 | 7 |
| 15 | 22 | 7 |
| 16 | 24 | 8 |
| 17 | 25 | 8 |
| 18 | 27 | 9 |
| 19 | 28 | 9 |
| 20 | 30 | 10 |

我們發現：

$$
m - n = \left\lfloor \frac{n}{2} \right\rfloor
$$

也就是

$$
m = n + \left\lfloor \frac{n}{2} \right\rfloor
$$

cout << n + (n / 2) << '\n'; 

---

## 3.1

> [zerojudge](https://zerojudge.tw/ShowThread?postid=24624&reply=0) 帳號 cges30901 想法

觀察**空瓶變化量**與**可樂容量**的關係

:::info
每減少 2 空瓶，得到 1 容量的可樂。
:::

$$
\begin{align}
3 \text{ 空瓶} &= 1 \text{ 可樂} + \text{ 空瓶} \\
\implies 2 \text{ 空瓶} &= 1 \text{ 可樂} \\
\implies n \text{ 空瓶} &= n/2 \text{ 可樂} \\
\end{align}
$$

---

## 3.2

換個角度，思考 **1 瓶可樂**的價值：

可

:::info
買 1 瓶，得到 1 份可樂，再多送 1/3 瓶；
此 1/3 瓶，得到 1/3 份可樂，再多送 1/9 瓶；
$\vdots$
:::

$$
\begin{align}
3 \text{ 瓶} &= 3 \text{ } + 1 \text{ 瓶} \\
\implies 1 \text{ 瓶} &= 1 + \frac{1}{3} \text{ 瓶} \\
&= 1 + \left( \frac{1}{3} + \frac{1}{9} \text{ 瓶} \right) \\
&= 1 + \left[ \frac{1}{3} + \left( \frac{1}{9} + \frac{1}{27} \text{ 瓶} \right) \right] \\
&\vdots \\
&=\left( 1 + \frac{1}{3} + \frac{1}{3^{2}} + \dots \right) + \frac{1}{\infty} \text{ 瓶}
\end{align}
$$

在高中我們學過**無窮級數公式** $\displaystyle{}S_{n} = \frac{a(1-r^{n})}{1-r}, \, r^{n} \to 0$

因此

$$
\sum_{n=0}^{\infty} \left( \frac{1}{3} \right)^n = 1 + \frac{1}{3} + \frac{1}{9} + \frac{1}{27} + \dots = \frac{1}{1 - \frac{1}{3}} = \frac{3}{2}
$$

---

# Proof

## Proposition 1

> **若 n 為偶數**，則需要借瓶子

下面舉兩個例子，會發現每一次 `while` loop 的結果都是與 n 相同的奇偶性。

**奇數 123：**

- $123 = 3 \times 41 + 0$ → $41 + 0 = 41$ (odd)
- $41 = 3 \times 13 + 2$ → $13 + 2 = 15$ (odd)
- $15 = 3 \times 5 + 0$ → $5 + 0 = 5$ (odd)
- $5 = 3 \times 1 + 2$ → $1 + 2 = 3$ (odd)
- $3 = 3 \times 1 + 0$ → $1 + 0 = 1$ (odd)

**偶數 120：**

- $120 = 3 \times 40 + 0$ → $40 + 0 = 40$ (even)
- $40 = 3 \times 13 + 1$ → $13 + 1 = 14$ (even)
- $14 = 3 \times 4 + 2$ → $4 + 2 = 6$ (even)
- $6 = 3 \times 2 + 0$ → $2 + 0 = 2$ (even)

轉換成數學，我們希望證明：

$$n \equiv \lfloor n/3 \rfloor + (n \pmod 3) \pmod 2$$

---

對於任何正整數 $n$，我們可以寫成： $$n = 3q + r$$

其中 $q = \lfloor n/3 \rfloor$，$r = n \pmod 3$，且 $r \in {0, 1, 2}$

兩邊同時 mod 2： $$n \equiv 3q + r \pmod 2$$

因為 $3 \equiv 1 \pmod 2$，所以： $$n \equiv q + r \pmod 2$$

也就是： $$n \equiv \lfloor n/3 \rfloor + (n \pmod 3) \pmod 2$$

證明完畢。

## Proposition 2

### Step 1

令函數 $g$ 為「結算每一輪的空瓶數」

$$
g(n) = \lfloor n/3 \rfloor + n \bmod 3
$$

函數 $f$ 為「累計額外得到的可樂量」

$$
f(n) = \lfloor n/3 \rfloor + f(g(n))
$$

我們希望找到 $\lfloor n/3 \rfloor$ 的 $g(n)$ 表達式，以便後續計算

$$
\begin{align}
n &= 3 \cdot \lfloor n/3 \rfloor + (n \pmod 3) \\
&= 2 \cdot \lfloor n/3 \rfloor + \underbrace{\lfloor n/3 \rfloor + (n \pmod 3)}_{g(n)}
\end{align}
$$

移項整理：

$$
\lfloor n/3 \rfloor = \frac{n - g(n)}{2}
$$

將上述結果代回原本的 $f(n)$ 公式：

$$
f(n) = \frac{n - g(n)}{2} + f(g(n))
$$

---

### Step 2：Telescoping Sum

設 $n_0 = n, n_1 = g(n), n_2 = g(g(n)), \ldots$

展開遞迴：

$$
\begin{align} \\
f(n_0) &= \frac{n_0 - n_1}{2} + f(n_1) \\
f(n_1) &= \frac{n_1 - n_2}{2} + f(n_2) \\
f(n_2) &= \frac{n_2 - n_3}{2} + f(n_3) \\
&\vdots \\
f(n_k) &= \frac{n_k - n_{k+1}}{2} + f(n_{k+1}) \\
\end{align} $$

逐項相加： $$f(n) = \frac{n_0 - n_1}{2} + \frac{n_1 - n_2}{2} + \frac{n_2 - n_3}{2} + \cdots + \frac{n_k - n_{final}}{2} + f(n_{final})$$

中間項消去： $$\boxed{f(n) = \frac{n - n_{final}}{2} + f(n_{final})}$$

在命題 1 已經證明：

- 若 $n$ 是 奇數，最終 $n_{final} = 1$，且 $f(1) = 0$
- 若 $n$ 是 偶數（且 $n>0$），最終 $n_{final} = 2$，且 $f(2) = 1$（借瓶）

---

結論：

$$
f(n) =
\begin{cases}
\frac{n - 1}{2} + 0 & n \text{ is odd} \\
\frac{n - 2}{2} + 1 & n \text{ is even}
\end{cases}
$$

也就是

$$
f(n) = n + \left\lfloor \frac{n}{2} \right\rfloor
$$

# 更多練習

:::success
### UVa 11877 - [The Coco-Cola Store](https://vjudge.net/problem/UVA-11877#author=0)

- 與上述完全相同的題目，差別在是要求輸出 $\displaystyle{\left\lfloor \frac{n}{2} \right\rfloor}$
:::

:::success
### UVa 10346 - [Peter's Smokes](https://vjudge.net/problem/UVA-10346)

### UVa 11313 - [Gourmet Games](https://vjudge.net/problem/UVA-11313)

- 推廣公式 (generalize)
:::