再再来称球[:)]

ob · 发表于 2005-10-19 04:37:54

你手边有一个有左右两个托盘的特殊天平，这个天平可以显示哪边放的物品重以及重多少克。比如左边放10克的砝码，右边放11克的砝码，那么天平会显示右托盘重1克。
给你N袋小球，每袋装有10个小球，其中只有一个袋子中的小球全部为次品，其余N-1的袋子中的小球全为正品。所有的袋子和小球外观相同，所有正品小球质量相同，所有次品小球的质量也相同，且正品比次品的重，但不知究竟重多少克。
现在允许你称三次小球，然后你要判断出那个袋装的是次品。问：N最大为多大时，你仍能找出装次品的袋子。解释你的称球方案。
（你可以从每袋取不同数目的小球，并给相应的袋子和小球做记号，以记录称的情况，但当然不会向那些大家都知道的老题目那样，如1,2,3,4,……或1,2,4,8之类）

fzy · 发表于 2005-10-19 06:34:19

好像可以几千，到底几千还没算出来。天平有多大？

fzy · 发表于 2005-10-19 18:24:28

设S为-10到10中的数组成的GCD=1的三元数组，例如（6，-8，9）属于S，（2，4，6）不属于S。这三个数中可以有0，例如（0。0，-1）属于S，（0，0，-2）不属于S。把（0，0，0）也加到S中。现在把S中每个三元数组分配给一个口袋。称的时候，如果数n>0，左边放n个球，如果n<0，右边放n个球，如果n=0，两边都不放。称的结果约简之后得到S中的一个数组，该数组对应的口袋就是坏球。例如称的结果是（6，-8，12），（3，-4，6）的口袋就是坏球。

现在计算|S|。S中不含0的正数组有1000-125-27-8+1-1+1=841个，含一个0的正数组有（100-25-9-4+1-1+1）*3=63个，含两个0的正数组有3个，总共加起来有841*8+63*4+3*2+1=7491个，所以可以称7491袋。

寒潭清 · 发表于 2005-10-20 07:56:16

新朋友吗?欢迎欢迎

fzy · 发表于 2005-10-20 18:40:17

称三次，每次用一个数。例如（3，-5，0），第一次左边放3个，第二次右边放5个，第三次不放。

没有顺序。少于7491袋时要保持对称性，保证每次称时两边球数一样。三袋球时可选（0，0，0），（1，1，1）（-1，-1，-1）。

三次结果放在一起形成一个数组，左边轻>0，右边轻<0。约简后必然是GCD=1的数组，一定在S中。例：（6，-8，9）的一袋是坏球，坏球比好球轻x,　则三次结果是　6x, -8x, 9x, 约简后得（6，-8，9）。

ob · 发表于 2005-10-21 09:29:47

无话可说，佩服！

fzy · 发表于 2005-10-21 18:58:13

		自动登录	找回密码
密码			立即注册

动态微博

再再来称球[:)]

回复：再再来称球[:)]

回复：再再来称球[:)]

新朋友吗?欢迎欢迎[:)][>:D<][@};-][>:D<]

回复：怎么老是丢掉内容？

[:O][:O][@};-]无话可说，佩服！

[:>] [:>]