數學與邏輯謎題

範圍 — 解腦筋急轉彎類題目的四個招式：計算一次測試能買到多少資訊、平衡最壞情況、找出不變量，以及運用期望值的線性性。本篇教的是招式，而不是謎題清單。 另見：combinatorics_math_patterns.md — 計數公式與鴿籠原理；dp_advanced.md — 以一般 DP 解丟雞蛋問題（LC 887）；binary_search_on_answer.md — 在單調判定式上套用同樣的「最小化最壞情況」思路。

LeetCode 題目清單

• Math
• Game Theory
• Probability and Statistics

0) 概念

謎題考的不是你有沒有聽過這道謎題，而是你能否把一個模糊的情境轉成可以計數的東西， 再一邊講一邊把它最佳化。四個招式幾乎涵蓋所有這類題目：

即使題目沒要求，也先從資訊量算起：它給出一個下界，而如果你的構造恰好達到這個下界， 你就可被證明是最佳的——這是這類面試中你能說出的最有力的一句話。

1) 一般形式

1-1) 計算一次測試能買到的資訊 ★★★★★優先度 5／5 — 必備 — 幾乎每一輪面試都會出現

一次有 k 種可區分結果的測試，重複 t 次，最多能區分 k^t 種情況。因此要從 N 種可能中辨識出一種，你需要

k^t >= N        ->        t >= log_k(N)

• 是非題式的測試：k = 2，而 log2(1000) = 9.97，所以 1,000 種情況至少需要 10 次測試。
• 天平：k = 3（左重、右重、平衡）。要指出 12 顆球中哪一顆是異常的以及它偏重還是偏輕， 共 24 種情況，而 3^3 = 27 >= 24，所以三次秤重並未被排除——而且確實有已知的秤法做得到——這就是為什麼謎題說 12 顆而從不說 14 顆 （28 種情況，多於 27，可證明不可能）。
• 比較排序：k = 2，N = n! 種可能順序，所以 t >= log2(n!) = O(n log n)。 著名的排序下界就是同一個計數。

達到下界的構造：每次測試成為答案編號的一個位元。 CtCI 6.10 — 1,000 瓶水，其中一瓶有毒，10 條試紙，結果要一週才出來，而你只有一輪測試。 2^10 = 1024 >= 1000，所以 10 條試紙剛好夠：把瓶子編號，讓試紙 j 測試所有編號第 j 個位元為 1 的瓶子，再把陽性的模式當成二進位數讀回來。

# python
# CtCI 6.10 - 1000 bottles, 1 poisoned, 10 test strips, ONE round of testing
# IDEA: strip j tastes every bottle whose id has bit j set, so the vector of
#       positive strips IS the poisoned bottle's id, written in binary
# time = O(n_bottles * n_strips) drops, space = O(n_strips)
def find_poisoned(n_bottles, n_strips, is_poisoned):
    assert (1 << n_strips) >= n_bottles          # 2^10 = 1024 >= 1000 -> solvable
    positive = [False] * n_strips

    for bottle in range(n_bottles):
        for j in range(n_strips):
            if (bottle >> j) & 1:                # bit j set -> a drop goes on strip j
                positive[j] |= is_poisoned(bottle)

    poisoned_id = 0
    for j in range(n_strips):
        if positive[j]:
            poisoned_id |= 1 << j                # read the pattern back as an id
    return poisoned_id

多輪是讓結果相乘，而不是相加。 如果試紙可以在 r 輪中重複使用，每條試紙回報的是 它在哪一輪首次變陽性，或從未變陽性——那是 r + 1 種結果，而不是 2 種。所以 s 條試紙 經過 r 輪能區分 (r + 1)^s 瓶，編碼也從二進位改為 r + 1 進位：瓶子編號在 r + 1 進位下的第 j 位數，說明試紙 j 該在哪一輪測它。十條試紙經過四輪可達 5^10 = 9.7 百萬瓶。

1-2) 平衡最壞情況 ★★★★★優先度 5／5 — 必備 — 幾乎每一輪面試都會出現

當一次錯誤的探測迫使你退回線性掃描時，一個方案的成本是 目前已花的探測次數 + 退回後要掃描的長度。最佳方案會讓這個總和對每種結果都相同—— 如果某個分支比另一個便宜，你就能在那裡更貪心一點，也就代表你原本並非最佳。

