Sieben Schalter

16.04.2020, 19:04

Leopold

Auf diesen Beitrag antworten »

Sieben Schalter

Ob es das heute noch im Mathematikum in Gießen gibt, weiß ich nicht, aber vor ein paar Jahren gab es das folgende Exponat.

Sieben Schalter zum Drücken waren in einem Kreis angeordnet. Einige davon waren eingeschaltet, was man daran erkannte, daß sie aufleuchteten. Drückte man auf einen Schalter, so änderten er und seine beiden Nachbarschalter ihren Zustand, aus eingeschaltet wurde ausgeschaltet und aus ausgeschaltet eingeschaltet.
Wie mußte man vorgehen, damit alle Schalter aufleuchteten?

16.04.2020, 20:38

Elvis

Auf diesen Beitrag antworten »

Ein isolierter AUS, einen AN daneben drücken ergibt zwei AUS. Drei Aus nebeneinander, mittleren drücken. Zwei AUS nebeneinander, einen drücken, damit sind beide AN, und insgesamt einer weniger AUS. (Kommt mir komisch vor, nochmal drüber schlafen, wenn ich vor lauter Grübeln dazu komme.)

16.04.2020, 21:34

Elvis

Auf diesen Beitrag antworten »

Ist da eventuell ein Trick dabei? Kann es sein, dass es keinen Weg von 1 AUS und 6 AN gibt? So ähnlich wie bei dem Verschiebespiel?
Nachtrag : geht doch, mit 4 mal drücken mach ich aus einem AUS deren drei nebeneinander.

16.04.2020, 22:44

Gualtiero

Auf diesen Beitrag antworten »

Nachdem eine Beschreibung des Vorgehens nicht sehr aussagekräftig ist, habe ich mich für eine Tabelle entschieden.
Der Anfangszustand ist nicht beschrieben, also setze ich alles auf AUS.
Die Schalter sind fortlaufend numeriert, der Umlaufsinn ist egal.

[attach]51028[/attach]

Bin gespannt, ob es auch mit weniger als 7 mal Drücken geht.

16.04.2020, 22:48

Elvis

Auf diesen Beitrag antworten »

Strategie: Im Uhrzeigersinn drücken. Fall 1: Situation besser, nächster Schalter. Fall 2: Situation schlechter, nochmal drücken stellt letzten Zustand wieder her, nächsten Schalter drücken.

Für alles AUS brauche ich auch 7 mal drücken. Das muss aber nicht optimal sein.

Zusatzfrage. Wie oft muss man mindestens drücken um von 0 bis 127 alle Dualzahlen darzustellen? Wie oft, wenn alle Zahlen aufsteigend geordnet angezeigt werden sollen? Wir werden es niemals wissen...

16.04.2020, 23:12

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Gualtiero
Der Anfangszustand ist nicht beschrieben, also setze ich alles auf AUS.

Gesucht ist eine Strategie, so daß man bei jedem Ausgangszustand ans Ziel kommt: alles an. Aber irgendwie muß man ja mal anfangen.

Zitat:

Original von Gualtiero
Bin gespannt, ob es auch mit weniger als 7 mal Drücken geht.

Aber vielleicht mit einer anderen Permutation ...

Anzeige

17.04.2020, 08:24

HAL 9000

Auf diesen Beitrag antworten »

Ich würde es so beschreiben (d.h. das Originalproblem, nicht das schwierigere von Elvis):

Durch Drücken der 5 Schalter $\begin{eqnarray*} n-3,n-1,n,n+1,n+3 \end{eqnarray*}$ (alles modulo 7) invertiert sich Zustand $\begin{eqnarray*} n \end{eqnarray*}$ , während die anderen bestehen bleiben.

Das macht man nun für alle im Ausgangszustand ausgeschalteten Schalter. Natürlich kann man auch alles vorher notieren und dann die notwendigen Schaltanzahlen pro Schalter modulo 2 reduzieren, denn doppeltes Schalten (auch wenn es zeitlich auseinander liegt) hat ja keinen Effekt. Somit muss jeder Schalter nur maximal einmal betätigt werden, es gibt damit tatsächlich eine Bijektion von den $\begin{eqnarray*} 2^7 \end{eqnarray*}$ Anfangsschalterstellungen zu den $\begin{eqnarray*} 2^7 \end{eqnarray*}$ möglichen Strategien "jeder Schalter wird maximal einmal gedrückt; Reihenfolge des Drückens spielt keine Rolle".

Das beantwortet nebenbei auch mit die Frage, ob es von "alles aus" zu "alles an" mit weniger als 7x Drücken geht: Es geht nicht, die Strategie "alle 7 Schalter jeweils einmal drücken (egal in welcher Reihenfolge)" ist da anzahlmäßig minimal.

Zitat:

Original von Elvis
Wie oft, wenn alle Zahlen aufsteigend geordnet angezeigt werden sollen?

Da verstehe ich noch nicht ganz, wie du das meinst: Abgesehen von den nur $\begin{eqnarray*} 2^4 \end{eqnarray*}$ Situationen, wo xxxx011 in xxxx100 umgewandelt wird, wird eine Schalterbetätigung immer dafür sorgen, dass runtergezählt oder um mehr als 1 hochgezählt wird. Meinst du das vielleicht so, dass eine Teilfolge der Anzeigen dann die Gestalt 0000000, 0000001, 0000010, ... , 1111110, 1111111 hat? Und du willst die minimale Länge der Gesamtfolge wissen, damit eine derartige Teilfolge existiert? verwirrt

