The $2,000 Math Problem I Solved (But Got Paid $0)
Part 1: The Story
老話說得好：『主動找上門的生意，通常不是好生意。』我以為我已經學乖了，但這次… 我還是沒學乖。
幾週前，矽谷著名的 AI 公司 Mercor 主動發信給我，邀請我為他們的 AI 模型出數學題。 合約看起來很誘人：時薪 50 ~ 90 美金。如果通過審核，還有額外的 Signing Bonus。
當時我已經一陣子沒收入了，心想：這不就是為我準備的嗎？ 我想起了以前看過的一個幾何移動問題，但我不會證明。 我花了整整兩天，進入了完全的心流狀態，想破了頭，終於證明出來了。
後來我去查資料，才發現這其實是 2018 年 IMO Shortlist 的 C3 難題。 說實話，還好我當時沒去查。如果知道是 IMO C3，而且他只要求證明一個比較弱的結論，我應該早就放棄了。 正因為不知道，我誤打誤撞，給出了一個比 IMO 解答更強的結果。我蠻相信這是一個新的發現。
我當時覺得：這是我今年最得意的作品，這 2000 美金拿定了。
結果呢？ 提交三天，審核中。 提交五天… 合約整個被單方面解除。不要說 2000 美金，我連其他好幾題還在審核中的費用都沒拿到。理由？沒有理由。沒有審核通過，當然，也就沒有錢。
根據合約，既然他們沒付錢，這題的 Intellectual Property (IP) 就還屬於我。 所以我想，與其讓這道漂亮的證明躺在我的硬碟裡發霉，不如把它免費獻給 YouTube 的觀眾。
沒錯，今天我要教你們這道『價值 2000 美金』的題目。 他們沒眼光買單，那是他們的損失。 現在，我們來看看這題數學，到底有多美。」
Part 2: The Meat（數學部分）
1. 遊戲設定：牛排塔 (The Steak Tower)
讓我們深入問題的核心。想像一張桌子上有 1,025 個盤子。在最左邊的盤子（第 0 號盤子）上，我們有一座疊了 1,024 塊牛排的塔。目標很簡單：把所有的牛排都移動到最右邊的最後一個盤子上。但我們有一個非常特殊的物理限制。
你只能移動一疊牛排中最上面那一塊。而且它可以移動的距離，取決於它離開時那一疊牛排的目前高度。如果一個盤子上有 \(k\) 塊牛排，最上面那一塊就可以跳到距離 \(k\) 以內的任何盤子上。簡而言之：塔越高，射程越遠。
讓我們先從簡單的開始。1 塊牛排，距離 1？很簡單。高度是 1，跳躍距離 1。需要 1 步。
如果是 2 塊牛排，距離 2 呢？你不能直接跳底下的牛排，因為它被壓住了。如果你把最上面的牛排（牛排 A）直接跳到第 2 號盤子，牛排 B 就會孤零零地留在第 0 號盤子上。現在高度變成了 1，所以牛排 B 只能跳到第 1 號盤子。你需要額外一步才能把它移動到第 2 號盤子，總共需要 3 步。這就是這個遊戲最基本的摩擦力。
2. 關於 IMO：石頭與牛排的關聯 (The IMO Connection)
數學愛好者可能會認出這個問題。這是 2018 年國際數學奧林匹亞（IMO）短名單問題 C3 的變形，只不過原題移動的是石頭。但當我在為 Mercor 設計這道題目時，我把它們換成了牛排——部分原因是牛排疊起來比較合理，另一部分原因是我想要提高難度。
在 IMO 的版本中，你只需要證明一個較寬鬆的下界：\(\sum_{i=1}^{n} \lceil n/i \rceil\)。那個證明很優雅——你幫牛排編號，然後證明第 1 塊牛排總是需要 \(n\) 步，第 2 塊牛排至少需要 \(n/2\) 步，依此類推。但那只是一個估算，它並沒有告訴你如何達成。事實上，這個下界只有在 \(n = 1, 2, 3, 4, 5, 7\) 時才是緊緻的（tight）。對於其他的數字，真正的答案要高得多。我們需要一個更精確的工具。
3. 找出規律：分而治之 (Divide and Conquer)
讓我們嘗試另一種哲學：分而治之。假設 \(F(n)\) 是將 \(n\) 塊牛排移動跨越距離 \(n\) 所需的最少步數。如果我們在第 \(k\) 號盤子設立一個檢查點呢？
計畫是這樣的：我們直接發射 1 塊牛排到終點線（第 \(n\) 號盤子），這利用了完整的高度。接著，我們將 \((n-k-1)\) 塊牛排直接飛到第 \(k\) 號盤子。然後我們用 \(F(k)\) 步把剩下的 \(k\) 塊牛排移動到第 \(k\) 號盤子。現在整個團隊（除了一塊牛排）都在檢查點了。接下來，我們從第 \(k\) 號盤子塔頂飛 \((k-1)\) 塊牛排到第 \(n\) 號盤子。最後，我們用 \(F(n-k)\) 步將剩下的 \((n-k)\) 塊牛排移動到終點。
總成本是多少？\((n-k-1) + F(k) + 1 + (k-1) + F(n-k)\)。它可以漂亮地化簡為： \[F(n) = (n-1) + F(k) + F(n-k)\] 但這真的是最佳解嗎？這感覺很直觀，但在數學中，直覺是證明危險的替代品。如果有一塊牛排「跳過」了檢查點怎麼辦？如果有些牛排「提早出發」而沒有在第 \(k\) 號盤子等待呢？如果這種遞迴結構被打破，這整個公式就會瓦解。
4. 突破點：「手術」證明 (The “Surgery” Proof)
這是我卡住最久的地方。我試圖找到一個遞減的變量（decreasing invariant），但都行不通。然後，我發現了「手術」——這是一種能嚴格證明這種遞迴結構絕不會比其他任何可能策略更糟的方法。
想像任何一種隨機、混亂的移動方式。我們找出一個最小的索引值 \(k^*\)，從這個位置有任何牛排直接跳到終點 \(n\)。如果我們有一些移動「越過」了這個 \(k^*\)——比方說，從 \(i \to j \to p\)，其中 \(i < k^* < j\)——我們就進行手術。
我們把 \(\{(i, j), (j, p)\}\) 替換成 \(\{(i, k^*), (k^*, p)\}\)。我們可以證明這樣總是合法的。\(i \to k^*\) 是一個較短的跳躍，而 \(k^*\) 保證有足夠的容量，因為它是前往終點的發射台。透過重複進行這種手術，我們消除了所有繞過我們檢查點的移動。我們有效地將任何「狂野」的策略簡化成一種有結構的遞迴策略，而且沒有增加任何一步。
這個簡化就是關鍵。它證明了最小成本必定滿足我們的遞迴公式。我們現在要做的，就只剩下解開它而已。
Part 3: The ending
雖然 Mercor 沒有付錢給我，但我還是很高興能把這個漂亮的數學題目分享給大家。希望你們喜歡這道題目的美麗證明，並且從中獲得啟發。