不妨设总共有m个人。我们用域 上的向量 表示第i个部落,其中 当且仅当第j个人在第i个部落,否则 。
接下来我们将证明这些向量线性无关,再由这些向量是m维向量,我们即可推出 。
我们用*表示向量內积。一个部落的人数不能被3整除,意味着 ;两个部落的相同成员人数必须是3的倍数,意味着 。考察任意一组 使得, ,则有 ,因此 ,因此这组向量线性无关,因此问题得证。