verwirrt

Falls das so gemeint ist, so komme ich auf minimal 535 Schalterbetätigungen für diese Monotonie-Zusatzfrage.

17.04.2020, 10:28

Ulrich Ruhnau

Auf diesen Beitrag antworten »

RE: Sieben Schalter
Ich würde so vorgehen, daß ich mir einen leuchtenden Schalter suche, der möglichst viele leuchtende Schalter rechts von ihm hat.
Dann gehe ich der Reihe nach zum nächsten Schalter links im Kreis und bringe jedes fehlende Licht zum leuchten, indem ich jeweils den Schalter links von ihm bediene.
Vielleicht habe ich Glück und bringe so alle Schalter zum leuchten.
Anderenfalls muß ich weiter knobeln.

17.04.2020, 10:29

Luftikus

Auf diesen Beitrag antworten »

Wenn man mit 0000000 startet, dann drücken

1) jeder Taste im Kreis
2) jeder 2. Taste im Kreis
3) jeder 3. Taste im Kreis

führt zu dem Zustand 1111111 (insg. 7x drücken).

Wenn man in diesen drei Zyklen mit jeder der 7 Lampen startet, bekommt man so

3*7*6 = 126 Kombinationen.

Die Vermutung ist, dass jede der 128 Kombination (mit Start und Ende) so genau einmal vorkommt.
Jede andere Reihenfolge des Drückens der Lämpchen sollte zwischen diesen Zyklen wechseln.
Vermutlich liegen in den 3 Zyklen aber die Minimalabstände zu dem Endzustand?

17.04.2020, 11:00

Elvis

Auf diesen Beitrag antworten »

Hier kommt eine vollständige Lösung, die vielleicht nicht optimal ist und auch nicht sonderlich elegant. Auf Seite A stehen die 18 möglichen Zustände, wobei ein Kringel für "aus" und ein Kreuzchen für "an" steht. (Bei "1" ist ein Kringel zu viel, bitte wegdenken.) Auf Seite E sind die Zustandsübergänge zusammengefasst. Details für E kann ich bei Bedarf nachliefern. (Vielleicht sind auch noch Fehler drin, macht's besser. Muss ich bei den Zuständen noch ggf. den Umlaufsinn "links"/"rechts" berücksichtigen ?)

17.04.2020, 11:16

HAL 9000

Auf diesen Beitrag antworten »

@Luftikus

Zunächst mal gehe ich davon aus, dass du über die Lösung der ersten Zusatzfrage von Elvis redest, oder?

Zitat:

Original von Luftikus
Wenn man mit 0000000 startet, dann drücken

1) jeder Taste im Kreis
2) jeder 2. Taste im Kreis
3) jeder 3. Taste im Kreis

führt zu dem Zustand 1111111 (insg. 7x drücken).

Hier beginnen schon meine Verständnisprobleme: Ich habe das so aufgefasst, dass in 1), 2) und 3) JEWEILS 7x gedrückt wird, also insgesamt 21-mal, und das unmittelbar hintereinander, d.h. etwa bei 1 beginnend in der Drücksequenz

1 2 3 4 5 6 7 2 4 6 1 3 5 7 3 6 2 5 1 4 7 .

Die entstehenden 22 Leuchtenstellungen (also inklusive Anfangsstellung 0000000) sind aber nicht paarweise voneinander verschieden: Tatsächlich tauchen dabei sowohl 0000000, 1111111 und auch noch 0111100 doppelt auf.

Also ganz unabhängig davon, dass ich nicht verstehe, wie (d.h. mit welcher Tastensequenz) du dann den Übergang auf diese 126 Kombinationen vollziehst, ist es mir ein Rätsel, wie du auf diese Weise alle 128 Kombinationen erfassen willst. verwirrt

verwirrt

P.S.: Elvis' letzten Beitrag habe ich noch nicht durchgelesen.

17.04.2020, 11:27

Leopold

Auf diesen Beitrag antworten »

Da habe ich ja was losgetreten. So viele verschiedene Strategien zur Lösung. HAL hat das wieder einmal perfekt gelöst, die andern konnte ich noch nicht durcharbeiten. Da ich gerne rechne, biete ich hier meine Lösung mit Linearer Algebra an.

$\begin{align*} \mathbb{Z}_m \end{align*}$ sei der Ring der ganzen Zahlen modulo $\begin{align*} m \end{align*}$ . Den Zustand der Schalter können wir als Abbildung $\begin{align*} u: \mathbb{Z}_7 \to \mathbb{Z}_2 \end{align*}$ auffassen und $\begin{align*} u \end{align*}$ mit einem Septupel $\begin{align*} u = \left( u_1, \ldots, u_7 \right) \end{align*}$ identifizieren. $\begin{align*} u_i \end{align*}$ ist 1, wenn der Schalter mit der Nummer $\begin{align*} i \end{align*}$ an ist, und 0, wenn er aus ist. Die Änderung des Zustands entspricht der Addition von 1. Drückt man auf den Schalter $\begin{align*} i \end{align*}$ , so geht $\begin{align*} u \end{align*}$ in $\begin{align*} u' \end{align*}$ über mit

