WPC... geht weiter! -> wpc12

Jester

volkard schrieb:

sie sind genau dann reduzierbar, wenn die anzahl der bits an positionen (bei 1 beginnend), die nicht durch 3 teilbar sind, gerade ist, oder?

Ah, jetzt kommen die neuen Sachen... das hatte ich mir nicht mehr überlegt.

Btw.: Kann schon jemand was über die Anzahl der möglichen Lösungen aussagen? (mit Beweis )

volkard

d-f-g schrieb:

Wenn das stimmt, dann natürlich nur für die Bitketten der Länge 3n+2. Das überprüfe ich morgen. Bin jetzt zu müde.

es sagt aber auch voraus, welcher der beiden linearen läufe bei 3n+1 zum ziel führen wird. danach suchten wird doch?

mir schwant fast, daß man die beiden pseudobits jenseits des randes miteinrechnen darf und ein muster geht genau nach obiger regel auf.

allerdings ist bei 3*n sowas zu sehen
(p==pseudobit, *==beliebiges bit, -==irrelevantes bit)
-|* * -|p

bei 3*n+1 sowas
-|* * - *|p

bei 3*n+2 sowas
-|* * - * *|-

also bei 3*n und 3n+1 kann man stets die parität selber bestimmen, weil das linke pseudobit bei der zählung irrelevant ist aber das rechte relevant ist. aber bei 3*n+2 ist man in den popo ekniffen, weil beide pseudobis irrelevant sind. dann geht's halt auf oder nicht.

und ich sehe leider keinen ansatz, im vorhinein zu sehen, welche der beiden folgen bei 3*n+2 die kürzere ist.

noch ne frage: die schalter, die zu den relevanten bitpositionen gehören, sind ja so verteilt, daß genau entweder zur einen oder zur anderen lösung gehören. gibt es aussagen über die schalter an den irrelevanten bitpositionen (vor allem: schalten sie dort schlicht abwechselnd?). das würde nämlich erlauben, wenn man die schalteranzahl einer lösung hat, die schalteranzahl der gegenlösung zu bestimmen.

volkard

Jester schrieb:

Btw.: Kann schon jemand was über die Anzahl der möglichen Lösungen aussagen? (mit Beweis )

keine beweise. aber die these von

TomasRiker schrieb:

Wenn die Zeichenkettenlänge 3*n+2 ist, dann gibt es entweder zwei Lösungen oder keine. Der Umkehrschluss (Wenn die Zeichenlänge nicht 3*n+2 ist, dann gibt es immer genau eine Lösung) scheint auch zu stimmen.

unterstütze ich.

Sgt. Nukem

-h

volkard

auch mal was begründen:
auf das muster --**-... (bit, bit, irrelevantes bit, bit, bit, irrelevantes bit, ...)
kam ich, als ich mal untersuchte, was eigentlich genau der unerschied zwischen
0|* * * * ... (pseudobit links ist 0 und dann irgendwas)
und
1| * * * *... (pseudobit links ist 1 und dann irgendwas)
ist.

also um das linke pseudobit durch die ganze reihe zu jagen, muß man die schalter an folgenden positionen drücken:
|1 1 0 1 1 0 ...

damit erklärt sich, daß wenn es bei 3*n+2 zwei lösungen gibt, sich genau an diesen schalterpositionen unterscheiden, denn sie unterscheiden sich ja nur am linken pseudobit.

jetzt könnte man eigenrlich noch schauen, wo das pseudobit am ende landet, also wie das muster am rechnetn ende aussieht. ich vermute, bei 3*n+2 kommt immer am ende ...0 0 0 1 1|0 also ...0 0 0 0 0|1 heraus. also lösbarkeitsirrelevant und paritätsirrelevant.
und bei 3*n+1 wohl immer ...0 0 1 0|0 und bei 3*n immer ...0 0 0 1|0.
klingt fast so, als könnte man sich ne vollstände induktion anziehen und parität und lösbarkeit bewiesen gleichsetzen.

<nachtrag>
mal nochmal 3n+1 angucken.
aus
1|0 0 0...0 0 0|0
wird
-|* * -...* - *|* //relevanz
0|0 0 0...0 1 0|0
und wird
0|0 0 0...0 0 1|1
dabei für die parität egal, wieviele schalter zwischenzeitlich gedrückt wurde. jeder schalter kann nur genau zwei paritärtrelevante lampen umschalten, also ist jeder schalter paritätsirrelevant.
es zeigt sich, daß bei 3n+1 ein durchschieben des pseudobits einen paritätswechsel im kern erzeugt. oder mit einrechnung des nicht irrelevanten rechten pseudobuts zeigt sich eh, daß die parität immer unverändert bleibt.
</nachtrag>

falls das funktioniert, steht "eine lichterkette ist genau dann lösbar, wenn an den positionen 3*n+2 (zählbeginn bei 0) (inclusive der beiden pseudobits) eine gerade anzahl von lichtern brennen" wohl als hauptsatz der lichterketten da. mir scheint, von ihm aus sind faszinierend viele beweise trivial.

beweis für hauptsatz geht wohl so:
jeder schalter ist paritätsirrelevant.

von da aus zu beweisen, daß man für 3*n und 3*n+1 immer eine lösung findet, ist trivial. und zu beweisen, daß es für 3*n+2 nicht immer klappt, isses auch.

Jester schrieb:

Ich hab mich zumindest redlich bemüht eine Aufgabe zu finden, die in ein paar (wenigen) Stunden lösbar ist.

