Unlogische Lichterkette

19.06.2024, 14:16

Dopap

Unlogische Lichterkette

Meine Enkelin hat eine digitale Lichtertkette aus China. Eigentlich sollte die komplett an
oder ausgehen wenn irgendeine Lampe gedrückt wird.
Fehlerhaft wird das logische NOT nicht auch an sich selbst gesendet.
So wird z.B. aus (0hell, 8dunkel ) (7h,1d).

Inzwischen kann ich meiner Enkelin helfen und finde konstruktiv den Weg aus
jedem der 9 möglichen Zustände zu (8h,0d) oder (0h,8d).

Allerdings stellte sich mir beim Betrachten Ihrer rein zufälligen Drückerei umgehend (!)
die Frage nach der mittleren Anzahl an Versuchen um z.B. von ganz dunkel nach ganz hell zu gelangen.
Der TR ist hier bei einer Simulation besonders langsam, teilweise gehen die seltenen Versuche
in die Hunderte oder mehr.

Idee: sieht mMn wie markovschen ketten aus,
geht da mathematisch was?

Warum fruchten meine Bemühungen bei einer ungeraden
Anzahl von Lämpchen nicht?

19.06.2024, 14:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
geht da mathematisch was?

Womöglich ja, sofern vorher eine Beschreibung der Situation erfolgt, die man auch wirklich verstehen kann und nicht so viel Raum für Spekulation offen hält wie die obige.

19.06.2024, 15:31

Steffen Bühler

Auf diesen Beitrag antworten »

Zum Beispiel: Alle sind aus, sie drückt Nummer 4, alle gehen an außer 4.

Nun drückt sie Nummer 5, alle gehen aus außer 5, die bleibt an und 4, die war ja aus und geht jetzt an.

Und so weiter. Ein Brute-Force-Programm zeigt bei willkürlichem Drücken eine durchschnittliche Dauer von etwas mehr als 300 Versuchen von "alle aus" zu "alle an" bei 8 LEDs, etwa 84 bei 6 LEDs, etwa 21 bei 4 LEDs und etwa 4 bei 2 LEDs.

Und tatsächlich schafft man es bei einer ungeraden Anzahl nie.

Viele Grüße
Steffen

19.06.2024, 19:01

Luftikus

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Dopap
geht da mathematisch was?

Womöglich ja, sofern vorher eine Beschreibung der Situation erfolgt, die man auch wirklich verstehen kann und nicht so viel Raum für Spekulation offen hält wie die obige.

Offenbar ist die Regel:
Die Nummer, die gedrückt wird, ändert sich nicht, die anderen werden invertiert; was an ist, geht aus, was aus ist, geht an..?!

19.06.2024, 19:39

HAL 9000

Auf diesen Beitrag antworten »

Na das ist doch relativ einfach überblickbar:

1) Die Schaltvorgänge sind kommutativ, d.h. jede Änderung der Reihenfolge der gedrückten Lampen bringt dasselbe Leuchtergebnis.

2) Zweimal dieselbe Lampe zu drücken ergibt wieder die Ausgangssituation. Also genügt es Vorgänge zu betrachten, wo jede Lampe maximal einmal gedrückt wird.

3) Bei gerader Anzahl an Schaltvorgängen sind genau die gedrückten Lampen an, bei ungerader Anzahl das Inverse davon.

Wenn man also alle Lampen anschalten will, dann geschieht das

a) bei gerader Gesamtlampenzahl, wenn man jede Lampe genau einmal drückt, und

b) bei ungerader Gesamtlampenzahl nie. In diesem Fall kann man sich zudem überlegen, dass die Anzahl der leuchtenden Lampen stets gerade ist, egal was man drückt.

Zitat:

Original von Dopap
Inzwischen kann ich meiner Enkelin helfen und finde konstruktiv den Weg aus jedem der 9 möglichen Zustände zu (8h,0d)