$\begin{align*} u' = u + e_{i-1} + e_i + e_{i+1} \end{align*}$

Hierbei bezeichne $\begin{align*} e_i \end{align*}$ den $\begin{align*} i \end{align*}$ -ten Einheitsvektor. Mit Hilfe der Matrix

$\begin{align*} T = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix} \end{align*}$

kann man das auch so schreiben:

$\begin{align*} u'^{\top} = u^{\top} + Te_i^{\top} \end{align*}$

Wird nun im Zustand $\begin{align*} u \end{align*}$ nacheinander auf die Schalter $\begin{align*} i,j,k,\ldots \end{align*}$ gedrückt, so bekommt man den Zustand

$\begin{align*} u'^{\top} = u^{\top} + T \left( e_i + e_j + e_k + \ldots \right)^{\top} \end{align*}$

Einheitsvektoren, die in der Summe zweimal vorkommen, heben sich gegenseitig weg. Man darf also annehmen, daß die $\begin{align*} i,j,k,\ldots \end{align*}$ paarweise verschieden sind. Offenbar führt auch jede Permutation der Indizes zum selben Ergebnis. Schreiben wir $\begin{align*} x = e_i + e_j + e_k + \ldots \end{align*}$ , so ist die Gleichung

$\begin{align*} a^{\top} = u^{\top} + Tx^{\top} \end{align*}$ für den Vektor $\begin{align*} a = (1,1,1,1,1,1,1) \end{align*}$ ("alle an")

zu lösen. Zu drücken sind genau die Schalter, deren Koordinate in $\begin{align*} x \end{align*}$ eine 1 enthält, und zwar in irgendeiner Reihenfolge. Drücken weiterer Schalter muß durch das Drücken desselben Schalters gleich oder später kompensiert werden (und ist somit überflüssig). $\begin{align*} T \end{align*}$ ist invertierbar, so daß die Schalter, die gedrückt werden müssen, eindeutig bestimmt sind:

$\begin{align*} T^{-1} = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{pmatrix} \end{align*}$

Ferner ist $\begin{align*} a \end{align*}$ unter $\begin{align*} T \end{align*}$ fix, so daß die Auflösung

$\begin{align*} x^{\top} = T^{-1} u^{\top} + a^{\top} \end{align*}$

ergibt.

Beispiel 1

Für $\begin{align*} u = (0,0,0,0,0,0,0) \end{align*}$ (alle Schalter sind aus) erhält man $\begin{align*} x = a \end{align*}$ . Man muß also auf alle Schalter drücken.

Beispiel 2

Für $\begin{align*} u = (0,0,1,1,1,0,0) \end{align*}$ (drei aufeinander folgende Schalter sind an) bekommt man $\begin{align*} x = (0,0,0,1,0,0,0) \end{align*}$ . Man drückt den mittleren der drei Schalter. (Da wäre man vielleicht auch so drauf gekommen.)

Beispiel 3

Für $\begin{align*} u = (1,1,1,0,1,1,1) \end{align*}$ (alle Schalter außer einem an) bekommt man $\begin{align*} x = (1,0,1,1,1,0,1) \end{align*}$ . Man drückt alle Schalter außer den beiden übernächsten Nachbarschaltern. (Hierin spiegelt sich auch die $\begin{align*} n-3,n-1,n,n+1,n+3 \end{align*}$ -Strategie von HAL.)

Hier noch meine Lösung für HALs Interpretation von Elvis' Frage: Man möchte die Dualzahlen von 0000000 bis 1111111 der Reihe nach erzeugen. Wie oft muß man minimal drücken, um diese Dualzahlenfolge als Teilfolge zu erhalten? Ein Stern soll für das unveränderliche Offset im Septupel $\begin{align*} u \end{align*}$ stehen.

Übergang von *0 nach *1: $\begin{align*} x^{\top} = T^{-1} e_1^{\top} = (1,0,1,1,0,1,1)^{\top} \end{align*}$
Anzahl der Drücke: 5

Übergang von *01 nach *10: $\begin{align*} x^{\top} = T^{-1} \left( e_1 + e_2 \right)^{\top} = (1,1,0,1,1,0,0)^{\top} \end{align*}$
Anzahl der Drücke: 4

Übergang von *011 nach *100: $\begin{align*} x^{\top} = T^{-1} \left( e_1 + e_2 + e_3 \right)^{\top} = (0,0,0,0,0,1,0)^{\top} \end{align*}$
Anzahl der Drücke: 1

Übergang von *0111 nach *1000: $\begin{align*} x^{\top} = T^{-1} \left( e_1 + e_2 + e_3 + e_4 \right)^{\top} = (1,0,1,1,1,1,1)^{\top} \end{align*}$
Anzahl der Drücke: 6

Übergang von *01111 nach *10000: $\begin{align*} x^{\top} = T^{-1} \left( e_1 + e_2 + e_3 + e_4 + e_5 \right)^{\top} = (1,1,0,0,1,0,0)^{\top} \end{align*}$
Anzahl der Drücke: 3

