数学杂题分享 6

周子衡 · 2023-04-17 16:49:23 · 个人记录

题目 给定正整数 k。纸上画了一个 k\times k 的方格表。Alice 和 Bob 按下面的规则玩游戏：

• Alice 给 Bob 指定一个字符串集合 \mathcal{D}，这个集合中的每个字符串的长度都应为 k，且只包含字符 0 和 1。
• Bob 需要在方格的每个格子中填入字符 0 或 1 中的一个，使得每一行从左往右读所形成的字符串出现在 \mathcal{D} 中，每一列从上往下读形成的字符串也出现在 \mathcal{D} 中。

求最小的正整数 m，使得只要 Alice 给出的集合 \mathcal{D} 的大小不小于 m，Bob 就一定能找到一组填法。

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

（剧透警告）

我们先来构造一个尽量大的词典 \mathcal{D} 使得 Bob 一定填不出来。假如我们让所有词的开头都是字符 0，那么从行上的限制来看，方格表的第一列就只能全是 0 了。那么，如果我们的词典恰好包含所有 0 开头且不是全 0 的串，那么 Bob 就一定填不出来了（这是因为第一列一定矛盾）。这样我们构造了一个大小为 2^{k-1}-1 的词典，已经接近总数的一半了。我们猜测这就是最大的反例，也就是说，符合题意的最小的 m=2^{k-1}。

我们来证明这一点。考虑一个反例词典 \mathcal{D}，首先可以知道全 0 串和全 1 串不能出现在 \mathcal{D} 中，否则 Bob 直接全填同一种字符即可。

其次，对于任意字符串 s，s 和把 s 的每一位都取反所得到的字符串 s' 不能同时出现在 \mathcal{D} 中。这是因为考虑如下的构造：让方格表位于 (i,j) 的格子填 0 当且仅当 s_i=s_j。这样，可以发现若 s_i= 0 则第 i 行从左往右读结果为 s，反之为 s'；列上同理。综上我们便证明了该结论。

来源 本题来自刚刚结束的 EGMO 2023。