Schalter-Rätsel

[Jockelx]

Der Thread mit den Wahrscheinlichkeiten hat mich an ein altes Rätsel erinnert, was ich damals ganz nett fand (da einfach zu verstehen aber nicht einfach zu lösen).
Also, wer auch gerne rätselt:

Man hat vor sich 9 Schalter die an oder aus (0 oder 1) sein können. Von diesen 9 Schaltern sind aber nur 3 relevant; welche das sind ist unbekannt.
Also z.B. machen diese Schalter ein Licht an, aber nur 3 dieser Schalter sind überhaupt irgendwo angeschlossen und nur eine bestimmte Kombination dieser 3 Schalter macht das Licht an.
Und jetzt die naheliegende Frage:

Wieviele Kombinationen muss man höchstens ausprobieren, um die korrekte Kombination zu finden?

Viel spass!

[empgodot]

*rat* 24

[Jockelx]

Du nimmst RÄtsel raten zu wörtlich
24 ist falsch.

[Christoph]

Mit 18 sollte es gehen, wenn eine einzelne 1 bzw. einzelne 0 durchwandern lässt. Ich konnte aber bisher noch nicht beweisen, dass es mit weniger Kombinationen nicht geht. Zum Brute-Forcen aller 17-Kombinations-Möglichkeiten auf meinem PC gibt es etwas zu viele davon, da müsste ein besserer Beweis her.

Interessantes Rätsel, würde mich interessieren, ob es einen eleganten Beweis gibt, dass die richtige Antwort wirklich optimal ist.

[Jockelx]

Cool! Die 18 kam fix.
Die ist aber mit einem ähnlichen Ansatz noch zu toppen!

[SeppJ]

Ich sage 47.

edit: Was, 18? Da ist meine Vorgehensweise wohl doch suboptimal.
edit2: Na klar, 18! Ich bin ja so blind... Jetzt muss ich über die verbesserte Version nachdenken.

[lustig]

Hmm, ich biete 17 ;). Den letzten muss man nicht mehr probieren, wenn die ersten 17 Versuche nichts waren.

[volkard]

Habt Ihr bei 17, 18 und 47 auch "und nur eine bestimmte Kombination dieser 3 Schalter macht das Licht an" eingebaut oder überlesen?

[lustig]

Edit: Kein neuer Vorschlag, sondern eine Erklaerung

18: Du laesst zuerst eine eins durchwandern, danach eine 0.

Eins durchwandern: Du deckst folgende Kombinationen ab:
000 (eins nicht auf einem der 3 richtigen Schalter)
100
010
001

Null durchwandern:
111 (null auf keinem der richtigen Schalter)
011
101
110

=> Du hast alle Kombinationen abgedeckt. Irgendwann geht das Licht an

[volkard]

Danke, mir geht ein Licht auf.

[SeppJ]

SPOILER

volkard schrieb:

Habt Ihr bei 17, 18 und 47 auch "und nur eine bestimmte Kombination dieser 3 Schalter macht das Licht an" eingebaut oder überlesen?

Ja, das ist eingebaut: Der Trick bei der 18 ist:
Es gibt nur 4 mögliche Kombinationen: Alle drei Schalter müssen an sein, Zwei müssen an, einer aus sein, alle bis auf einen müssen aus sein, alle müssen aus sein.
Wir wollen nur das Licht anmachen, wir wollen nicht rausfinden, welche Schlater richtig sind.
Die Fälle alle drei aus und alle 3 an, kann man abdecken indem man einmal alle an und einmal alle aus macht - > 2 Kombinationen
Den Fall, dass einer an sein muss und die anderen beiden aus, erwischt man auf jeden Fall, indem man alle aus mach und dann alle 9 Schalter einzeln ausprobiert -> 9 Fälle
Umgekehrt erwischt man den Fall in dem genau einer aus sein muss -> 9 Fälle
höchstens 20 Kombinationen

Irgendwie habe ich mich entweder jetzt oder heute Nachmittag verzählt. Aber das ist zumindest die Idee.

edit: Ach ja, hatte vergessen, dass man 000 und 111 bei den anderen mit erledigt.
Und ich schreibe viel zu langsam...

[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.

[shisha]

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?

[sfdljksfdljk]

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):

000
011
101
110

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;
}