珍珠湾ART

标题: 再来称球推广答案 [打印本页]

作者: constant 时间: 2005-11-6 00:10
标题: 再来称球推广答案

你手边有一个有左右两个托盘的特殊天平，这个天平可以显示哪边放的物品重以及重多少克。比如左边放10克的砝码，右边放11克的砝码，那么天平会显示右托盘重1克。
给你N袋小球，每袋装有10个小球，其中只有一个袋子中的小球全部为次品，其余N-1的袋子中的小球全为正品。所有的袋子和小球外观相同，所有正品小球质量相同，所有次品小球的质量也相同，正品与次品重量不同，但不知是重还是轻。
现在允许你称三次小球，然后你要判断出那个袋装的是次品并确定坏球是轻还是重。问：N最大为多大时，你仍能找出装次品的袋子。解释你的称球方案。

如果另外有一个好球呢？如果不需要知道轻重呢？

原题（已知坏球较轻）的解答用到-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 验证的，还没想出怎么直接证明。

作者: 寒潭清 时间: 2005-11-6 08:47
标题: 谢谢constant![@};-][>:D<] 建议下次推迟一二天给出答案,这样大家思考时间比较宽裕

谢谢constant!

建议下次推迟一二天给出答案,这样大家思考时间比较宽裕

作者: constant 时间: 2005-11-6 17:49
标题: 回复：谢谢constant![@};-][>:D<] 建议下次推迟一二天给出答案,这样大家思考时间比

大家都不认真做题。

作者: 寒潭清 时间: 2005-11-7 14:52
标题: constant,不是大家不认真做题,而是有可能

有些题的难度让人望而怯步,我就是

但可以肯定的是,你的题会让爱动脑的朋友们受益匪浅,这也是最重要的一点.都是好题啊!

答案推迟公布,比如说四~五天期限,这样可以激发大家,也可以给大家多点时间思考,有很多朋友都要学习\工作,休闲健脑时间有限, 多给大家留点机会嘛

欢迎光临珍珠湾ART (http://66.160.158.134/)