Schalter-Rätsel

Jockelx

Ja, aber wie gesagt: Geht besser!

Und als Extra-Bonbon:
Es könnten auch mehr als 9 Schalter sein und man würde trotzdem mit weniger als 18 Kombinationen auskommen!

DerBaer

will ich jetzt die 3 Schalter finden oder nur das Licht ankriegen?

SeppJ

DerBaer schrieb:

will ich jetzt die 3 Schalter finden oder nur das Licht ankriegen?

Nur Licht anmachen.

Hmm, an dem Verfahren mit weniger als 18 Versuchen beiß ich mir immer noch die Zähne aus. Ich hatte etwas, dass durch geschickte geometrische Muster auf 16 kam, bis mir auffiel, dass ich damit 4 Kombinationen nicht abdeckte.

Und als Extra-Bonbon:
Es könnten auch mehr als 9 Schalter sein und man würde trotzdem mit weniger als 18 Kombinationen auskommen!

Wie viele mehr ginge denn?

Ja nu, was ist denn jetzt die lösung?

Mario Sandler

Ich denke es geht mit 8.
Es gibt bei 9 Schaltern 2^9 = 516 Kombinationen, davon sind 2^6 = 64 korrekte Schalterstellungen ( 3 Schalter fest und 6 Schalter beliebig ). Das bedeutet man hat im durschnitt 2^9 / 2^6 = 2^3 = 8: Alle 8 Kombinationen eine korrekte Lösung. Man sollte also eine Permutation finden die genau diese 8 Kombinationen enthält.
Von diesen Permutationen sollte es 2^6 Stück geben.

Jockelx

8 kann ich mir nicht vorstellen und ich verstehe deine Begründung auch nicht.
Ich bin mir ziemlich sicher, dass 16 die Untergrenze ist. Z.B. ist

0 0 0 0 0 0 0 1 0 
0 0 0 1 0 1 0 0 1 
0 0 1 0 1 1 0 1 1 
0 0 1 1 0 1 1 1 0 
0 0 1 1 1 0 0 0 0 
0 1 0 0 1 1 1 0 0 
0 1 0 1 1 0 1 1 1 
0 1 1 1 0 1 0 1 0 
1 0 0 0 1 0 1 0 1 
1 0 1 0 0 1 0 0 0 
1 0 1 1 0 0 0 1 1 
1 1 0 0 0 1 1 1 1 
1 1 0 0 1 0 0 0 1 
1 1 0 1 0 0 1 0 0 
1 1 1 0 1 0 1 1 0 
1 1 1 1 1 1 1 0 1

eine Lösung. Konstruieren kann man solche (offenbar nicht eindeutigen) Lösungen,
indem man alle Kombinationen der 3 Schalter 2x untereinander schreibt und dann
sukzessive neue Spalten konstruiert, indem man sich eine Spalte wegdenkt und
die neue Spalte wieder alle Kombinationen zulässt.
Dabei sieht man dann auch, dass es mehr als 9 Spalten sein können.

Mario Sandler

Nehmen wir mal an es sind nur 3 Schalter und nur 2 sind relevant:
Deine Konstruktion liefert dann eine Lösung mit 8 Stellungen.
Meine eine mit 4 (2^3/21):

Ich hab mal genauer darüber nachgedacht, und mein Lösungsweg funktioniert nicht immer. Aber den Beweis das 16 die untere Grenze ist will ich erst noch sehen.
Ich tüffel mal noch etwas an meinem Lösungsweg, für 9 Schalter ist er leider sehr schwer durchzuziehen.

Es sollte übrigens nur für 10 Schalter und 3 relevanten noch mit 16 Lösungen funktionieren (2^10/26 = 16). Für noch mehr Schalter ist das keinesfalls mehr möglich, da die Lösungen dann nicht dicht genug liegen.

//EDIT:
Ok, mein Lösungsweg funktioniert nicht mit so vielen Schaltern und so wenig
relevanten. Hat sich also erledigt

volkard

Jockelx schrieb:

Z.B. ist
0 0 0 0 0 0 0 1 0 
...
eine Lösung.

Sagt mein Testprogramm auch.

#include <iostream>

using namespace std;

char const* eingabe[]={
"0 0 0 0 0 0 0 1 0",
"0 0 0 1 0 1 0 0 1",
"0 0 1 0 1 1 0 1 1",
"0 0 1 1 0 1 1 1 0",
"0 0 1 1 1 0 0 0 0",
"0 1 0 0 1 1 1 0 0",
"0 1 0 1 1 0 1 1 1",
"0 1 1 1 0 1 0 1 0",
"1 0 0 0 1 0 1 0 1",
"1 0 1 0 0 1 0 0 0",
"1 0 1 1 0 0 0 1 1",
"1 1 0 0 0 1 1 1 1",
"1 1 0 0 1 0 0 0 1",
"1 1 0 1 0 0 1 0 0",
"1 1 1 0 1 0 1 1 0",
"1 1 1 1 1 1 1 0 1",
};

int const SPALTENANZAHL=9;

int main(){
	for(int a=0;a<SPALTENANZAHL;++a){
		for(int b=a+1;b<SPALTENANZAHL;++b){
			for(int c=b+1;c<SPALTENANZAHL;++c){
				bool gehabt[8]={};
				for(int i=0;i!=sizeof(eingabe)/sizeof(eingabe[0]);++i){
					int ba=eingabe[i][2*a]=='1';
					int bb=eingabe[i][2*b]=='1';
					int bc=eingabe[i][2*c]=='1';
					int b=ba*4+bb*2+bc;
					gehabt[b]=true;
				}
				for(int i=0;i<8;++i){
					if(!gehabt[b]){
						cout<<"fehler!\n";
						cout<<'\n';
					}
				}
			}
		}
	}
	return 0;
}

otze

ih bin eigentlich davon ausgegangen, dass das Resultat Zeilen wie

[0,0,1,0,0,1,0,0,1] (und 2 jeweils nach rechts rotierte Versionen)
[0,1,1,0,1,1,0,1,1] (same)

enthalten würde. das schöne an diesen beiden Typen ist, dass sie eine periodenlänge von 3 haben und verdammt viele Lösungen abdecken. Leider kam ich danach nicht weiter, wie weitere Zeilen aussehen müssten.