一题智力题(电池电线)
有3根电线 每根的一头在楼底 另一端在楼顶 有一个灯泡 一个电池 无数根很短的电线 怎么样在楼上一次再楼下去一次将电线的对应关系弄清楚。
和原来题目比, 简化了一下变3跟了, 好请高智商人士, 解答思路即可. 谢谢!
原来题目:
有101根电线 每根的一头在楼底 另一端在楼顶 有一个灯泡 一个电池 无数根很短的电线 怎么样在楼上一次在楼下去一次将电线的对应关系弄清楚。 智力题 电池电线
[解决办法]
那种进制题吧，可以google之
[解决办法]
现在下边联好1和2，在上边可以知道3是那根，然后23联上回下边，
[解决办法]
首先这个模型可以抽象成这样：楼上你线布置成一个无向图G=(V,E)。未知的长线代表一个V的排列pi。底下你可以测出来的是pi(G)的传递闭包C=C(pi(G))。这个问题求的是，该怎么构造G使得C唯一。
如果一个n个点的图有非平凡的自同构群，那么当楼上的短线布置成那个图的样子的时候，在楼下的时候无论怎么测都区分不了那几个自同构的情况的。因为如果自同构群不平凡，那么就有两个不同的排列pi1,pi2使得pi1(G)=pi2(G)。那这时候它们的传递闭包一定相同，也就是说你楼下测的结果就算完全一样，线的排列也至少有两种不同的可能性。
对于3来说。3个点的无向图自同构群都至少有一个非平凡元素。也就是说3是做不了的。
最小的平凡自同构群至少需要6个点，那个图是一个三角形，一个点伸出一个长1的边，一个点伸出一条长2的边。也就是说这个问题对于5个或以下的点数都是无解。
但是，就算构造出了一个有平凡自同构群的图，平凡的自同构群只能代表pi(G)和G有一一对应关系。但是G和它的传递闭包C之间不一定有一一对应关系，可能有不同的G拥有相同的传递闭包（比如G!=C(G)的时候，因为C(C(G))=C(G)，G和C(G)同时有传递闭包C(G)但是G!=C(G)）。所以光构造拥有平凡自同构群的图G是不够的。
对于101个点怎么构造这个G，等我有时间了想一下。
[解决办法]
又想了一下。无向图的传递闭包直接就把图分成了若干个连通分量。连通分量内部是区分不出的。所以只有一次上一次下对于所有的都是无解。
[解决办法]
