一题智力题(电池电线)
有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,等我有时间了想一下。
[解决办法]
又想了一下。无向图的传递闭包直接就把图分成了若干个连通分量。连通分量内部是区分不出的。所以只有一次上一次下对于所有的都是无解。
[解决办法]