你手边有一个有左右两个托盘的特殊天平，这个天平可以显示哪边放的物品重以及重多少克。比如左边放10克的砝码，右边放11克的砝码，那么天平会显示右托盘重1克。
给你N袋小球，每袋装有10个小球，其中只有一个袋子中的小球全部为次品，其余N-1的袋子中的小球全为正品。所有的袋子和小球外观相同，所有正品小球质量相同，所有次品小球的质量也相同，正品与次品重量不同，但不知是重还是轻。
现在允许你称三次小球，然后你要判断出那个袋装的是次品并确定坏球是轻还是重。问：N最大为多大时，你仍能找出装次品的袋子。解释你的称球方案。www.ddhw.com
如果另外有一个好球呢？如果不需要知道轻重呢？ 原题（已知坏球较轻）的解答用到-10到10中的数组成的GCD=1的三元数组S。S中每个数组对应一袋球，总共可以称|S| = 7491 袋球。我们要找S的子集T来标记球袋。因为不知坏球轻重，S中一个数组和它的对称组只能用一个，即如果用了（6，-8，9），就不能再用（-6，8，-9）。所以T最多只能是S的一半。另外一个条件是每次称时两边的球数要相等，也就是T中所有元素在每个坐标上的和必须是0。下面是一个构造方法。 把-10到10这21个数排成一圈。T中的数组（a, b, c) 满足下列条件之一：1）b 在 a 的顺时针方向的下半圈里，例如 a = 3, b 可以是 4 到 10，-10，-9，-8，不可以是 -7 到 2；2）a= b, c 在 a 的顺时针方向的下半圈里。这个T满足所需的两个条件，且有|T| = 3744：三个常数组（0，0，0），（1，1，1），（-1，-1，-1）不在T中，S中剩下的数组有一半在T中。 用这个方法N最大可以是3744。如果另外有一个好球，数组（1，1，1）可以加到T中，称的时候用好球来平衡。如果不需要知道轻重，（0，0，0）也可以用上，总共可以有3746袋。 需要说明的是其中第二个条件，T中所有元素在每个坐标上的和必须是0，我是用 computer 验证的，还没想出怎么直接证明。 www.ddhw.com
| 
哈哈哈哈 O(∩_∩)O哈哈~ 好久不来了，不小心看了一眼自己主页，发现自动关联了自己以往发过的帖，点进这个看了一眼，笑个半死。。。敢情我当初还发过这么搞笑的东西啊，我自己完全不记得了 
雷达卡
发表于 2005-11-6 00:10:45
收藏
分享
支持
反对
置顶卡
千斤顶
建议下次推迟一二天给出答案,这样大家思考时间比较宽裕
楼主