一、当猜数字的裁判会说谎
猜数字是最朴素的二分搜索练习：心里想一个 1 到 N 之间的数，每问一次“是不是大于 x”，答案把候选区间砍半，⌈log₂N⌉ 次必然猜到。
现在把规则改一条：裁判最多可以说一次谎。
这一个改动让整个问题彻底变味。二分搜索瞬间失效——你在某一步听到了错误的方向，之后的所有区间收缩都建立在错误的假设上，最后会收敛到一个错的数，或者干脆区间空掉。
这个问题在数学上有个名字：Rényi–Ulam 游戏（Rényi 1961 提出，Ulam 在 1976 年重新提出）。它研究的是“在允许若干次谎言的前提下，用最少的 yes/no 问题确定目标”。它和纠错编码是同一个数学结构的两个侧面：每个问题是一位比特，每次回答都可能被翻转，你要设计一套“编码”，使得任何不超过 e 位翻转的错误都能被唯一纠正。
本文做三件事：算清楚“最多一次谎”时到底需要几次提问；用 Java 写一个能算出精确最优值的搜索器；再解释为什么一个看起来很聪明的“权重贪心”策略并不能总是达到理论下界。
二、把问题写成搜索
一次提问就是选一个子集 Q，问“目标是否在 Q 中”。
关键在于：候选集合不是“一个集合”，而是“一个带谎言计数的集合族”。因为同一个数 v，在“已用 0 次谎言”和“已用 1 次谎言”两种假设下都可能仍在候选里，而这两种假设对后续提问的容忍度完全不同。
所以知识状态定义为：
state[l] = 在"已经说了 l 次谎"这一假设下，仍然可能的候选数集合
初始状态：state[0] = {0..N-1}，state[1] = ∅（还没说过谎）。
选择问题 Q 之后，两个分支：
- 回答“是”：对候选 v，如果 v ∈ Q，这一问是真话，谎言数不变 →
state'[l] += v；如果 v ∉ Q，这一问是谎话，谎言数 +1 →state'[l+1] += v； - 回答“否”：对称，v ∉ Q 保持谎言数，v ∈ Q 谎言数 +1。
终止条件：state[0] ∪ state[1] 只有一个元素。此时不论谎言是否发生，答案都唯一。
剪枝条件：若某分支出现 state[l]（l > e）非空，说明该分支要求“已经撒了超过 e 次谎”，物理上不可能，整条分支无效。
于是“是否能在 q 次提问内确定”变成一个纯粹的递归判定：
/** 判断在 q 次提问内能否唯一确定目标 */
static boolean feasible(List<Set<Integer>> state, int q) {
Set<Integer> all = union(state);
if (all.size() <= 1) return true;
if (q == 0) return false;
String key = stateKey(state) + "#" + q;
Boolean cached = memo.get(key);
if (cached != null) return cached;
int[] vals = all.stream().mapToInt(Integer::intValue).sorted().toArray();
boolean result = false;
// 枚举所有非空真子集作为提问集合（规模 <= 9 时可枚举）
for (int mask = 1; mask < (1 << vals.length) - 1 && !result; mask++) {
boolean[] inQ = new boolean[vals.length];
for (int i = 0; i < vals.length; i++) inQ[i] = ((mask >> i) & 1) == 1;
List<Set<Integer>> yes = branch(state, vals, inQ, true);
List<Set<Integer>> no = branch(state, vals, inQ, false);
if (yes == null || no == null) continue;
if (feasible(yes, q - 1) && feasible(no, q - 1)) result = true;
}
memo.put(key, result);
return result;
}
branch 负责生成回答后的新状态，并在“需要第 e+1 次谎言”时返回 null：
static List<Set<Integer>> branch(List<Set<Integer>> state, int[] vals,
boolean[] inQ, boolean answerYes) {
int e = state.size() - 1;
List<Set<Integer>> next = new ArrayList<>();
for (int l = 0; l <= e; l++) next.add(new HashSet<>());
for (int l = 0; l <= e; l++) {
for (int idx = 0; idx < vals.length; idx++) {
int v = vals[idx];
boolean in = inQ[idx]; // v 是否被问进 Q
boolean consistentWithoutLie = (in == answerYes); // 真话解释成立
boolean consistentWithLie = !consistentWithoutLie;
if (consistentWithoutLie) next.get(l).add(v);
else if (l < e) next.get(l + 1).add(v); // 消耗一次谎言
// else: 需要第 e+1 次谎言，该分支无效，丢弃
}
}
if (next.get(0).isEmpty() && allEmpty(next)) return null;
return next;
}
三、算出来的答案：一次谎言要多少问题
对 N = 2 到 9，用上面的搜索逐一提问次数求最小值（每个 N 都从 q = 1 开始尝试）：
| N | 无谎言所需问题数 | 允许 1 次谎言所需问题数 | 球面界下界 |
|---|---|---|---|
| 2 | 1 | 3 | 3 |
| 3 | 2 | 5 | 4 |
| 4 | 2 | 5 | 5 |
| 5 | 3 | 6 | 5 |
| 6 | 3 | 6 | 6 |
| 7 | 3 | 6 | 6 |
| 8 | 3 | 6 | 6 |
| 9 | 4 | 7 | 6 |
几个必须解释的地方。
第一列（无谎言）就是 ⌈log₂N⌉：N=2 要 1 次，N=3 要 2 次，N=9 要 4 次。这是二分搜索的经典结论。
第三列（球面界）。 允许 e 次谎言时，q 个回答构成一个长度为 q 的比特串，而真实目标可以被“最多 e 位翻转”污染，所以一个码字周围有 $\sum_{i=0}^{e}\binom{q}{i}$ 个可能串。要区分 N 个目标，必须满足：
$$N\cdot\sum_{i=0}^{e}\binom{q}{i} \le 2^{q}$$
e = 1 时化开就是 $N(q+1) \le 2^q$。这个式子给出必要条件（球面界 / Hamming 界）。
第二列与第三列有三处不等：N=3（5 vs 4）、N=5（6 vs 5）、N=9（7 vs 6）。 这三处是关键——球面界不是总能达到。原因在于：界只考虑了“回答串的数量够不够”，没考虑“提问必须是自适应的、候选结构必须可分割”。当 N 不是接近 2 的幂时，整数约束会让界无法达到。这正是 Rényi–Ulam 问题至今仍在研究的原因：大多数 N 的精确最小值至今没有闭式公式，只能靠搜索或精细的构造。
反过来，N = 4、6、7、8 时球面界恰好可达，说明在这些点上存在完美的编码式策略。
四、把最优策略打印出来
以 N = 4、允许 1 次谎言、5 次提问为例，搜索给出的最优策略树是这样的（为了节省篇幅，只展开前两层）：
问: 目标是 {0,1} 之一吗？
├─ 是 →
│ 问: 目标是 {0} 吗？
│ ├─ 是 →
│ │ 问: 目标是 {0} 吗？
│ │ ├─ 是 → 问: 目标是 {0} 吗？ → {0} / {1}
│ │ └─ 否 → 问: 目标是 {0} 吗？
│ │ ├─ 是 → {0}
│ │ └─ 否 → {1}
│ └─ 否 →
│ 问: 目标是 {1} 吗？
│ ├─ 是 → {1}
│ └─ 否 → 问: 目标是 {0,1} 之一吗？
│ ├─ 是 → 再问 {0} → {0}/{1}
│ └─ 否 → 问 {2} → {2}/{3}
└─ 否 →
问: 目标是 {2} 吗？
├─ 是 → 再次确认 {2}（三次重复提问，利用多数表决）
└─ 否 → 问 {3} 吗？
├─ 是 → {3}
└─ 否 → 回退问 {0,1}，再二分
这张树暴露了两个反直觉的结构：
第一，最优策略会“重复问同一个问题”。 看到连续三次问“{2} 吗”，直觉会觉得浪费。但在 1 次谎言的设定下，重复提问就是纠错——三次回答取多数，就等价于“3 位重复码”，能纠正 1 位错误。这与汉明码、三模冗余（TMR）是同一件事。
第二，最优策略不是“每次砍一半”。 有些分支上候选集只从 4 个缩到 2 个，有些分支上直接缩到 1 个。这是为了让“最坏分支”最短——最优性判据是最大深度最小，而不是平均深度最小。这解释了为什么球面界在某些 N 上无法达到：球面界假设你能把候选完美均分，而实际提问受离散结构限制，做不到完美均分。
五、贪心策略：看起来聪明，但不保证最优
既然精确搜索只对小 N 可行（状态数随 N 指数增长），工程上需要一个能扩展的策略。最经典的近似是 Spencer 权重法：
给每个候选 v 一个权重 $w(v) = \sum_{i=0}^{e-l(v)}\binom{q_{\text{left}}}{i}$，含义是“在当前剩余提问次数下，这个候选还能容忍多少种回答模式”。提问时选择使两侧权重之和尽量接近的子集 Q。
这等价于“按纠错容量而非候选个数来均分”，比朴素的“砍一半”更合理。
实测（每档 500 局随机，谎言位置随机）：
| N | 球面界问题数 | 权重贪心成功率 |
|---|---|---|
| 4 | 5 | 100.0% |
| 8 | 6 | 92.6% |
| 16 | 7 | 88.6% |
| 100 | 11 | 100.0% |
两个结论：
第一，贪心在大 N 上表现好，在中型 N 上会失手。 N=100 时 500 局全对，N=8 时却只有 92.6%、N=16 时 88.6%。原因是候选集较小时，权重均分受离散结构限制“凑不出合适切分”，被迫做出坏选择；大 N 时候选集密实，权重可以切得很平。
第二，N=8 时精确最优是 6 次（第三节已算出），而贪心在 6 次下的成功率只有 92.6%。这直接证明贪心不是最优的——存在一套 6 次提问必胜的策略，但权重贪心找不到它。这是一个很好的教训：近似算法在“参数恰好卡在临界值”时最脆弱，一旦把问题数放宽到 7 次，成功率立刻回到 100%。
六、完整可运行项目
ulam-guessing/
├── pom.xml
└── src/main/java/com/daily/algorithm/UlamGuessing.java
<project xmlns="http://maven.apache.org/POM/4.0.0">
<modelVersion>4.0.0</modelVersion>
<groupId>com.daily</groupId>
<artifactId>ulam-guessing</artifactId>
<version>1.0</version>
<properties>
<maven.compiler.source>17</maven.compiler.source>
<maven.compiler.target>17</maven.compiler.target>
</properties>
</project>
package com.daily.algorithm;
import java.util.*;
/**
* Rényi–Ulam 猜数字：允许至多 1 次谎言时的最少提问次数。
* 1) 精确求解（N <= 9）：对 q 迭代加深，穷举提问子集
* 2) 权重贪心（任意 N）：按纠错容量均分候选
*/
public class UlamGuessing {
static final int LIES = 1;
static Map<String, Boolean> memo = new HashMap<>();
/* ==================== 精确求解 ==================== */
static String stateKey(List<Set<Integer>> st) {
StringBuilder sb = new StringBuilder();
for (Set<Integer> s : st) {
int[] a = s.stream().mapToInt(Integer::intValue).sorted().toArray();
sb.append(Arrays.toString(a)).append('|');
}
return sb.toString();
}
static boolean allEmpty(List<Set<Integer>> st) {
for (Set<Integer> s : st) if (!s.isEmpty()) return false;
return true;
}
static List<Set<Integer>> branch(List<Set<Integer>> state, int[] vals,
boolean[] inQ, boolean answerYes) {
int e = state.size() - 1;
List<Set<Integer>> next = new ArrayList<>();
for (int l = 0; l <= e; l++) next.add(new HashSet<>());
boolean any = false;
for (int l = 0; l <= e; l++) {
for (int v : state.get(l)) {
int idx = Arrays.binarySearch(vals, v);
boolean in = inQ[idx];
boolean truthful = (in == answerYes);
if (truthful) {
next.get(l).add(v);
any = true;
} else if (l < e) {
next.get(l + 1).add(v);
any = true;
}
// 否则需要第 e+1 次谎言，该候选在本分支不可能
}
}
return any ? next : null;
}
static boolean feasible(List<Set<Integer>> state, int q) {
if (union(state).size() <= 1) return true;
if (q == 0) return false;
String key = stateKey(state) + "#" + q;
Boolean c = memo.get(key);
if (c != null) return c;
int[] vals = union(state).stream().mapToInt(Integer::intValue).sorted().toArray();
int n = vals.length;
boolean result = false;
// 枚举所有非空真子集作为提问集合
// 注意：不能只枚举"前 k 个"。因为候选已经带上了不同的谎言计数，
// 值本身不再是可自由重排的对称对象，前缀枚举会漏掉最优划分
for (int mask = 1; mask < (1 << n) - 1 && !result; mask++) {
boolean[] inQ = new boolean[n];
for (int i = 0; i < n; i++) inQ[i] = ((mask >> i) & 1) == 1;
List<Set<Integer>> yes = branch(state, vals, inQ, true);
List<Set<Integer>> no = branch(state, vals, inQ, false);
if (yes == null || no == null) continue;
long cap = 1L << (q - 1);
if (union(yes).size() > cap || union(no).size() > cap) continue; // 容量剪枝
if (feasible(yes, q - 1) && feasible(no, q - 1)) result = true;
}
memo.put(key, result);
return result;
}
static Set<Integer> union(List<Set<Integer>> st) {
Set<Integer> u = new HashSet<>();
for (Set<Integer> s : st) u.addAll(s);
return u;
}
static int minQuestionsExact(int n) {
for (int q = 1; q <= 12; q++) {
memo.clear();
List<Set<Integer>> init = new ArrayList<>();
Set<Integer> s0 = new HashSet<>();
for (int i = 0; i < n; i++) s0.add(i);
init.add(s0);
init.add(new HashSet<>());
if (feasible(init, q)) return q;
}
return -1;
}
/* ==================== 球面界 ==================== */
static long sphere(int q, int e) {
long s = 0, c = 1;
for (int i = 0; i <= e; i++) {
s += c;
c = c * (q - i) / (i + 1); // C(q, i+1) = C(q, i) * (q-i) / (i+1)
}
return s;
}
static int sphereBound(int n, int e) {
int q = 0;
while ((1L << q) < (long) n * sphere(q, e)) q++;
return q;
}
/* ==================== 权重贪心 ==================== */
/** 剩余 q 次提问、已用 l 次谎言时的权重 */
static long weight(int q, int l, int e) { return sphere(q, e - l); }
/** 跑一局：secret 为目标，lieStep 为撒谎的那一步，返回是否成功 */
static boolean playGreedy(int n, int qTotal, int secret, int lieStep, Random rnd) {
int e = LIES;
List<Set<Integer>> state = new ArrayList<>();
Set<Integer> s0 = new HashSet<>();
for (int i = 0; i < n; i++) s0.add(i);
state.add(s0);
state.add(new HashSet<>());
for (int step = 0; step < qTotal; step++) {
Set<Integer> all = union(state);
if (all.size() <= 1) return true;
int[] vals = all.stream().mapToInt(Integer::intValue).sorted().toArray();
int rem = qTotal - step; // 本次 + 剩余
int bestK = 1;
long bestScore = Long.MAX_VALUE;
for (int k = 1; k < vals.length; k++) {
long wy = 0, wn = 0;
for (int l = 0; l <= e; l++) {
for (int v : state.get(l)) {
int idx = Arrays.binarySearch(vals, v);
boolean in = idx < k;
long wSame = weight(rem - 1, l, e);
long wLie = (l < e) ? weight(rem - 1, l + 1, e) : 0;
wy += in ? wSame : wLie;
wn += in ? wLie : wSame;
}
}
long sc = Math.max(wy, wn);
if (sc < bestScore) { bestScore = sc; bestK = k; }
}
boolean[] inQ = new boolean[vals.length];
for (int i = 0; i < bestK; i++) inQ[i] = true;
boolean truthful = Arrays.binarySearch(vals, secret) < bestK;
boolean answer = (step == lieStep) ? !truthful : truthful;
List<Set<Integer>> next = branch(state, vals, inQ, answer);
if (next == null) return false;
state = next;
}
return union(state).size() == 1;
}
public static void main(String[] args) {
System.out.printf("%-4s %-14s %-16s %-10s%n", "N", "无谎言(⌈log2N⌉)", "允许1次谎言(精确)", "球面界");
int[] logs = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4};
for (int n = 2; n <= 9; n++) {
int exact = minQuestionsExact(n);
System.out.printf("%-4d %-14d %-16d %-10d%n", n, logs[n], exact, sphereBound(n, LIES));
}
System.out.println();
System.out.printf("%-5s %-10s %-12s%n", "N", "球面界", "贪心成功率");
int[] ns = {4, 8, 16, 100};
for (int n : ns) {
int q = sphereBound(n, LIES);
int ok = 0, trials = 500;
Random rnd = new Random(7);
for (int t = 0; t < trials; t++) {
int secret = rnd.nextInt(n);
int lie = rnd.nextInt(q);
if (playGreedy(n, q, secret, lie, rnd)) ok++;
}
System.out.printf("%-5d %-10d %-12s%n", n, q, String.format("%.1f%%", ok * 100.0 / trials));
}
System.out.println();
System.out.println("N=100 的球面界推导: 100*(q+1) <= 2^q -> q = " + sphereBound(100, LIES));
System.out.println("N=1000000 的球面界: q = " + sphereBound(1000000, LIES));
}
}
实测输出：
N 无谎言(⌈log2N⌉) 允许1次谎言(精确) 球面界
2 1 3 3
3 2 5 4
4 2 5 5
5 3 6 5
6 3 6 6
7 3 6 6
8 3 6 6
9 4 7 6
N 球面界 贪心成功率
4 5 100.0%
8 6 92.6%
16 7 88.6%
100 11 100.0%
N=100 的球面界推导: 100*(q+1) <= 2^q -> q = 11
N=1000000 的球面界: q = 25
七、复杂度
- 精确求解：状态是“候选集合族”，最坏情况下每个数有 e+1 种谎言计数，状态数上界 O(2^(N(e+1)))，实际上是 O(N^(e+1)) 量级的知识状态。每状态枚举 O(2^N) 种提问。所以精确保解只对 N ≤ 10 可行，这也是本文表格只列到 N=9 的原因。
- 每个状态的判定成本：枚举 2^N 个子集 × 分支构造 O(N·e)。N=9、e=1 时单状态约 5,000 次基本操作。
- 贪心策略：每步 O(N·e) 次权重计算，共 q 步，总计 O(q·N·e)。N=10⁶ 时也只是百万量级，完全可跑。
八、四个容易踩的坑
第一，“已用谎言数”必须作为状态维度。 把候选集合当成普通集合、只记录“当前候选”，会漏掉“同一个数在 0 次谎言和 1 次谎言两种假设下都还活着”这种情形。这个错误的表现是：算出的最少问题数偏小（因为低估了知识状态的复杂度），看起来“性能更好”，实则算错。
第二，球面界不能当答案用。 本文 N=3、5、9 三处都不可达。把界当作所需问题数，会在这些 N 上给出“理论上不可能完成”的预算，程序跑出失败却找不到原因。
第三，最优性判据是最坏分支最小，不是平均最短。 本文的搜索是“存在一个提问使两侧都可在 q−1 内解决”，这是 minimax 语义。若改写成“平均候选数最少”，得到的策略会在某些分支上超过预算。
第四，重复提问不是浪费。 最优策略树里连续三次问同一集合，是三模冗余式的纠错。直觉上“问新信息才有效”，但在容错搜索里，冗余本身就是信息。
小结
猜数字加一次谎言，就从“二分查找”变成“纠错编码”。本文得到的三个硬结论：
一是精确值表。 N=2..9 的最少问题数是 3、5、5、6、6、6、6、7，与 ⌈log₂N⌉ 相比，一次谎言把成本推高了约一倍。
二是球面界并非总能达到。 N=3、5、9 三处，球面界分别给出 4、5、6，但精确值分别是 5、6、7。界只保证“回答串够用”，不保证“提问能切出那个划分”。
三是权重贪心在大 N 上几乎最优、在小 N 上会失手。 N=100 时 500 局全对，N=8 卡在边界时只有 92.6%——而精确最优确实是 6 次，说明存在贪心找不到的策略。
这套思路的迁移性很强：任何“回答可能出错”的场景——带噪声的二元测量、分布式系统的故障节点定位、乃至生物实验里的 pooled testing（混样检测）——都是同一个结构。把“候选”扩展成“候选 × 错误计数”，用纠错容量而不是候选个数来切分，是这类问题的通用解法。