Übergang von *011111 nach *100000: $\begin{align*} x^{\top} = T^{-1} \left( e_1 + e_2 + e_3 + e_4 + e_5 + e_6 \right)^{\top} = (0,0,1,0,0,1,0)^{\top} \end{align*}$
Anzahl der Drücke: 2

Übergang von 0111111 nach 1000000: $\begin{align*} x^{\top} = T^{-1} \left( e_1 + e_2 + e_3 + e_4 + e_5 + e_6 + e_7 \right)^{\top} = (1,1,1,1,1,1,1)^{\top} \end{align*}$
Anzahl der Drücke: 7

Damit ist die Minimalzahl von Drücken

$\begin{align*} 7 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 6 \cdot 8 + 1 \cdot 16 + 4 \cdot 32 + 5 \cdot 64 = 535 \end{align*}$

EDIT 1
Schreibfehler korrigiert

EDIT 2
Nach Intervention von HAL Schreibfehler in Matrix korrigiert

17.04.2020, 11:30

HAL 9000

Auf diesen Beitrag antworten »

@Elvis

Da besteht für mich einiger Klärungsbedarf. Zunächst mal die Zustände:

Durch Rotation ODER Spiegelung ineinander übergehende Konstellationen betrachtest du dabei als gleich, oder? Ich hatte erst angenommen "nur Rotation", aber da würden ja dann einige fehlen:

Es gibt die rotationssymmetrischen Zustände 0 und 7, die restlichen 126 Konstellationen müssten sich dann in $\begin{eqnarray*} \frac{126}{7}=18 \end{eqnarray*}$ weiteren Zuständen abbilden, bei dir sind es ja aber nur 16.

Nachtrag: Die beiden fehlenden bei "nur Rotation" wären die Spiegelvarianten von $\begin{eqnarray*} 3_{01} \end{eqnarray*}$ sowie $\begin{eqnarray*} 4_{01} \end{eqnarray*}$ .

@Leopold

Ja, genauso bin ich auch auf die 535 gekommen.

In deiner $\begin{eqnarray*} T^{-1} \end{eqnarray*}$ -Matrix scheint übrigens eine Zeile abhanden gekommen zu sein - wie es aussieht die zweite:

$\begin{eqnarray*} T^{-1} = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{pmatrix} \end{eqnarray*}$ .

17.04.2020, 12:01

Elvis

Auf diesen Beitrag antworten »

HAL 9000 und Leopold, ihr zeigt euch wieder einmal überlegen. Gute Mathematik ist eben doch besser als Bleistift und Papier. STUDIEREN GEHT ÜBER PROBIEREN.

Mit meiner Bemerkung " Wir werden es niemals wissen... " lag ich auch knapp daneben. Das war wieder einmal eine sehr kurze Ewigkeit.

17.04.2020, 12:11

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
@Leopold
In deiner $\begin{eqnarray*} T^{-1} \end{eqnarray*}$ -Matrix scheint übrigens eine Zeile abhanden gekommen zu sein - wie es aussieht die zweite:

