找次品例题分析

寻找未知特性的缺陷产品的“通用模型”

2018年8月11日星期六

本文给出了解决“N-1中缺陷产品特性未知”问题的一般模型。

首先重申一下问题的假设:

1.次品清单由质量定义；

2.缺陷产品是独特的；

3.其他合格产品的质量是一致的。

问题的技术手段:用失重天平进行比较称重。

问题的目标是用最少的称重次数找出次品，知道次品的重量特征，并给出一个完整的包括所有可能的称重步骤的称重实验程序。

一般来说，对于N，按照“尽可能分成三份”的最优策略，做如下分类:

(1)n=3a

(2)n=3a+1

(3)n=3a+2

其中:N，a∈N，a≥1。(如果a = 0，那么有n = 0，1，2。这三种情况没有讨论的意义:0-1不存在，1-1不良品是唯一需要发现的，2-1不良品特征未知，永远无法发现。因此，讨论仅限于n≥3。上面的分类其实就是n除以3，余数为0，1，2的三种情况。)

由于对情况(3)的讨论涵盖了情况(1)和(2)，本文重点讨论情况(3)，情况(1)和(2)很容易类比。

(A)对于n = 3a+2，分组如下:

N(3个最大的相同组，剩余组)= n (a组，B组，C组，剩余组)= n(A，A，A，2)

(2)一个引理:

如果经过两次比较后可以获得缺陷产品的特性，则至少需要三组相同的产品，如下所示:

|A|=|B|=|C|

(|A|:表示集合A中元素的个数，其余相同)

(重要性★★★★)

第一次:(A)←→(B)

第二次:(A)←→(C)

0-1:如果A和B平衡，C含有不良品，通过第二次称重可以知道不良品的重量；

1-0:如果A和B不平衡，A和C第二次平衡，B含有不良品，根据第一次称重可以知道不良品的重量；

1-1:如果A和B不平衡，第二次A和C不平衡，A含有不良品，从第一次或第二次称重就可以知道不良品的重量。

(符号的含义请参考前面的“特例1-5-1”破组法“寻找特性未知的不良品”)

(3)特殊情况:

当a = 0，n = 2时，2对1的缺陷产品特征是未知的，并且永远无法发现。原因可以理解为:不满足引理中“三个同群”的条件。

(IV)对于n = 3a+2，取3个“最大相同组”:

n(a，a，a，2)=n(a-1，a-1，a-1，5)=n(a-2，a-2，a-2，8)=……

只有取三个最大的同组(A，A，A)，剩下的组才能保持最小，剩下的组就是此时的余数2。

上面的分组把N分成了四组，为了让模型更接近“平分三分”的最优策略，剩下的一组是最小的。下面的推理过程和结论将有助于理解其中的原因。

(5)开始称重实验:

第一步:(A)←→(B)

第二步:(A)←→(C)

第三步:

分两种情况讨论:

ⅰ.缺陷产品属于3个最大的相同类别。

此时，会出现前两步:

1-1:不良品在A组，不良品特性已知；

1-0:不良品在B组，不良品的特性已知；

0-1:不良品在C组，不良品的特性已知。

问题转化为“N-2中的不良品特征已知”，总称重次数为:

(其中:M下标n-2表示“n-2知道缺陷产品特性的次数”)

二。残次品在剩下的一组。

也就是说，称重的前两步出现了:0-0。

设剩余组中的两个乘积为α和β。

结果只有一个:1。

从相同的A、B、C三组中选择一个合格产品:γ。与任何α或β进行比较和权衡:

1:说明α是次品，根据①或②可知；

0:表示β有缺陷，根据①重量可知。

这样的话:总共称2+2 = 4次。

㈥最后结论:

(重要性★★★★★)

(七)模型解的例子:

例1 29 Find 1不良品的特性未知。

“已知N发现1个不良品”的次数再次显示在下表中。原因请参考之前的《小学数学寻找次品简明写法》。

“发现1个已知特性的不良品”次数对照表

例2 28发现1不良品的特性未知。

例3 27发现1不良品的特性未知。

不良品的特性未知。

例5 10发现1不良品的特性未知。

例6 3发现1不良品的特性未知。

(8)补充说明:

1.该模型的应用可分为三种情况(n mod 3 = 0，1，2)。一般来说，不能保证提供“发现1个特性未知的不良品”的最优次数，但肯定能提供一个“可行的解决方案”和具体的“权衡实验步骤”；

2.与“破组法”和“换组法”相比，该模型中的每个组都是独立的，互不影响。实验操作简单易懂，采用“简单模型”。但是，不排除潜在的更好的模式；

3.该模型发展了“公式A”的思想，期望通过“额外称重”和“正常首重”来了解不良品的特性，将不良品的范围从三组缩小到一组。也可以看出，在3 | n(可除)的情况下，“公式A”的结果与该模型的结果完全一致；在3 ∤n(不可分)的情况下，当n的值正好是3的幂加1和2时，“公式a”的结果就会是错误的。所谓“3的幂”，指的是正常情况下找到“已知N的缺陷产品的特性”的次数的规则。详情请参考上面的“简明写作”。

再见。