Ja, das geht mit einer einfachen Regel, die natürlich (s.o.) nur bei gerader Gesamtlampenanzahl greift:
- Ist die Anzahl der hellen Lampen gerade, dann drückt man eine der dunklen Lampen.
- Ist die Anzahl der hellen Lampen ungerade, dann drückt man eine der hellen Lampen.
Da die Paritäten der Anzahlen heller bzw. dunkler Lampen zu jedem Zeitpunkt übereinstimmen, kann man diese Fallunterscheidung alternativ auch an der Anzahl dunkler Lampen festmachen.

EDIT: Achso, du willst durch wild zufälliges Drücken zum Ziel kommen? Das erinnert mich an die Aufgabe mit dem Nachtwächter, der in seinem Schlüsselbund den richtigen Schlüssel für eine bestimmte Tür sucht:

i) Ist er nüchtern, geht er einen Schlüssel nach dem anderen durch, also achtet drauf keinen mehrfach zu probieren.

ii) Ist er besoffen, dann wählt er bei jedem Probierversuch zufällig einen der verfügbaren Schlüssel aus, ohne Beachtung dessen, ob der schonmal probiert wurde. Augenzwinkern

Zitat:

Original von Dopap
teilweise gehen die seltenen Versuche in die Hunderte oder mehr.

Wundert mich nicht: Bei 8 Lampen und zufälligem Drücken ist der Erwartungswert der Schaltanzahl bis alle Lampen an sind gleich $\begin{eqnarray*} \frac{32768}{105}\approx 312 \end{eqnarray*}$ .

--------------------------------------------------------------------------------------------------------

Zur Berechnung: Wir gehen mal von einer Lichterkette mit genau $\begin{eqnarray*} n \end{eqnarray*}$ Lampen aus. Betrachten wir das ganze zunächst OHNE die Negation, d.h., wenn jeder Tastendruck auf eine Lampe genau diese umschaltet und die anderen in Ruhe lässt. Zustand $\begin{eqnarray*} k \end{eqnarray*}$ bedeute, dass genau $\begin{eqnarray*} k \end{eqnarray*}$ Lampen an sind (also $\begin{eqnarray*} k=0,1,\ldots,n \end{eqnarray*}$ ). Bei rein zufälliger Schalterei ist das ganze dann eine Markov-Kette mit $\begin{eqnarray*} p_{k,k-1} = \frac{k}{n} \end{eqnarray*}$ ( $\begin{eqnarray*} k=1,\ldots,n \end{eqnarray*}$ ) und $\begin{eqnarray*} p_{k,k+1} = \frac{n-k}{n} \end{eqnarray*}$ ( $\begin{eqnarray*} k=0,\ldots,n-1 \end{eqnarray*}$ ). Für

$\begin{eqnarray*} m_k \end{eqnarray*}$ ... mittlere Anzahl Schaltvorgänge bis zum ersten Erreichen von Zustand $\begin{eqnarray*} n \end{eqnarray*}$ , ausgehend von Zustand $\begin{eqnarray*} k \end{eqnarray*}$

bekommt man folgendes Gleichungssystem:

$\begin{eqnarray*} m_0 = 1+m_1 \end{eqnarray*}$

$\begin{eqnarray*} m_k = 1 + \frac{km_{k-1}+(n-k)m_{k+1}}{n} \end{eqnarray*}$ für $\begin{eqnarray*} k=1,\ldots,n-1 \end{eqnarray*}$

$\begin{eqnarray*} m_n = 0 \end{eqnarray*}$ .

Letzten Endes suchen wir natürlich $\begin{eqnarray*} m_0 \end{eqnarray*}$ , welches übrigens im Fall gerader $\begin{eqnarray*} n \end{eqnarray*}$ auch genau jener mittleren Schaltanzahl in deinem Probem mit Negation entspricht (siehe obige Anmerkung 3).

Eine explizite Darstellung von $\begin{eqnarray*} m_0 \end{eqnarray*}$ als Funktion von $\begin{eqnarray*} n \end{eqnarray*}$ konnte ich nicht erkennen. Allerdings ist $\begin{eqnarray*} m_{n-1} = 2^n-1 \end{eqnarray*}$ , so dass man über die obige Rekursion

