数竞趣题

来自数竞同学, 有12个球和一个天平, 天平可以比较两组球的重量和的大小关系, 其中一个球是假的, 可能更重或更轻, 称3次找出

这类题的关键是对获得信息量的考虑, 要使得每次询问的最坏情况下获取的信息量最多, 相当于尽量均衡

这个题第一步可以划分成4, 4, 4也可以是3, 3, 6, 发现若是3, 3, 6, 则不相等比相等多知道一个大小关系, 而4, 4, 4则更均衡

于是先考虑4, 4, 4, 如果相等则用2次从剩下的4个里找, 简单

如果不相等, 就要想办法利用这个不相等关系, 设球从1编号, 两组分别为1, 2, 3, 4和5, 6, 7, 8, 显然可以设1, 2, 3, 4>5, 6, 7, 8, 于是考虑问1, 2, 5和3, 4, 6, 如果相等仍然简单

如果又不相等, 考虑如果那个假球比正常的大, 则只能在1, 2, 3, 4和两组中大的那组的交中, 只有两个, 如果更小则是5, 6, 7, 8和两组中更小的那组的交中, 只有一个, 可以假设更大称那两个, 如果相等说明假设错了就是那一个, 否则取更大的一个.

还是很有意思的