9條電線... - 拼圖

※ 引述《stool100 (思念是毒妳是解藥)》之銘言：
: 一個101摩天大樓..
: 一樓到 101 樓 有九條獨立的電線
: 就是 一樓有九個線頭
: 101樓也是有九個線頭
: 顏色相同....如何查線??
: 限制的工具只有一個量測導通於否的電表..
: 可以將任意條線短路..
: 不過只能上樓一次..........
: 如何將一樓線號 123456789 對上101 樓ABCDEFGHI??

看到各種有趣的辦法,小弟來獻醜一下

剛剛看到bigboat大大的發文之後,突發奇想覺得這題好像有通解

稍微想了一下,決定po上來給各位大大鞭

先說原題的情況,是3的倍數

此時將線路短路為1 2 3 3 3 3...的組合(這邊指的是線路數目)

先假設1組的線路為A,2組的線路為BC,

很多3組的線路分別為K(x,y),其中x代表他是第幾組的線路,y代表第幾條線路
(以上的符號都是方便說明,事實上在過程中,我們不知道每條的順序,可以任意定義)

上樓測出組合後,清除掉所有連線,把A,B,K(1,1)連起來

對所有n,我們把每個K(n-1,2)和K(n,1)連起來,然後最後的一組,則將K(q,2)和C連起來
(假設q是最後一組)

下樓之後,由於我們已經知道A了,

所以就可以藉由和A連結的是來知道誰是B和K(1,1)
(B和K(1,1)之間是不會搞混的,他們一個是3組一個是2組)

知道K(1,1)之後,就可以開始查第1組,

結果會發現K(1,2)是有和別人短路的線路,其連結對象便是K(2,1)

而K(1,3)則和所有線路斷路,由此可以分辨K(1,2)和K(1,3)

以此方式類推,當知道K(n-1,1)時,就可以分辨出K(n-1,2)和K(n-1,3),

且可以找出K(n,1)

當搜尋進行到最後一組時,我們已經找出K(q,1)

此時和C有連結的q組成員則是K(q,2),另外一條線路則是K(q,3)




這個方法理解之後,便可以做總數為3n+1和3n+2的case

3n+1的case做法完全相同,只是一開始的分組變為1 1 2 3 3 3 3 3 3 3...

隨便排除一個1組然後像剛剛解3n的問題那樣接

下樓時,沒有和任何人接起來的1組就可以被分辨出來了




3n+2也是類似的做法,一開始的分組變成1 2 2 3 3 3 3 ...

上樓後,把其中一個2組移出,先照著3n的方式接好

然後把剛剛移出的2組其中一個成員接到1上

如此一來,關於後面無限的3組的部分就沒問題了

而2組中,靠著"另一條線路是不是和所有人斷路"就可以分辨是不是先被我們移除的2組

然後每一組內可以用是否和1連結來分辨彼此



這樣一來,所有數字的線路都可以用這個方法解決

不是很擅長講解= =a 如果看不太懂請鞭小力一點

--