Nehmen wir mal an, n = 3.
Dann kann man auf der einen Seite erstmal zwei Drähte miteinander verbinden.
Dann überquert man den Fluss und prüft nach Spannung. Dadurch kann man schon einen Draht eindeutig zuordnen, weil dies der einzige ist, durch den kein Strom fließt.
Dann fährt man nochmal rüber und verbindet zwei andere Drähte um den Fluss ein drittes Mal zu überqueren und auf Spannung zu prüfen.
Jetzt müsste der Draht, der vorhin keinen Strom hatte, Strom leiten und einer von den anderen, wodurch man die beiden anderen zuordnen kann.
Man kommt also mit 3 Flussüberquerungen aus.
Nehmen wir jetzt mal an, n = 4.
Man verbindet wieder zwei Drähte miteinander, überquert den Fluss und prüft auf Spannung.
Man hat also zwei Drähte mit Spannung und zwei ohne Spannung.
Dann überquert man wierder den Fluss und verbindet einen von den bisherig verbundenen Draht mit einen anderen.
Wieder eine Flussüberquerung und Prüfung.
Nun hat man einen Draht, der beide Male keinen Strom geleitet hatte, einen der beide Male Strom geleitet hatte und zwei, die nur jeweils einmal Strom geleitet haben, die sich aber durch die Reihenfolge unterscheiden.
Man kommt also auch mit 3 Flussüberquerungen aus.
Nehmen wir nun an, n = 5.
Man verbindet zwei Drahtpaare miteinander, überquert den Fluss und prüft.
Man kann also einen Draht wieder zuordnen. Dafür hat man vier Drähte, die Strom leiten, womit man wieder bei n = 4 ist.
Man hat also eine zusätzliche Flussüberquerung. Naja, im Prinzip 2, weil man ja wieder auf die Seite muss, wo die Drähte verbunden sind.
Allgemein:
Man teilt die Drähte in Gruppen von je drei Drähten ein. Nun misst man alle Gruppen gleichzeitig, wodurch man die Drähte in drei Gruppen auteilen kann: Immer Strom, nie Strom oder manchmal Strom.
Diese Gruppen kann man wieder in Gruppen von drei Drähten einteilen und geht wie vorhin vor.
Pro Messgang hat man 4 Flussüberquerungen.
Wenn also n durch 3 teilbar ist, Also n mod 3 = 0, dann hat man n/3 * 4 - 1 Flussüberquerungen. Wenn n mod 3 = 1, dann hat man (n - 1) / 3 * 4 - 1 Flussüberquerungen. Bei n mod 3 = 2 hat man (n - 2) / 3 * 4 + 2 Flussüberquerungen. |