IBM Ponder This #058 · 2003 年 2 月

Michael Brand 提出了这个问题。有 2^N 张卡片，每张 C[c] 带有两个 N 维向量：标签 T[c] 和取值 V[c]。标签的各分量属于 {-1,+1}，所有 2^N 种标签各出现一次。取值的每个分量要么与对应标签分量相同，要么为零，因此 V[c] 的分量属于 {-1,0,+1}。标签固定，取值由外部人员事先任意指定，之后全部向你公开。

一组非空卡片的总值，是各张卡片的取值向量逐分量相加。例如 N=4 时，16=2^4 张卡片中取出三张：

• T[1]=[-1,-1,+1,+1]，V[1]=[-1,-1,0,+1]；
• T[2]=[+1,-1,+1,+1]，V[2]=[+1,0,+1,0]；
• T[3]=[+1,+1,-1,+1]，V[3]=[0,+1,-1,+1]。

这三张的总值为 [0,0,0,2]。

证明：无论这些取值如何指定，总能找到一个非空卡片子集，其总值为全零向量 [0,0,…,0]；并给出寻找方法。

解答

认真尝试后再打开

待补充。