CtCI 6.5 — 兩顆雞蛋、100 層樓，找出雞蛋開始會破的樓層，並最小化最壞情況下的丟擲次數。 雞蛋 1 負責跳躍，一旦它破了，雞蛋 2 就必須一層一層掃描那段間隔。把雞蛋 1 丟在第 x 層， 接著 x + (x-1)，再來 x + (x-1) + (x-2)：第 i 次跳躍後你已花了 i 次丟擲，剩下要掃描的 間隔是 x - i，所以不論在哪裡破，總數都是 x。涵蓋所有樓層，就得到

x + (x-1) + ... + 1 = x(x+1)/2 >= 100    ->    x = 14   (14*15/2 = 105)

# python
# CtCI 6.5 - 2 eggs, n floors: find the breaking floor in at most x drops,
# where x is the smallest integer with x(x+1)/2 >= n  (n = 100 -> x = 14)
# IDEA: shrink the jump by 1 after each survived drop, so (drops used + worst
#       remaining scan) stays constant at x for every outcome
# time = O(sqrt(n)) drops, space = O(1)
def find_breaking_floor(floors, breaks_at):      # breaks_at(f) -> True if the egg breaks
    step = 1
    while step * (step + 1) // 2 < floors:       # derive x from the building, not from 100
        step += 1

    floor, prev, broke = step, 0, False
    while step > 0 and floor <= floors:          # egg 1: jumps that shrink by 1
        if breaks_at(floor):
            broke = True
            break
        step -= 1
        prev, floor = floor, floor + step

    top = floor - 1 if broke else min(floor, floors)   # never re-test the floor that broke
    for f in range(prev + 1, top + 1):                 # egg 2: scan the gap, bottom-up
        if breaks_at(f):
            return f
    return floor if broke else -1                # nothing lower broke, so it is `floor`

同樣的平衡手法，換了件外衣：

• 二分搜尋就是雞蛋無限供應的版本——每次探測都把空間減半，所以兩個分支成本相同。
• k 顆蛋、n 層樓是 dp_advanced.md 中的 DP（LC 887）：用 d 次丟擲和 k 顆蛋，你能涵蓋 f(d, k) = f(d-1, k-1) + f(d-1, k) + 1 層樓。上面兩顆蛋的 閉式解就是這個遞迴式的特例。
• 單調判定式上的**「最小化最大的 X」**就是 binary_search_on_answer.md——猜答案，再驗證它。

1-3) 找出不變量 ★★★★☆優先度 4／5 — 高價值 — 這裡有缺口就會掉關

「這是否總是做得到？」和「誰會贏？」幾乎從來不是靠搜尋解的。找出一個任何合法操作都 無法改變的量，再證明目標狀態的值不同。

100 個置物櫃。 100 個置物櫃一開始全部關著；第 k 趟切換每第 k 個置物櫃。最後哪些是 開著的？置物櫃 n 每遇到 n 的一個因數就被切換一次，所以恰好當 n 有奇數個因數時， 它最後是開著的。因數會兩兩配對成 d 與 n/d，唯一落單的情況是 d == n/d——所以開著的 置物櫃就是完全平方數。

# python
# The 100 lockers puzzle: pass k toggles every k-th locker; which end up open?
# IDEA: locker n is toggled once per divisor of n; divisors pair up as (d, n/d),
#       so the count is odd only when d == n/d — that is, n is a perfect square
# time = O(sqrt(n)), space = O(sqrt(n))
def open_lockers(n):
    out, k = [], 1
    while k * k <= n:
        out.append(k * k)
        k += 1
    return out                                   # n=100 -> [1, 4, 9, ..., 100]

以著色表達奇偶性。 把棋盤兩個對角的角落移除——31 張骨牌能鋪滿剩下的 62 格嗎？不行： 每張骨牌都覆蓋一黑一白兩格，所以任何鋪法都需要黑白數量相等，而你移除的兩個角是同一種顏色。 不變量是「黑格減白格」，它從 ±2 開始，任何操作都無法改變它。

在 LeetCode 上，不變量通常是一個模數：

1-4) 期望值的線性性 ★★★★☆優先度 4／5 — 高價值 — 這裡有缺口就會掉關

即使事件彼此相依，期望值仍然可以相加，這讓你完全避開聯合分布。

