0
Erstmal das geht hier um Kombinatorik oder?
So sieht das Spiel aus:
Das ist die Spielanleitung:
Und nun verstehe ich nicht, wie soll man hier rechnen? 12 Uhr ist auf dem Spiel da vorne, wo der Pfeil am Anfang zeigt.
Hat jemand eine Idee bzw. ein Mathecrack?
Die Aufgabe ist von einem Informatikkurs, über künstliche Intelligenz
Also, was mir zumindest nun aufgefallen ist, da steht ja , bei wie vielen Möglichkeiten muss man sich beim schlimmsten Fall entscheiden, das sind ja 10 oder? Ganz am Anfang hat man ja 10 Möglichkeite.
Und zur zweiten Frage der a, wie viel Züge es dauert, bsi das Spiel zu ende geht, das ist ja 11 oder, das steht ja in der Anleitung?d
Und zur zweiten Frage der a, wie viel Züge es dauert, bsi das Spiel zu ende geht, das ist ja 11 oder, das steht ja in der Anleitung?d
Diese Frage melden
gefragt
dertommy
Punkte: 10
Punkte: 10
Die Bi9lder waren nicht verfügbar, habe es aktualisiert!
─
dertommy
09.09.2023 um 13:26
Ist Kombinatik, aber nicht nur. Bei dieser Aufgabe muss man mehrere Tricks verwenden.
12 Uhr ist im Bild oben, und da in der Mitte, also dort, wo der obere Pfeil ist.
Stell Dir vor, das Bild hängt an der Wand, wie eine Wanduhr also, und die Löcher sind wie die Ziffern dieser Wanduhr durchnummeriert.
Am Anfang hat man 11 Möglichkeiten - jeweils eine für jedes freie Loch.
Ja, die Anzahl der Züge ist 11 - jeweils ein Zug für jedes freie Loch.
Hinweis zu b)
Man muss ja nacheinander alle 11 Löcher füllen.
Wenn man immer im Uhrzeigersinn dreht, muss man, um das Loch auf k Uhr zu füllen, k Positionen weiter drehen.
Um wieviele Positionen hat man dann insgesamt im Uhrzeigersinn weitergedreht?
Für allgemeine n muss man https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Summenformel verwenden.
─ m.simon.539 09.09.2023 um 14:22
12 Uhr ist im Bild oben, und da in der Mitte, also dort, wo der obere Pfeil ist.
Stell Dir vor, das Bild hängt an der Wand, wie eine Wanduhr also, und die Löcher sind wie die Ziffern dieser Wanduhr durchnummeriert.
Am Anfang hat man 11 Möglichkeiten - jeweils eine für jedes freie Loch.
Ja, die Anzahl der Züge ist 11 - jeweils ein Zug für jedes freie Loch.
Hinweis zu b)
Man muss ja nacheinander alle 11 Löcher füllen.
Wenn man immer im Uhrzeigersinn dreht, muss man, um das Loch auf k Uhr zu füllen, k Positionen weiter drehen.
Um wieviele Positionen hat man dann insgesamt im Uhrzeigersinn weitergedreht?
Für allgemeine n muss man https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Summenformel verwenden.
─ m.simon.539 09.09.2023 um 14:22
Danke, a also die a) besteht ja aus 3 Fragen:
die erste Frage: "Zwichen wie vielen Möglichkeiten muss man beim schlimmsten Fall sich bei einem Zug entscheiden" Hier wäre die Lösung 10 dann?
Zweite Frage: "Wie lange dauert es (Anzahl der Züge) bis das Spiel zu Ende ist?" Hier wäre die Antwort 11 oder?
Und die dritte Frage muss ich noch herausfinden, also die Lösung dazu, aber sind die ersten beiden korrekt?
Und bezüglich der 3 Frage der a):
"Wie lange dauert es alle Möglichkeiten auszuprobieren, wenn man pro Sekunde 1000 Züge ausprobieren kann."
DAfür muss ich ja alle Möglichkeiten bestimmen, ist das soweit korrekt?:
beim ersten Zug habe ich 10 verschiedene Möglichkeiten,
beim zweiten Zug 9,
beim dritten Zug 8,
beim vierten 7,
beim fünften 6,
beim sechsten 5,
beim siebten 4,
beim achten 3,
beim neunten 2,
beim zehnten 1
und beim elften Zug 0 oder wie kann man den elften Zug verstehen?
Und von diesen abnehmenden Möglichkeiten pro Zug muss man dann die verschiedenen Kombinationen bestimmen? Wenn ja, was hat das mit einer oberen Schranke zutun, wozu das?
─ dertommy 09.09.2023 um 14:30
die erste Frage: "Zwichen wie vielen Möglichkeiten muss man beim schlimmsten Fall sich bei einem Zug entscheiden" Hier wäre die Lösung 10 dann?
Zweite Frage: "Wie lange dauert es (Anzahl der Züge) bis das Spiel zu Ende ist?" Hier wäre die Antwort 11 oder?
Und die dritte Frage muss ich noch herausfinden, also die Lösung dazu, aber sind die ersten beiden korrekt?
Und bezüglich der 3 Frage der a):
"Wie lange dauert es alle Möglichkeiten auszuprobieren, wenn man pro Sekunde 1000 Züge ausprobieren kann."
DAfür muss ich ja alle Möglichkeiten bestimmen, ist das soweit korrekt?:
beim ersten Zug habe ich 10 verschiedene Möglichkeiten,
beim zweiten Zug 9,
beim dritten Zug 8,
beim vierten 7,
beim fünften 6,
beim sechsten 5,
beim siebten 4,
beim achten 3,
beim neunten 2,
beim zehnten 1
und beim elften Zug 0 oder wie kann man den elften Zug verstehen?
Und von diesen abnehmenden Möglichkeiten pro Zug muss man dann die verschiedenen Kombinationen bestimmen? Wenn ja, was hat das mit einer oberen Schranke zutun, wozu das?
─ dertommy 09.09.2023 um 14:30
Nee, beim ersten Zug hast Du 11 Möglichkeiten, nicht 10.
Beim 2. Zug hast Du maximal 10 Möglichkeiten.
....
Beim 11. und letzten Zug hast Du maximal 1 Möglichkeit.
Und ja, von diesen abnehmenden Möglichkeiten pro Zug muss man dann die verschiedenen Kombinationen bestimmen! Und das ist dann eine obere Schranke.
.
─ m.simon.539 09.09.2023 um 19:18
Beim 2. Zug hast Du maximal 10 Möglichkeiten.
....
Beim 11. und letzten Zug hast Du maximal 1 Möglichkeit.
Und ja, von diesen abnehmenden Möglichkeiten pro Zug muss man dann die verschiedenen Kombinationen bestimmen! Und das ist dann eine obere Schranke.
.
─ m.simon.539 09.09.2023 um 19:18
Aber warum habe ich 11 Möglichkeiten, bei der a) gibt es ja auch die Frage:
"Zwichen wie vielen Möglichkeiten muss man beim schlimmsten Fall sich bei einem Zug entscheiden" Ich dachte hier wäre die Lösung 10, das würde aber wiederum heißen, dass ich ja maximal 10 Möglichkeiten beim ersten Zug habe?
─ dertommy 09.09.2023 um 19:24
"Zwichen wie vielen Möglichkeiten muss man beim schlimmsten Fall sich bei einem Zug entscheiden" Ich dachte hier wäre die Lösung 10, das würde aber wiederum heißen, dass ich ja maximal 10 Möglichkeiten beim ersten Zug habe?
─ dertommy 09.09.2023 um 19:24
Im originalen RR-Spiel hat man anfangs 10 Möglichkeiten. In der Variante - also ohne weißem Stift - 11. Und in der Aufgabe geht es ausschließlich um diese Variante.
─
m.simon.539
10.09.2023 um 01:10
Danke, aber wozu eine obere Schranke, die Möglichekiten wären ja einfach 11! für n=12 und für beliebiges n € |N, wäre es (n-1)!
Ich verstehe daher nicht, wozu man eine obere Schranke benötigt? ─ dertommy 10.09.2023 um 13:54
Ich verstehe daher nicht, wozu man eine obere Schranke benötigt? ─ dertommy 10.09.2023 um 13:54
Also, 11! und (n -1)! ist schon mal richtig.
Gute Frage.
Naja, wenn man eine obere Schranke hätte, die nicht allzu groß ist, dann hätte man eine Garantie, dass man immer in akzeptabler Zeit eine Lösung finden wird. Das wäre dann recht erfreulich.
Hier aber ist die obere Schranke, 11!, so groß, dass die Rechenzeit nur bedingt akzeptabel ist. Das soll wohl die Botschaft der Aufgabe sein: Bei kombinatorischen Problemen kann die Rechenzeit ins Unermessliche wachsen. Garantien, das ein Programm immer in akzeptabler Zeit fertig ist, kann man bei kombinatorischen Problemen selten geben.
Allerdings: 11! ist eben eine obere Schranke, die die tatsächliche Rechenzeit möglicherweise maßlos überschätzt, Es gibt berechtige Hoffnung, dass ein real existierendes Programm sehr viel schneller ist. Aber das ist dann eben nur Hoffnung, keine Gewissheit.
In meinem Programmierpraktikum - lang ist's her - ging es um Probleme der Graphentheorie. Das waren allesamt kombinatorische Probleme. Da fragte jemand, wie lang den unser Programm für eine Lösung maximal brauchen darf. Antwort des Dozenten: "Es gibt hier keine Obergrenze. Das sind kombinatorische Probleme. Das darf auch über 100 Jahre dauern." ─ m.simon.539 10.09.2023 um 19:46
Gute Frage.
Naja, wenn man eine obere Schranke hätte, die nicht allzu groß ist, dann hätte man eine Garantie, dass man immer in akzeptabler Zeit eine Lösung finden wird. Das wäre dann recht erfreulich.
Hier aber ist die obere Schranke, 11!, so groß, dass die Rechenzeit nur bedingt akzeptabel ist. Das soll wohl die Botschaft der Aufgabe sein: Bei kombinatorischen Problemen kann die Rechenzeit ins Unermessliche wachsen. Garantien, das ein Programm immer in akzeptabler Zeit fertig ist, kann man bei kombinatorischen Problemen selten geben.
Allerdings: 11! ist eben eine obere Schranke, die die tatsächliche Rechenzeit möglicherweise maßlos überschätzt, Es gibt berechtige Hoffnung, dass ein real existierendes Programm sehr viel schneller ist. Aber das ist dann eben nur Hoffnung, keine Gewissheit.
In meinem Programmierpraktikum - lang ist's her - ging es um Probleme der Graphentheorie. Das waren allesamt kombinatorische Probleme. Da fragte jemand, wie lang den unser Programm für eine Lösung maximal brauchen darf. Antwort des Dozenten: "Es gibt hier keine Obergrenze. Das sind kombinatorische Probleme. Das darf auch über 100 Jahre dauern." ─ m.simon.539 10.09.2023 um 19:46
Hast du ne Idee für den Beweis, da fällt mir ehrlich gesagt nichts ein?
─
dertommy
10.09.2023 um 22:27
Sowas kommt, wenn man anfängt und sich Gedanken macht. Spiel die Situation für kleine $n$ durch.
─
cauchy
10.09.2023 um 22:55
Ja, wie gesagt, man nimmt erstmal an: Es wird immer im Uhrzeigersinn weiter gedreht. Das ist keine Einschränkung, denn das Ergebnis einer Drehung gegen Uhrzeigersinn kann man immer durch eine passende Drehung im Uhrzeigersinn erreichen. Beispielsweise ist es egal, ob ich 3 Positionen gegen Uhrzeigersinn oder 9 Positionen im Uhrzeigersinn drehe.
Angenommen, man hätte das Rätsel gelöst. Man überlegt sich, um wieviel Positionen man denn nun weitergedreht hat.
Das kann man sich ausrechnen, ohne die Lösung zu kennen!
Bei n=12 sieht das so aus:
Als das Loch bei 1 Uhr gefüllt wurde, muss ich eine Position im Uhrzeigersinn weitergedreht haben.
Als das Loch bei 2 Uhr gefüllt wurde, muss ich 2 Positionen im Uhrzeigersinn weitergedreht haben.
...
Als das Loch bei 11 Uhr gefüllt wurde, muss ich 11 Positionen im Uhrzeigersinn weitergedreht haben.
Nun kann man sich ausrechnen, um wieviele Positionen im Uhrzeigersinn ich insgesamt weitergedreht habe.
Und damit kann man sich ausrechnen, wo der innere Pfeil dann steht.
─ m.simon.539 11.09.2023 um 00:29
Angenommen, man hätte das Rätsel gelöst. Man überlegt sich, um wieviel Positionen man denn nun weitergedreht hat.
Das kann man sich ausrechnen, ohne die Lösung zu kennen!
Bei n=12 sieht das so aus:
Als das Loch bei 1 Uhr gefüllt wurde, muss ich eine Position im Uhrzeigersinn weitergedreht haben.
Als das Loch bei 2 Uhr gefüllt wurde, muss ich 2 Positionen im Uhrzeigersinn weitergedreht haben.
...
Als das Loch bei 11 Uhr gefüllt wurde, muss ich 11 Positionen im Uhrzeigersinn weitergedreht haben.
Nun kann man sich ausrechnen, um wieviele Positionen im Uhrzeigersinn ich insgesamt weitergedreht habe.
Und damit kann man sich ausrechnen, wo der innere Pfeil dann steht.
─ m.simon.539 11.09.2023 um 00:29