Drahtenden zuordnen

[Enigmemulo]

Durch einen Fluss verläuft ein Rohr, in dem n isolierte Drähte verlaufen, deren Enden an beiden Ufern des Flusses zugänglich sind. Dummerweise ist die Beschriftung verloren gegangen und so weiß man nicht, welches Ende an Ufer A zu welchem an Ufer B gehört. Um die Zuordnung neu zu erstellen, kann man Drahtenden verbinden und dann von der anderen Seite Spannung anlegen um zu prüfen, ob Strom fließt. Man hat keine Dioden, Widerstände usw., man kann zu zwei Drähten immer nur prüfen, ob sie auf der anderen Flussseite verbunden sind oder nicht.

Entwickle ein Strategie, die die Zuordnung aller Enden mit geringstem Aufwand wieder herstellt. Das Kostenmaß ist die Anzahl der Flussüberquerungen, wie viel man auf einer Seite vor sich hin wurschtelt ist egal.

[Otmar]

Erste Annährung:

Mehr ->

n=1 klar, geht ohne Überfahrt
n=2 geht m.E. gar nicht
n=m(m+1)/2 geht mit zwei Überfahrten:

Man lasse einen Draht unverbunden, verbinde die nächsten zwei, die nächsten drei, und so fort und fahre über.

Dort misst man jeden Draht mit allen anderen durch. Man erkennt, dass einer mit keinem anderen verbunden ist, das war drüben der erste. Zwei sind nur mit einem anderen verbunden, das war drüben Nummer 2 und 3. Drei sind genau mit zwei anderen verbunden, das waren drüben Nummer 3, 4 und 5 und so weiter.
Man hat also m Gruppen G1, G2, ..., Gi, ... Gm wobei in jeder Gruppe i Drähte sind. Nun verbinde man den einen Draht in G1 mit dem jeweils ersten jeder größeren Gruppe. Den zweiten Draht in G2 mit dem jeweils zweiten in G3, G4, ..., Gm und so weiter und fahre über.

Auf der Ausgangsseite angekommen, klingelt man die Verbindung des ersten Drahtes, der ja der eine in G1 ist, in jeder anderen Gruppe durch. Danach weiß man, welche Drähte mit dem jeweils ersten in jeder Gruppe verbunden sind und kennt auch den verbliebenen zweiten Draht in G2. Für diesen sucht man die Verbindung zu dem Draht in jeder größeren Gruppe und kennt dann den zweiten Draht jeder Gruppe auf der anderen Seite und auch den verbliebenen dritten Draht in G3. Fährt man so fort, hat man alle Drahtenden zugeordnet.

Vielleicht fällt mir für die anderen n auch noch was ein.

Muss jetzt noch meine Heizung verdrahten....

[Otmar]

Zweiter Teil

Mehr ->

auch der verbliebene Fall
n=m*(m+1)/2 + r mit m>=2 und 1 <=r<= m ist mit zwei Überfahrten machbar:

Man beginnt an Ufer A und nummeriert die Drähte von 1..n. Und bildet Gruppen
G1={1}, G2={2,3}, G3={4,5,6} .... Gm={n-r-m+1, ..., n-r} und die Gruppe R={n-r+1, ..., n}
Alle Drähte, die zu einer Gruppe gehören, werden verdrillt. Dann fährt man über zum Ufer B.