rofl.
*nochmal so durch den Thread querles*

Ponto

Ich hätte nicht gedacht, dass es algorithmisch schneller geht, aber Volkards Ausführungen machen das Ding hier noch 30-40% schneller. Nun ist auch meine Version mit kleinem konstanten Overhead auch schneller als die, welche mehr Speicher spendiert.

volkard

wirklich spannend ist, was die leute, die hier tricks veröffentlichen, in der hinterhand haben. man macht sich ja keine medallie kaputt, indem man einen trick verrät, den man nicht schon als nicht so wichtig abgetan hat.

Jester

Optimizer schrieb:

Jester schrieb:

Ich hab mich zumindest redlich bemüht eine Aufgabe zu finden, die in ein paar (wenigen) Stunden lösbar ist.

rofl.
*nochmal so durch den Thread querles*

ich hab nicht behauptet, daß man in wenigen Stunden ne optimale Lösung findet. Die erste Lösung ging aber noch Freitag abend (oder war's Samstag?) ein.

Jester

Bin aber echt gespannt, was so an Einsendungen kommt! Schätze mal es wird mindestens ne knappe Entscheidung.

Ponto

volkard schrieb:

wirklich spannend ist, was die leute, die hier tricks veröffentlichen, in der hinterhand haben. man macht sich ja keine medallie kaputt, indem man einen trick verrät, den man nicht schon als nicht so wichtig abgetan hat.

Man kann auch versuchen durch mathematische Argumentationen und das Aufstellen von Sätzen potentielle Mitbewerber von vornerein abzuschrecken.

Michael E.

Ponto: Das klappt bei mir ziemlich gut

Ponto

Michael E. schrieb:

Ponto: Das klappt bei mir ziemlich gut

Dann lass dir gesagt sein, dass man das meiste hier mathematisch Gesagte nicht für eine schnelle Lösung gebrauchen kann. Man kann auf einen linearen Algorithmus kommen, ohne das alles zu kennen. Ich glaube es kommen alle im Endeffekt auf äquivalente lineare Algorithmen, und nur die Güte der Implementierung wird über den Gewinner entscheiden. Schneller als linear kann man nicht werden, da alle Eingabebits gelesen werden müssen.

Hattest du nicht am Anfang schon etwas schnelles?

Jester

Sehe ich genauso. Die mathematische Untersuchung macht einfach Spaß und hilft das Problem *vollständig* zu begreifen. Dazu gehört natürlich auch eine Klassifikation aller möglichen Situationen nach handlichen Kriterien, Eindeutigkeitsbeweise für Lösungen etc.

Zum implementieren kann man nur einen kleinen Teil der Resultate brauchen. Macht aber nix. Geht ja um's Lernen.

Jester

und weg

Ponto

Jester schrieb:

Da ihr inwzischen schon fast alles beweisen konntet was ich auch hab verrate ich mal meinen Beweisansatz. Vielleicht kriegt ihr damit noch mehr raus.

Wir haben ja bei d-f-g gesehen, daß es reicht Lampen ausschalten zu können.
Also kann ich das ganze als Z/2Z-Vektorraum auffassen. Als Erzeugenden-System nehme ich die Bitvektoren die durch das anschalten einer einzelnen Lampe entstehen:
110....0
1110...0
01110..0
   .
   .
   .
0..01110
0...0111
0.000011
sind das. (ist egal ob ihr's waagrecht oder senkrecht lest).
Eine Lichterkette komplett auszuschalten ist sozusagen eine Lösung des inhom. LGS A*x=b mit dieser Matrix als A und der geg. Lichterkette als b.

Jetzt sind viele Aussagen leicht: Bei 3*n oder 3*n+1 geht's immer haben wir. Dann sagt uns das: die Matrix muß wohl invertierbar sein => Eindeutigkeit der Lösung.

Wenn man weiß, daß diese Matrix immer mindestens Rang n-1 hat, daß es maximal zwei Lösungen gibt. Außerdem kennen wir die Struktur der Lösung:

inhom. Lösung = spezielle Lösung + c*homogene Lösung. Achtung c ist nur 0 oder 1, da wir uns Z/2Z befinden. Die homogene Lösung habt ihr ja auch schon gefunden...

MfG Jester

Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat.

volkard

Ponto schrieb:

Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat.

haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet?

Jester

Ponto schrieb:

Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat.

Ups, aber wie kann das denn sein?

Ich meine, ich habe überhaupt nichts neues geliefert. Keine neue Aussage, nur einen Beweis für die Eindeutigkeit der Lösung, die war aber schon vor einigen Seiten postuliert.

Hilft's was wenn ich editiere?

Ponto

Jester schrieb:

Ponto schrieb:

Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat.

Ups, aber wie kann das denn sein?

Ich meine, ich habe überhaupt nichts neues geliefert. Keine neue Aussage, nur einen Beweis für die Eindeutigkeit der Lösung, die war aber schon vor einigen Seiten postuliert.

Hilft's was wenn ich editiere?

Lass es so wie es ist.

d-f-g

volkard schrieb:

Ponto schrieb:

Super, damit hab ich nichts mehr in der Hinterhand, wie es Volkard gesagt hat.

haben jetzt alle den spaß verloren und ich bin der einzigste, der einsendet?

Nene, ich habe da noch ein paar Tricks

WPC... geht weiter! -&gt; wpc12

WPC... geht weiter! -> wpc12