Das siehst du völlig falsch. Ich habe nur eine Methode entwickelt, eine 7×7-Matrix als eine 6×7-Matrix zu invertieren. "Zeilenreduktion nach Leopold" heißt das Verfahren. (Hab's ausgebessert. Danke für das genaue Lesen.) Augenzwinkern

Augenzwinkern

Man kann das Problem auch von $\begin{align*} n=7 \end{align*}$ Schaltern auf eine Schalterzahl $\begin{align*} n \geq 4 \end{align*}$ erweitern. Bildet man entsprechend die Matrix $\begin{align*} T_n \end{align*}$ , so gilt,

wenn man $\begin{align*} T_n \end{align*}$ als Matrix über $\begin{align*} \mathbb{Z} \end{align*}$ auffaßt:

$\begin{align*} \det \left( T_n \right) = \begin{cases} 0, & n \equiv 0 \ (3) \\ (-1)^{n+1} \cdot 3, & n \not \equiv 0 \ (3) \end{cases} \end{align*}$

wenn man $\begin{align*} T_n \end{align*}$ als Matrix über $\begin{align*} \mathbb{Z}_2 \end{align*}$ auffaßt, folglich

$\begin{align*} \det \left( T_n \right) = \begin{cases} 0, & n \equiv 0 \ (3) \\ 1, & n \not \equiv 0 \ (3) \end{cases} \end{align*}$

Das Problem ist also nur für alle $\begin{align*} n \end{align*}$ , die nicht durch 3 teilbar sind, eindeutig lösbar.

17.04.2020, 13:07

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
HAL 9000 und Leopold, ihr zeigt euch wieder einmal überlegen.

Das sehe ich anders: Da es hier nur um $\begin{eqnarray*} GF\left(2^7\right) \end{eqnarray*}$ geht, noch dazu nur die Additionsgruppe, kann ich noch mithalten - ist vielleicht für einen echten Algebraiker wie dich einfach ein viel zu popeliges Problem. Big Laugh

Big Laugh

17.04.2020, 13:28

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Da es hier nur um $\begin{eqnarray*} GF\left(2^7\right) \end{eqnarray*}$ geht, noch dazu nur die Additionsgruppe ...

Der Vektorraum $\begin{align*} \left( \mathbb{Z}_2 \right)^7 \end{align*}$ , oder wie das heißt, seit die Angelsachsen auch noch die Algebra erobert und alle Körper zu Feldern gemacht haben, sozusagen plattgewalzt: $\begin{align*} \left( \mathbb{F}_2 \right)^7 \end{align*}$ , ist nicht dasselbe wie $\begin{align*} \mathbb{F}_{2^7} = \operatorname{GF}\left( 2^7 \right) \end{align*}$ . Augenzwinkern

Augenzwinkern

@ Elvis

Es ist ja nicht so, daß ich die Lösung dieser Aufgabe, die ich selbst gestellt habe, nicht gekannt und über Nacht durch Eingebung des Gottes Arithmos gelöst hätte. Vielmehr war ich mal vor Jahren mit einer Schulklasse im Mathematikum in Gießen. Das Problem hat mich fasziniert, und ich habe mich hinterher damit beschäftigt. Ob ich für meine Lösung damals eine Stunde, einen Tag oder eine Woche gebraucht habe, weiß ich nicht mehr.

17.04.2020, 13:33

HAL 9000

Auf diesen Beitrag antworten »

Womit auch Leopold nochmals deutlich untermalt hat, wie wenig Ahnung ich von Algebra und deren Bezeichnungen habe. Big Laugh

Big Laugh

17.04.2020, 14:21

Elvis

Auf diesen Beitrag antworten »

Danke, das baut mich wieder etwas auf, nachdem ich von der Algebra weg auf Irrwege geraten war. Zu Zeiten der jungen Emmy Noether nannten "wir" die Algebren noch Hyperkomplexe Systeme ... ich ergötze mich zur Zeit an Deurings "Algebren" (1934) und Krulls "Idealtheorie" (1935), immer geleitet von van der Waerdens "moderner Algebra" (insbesondere Teil II ist wärmstens zu empfehlen ... eine wahre Fundgrube an Schätzen ... mit manchen Sätzen und Beweisen kann man sich Tage und Wochen beschäftigen).

17.04.2020, 18:40

PhyMaLehrer

Auf diesen Beitrag antworten »

Ich verstehe zwar die vorangegangenen Erklärungen nicht Gott

Gott

, aber diese AuUfgabe hat mich auf die Idee gebracht, daraus ein kleines elektronisches Spiel zu machen. Augenzwinkern

Augenzwinkern

Wenn's fertig ist (ist aber noch nicht gleich morgen...), zeige ich mal ein Bild hier. Wink

Wink

17.04.2020, 19:51

Leopold

Auf diesen Beitrag antworten »

@ PhyMaLehrer

Selbst wenn du die Details der Herleitung nicht verstanden hast, kannst du doch die Formel anwenden: Zustandsvektor $\begin{align*} u \end{align*}$ gegeben, Zustandsvektor $\begin{align*} u' \end{align*}$ soll erreicht werden. Ich schreibe die Vektoren in Spaltenschreibweise. Dann gilt

$\begin{align*} u' = u + Tx \ \ \Leftrightarrow \ \ x = T^{-1} \left( u' - u \right) \end{align*}$

Die Matrix $\begin{align*} T^{-1} \end{align*}$ steht in meinem Beitrag. Du kannst wie in $\begin{align*} \mathbb{Z} \end{align*}$ rechnen und darfst dabei zu jeder Zeit jede gerade Zahl durch 0 und jede ungerade durch 1 ersetzen.

Beispiel

Die Schalter 2,4,6 leuchten auf. Wie muß man vorgehen, damit die Schalter 1,2,3 aufleuchten?

Ausgangszustand: $\begin{align*} u = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \end{align*}$ , gewünschter Zustand: $\begin{align*} u' = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{align*}$

$\begin{align*} u' - u = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} - \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ -1 \\ 0 \\ -1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \end{align*}$

Jetzt $\begin{align*} T^{-1} \end{align*}$ damit multiplizieren:

$\begin{align*} x = \begin{pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 2 \\ 3 \\ 3 \\ 3 \\ 3 \\ 2 \\ 4 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} \end{align*}$

Ergebnis: Betätige (in irgendeiner Reihenfolge) die Schalter 2,3,4,5.

17.04.2020, 21:04

HAL 9000

Auf diesen Beitrag antworten »

Es gibt übrigens folgende verblüffend einfache Lösung für die erste Zusatzfrage von Elvis:

Man betätigt die Schalter einfach gemäß einer 7-Bit-Graycode-Reihenfolge, wegen der o.g. Bijektion (beschrieben durch Leopolds $\begin{eqnarray*} T \end{eqnarray*}$ bzw. $\begin{eqnarray*} T^{-1} \end{eqnarray*}$ ) durchlaufen dann auch die zugehörigen Schalterstellungen genau die 128 Möglichkeiten (diese dann natürlich weder in Graycode- noch monotoner Reihenfolge). Somit kann man mit 127 Schalterbetätigungen alle Zustande durchlaufen, bzw. mit 128 Schalterbetätigungen ist man wieder am Anfang (zyklischer Durchlauf). Augenzwinkern

Augenzwinkern

18.04.2020, 09:54

quadrierer

Auf diesen Beitrag antworten »

