电线头对应测试

袁哥哥

善科网上有一道趣题。楼上楼下有15跟电线穿过墙壁，两边都露出线头，电线大小颜色等一样，只有一个联通测试仪，楼层比较高怎么设计方案楼上楼下来回次数最少，测试出所有电线头对应关系？

我好像有一个任意大于2跟线头只跑一趟一个来回的方案，但看出题者意思应该不是这种，先看看这儿的高手怎么个方案？

mathe

就是来回一趟。

sunwukong

首先，在楼下，线头分成 5 组，把每组的线头连在一起。

X1 组： 标记为 A11
X2 组： 标记为 A21、A22
X3 组： 标记为 A31、A32、A33
X4 组： 标记为 A41、A42、A43、A44
X5 组： 标记为 A51、A52、A53、A54、A55

然后，跑到楼上，测试每2个线头的连通情况，这趟测试把楼上的线头分成 5 组：

第一组：与其他线头都不连通的一个线头，与 X1 组对应。标记为 B11
第二组：有且只有两个线头互相连通的，与 X2 组对应。标记为 B21、B22
第三组：有且只有三个线头互相连通的，与 X3 组对应。标记为 B31、B32、B33
第四组：有且只有四个线头互相连通的，与 X4 组对应。标记为 B41、B42、B43、B44
第五组：五个线头互相连通的，与 X5 组对应。标记为 B51、B52、B53、B54、B55

然后，按以下的分组，把线头分成 5 组，每组的线头连在一起：

S1 组：B11、B21、B31、B41、B51
S2 组：B22、B32、B42、B52
S3 组：B33、B43、B53
S4 组：B44、B54
S5 组：B55

然后，下楼，把原先连结在一起的线头都解开，再测试每 2 个线头的连通情况，这趟测试把楼下的线头按楼上的分组情况分成 5 组。根据这两次的编组情况就能确定每个线头的对应关系了。
对应关系如下：

楼下的线头，第一次编组时在 Xi 组，第二次测试时在 Sj 组。（i从1到5，j从1到5），则此线头与 Bij对应。

具体列出来，就是
第一次所在的编组   第二次测试所在的组   对应的楼上的编号
X1                 S1                   B11
X2                 S1                   B21
X2                 S2                   B22
X3                 S1                   B31
X3                 S2                   B32
X3                 S3                   B33
X4                 S1                   B41
X4                 S2                   B42
X4                 S3                   B43
X4                 S4                   B44
X5                 S1                   B51
X5                 S2                   B52
X5                 S3                   B53
X5                 S4                   B54
X5                 S5                        B55

袁哥哥

3# sunwukong

这办法好像对根叔有限制吧？

袁哥哥

当时手机上看到在大脑里演算出一个只跑一趟一个来回的方案，看题目意思和称小球等题目觉得还可能是线头数n的一个表达式，后来用笔确认演算一下方案确实没错。

线头数n＞2，

1、A端任意两两线头连接，直到留下1根或者2根。（n奇数留下一根，偶数留下2根。）

2、B端测试连通性，连通者以2和3、4和5等依次配对标号。最后没有连通者取一根标号1，重新1和2、3和4等依次配对两两连接。注意此时最大标号没有连接。如果n为偶数，此时还有一根没有标号，标号n。

3、A端，如n为奇数，没有连接一根标号1，如n为偶数，取没有连接两根，测试和其它没有连通一根标号n，另一跟标号1。测试和1连通者标号2，和2原来连接在一起者标号3，以3继续上面过程，标号顺序增加，直到标号完。（怎么测试连通性不再叙述。）

现在AB两边标号相同者为同一根电线。

注意2完成后，如果n为奇数，整个电线从标号1开始依标号依次连接成为一根，如n为偶数，前面n-1根如前所述，单独标号n一根。很优美的结果。