智力题吧 关注：49,494贴子：478,030
- 27回复贴，共1页
我应该能做到猜出23个位置 27个无法确定 首先，这题耍了个小把戏，问乙能确定多少张，但其实乙只需把每种组合都问完即可，我们真正要考虑的是甲的策略。
换言之，问题可以等价为：设有n张纸条，若不论乙如何指定，甲总能保证乙无法确定任何一张纸条，求n的最大值。原题答案即是50-n（若为负数则取0）。
对于n=27，我们可以构造出甲的一种策略：
先考虑“3张纸条、每轮指定2或3张”的情况。
设数字为a、b、c，甲采用“三角轮换策略”：指定ab时，答a；指定bc时，答b；指定ca时，答c；指定abc时，随便答。
再考虑“27张纸条、每轮指定10张”的情况。
甲只需对“三角轮换策略”进行推广：将卡片分为9堆，每堆3张。则每次指定时必有1堆被指定2或3张，对其使用“轮换策略”即可。
换言之，问题可以等价为：设有n张纸条，若不论乙如何指定，甲总能保证乙无法确定任何一张纸条，求n的最大值。原题答案即是50-n（若为负数则取0）。
对于n=27，我们可以构造出甲的一种策略：
先考虑“3张纸条、每轮指定2或3张”的情况。
设数字为a、b、c，甲采用“三角轮换策略”：指定ab时，答a；指定bc时，答b；指定ca时，答c；指定abc时，随便答。
再考虑“27张纸条、每轮指定10张”的情况。
甲只需对“三角轮换策略”进行推广：将卡片分为9堆，每堆3张。则每次指定时必有1堆被指定2或3张，对其使用“轮换策略”即可。
接下来，证明n≤27。这等价于证明“当n=28，乙必能确定至少一个数”。
将纸条编号为(1)~(28)，假设通过甲的回答，乙最终得到了k种可能的结论。记第i种可能中，卡(j)的数字为x_ij。
不用担心有数字没被回答过，用w_1、w_2之类的代数来代称这些未知数就行。（相应地，其它知道数值的数就叫已知数。）
若此时乙无法确定任何一个数，则必有：k≥2，且每一列的数都不全为同一个已知数。
此时，我们不妨试着从第1行中任取一个数x_1a。若它是未知数，则甲任何时候都不能回答x_1a；若它是已知数，则必存在一个不同行、不同列的x_bc满足x_bc=x_1a，那么只要乙指定的10张纸条不同时包含(a)、(c)，甲就不能回答x_1a。
故，我们只需说明，总存在一种10张纸条的组合，迫使甲无法回答任何一个数，引发矛盾，即可完成证明。
对第一行中所有的已知数x_1a都取一个相等且在不同行、列的x_bc，并记下(a, c)。
然后我们画一张有28个点的图，将点记为点1~点28，连接所有的(点a,点c)。
于是，找到一种迫使甲无法回答任何一个数的10纸组合，就等价于找到10个两两不相连的点。
考虑将1张图分为若干个连通的部分。举个简单的栗子：
设一个连通部分有m个点，则它最多有m条边。我们只需考虑有m点m边的情况，因为其他情况都是更弱的。
一个m点m边的连通图一定恰好存在一个环，其余部分为树状。砍掉环上任意一条边，整个图就会变成树状。
此时给点交替黑白上色，相同颜色的点就是不相连的，我们选取数量更多的那一方即可。如果刚好选到了环上被砍开的、原本相连的两点，则删掉其中的一个。
举个简单的栗子：
于是，我们在一个有m个点的连通部分中，至少能选出⌊m/2⌋个不相连点（⌊ ⌋为向下取整）。
将每个连通部分的点数累加，就是总的不相连点数。
要使这种取法下的最少点数尽可能多，就要让每个部分尽可能都是3点环：
而n=28最多最多就只能做到9个3点环+1个孤立点，必然可以选出10个不相连点，引发矛盾，证毕。
对于任意的纸条总数与任意的每轮纸条指定数量，这个结论都可以轻易推广。
将纸条编号为(1)~(28)，假设通过甲的回答，乙最终得到了k种可能的结论。记第i种可能中，卡(j)的数字为x_ij。
不用担心有数字没被回答过，用w_1、w_2之类的代数来代称这些未知数就行。（相应地，其它知道数值的数就叫已知数。）
若此时乙无法确定任何一个数，则必有：k≥2，且每一列的数都不全为同一个已知数。
此时，我们不妨试着从第1行中任取一个数x_1a。若它是未知数，则甲任何时候都不能回答x_1a；若它是已知数，则必存在一个不同行、不同列的x_bc满足x_bc=x_1a，那么只要乙指定的10张纸条不同时包含(a)、(c)，甲就不能回答x_1a。
故，我们只需说明，总存在一种10张纸条的组合，迫使甲无法回答任何一个数，引发矛盾，即可完成证明。
对第一行中所有的已知数x_1a都取一个相等且在不同行、列的x_bc，并记下(a, c)。
然后我们画一张有28个点的图，将点记为点1~点28，连接所有的(点a,点c)。
于是，找到一种迫使甲无法回答任何一个数的10纸组合，就等价于找到10个两两不相连的点。
考虑将1张图分为若干个连通的部分。举个简单的栗子：
设一个连通部分有m个点，则它最多有m条边。我们只需考虑有m点m边的情况，因为其他情况都是更弱的。
一个m点m边的连通图一定恰好存在一个环，其余部分为树状。砍掉环上任意一条边，整个图就会变成树状。
此时给点交替黑白上色，相同颜色的点就是不相连的，我们选取数量更多的那一方即可。如果刚好选到了环上被砍开的、原本相连的两点，则删掉其中的一个。
举个简单的栗子：
于是，我们在一个有m个点的连通部分中，至少能选出⌊m/2⌋个不相连点（⌊ ⌋为向下取整）。
将每个连通部分的点数累加，就是总的不相连点数。
要使这种取法下的最少点数尽可能多，就要让每个部分尽可能都是3点环：
而n=28最多最多就只能做到9个3点环+1个孤立点，必然可以选出10个不相连点，引发矛盾，证毕。
对于任意的纸条总数与任意的每轮纸条指定数量，这个结论都可以轻易推广。
这个证明的关键在于2点：
1.建立乙的推理过程：
可以想象为，乙会列出一张“可能性表格”，初始时用w_1~w_50代表纸条上的50个数字，并进行全排列得到所有可能性。每当获得某10纸组合的回答时，若该数未出现过，则将1个未知代数替换为已知数，并将该数不出现在这10张纸条中的可能性排除；若该数出现过，则只进行排除的步骤。直到问完所有组合，根据最终剩余的可能性进行数字推断。
2.将证明转化为图。
第2点我没想出来，也许是因为没学过图论吧（别找借口，菜是原罪
）。上面的证明是我整理别人答案写出来的。从这个证明反推，一种可能的思路是，在直觉上甲做得最“极限”时，乙最终会剩2种可能结论且所有数都是已知数（也即甲采用“推广三角轮换策略”会产生的状况）。单独考察这种情况，就比较容易与图联系在一起，并证明出纸条的最佳构造是三角轮换，而后再推广到更普遍的情况。
不过这么说感觉还是有点牵强，如果有朋友有非常直观的将这题与图联系在一起的思路，可以分享下。
1.建立乙的推理过程：
可以想象为，乙会列出一张“可能性表格”，初始时用w_1~w_50代表纸条上的50个数字，并进行全排列得到所有可能性。每当获得某10纸组合的回答时，若该数未出现过，则将1个未知代数替换为已知数，并将该数不出现在这10张纸条中的可能性排除；若该数出现过，则只进行排除的步骤。直到问完所有组合，根据最终剩余的可能性进行数字推断。
2.将证明转化为图。
第2点我没想出来，也许是因为没学过图论吧（别找借口，菜是原罪
）。上面的证明是我整理别人答案写出来的。从这个证明反推，一种可能的思路是，在直觉上甲做得最“极限”时，乙最终会剩2种可能结论且所有数都是已知数（也即甲采用“推广三角轮换策略”会产生的状况）。单独考察这种情况，就比较容易与图联系在一起，并证明出纸条的最佳构造是三角轮换，而后再推广到更普遍的情况。不过这么说感觉还是有点牵强，如果有朋友有非常直观的将这题与图联系在一起的思路，可以分享下。