Hallo HAL,
kannst du es bitte etwas ausführlicher erklären, wie das gelingt? Ich brauche schon 7 Drücker um von 7 AUS zu 6 AUS und 1 AN zu gelangen, da 1 Drücker immer 3 benachbarte Stellen ändert? Was mach ich falsch? Sind es 127 Drücker für alle Gray-Code-Zahlne oder 127 Drückerzyklen?

18.04.2020, 10:43

HAL 9000

Auf diesen Beitrag antworten »

Ich hab mal eine dieser Möglichkeiten aufgelistet: In der folgenden Tabelle ist die erste Spalte einfach die Zeit, die zweite der zu drückende Schalter, die dritte Spalte protokolliert, wie oft jeder Schalter bisher gedrückt wurde (aber nur modulo 2), und die vierte und letzte Spalte gibt schließlich an, wie die Schalterstellungen nach dem eben getätigten Drücken aussieht. Das ganze mit Start "alle Schalter aus".

Die dritte Spalte folgt dabei einem Graycode.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:

001	7	0000001	1000011
002	6	0000011	1000100
003	7	0000010	0000111
004	5	0000110	0001001
005	7	0000111	1001010
006	6	0000101	1001101
007	7	0000100	0001110
008	4	0001100	0010010
009	7	0001101	1010001
010	6	0001111	1010110
011	7	0001110	0010101
012	5	0001010	0011011
013	7	0001011	1011000
014	6	0001001	1011111
015	7	0001000	0011100
016	3	0011000	0100100
017	7	0011001	1100111
018	6	0011011	1100000
019	7	0011010	0100011
020	5	0011110	0101101
021	7	0011111	1101110
022	6	0011101	1101001
023	7	0011100	0101010
024	4	0010100	0110110
025	7	0010101	1110101
026	6	0010111	1110010
027	7	0010110	0110001
028	5	0010010	0111111
029	7	0010011	1111100
030	6	0010001	1111011
031	7	0010000	0111000
032	2	0110000	1001000
033	7	0110001	0001011
034	6	0110011	0001100
035	7	0110010	1001111
036	5	0110110	1000001
037	7	0110111	0000010
038	6	0110101	0000101
039	7	0110100	1000110
040	4	0111100	1011010
041	7	0111101	0011001
042	6	0111111	0011110
043	7	0111110	1011101
044	5	0111010	1010011
045	7	0111011	0010000
046	6	0111001	0010111
047	7	0111000	1010100
048	3	0101000	1101100
049	7	0101001	0101111
050	6	0101011	0101000
051	7	0101010	1101011
052	5	0101110	1100101
053	7	0101111	0100110
054	6	0101101	0100001
055	7	0101100	1100010
056	4	0100100	1111110
057	7	0100101	0111101
058	6	0100111	0111010
059	7	0100110	1111001
060	5	0100010	1110111
061	7	0100011	0110100
062	6	0100001	0110011
063	7	0100000	1110000
064	1	1100000	0010001
065	7	1100001	1010010
066	6	1100011	1010101
067	7	1100010	0010110
068	5	1100110	0011000
069	7	1100111	1011011
070	6	1100101	1011100
071	7	1100100	0011111
072	4	1101100	0000011
073	7	1101101	1000000
074	6	1101111	1000111
075	7	1101110	0000100
076	5	1101010	0001010
077	7	1101011	1001001
078	6	1101001	1001110
079	7	1101000	0001101
080	3	1111000	0110101
081	7	1111001	1110110
082	6	1111011	1110001
083	7	1111010	0110010
084	5	1111110	0111100
085	7	1111111	1111111
086	6	1111101	1111000
087	7	1111100	0111011
088	4	1110100	0100111
089	7	1110101	1100100
090	6	1110111	1100011
091	7	1110110	0100000
092	5	1110010	0101110
093	7	1110011	1101101
094	6	1110001	1101010
095	7	1110000	0101001
096	2	1010000	1011001
097	7	1010001	0011010
098	6	1010011	0011101
099	7	1010010	1011110
100	5	1010110	1010000
101	7	1010111	0010011
102	6	1010101	0010100
103	7	1010100	1010111
104	4	1011100	1001011
105	7	1011101	0001000
106	6	1011111	0001111
107	7	1011110	1001100
108	5	1011010	1000010
109	7	1011011	0000001
110	6	1011001	0000110
111	7	1011000	1000101
112	3	1001000	1111101
113	7	1001001	0111110
114	6	1001011	0111001
115	7	1001010	1111010
116	5	1001110	1110100
117	7	1001111	0110111
118	6	1001101	0110000
119	7	1001100	1110011
120	4	1000100	1101111
121	7	1000101	0101100
122	6	1000111	0101011
123	7	1000110	1101000
124	5	1000010	1100110
125	7	1000011	0100101
126	6	1000001	0100010
127	7	1000000	1100001
128	1	0000000	0000000

18.04.2020, 13:37

quadrierer

Auf diesen Beitrag antworten »

Danke.
Wenn ich es nun richtig verstanden habe, kann man bei Kenntnis solcher Tabellen auch von einem beliebigen Anfangszustand starten, der dann in solch einer Tabelle zu suchen ist.

18.04.2020, 13:42

HAL 9000

Auf diesen Beitrag antworten »

Da das ganze ja zyklisch angelegt ist, kannst du an beliebiger Stelle starten.