$\begin{eqnarray*} m_{k-1} = \frac{n\left(m_k-1\right)-(n-k)m_{k+1}}{k} \end{eqnarray*}$ sukzessive für $\begin{eqnarray*} k=n-1,n-2,\ldots,1 \end{eqnarray*}$

damit rasch den gesuchten Wert $\begin{eqnarray*} m_0 \end{eqnarray*}$ berechnen kann.

20.06.2024, 07:49

Steffen Bühler

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Eine explizite Darstellung von $\begin{eqnarray*} m_0 \end{eqnarray*}$ als Funktion von $\begin{eqnarray*} n \end{eqnarray*}$ konnte ich nicht erkennen.

Ich hab mal bis n=16 die Werte bestimmt - es scheint ein exponentieller Zusammenhang zu sein:

[attach]57849[/attach]

20.06.2024, 08:11

HAL 9000

Auf diesen Beitrag antworten »

"Ungefähr" mag das stimmen. Ich meinte selbstredend eine exakte Formel. Augenzwinkern

Hab etwas weiter gerechnet (bis n=1000) und festgestellt, dass wohl sogar $\begin{eqnarray*} m_0(n) = 2^n\cdot f(n) \end{eqnarray*}$ mit einer (ab $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ ) monoton gegen 1 fallenden Funktion $\begin{eqnarray*} f \end{eqnarray*}$ gilt.

In erster Näherung scheint $\begin{eqnarray*} m_0(n) \approx 2^n \cdot e^{\frac{1}{n}} \end{eqnarray*}$ für große $\begin{eqnarray*} n \end{eqnarray*}$ zu gelten.

20.06.2024, 15:58

Dopap

Auf diesen Beitrag antworten »

Jede Fragen ausreichend ( und mehr ) beantwortet!

Danke an Alle für die posts.

20.06.2024, 16:22

HAL 9000

Auf diesen Beitrag antworten »

Ein wenig vom Thema entfernt:

Die obige Rekursion ist übrigens numerisch ganz interessant, wenn man sie (wie ich oben ja auch) für große $\begin{eqnarray*} n \end{eqnarray*}$ ausführen will:

Ab ca. n=50 wird es von der Genauigkeit her bedenklich (mehr als 1% Fehler), und bereits für n=60 bekommt man ein negatives (!) $\begin{eqnarray*} m_0 \end{eqnarray*}$ - wohlgemerkt wenn man die Rekursion mit den üblichen 64Bit-Fließkommazahlen "double" durchführen will.

Ausweg: Durch Einsetzen von Ansatz $\begin{eqnarray*} m_k := \frac{k!}{(n-1)!}\cdot a_k \end{eqnarray*}$ in die Rekursion und etwas umformen bekommt man

$\begin{eqnarray*} a_{k-1} = n a_k - (n-k)(k+1) a_{k+1} - \frac{n!}{k!} \end{eqnarray*}$ mit $\begin{eqnarray*} a_n=0 \end{eqnarray*}$ sowie $\begin{eqnarray*} a_{n-1} = 2^n-1 \end{eqnarray*}$ ,

d.h. alle $\begin{eqnarray*} a_k \end{eqnarray*}$ sind ganzzahlig. Rechnet man also mit deren Rekursion sowie beliebig genauen Zahlen (wie in Python möglich), so kann man die oben beobachteten double-Auslöschungseffekte umschiffen.

Ein gewisse Abschlusskontrolle für die Numerik ist die Berechnung von $\begin{eqnarray*} m_0-m_1 \end{eqnarray*}$ : Da muss (s.o.) theoretisch genau 1 herauskommen. Man schaue sich diesen Wert mal an in der double-Rekursionsroutine so ab etwa n=40 an... smile

Neue Frage »

Antworten »

Unlogische Lichterkette

Verwandte Themen