Dort ermittelt man Drähte der m-1 Gruppen {G1, G2, .... Gm} \ Gr anhand der Anzahl der Verbindungen. Da Gr und R die gleiche Zahl von Verbindungen haben, bekommt man am Ufer B zwei Gruppen mit r Drähten. Eine der beiden nennt man Gr'' und legt diese erstmal beiseite. Die andere nennt man Gr' und benutzt diese genau so, wie im oben beschriebenen Fall mit n=m*(m+1)/2. Nun widmet man sich den Drähten in Gr''. Der erste Draht in Gr'' bleibt am Ufer B unverbunden. Die anderen werden mit den Drähten gleicher Nummer in Gr' verbunden. Damit ist in Gr'' kein Draht mit G1 (für r=1 wäre das Gr') verbunden. Nun geht's zurück zum Ufer A.

Dort löst man erstmal die Verbindungen von vorher und beginnt mit dem Durchklingeln. (Das musste man auch obiger erster Antwort tun).
Für r = 1 prüft man, ob der erste Draht (der in G1) mit einem aus G2 verbunden ist. Wenn ja, dann war Gr'=G1 und Gr''=R. Die Zuordnung der restlichen Drähte stellt man wie im Fall n=m(m+1)/2 fest. Wenn nein, dann war Gr'=R und Gr''=G1 und man findet auch die Zuordnung.

Für r>1 prüft man, ob ein Draht in Gr mit dem Draht in G1 verbunden ist. Wenn ja, ist Gr'=Gr und Gr''=R und man kann die Zuordnung der Drähte für G1...Gm bestimmen. Der erste Draht in R war der unverbundene die anderen ermittelt man mit Gr. Wenn nein, ist Gr'=R und Gr''=Gr. Jetzt tauscht man einfach Gr und R am Ufer A und prüft so wie oben.

[MadMac]

Ein sehr schönes Rätsel, durchaus knifflig. Bin an zwei Stellen fast ins Schwimmen geraten.

Mehr ->

Bei zwei Drähten ist eine Identifizierung unmöglich.

Ansonsten muss man zweimal die Seite wechseln.

Ist n eine Dreieckszahl n = (m+1)*m/2, dann ist es einfach. Man verbindet je 1 (also eigentlich keine Verbindung, gekennzeichnet durch das kleine x für die erste und das große X für die zweite Runde), 2, 3, ... m Drähte miteinander

x
22
333
4444
55555
...
mmmmmmmm...m

, nimmt diesseits die erste Zuordnung in die Gruppen 1 bis m vor, und wechselt die Seite. Dort misst man, und kann die Gruppen 1 bis m ebenfalls identifizieren, lediglich über die Anzahl miteinander verbundenen Kontakte.

Nun schafft man hier wiederum Verbindungen in genau der gespiegelten Form

A
AB
ABC
ABC
...
ABCDE...X

Man nimmt die entsprechende Zuordnung in die Gruppen A bis X vor und wechselt die Seite, dröselt die dortigen Verbindungen auseinander und misst.

Anschließend kann man jedem Draht auf beiden Seiten eindeutig eine Kombination aus Zahl und Buchstaben zuordnen. Somit ist alles bekannt.



Kniffliger wird es, wenn es n keine Dreieckszahl ist.

Hier nimmt man für den ersten Versuch das größtmögliche m, so dass n > (m+1)*m/2. Es gibt m-1 Gruppen, die man zunächst verbindet wie oben dargestellt, ausgenommen die Gruppe 1. Die übrigen lässt man unverknüpft. Dies sind maximal m+1 Drähte.

22
333
4444
...
mmmmmmm...m
xxxxxxx...xxx(...x)

Die zweite Zuordnung funktioniert so:

für m+1 mal x

AY
ABX
ABCX
...
ABCD...X
ABCD...YX

oder für m mal x

AX
ABX
ABCX
...
ABCD...M
ABCD...M

oder für kleinere Anzahlen

AX
ABX
ABCX
...
ABCD ...X
ABCD...M

Den Kniff mit dem Y, das aus dem Dreiecksschema abweicht, braucht man, um das gegebenenfalls überzählige x aus der ersten Runde nicht allein über die Anzahl Verknüpfungen aber über die bekannte Information aus der ersten Runde eindeutig vom M unterscheiden zu können (Y und M verbinden je zwei Drähte).


Einzig und allein bei 5 Drähten funktioniert dies so nicht, da muss man weitere Information auswerten.

Erste Runde:

Ich verbinde auf einer Seite zeilenweise

1
22
22

Auf der anderen Seite erkenne ich das Muster, und Unterteile zusätzlich die beiden Zweiergruppen nochmal (und erkenne die erste Zuordnung 1):

1
2(a), 2(a)
2(b), 2(b)

Dann verbinde ich

A
AB
XB

und wechsele die Seite. Dort merke ich mir natürlich, wer mit wem verbunden war. Ich nehme das bekannte Drahtende 1A und finde die Verbindung zu Drahtende 2(a)A, womit der zweite Draht eindeutig identifiziert ist. Damit kann ich (weil ich weiß, mit wem (2(a)A) zuvor verbunden war) ohne zu messen 2(a)B identifizieren. Mit Messen dann 2(b)B, und über die bekannte alte Verbindung 2(b)X

Gruß,
MadMac

[MadMac]

P.S.:

Mehr ->

n = 4 ist in meinen Darstellungen nicht enthalten:

xx
22

XA
XA

[Half-Eye]

Mehr ->

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.

[MadMac]

Witzig ... ich konnte unangemeldet Half-Eyes Spoiler lesen. Angemeldet ist er wieder zu. Aber seine Lösung weicht eh in ihrer Systematik sehr von meiner ab

Gruß,
MadMac

[Otmar]

Finde auch, dass es ein sehr schönes Rätsel ist und versuche deshalb noch eine etwas anschaulichere Lösung;

Mehr ->

n=1 ohne Überfahrt
n=2 geht nicht.
Fall: n = m(m+1)/2:

Am Ufer A legt man die Drähte als Dreieck und verbindet alle Drähte einer Zeile:

1
2 3
4 5 6
7 8 9 10

Am Ufer B kann man anhand der Anzahl der Verbindungen die Zeilen rekonstruieren aber nicht die Reihenfolge in den Zeilen. Man kann also ein gleichartiges Dreieck legen wobei gegenüber dem Dreieck am Ufer A Vertauschungen innerhalb der Zeilen möglich sind. Z.B.

1
3 2
4 6 5
8 7 10 9

Nun verbindet man am Ufer B die Spalten miteinander und fährt zum Ufer A. Dort löst man alle vorhandenen Verbindungen und sortiert die Zeilen derart um, dass alle Drähte einer Spalte verbunden sind. Dazu wird alles was mit 1 verbunden ist, nach links sortiert. Dann hat man die erste Spalte, so wie am Ufer B und kann mit der zweiten Spalte weitermachen und so fort. Wenn man fertig ist, hat man am Ufer A das gleiche Dreieck wie am Ufer B, also die Drähte an selber Dreiecksposition sind die selben.

Für n=m(m+1)/2+r mit 1<=r<=m macht man auch ein Dreieck mit einer Zusatzzeile unten. Drei Beispiele für m=3 und r = 1, 2 oder 3

1              1             1  
2 3            2 3           2 3
4 5 6          4 5 6         4 5 6
7              7 8           7 8 9

Am Ufer A werden wieder alle Drähte in jeder Zeile verbunden und am Ufer B rekonstrueiert, dabei kann die untere Zeile mit r Elementen mit der anderen Zeile mit r Elementen vertauscht sein:

7              1             1
3 2            2 3           3 2
4 6 5          5 6 4         8 7 9
1              8 7           5 6 4

Auch hier werden wieder die Spalten miteinander verbunden, wobei man den links unten stehenden Draht unverbunden lässt und fährt zum Ufer A. Dort findet man erstmal heraus, ob am Ufer B die beiden Zeilen mit jeweils r Drähten gegenüber der Anordnung am Ufer A vertauscht sind. Bei B ist nun auf jeden Fall der erste Draht in der oberen Zeile mit r Elementen mit einem anderen Draht verbunden. (Auch für r = 1) Auch die anderen Drähte der oberen Zeile mit r Elementen sind verbunden, z.B. mit den Drähten der untersten Zeile, die ja auch r Drähte hat. Man sucht bei A nun in der unteren Zeile einen Draht, der mit keinem anderen verbunden ist. Findet man den nicht, vertauscht man die beiden Zeilen mit r Elementen. Jetzt sind an beiden Ufern die Dreiecke wieder so, dass es nur noch Vertauschungen in den Spalten gibt und man kann bei A die Zeilen wieder so sortieren, dass die Spalten untereinander, mit Ausnahme des Drahtes links unten, verbunden sind und hat dann an beiden Ufern die gleiche Anordnung.

[Enigmemulo]

Ich finde auch, dass es ein sehr schönes Rätsel ist, leider nicht von mir. Ich weiß aber auch nicht von wem es ist, ich habe es irgendwo aufgeschnappt.

Mehr ->

Ich habe natürlich auch eine Musterlösung, aber die ist fast identisch mit Otmars letztem Beitrag, deshalb spare ich sie mir. Und dass es nicht besser als mit 2 Überfahrten geht, ist auch klar.

Es hat mich etwas gewundert, dass keiner die Verdoppelungslösung vorgeschlagen hat: Verzwirbele alle Drähte bis auf einen und wechsele die Seite, damit ist einer bekannt. Jetzt verbinde immer jeden bekannten Draht mit genau einem unbekannten und wechsele. Damit verdoppelt sich die Zahl der bekannten in jedem Zug. Das ist mit 1+log_2(n) Überfahrten natürlich nicht optimal, gehört aber oft zu den ersten Sachen, auf die die Leute kommen.

[MadMac]

@Otmar: wenn ich das richtig sehe, funktioniert Dein zweiter Fall nicht für ...

Mehr ->

r = m, denn in beiden Gruppen bleibt je ein Draht im zweiten Versuch unverbunden, und die übrigen sind in jeweils den gleichen Gruppen vertreten. Demnach könntest Du Gr und R und Gr' und Gr'' nicht zuordnen.

Das war einer der Gründe, warum meine Lösung für nicht-Dreieckszahlen Fallunterscheidungen hat ...

Gruß,
MadMac