18.04.2020, 13:54

Luftikus

Auf diesen Beitrag antworten »

Das ist echt stark! Freude

Freude

Der Graycode liefert ja aber nicht den kürzesten Abstand zwischen zwei beliebigen Zuständen. Gibt es hierfür ein Verfahren?

18.04.2020, 14:14

HAL 9000

Auf diesen Beitrag antworten »

Das geht doch schon mit Leopolds Überlegungen: Von $\begin{eqnarray*} x \end{eqnarray*}$ nach $\begin{eqnarray*} y \end{eqnarray*}$ kommt man mit den Schalterbetätigungen (d.h. den Einsen in) $\begin{eqnarray*} T^{-1} (x-y) = T^{-1} (x+y) \end{eqnarray*}$ .

Beispiel: Von 0111111 nach 1000101 kommt man mit

$\begin{eqnarray*} T^{-1} \left( 0111111 + 1000101 \right) = T^{-1} ~ 1111010 = 1001010 \end{eqnarray*}$ ,

d.h. durch Betätigen der Schalter 1,4 und 6 (egal in welcher Reihenfolge. Kürzer geht es nicht.

19.04.2020, 18:34

quadrierer

Auf diesen Beitrag antworten »

HAL zeigt noch mal deutlich, wie mit Hilfe der Invers-Matrix T^{-1}, die aus T hervorgeht, zu einer aktuellen Drücker-Folge gelangt wird. Leider kann ich nicht nachvollziehen wie Leonhard zur Matrix T gelangt. Ich sehe in seiner Matrix T jeweils 3 AN und 4 AUS und dann in jeder nachfolgenden Zeile eine Rechtsverschiebung. Wie ist das zu verstehen?

19.04.2020, 19:44

Leopold

Auf diesen Beitrag antworten »

Du hast das genau richtig beschrieben: die drei Einsen mit der Rechtsverschiebung in

$\begin{align*} T = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \end{pmatrix} \end{align*}$

Wenn du jetzt zum Beispiel mit $\begin{align*} e_7 \end{align*}$ , dem siebten Einheitsvektor, als Spalte geschrieben, multiplizierst, erhältst du genau die siebte Spalte der Matrix, weil die Nullen in $\begin{align*} e_7 \end{align*}$ die anderen Spalten ignorieren.

$\begin{align*} Te_7 = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 & \color{red} 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & \color{red} 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & \color{red} 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & \color{red} 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & \color{red} 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & \color{red} 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & \color{red} 1 \end{pmatrix} \cdot \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \color{red} 1 \end{pmatrix} = \color{red} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{pmatrix} \end{align*}$

Und die siebte Spalte der Matrix ist nichts anderes als $\begin{align*} e_6 + e_7 + e_1 \end{align*}$ , das ist vom Typ $\begin{align*} e_{i-1} + e_i + e_{i+1} \end{align*}$ mit $\begin{align*} i=7 \end{align*}$ (in den Indizes rechnen wir modulo 7). Und da die Matrix systematisch so aufgebaut ist, gilt allgemein

$\begin{align*} Te_i = e_{i-1} + e_i + e_{i+1} \end{align*}$

Wieder zurück zum Beispiel $\begin{align*} i=7 \end{align*}$ . Addiert man $\begin{align*} Te_7 \end{align*}$ zu einem Vektor $\begin{align*} u \end{align*}$ , so ändern genau die Koordinaten Nummer 6,7,1 ihren Zustand. Beachte, daß hier modulo 2 gerechnet wird:

$\begin{align*} \begin{pmatrix} \color{red} 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ \color{red} 1 \\ \color{red} 0 \end{pmatrix} + \begin{pmatrix} \color{red} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ \color{red} 1 \\ \color{red} 1 \end{pmatrix} = \begin{pmatrix} \color{red} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ \color{red} 0 \\ \color{red} 1 \end{pmatrix} \end{align*}$

Lange Rede, kurzer Sinn: Die Addition von $\begin{align*} Te_i \end{align*}$ beschreibt das Drücken auf den Schalter $\begin{align*} i \end{align*}$ .

19.04.2020, 21:59

URL

Auf diesen Beitrag antworten »

Um den Zustand des Schalters an der Position n zu invertieren, kann man die Schalter $\begin{eqnarray*} n+1,n+4,n,n+3,n+6 \end{eqnarray*}$ drücken - das ist letztlich die gleiche Sequenz, die HAL angegeben hat.
Für die Anzahl $\begin{eqnarray*} d \end{eqnarray*}$ der betätigten Schalter gilt $\begin{eqnarray*} 3d \equiv 1 \bmod (2n) \end{eqnarray*}$
$\begin{eqnarray*} 3d \end{eqnarray*}$ weil man immer drei Schalter ändert, modulo $\begin{eqnarray*} 2n \end{eqnarray*}$ , weil man zweimal um den Kreis herum muss, damit die Ausgangszustände wieder hergestellt sind.
Also ist $\begin{eqnarray*} d \end{eqnarray*}$ invertierbar und das geht nur, wenn n nicht durch 3 teilbar sind - ein Ergebnis, das Leopold schon auf anderem Wege gefunden hat.

20.04.2020, 11:02

quadrierer

Auf diesen Beitrag antworten »

Kann man es so verstehen, dass in der Matrix T in jeder Zeile die Wirkung des Drückens des Schalters dargestellt wird, der die Nummer der Zeile hat? Wenn ja, funktioniert dieses Verfahren des Berechnens auch dann noch, wenn beispielsweise der zweite Schalter nur seinen Zustand ändert und seine Nachbarn unverändert bleiben?

20.04.2020, 11:28

HAL 9000

Auf diesen Beitrag antworten »

Man kann sich durchaus vorstellen, für jeden Schalter getrennt festzulegen, welche Schalter sein Betätigen zusätzlich noch mit umkippt, was sich in einer entsprechend veränderten Matrix $\begin{eqnarray*} T \end{eqnarray*}$ niederschlägt. Die Frage, ob man mit dieser Konstellation dann aber immer noch alle Schalterstellungen erreichen kann, steht und fällt mit der $\begin{eqnarray*} \mathbb{F}_2 \end{eqnarray*}$ -Invertierbarkeit von $\begin{eqnarray*} T \end{eqnarray*}$ .

Ist $\begin{eqnarray*} T \end{eqnarray*}$ jedoch nicht invertierbar, dann wird man ausgehend von einer vorgefundenen Konstellation nur noch einen Bruchteil der 128 Schalterstellungen erreichen, d.h., nur noch $\begin{eqnarray*} 2^m \end{eqnarray*}$ Schalterstellungen mit $\begin{eqnarray*} m\leq 6 \end{eqnarray*}$ . Dabei ist $\begin{eqnarray*} m \end{eqnarray*}$ der Rang von $\begin{eqnarray*} T \end{eqnarray*}$ .

Extrembeispiel: Jeder Schalter kippt immer auch mit alle anderen Schalter um. Dann ist $\begin{eqnarray*} T \end{eqnarray*}$ die 1-Matrix sowie $\begin{eqnarray*} m=1 \end{eqnarray*}$ , d.h., gibt es nur noch $\begin{eqnarray*} 2^1=2 \end{eqnarray*}$ erreichbare Schalterstellungen: Die Ausgangsstellung (welche immer das auch ist) sowie deren invertierte.

03.05.2020, 18:30

PhyMaLehrer

Auf diesen Beitrag antworten »

Mein elektronisches Spiel "7Schalter" ist fertig smile

smile

Hier kann man es sehen: 7Schalter-Video
Die Schaltreihenfolge ist sicher optimierungswürdig... Big Laugh

Big Laugh

03.05.2020, 22:53

Leopold

Auf diesen Beitrag antworten »

Leider sehe ich nur dieses:

[attach]51151[/attach]

Ich selber habe eine digitale Version als .exe-Datei mit Lazarus erstellt. Ich würde sie gerne hier hochladen. Sie ist aber zu groß (als .zip-Datei 932 KB). Weiß jemand, was ich tun kann?

04.05.2020, 07:38

PhyMaLehrer

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Leider sehe ich nur dieses:

Das ist sehr schade... Ich sehe das Video natürlich. Mal sehen, ob ich das private Video vergesellschaften kann. Für's erste hier ein Bild:

04.05.2020, 08:33

PhyMaLehrer

Auf diesen Beitrag antworten »

Das Video sollte jetzt sichtbar sein.

04.05.2020, 09:19

Gualtiero

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Ich würde sie gerne hier hochladen. Sie ist aber zu groß (als .zip-Datei 932 KB). Weiß jemand, was ich tun kann?

Ich würde die Frage unter Fragen zum MatheBoard & click for knowledge stellen, da sehen sie die Organisatoren bzw. Thomas am schnellsten.
Aber bei .exe-Dateien bin ich mir nicht sicher . . .

@PhyMaLehrer
Sehr schön, hab das Video gesehen. Freude

Freude

Und hast Du schon einen Elektronikkonzern gefunden, um über Produktion, Vertrieb und Preis zu verhandeln? Augenzwinkern

Augenzwinkern

04.05.2020, 09:41

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Gualtiero
@PhyMaLehrer
Sehr schön, hab das Video gesehen. Freude

Freude

Und hast Du schon einen Elektronikkonzern gefunden, um über Produktion, Vertrieb und Preis zu verhandeln? Augenzwinkern

Augenzwinkern

Ich stimme zu. Leider ist kein Ton dabei. Denn wenn alle Schalter leuchten, dann ertönt doch sicher eine Fanfare oder Hymne. "We are the champions." Augenzwinkern

Augenzwinkern

Zitat:

Original von Gualtiero
Aber bei .exe-Dateien bin ich mir nicht sicher . . .

Im Normalfall geht so etwas natürlich aus Sicherheitsgründen nicht. Aber vielleicht macht man bei jemandem, der in vier Jahren sein 20jähriges feiert, eine Ausnahme.

04.05.2020, 09:47

HAL 9000

Auf diesen Beitrag antworten »

So schön das haptische Erkunden dieses Problems auch sein mag - als selbsternannter Corona-Wächter (zu sowas sollen sich ja hierzulande immer mehr Leute berufen fühlen) sage ich: Nehmt sicherheitshalber lieber eine App (welche man zwar nicht einem Corona- aber anderen Virustest unterziehen möge). Lehrer

Lehrer

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »