SET 卡牌的第三張怎麼算：mod 3 補全與 1,080 組 SET 的由來

SET 的三張牌，每個特徵都要全部相同或全部不同。把各特徵的值編成 0、1、2，這條規則就等於三個值相加後除以 3，餘數為 0，所以任取兩張不同的牌 a、b，第三張只能是逐特徵計算的 c = −(a+b) mod 3。

整副 81 張牌共有 1,080 組 SET，每張牌參與 40 組，每對牌恰在一組裡。三張列舉和兩張補全都能算出 1,080；桌面只有 12 張時，補全法最多查表 66 次就能判斷有沒有 SET，隨機抽出 12 張卻沒有 SET 的機率約 3%。

規則與編碼

SET 有 81 張牌，每張牌有顏色、形狀、數量、底紋四個特徵。判斷時各特徵分開看，顏色可以全同，數量可以全異，只要各自符合規則即可。

四個特徵各有三種值，整副牌包含所有組合，所以牌數是 81 = 3^4。把各特徵的值編成 0、1、2，一張牌就能用四個數字組成的 tuple 表示，也就是 (Z₃)⁴ 的一個點。

先只看一個特徵，把三張牌對應的值記為 x、y、z，可能情況如下：

三個值的關係	相加後會怎樣
全部相同	和為 0、3 或 6，都能被 3 整除
全部不同	一定各有一個 0、1、2，和為 3
兩個相同、一個不同	設重複的值為 x，另一個為 y，`2x+y ≡ y−x (mod 3)`；x、y 不同，餘數就不會是 0

因此，全同或全異與 x+y+z ≡ 0 (mod 3) 等價，四個特徵都符合這個條件，三張牌就構成 SET。程式只要逐欄相加取餘數，不必另外寫全同與全異的分支。

第三張唯一

已知 a、b 兩張牌，將 a+b+c ≡ 0 (mod 3) 移項，就得到 c ≡ −(a+b) (mod 3)，每個特徵各算一次，第三張牌便確定了。

這張 c 也不會與 a 或 b 重複。假設 c 等於 a，原式就成了 2a+b ≡ 0 (mod 3)，也就是 b ≡ a (mod 3)，與起初選兩張不同的牌矛盾；c 等於 b 時同理。

整副牌共有 C(81,2) = 81×80/2 = 3,240 對，一組 SET 含三對牌，同一組會算到三次，所以總數是 3,240/3 = 1,080。固定其中一張牌，它能和其餘 80 張各配一對，每組包含這張牌的 SET 會貢獻兩對，於是每張牌參與 80/2 = 40 組。

每張牌參與 40 組、每對牌恰在一組，總數也可寫成 81×80/3! = 1,080。

列舉三張與補全兩張

整副牌只有 85,320 種三張組合，直接逐組檢查，就能和兩張補全的結果對照。set_count.py 用前面推導的餘數條件判斷 SET：

# SET: 81 cards = every point of (Z_3)^4 (four features, three values each).
# Three cards form a SET iff for every feature the values are all equal or all different,
# which is the same as summing to 0 mod 3. Hence for any two cards the third is unique:
# c = -(a + b) mod 3, feature by feature.
# Count all SETs two ways and time them.
from itertools import product, combinations
import time

cards = list(product(range(3), repeat=4))

def is_set(a, b, c):
    return all((x + y + z) % 3 == 0 for x, y, z in zip(a, b, c))

def third(a, b):
    return tuple((-x - y) % 3 for x, y in zip(a, b))

t0 = time.perf_counter()
by_triples = sum(is_set(*tri) for tri in combinations(cards, 3))
t_triples = time.perf_counter() - t0

t0 = time.perf_counter()
pairs = list(combinations(cards, 2))
by_pairs = {frozenset((a, b, third(a, b))) for a, b in pairs}
t_pairs = time.perf_counter() - t0

print(f"cards={len(cards)}  triples C(81,3)={len(list(combinations(cards, 3)))}  pairs C(81,2)={len(pairs)}")
print(f"SETs by enumerating triples: {by_triples}  ({t_triples * 1000:.0f} ms)")
print(f"SETs by completing pairs:    {len(by_pairs)}  ({t_pairs * 1000:.0f} ms)")
print(f"check: 81*80/6 = {81 * 80 // 6};  each card in {len(by_pairs) * 3 // 81} SETs;  pairs / 3 = {len(pairs) / 3:.0f}")
print("every completed triple really is a SET:", all(is_set(*s) for s in by_pairs))

cards=81  triples C(81,3)=85320  pairs C(81,2)=3240
SETs by enumerating triples: 1080  (28 ms)
SETs by completing pairs:    1080  (3 ms)
check: 81*80/6 = 1080;  each card in 40 SETs;  pairs / 3 = 1080
every completed triple really is a SET: True

by_triples 走訪全部 85,320 個三元組，逐一呼叫 is_set；這個函式檢查四個特徵，有任何一個不符合就回傳 False。by_pairs 則只走訪 3,240 對，每對算出第三張，用 frozenset 表示不分順序的一組牌，外層 set 再把重複的組合去掉。

兩種寫法都得到 1,080，最後的 is_set 檢查也全部通過，列舉版可以留下來做回歸測試。輸出的每牌組數由總數算平均，每張牌都參與同樣多組則由前面的配對證明保證。

三張列舉耗時 28 ms，兩張補全耗時 3 ms，後者包含建立 pairs 與去重集合的時間。這是 Mac 上的單次量測，不能當成固定的效能比例。

用兩張補全搜尋桌面的 SET

桌面只有 n 張牌時，第三張仍然唯一，只是可能不在桌面上。先把桌面牌放進 Python 的 set，每對牌算出第三張後查一次，平均一次查詢是 O(1)。

桌面張數	三張列舉的候選數	兩張補全的查表上限
12	`C(12,3) = 220`	`C(12,2) = 66`
15	`C(15,3) = 455`	`C(15,2) = 105`

只要判斷有沒有 SET，找到第一組就能停止，無 SET 時才需要查完每一對。no_set_probability.py 對 12 張與 15 張桌面各抽樣 200,000 次，seed 固定為 42，以 1.96 × sqrt(p×(1−p)/T) 計算近似 95% 信賴區間的半寬：

# Probability that a random layout of 12 (or 15) cards contains no SET, by Monte Carlo (seed 42).
# Finding a SET in a layout of n cards costs C(n,2) lookups with the "third card" trick
# instead of C(n,3) triple checks.
from itertools import product, combinations
import random, math

random.seed(42)
cards = list(product(range(3), repeat=4))

def third(a, b):
    return tuple((-x - y) % 3 for x, y in zip(a, b))

def has_set(layout):
    s = set(layout)
    return any(third(a, b) in s for a, b in combinations(layout, 2))

T = 200_000
for n in (12, 15):
    none = sum(not has_set(random.sample(cards, n)) for _ in range(T))
    p = none / T
    ci = 1.96 * math.sqrt(p * (1 - p) / T)
    print(f"{n} cards: P(no SET) = {p:.4f} +/- {ci:.4f}   lookups per layout: C({n},2)={math.comb(n, 2)} vs C({n},3)={math.comb(n, 3)}")

12 cards: P(no SET) = 0.0317 +/- 0.0008   lookups per layout: C(12,2)=66 vs C(12,3)=220
15 cards: P(no SET) = 0.0004 +/- 0.0001   lookups per layout: C(15,2)=105 vs C(15,3)=455

random.sample 每次從完整 81 張牌抽出不重複的 n 張，因此這些機率適用於獨立重新發牌。has_set 裡的 any 會提早停止，輸出的 66 與 105 都是查表上限。

12 張桌面約有 3.17% 找不到 SET，誤差範圍約正負 0.08 個百分點；15 張降到 0.04%，約正負 0.01 個百分點。

這個估計也接近 Norvig 的模擬。¹

小桌面值不值得最佳化

先做出可用的工具，12 張牌直接列舉 220 個三元組就夠。搜尋成為瓶頸時，再量補全法把候選數從 220 降到 66 能省多少時間；前面的計時涵蓋整副 81 張牌，12 張桌面要另外測，包含建立查表集合的成本。

做練習題生成器，可以直接把抽樣程式裡的桌面送進 has_set，沒有 SET 就重抽，通過才交給玩家，並記錄淘汰比例與每題耗時。改用補全法時，保留列舉版核對篩選結果，再用整段生成流程的耗時決定值不值得換。提示功能需要實際的牌，搜尋找到第一組時就回傳這一對和第三張；遊戲途中要加牌，則保留桌面剩牌，從未發出的牌堆補。

補充筆記

實作判定時，把四個特徵各編成 0、1、2，逐欄檢查相加後模 3 是否為 0。
用每對牌恰在一組 SET 檢查重複計數，整副牌應有 1,080 組，每張牌參與 40 組。
改搜尋法時，保留列舉 85,320 個三元組的版本做回歸基準，補全 3,240 對也應得到 1,080 組。
生成有解的練習題時，12 張桌面約會淘汰 3.17%，15 張約 0.04%（每種桌面各抽樣 200,000 次）。
搜尋 12 張桌面時，找到 SET 就停止，66 次是查完所有牌對的上限。