CtCI 6.7 — 末日。 每個家庭一直生孩子直到生出女孩才停止。男孩與女孩的比例是多少？ 很容易想去加總一個級數；其實沒必要。每一次出生都是一枚獨立的 50/50 硬幣，任何停止規則 都不會改變這枚硬幣。停止規則決定的是出生幾次，而不是每次生出什麼，所以比例是 1:1。 （以每個家庭來看：恰好 1 個女孩，期望 1/0.5 - 1 = 1 個男孩。）

期望嘗試次數。 如果每次嘗試獨立地以機率 p 成功，期望的嘗試次數是 1/p。這一個事實 就能為每個拒絕取樣迴圈定價——包括用 rand5() 做出 rand7()，其中 25 次抽取有 21 次可用， 所以期望成本是 25/21 ~= 1.19 輪。構造方式在 combinatorics_math_patterns.md（LC 470）。

LC 橋接： LC 470（Implement Rand10 Using Rand7）、LC 688（Knight Probability in Chessboard）與 LC 837（New 21 Game）都是「狀態上的期望值」——一個狀態的值等於其後繼狀態 平均值的 DP。

1-5) 鴿籠原理 ★★★☆☆優先度 3／5 — 值得會 — 多半是必備模式的變形

n + 1 個物品放進 n 個箱子，必有一個箱子裝兩個。在面試中它以必然重複的狀態空間的形式 出現：在有限集合上反覆套用一個確定性映射，保證在 |states| + 1 步之內出現循環。實例—— LC 957 與循環偵測家族——在 combinatorics_math_patterns.md。

2) LC 範例

2-1) Nim Game — LC 292 ★★★☆☆優先度 3／5 — 值得會 — 多半是必備模式的變形

LeetCode 上最乾淨的不變量題，值得能夠推導而非背誦：每次可拿 1–3 顆石頭，拿到最後一顆的人獲勝。

# python
# LC 292 - Nim Game
# IDEA: multiples of 4 are the losing states. From any other pile you can move TO a
#       multiple of 4; from a multiple of 4 every move (1..3) leaves one, so the
#       opponent hands it straight back.
# time = O(1), space = O(1)
class Solution(object):
    def canWinNim(self, n):
        return n % 4 != 0

// java
// LC 292 - Nim Game
// IDEA: n % 4 == 0 is invariant under "opponent restores it" — those states lose
// time = O(1), space = O(1)
class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

要說出口的是推導過程：手動檢查 n = 1, 2, 3（贏）、n = 4（輸）、n = 5, 6, 7 （走到 4 就贏），從此規律就被確定下來了。

3) 如何處理沒見過的謎題

1. 把它重述成在有限集合上的搜尋。 有多少種可能的答案？那個數就是 §1-1 中的 N。
2. 計算一次探測能買到多少。 k 種結果，所以你至少需要 log_k(N) 次探測。 在你有構造之前就先說出下界——它為之後的一切定下框架。
3. 嘗試達到下界。 通常是讓每次探測回答答案編號在 k 進位下的一位數。
4. 如果答案必須被保證，就平衡各分支（§1-2）。如果只需平均表現好，就計算期望值（§1-4）。
5. 如果題目聞起來像不可能，就找不變量（§1-3）——奇偶性、模數、著色、守恆的總和。
6. 用最小的情況做合理性檢查。 n = 1, 2, 3 抓出錯誤規律的速度比任何代數都快。

4) 常見陷阱

• 在算出下界之前就追逐巧妙技巧。 資訊量計算只要十秒，就能告訴你你在找的技巧究竟是否存在。
• 混淆平均與最壞情況。 「平均 13 次丟擲」並沒有回答「保證最少的丟擲次數」。題目要哪一個， 通常就在提示中的一個詞。
• 以為停止規則會改變分布。 它改變的是你取多少樣本，而不是每個樣本是什麼——這就是末日陷阱。
• 把結果相加而不是相乘。 兩輪 3 種結果的測試給出 3^2 = 9 種情況，而不是 6 種。
• 談論「奇數個」卻沒檢查配對。 置物櫃的答案之所以是完全平方數，正是因為因數兩兩配對； 要說出配對，而不是只說結果。
• 把謎題當成冷知識。 即使你知道答案，也要把推導講出來——分數來自推理過程，而背下來的數字 聽起來就完全像背下來的數字。

5) 總結