(Twitter)
0
Erstmal funktioniert die Strategie, für jedes mögliche Tripel ein Los zu kaufen, natürlich immer noch. Allerdings ist das wahnsinnig ineffizient: Erstens benutzen wir nur 3 der 6 Felder, die wie ankreuzen dürfen, zweitens verwenden wir nicht, dass der "Gegner" sogar 4 Zahlen auswählt.
Die eigentliche Frage ist also, was die minimale Anzahl an Losen ist, die man kaufen kann, sodass diese Eigenschaft noch gegeben ist. Das ist eine sehr interessante Frage, aber ich sehe kein unmittelbares Argument, wie man sie beantworten könnte. Trotzdem wollte ich mal eine Antwort schreiben, damit du nicht ganz leer ausgehst. Vielleicht hat aber auch jemand anderes noch einen schlauen Einfall. (Ich hab das Gefühl, dass man vielleicht eine Verbindung zu endlicher projektiver Geometrie ziehen könnte, aber so ganz hat das noch nicht funktioniert.)
Ein paar Gedanken hab ich mir gemacht: Die "triviale" Strategie von oben benötigt \(\binom{27}3=2925\) Lose. Auf einem Los sind \(\binom63=20\) Tripel. Wäre es also möglich, die Tripel perfekt auf die Lose zu verteilen, so dass jedes Tripel auf genau einem Los vorkommt, dann bräuchte man nur noch \(147\) Lose. Dadurch, dass man gar nicht alle Tripel braucht, könnte die Zahl sogar noch weiter runtergehen. Ich würde also erwarten, dass die optimale Lösung irgendwo zwischen \(100\) und \(150\) liegt.
Ich habe ein kurzes Computerprogramm geschrieben, das solche Lose zusammensetzt. Dabei habe ich keinen schlauen Algorithmus verwendet, sondern immer das nächstbeste Los genommen, das mir weiterhilft (ein sog. Greedy-Algorithmus). Der hat eine Menge von \(177\) Losen geliefert, ich kopier die Ausgabe mal unten rein. Das ist sicher nicht das Optimum, aber schon eine sehr gute Verbesserung zu den \(2925\) Losen am Anfang und auch nicht sehr weit von meiner Schätzung der optimalen Lösung entfernt.
Ich denke noch weiter drüber nach, vielleicht fällt mir ja noch was Schlaues dazu ein. Dann melde ich mich natürlich nochmal.
Hier also die 177 Lose, sodass für jedes Quadrupel von Zahlen aus 1-27 mindestens 1 Los mit diesem Quadrupel 3 Zahlen gemeinsam hat:
[[1,2,3,4,5,6],[1,2,7,8,9,10],[1,2,11,12,13,14],[1,2,15,16,17,18],[1,2,19,20,21,22],[1,2,23,24,25,26],[1,3,7,8,11,9],[1,3,10,12,15,13],[1,3,14,16,19,17],[1,3,18,20,23,21],[1,3,22,24,27,4],[1,4,7,8,12,9],[1,4,10,11,15,13],[1,4,14,16,20,17],[1,4,18,19,23,21],[1,5,7,8,13,9],[1,5,10,11,16,12],[1,5,14,15,19,17],[1,5,18,20,24,21],[1,5,22,23,27,6],[1,6,7,8,14,9],[1,6,10,11,17,12],[1,6,13,15,20,16],[1,6,18,19,24,21],[1,7,15,16,21,17],[1,7,18,19,25,20],[1,7,22,26,27,8],[1,8,15,16,23,17],[1,8,21,9,15,22],[1,9,16,17,24,18],[1,9,19,20,26,25],[1,10,14,18,22,19],[1,10,20,21,25,11],[1,11,18,19,27,12],[1,12,21,22,25,13],[1,13,17,18,26,14],[1,14,21,25,27,2],[2,3,7,8,12,9],[2,3,10,11,15,13],[2,3,14,16,20,17],[2,3,18,19,23,21],[2,3,22,26,27,4],[2,4,7,8,11,9],[2,4,10,12,15,13],[2,4,14,16,19,17],[2,4,18,20,23,21],[2,5,7,8,14,9],[2,5,10,11,17,12],[2,5,13,15,20,16],[2,5,18,19,24,21],[2,5,22,6,7,13],[2,6,8,9,15,10],[2,6,11,12,16,14],[2,6,17,18,25,19],[2,6,20,21,26,24],[2,7,15,16,23,17],[2,7,18,19,26,20],[2,7,24,8,13,17],[2,8,16,18,22,19],[2,8,20,23,27,9],[2,9,13,16,21,17],[2,9,22,10,14,23],[2,10,16,18,27,11],[2,11,22,12,20,25],[2,12,24,13,19,27],[2,14,15,22,24,3],[3,4,7,8,10,9],[3,4,11,12,14,13],[3,4,15,16,18,17],[3,4,19,20,25,5],[3,5,7,8,15,9],[3,5,10,11,18,12],[3,5,13,14,21,16],[3,5,17,23,24,6],[3,6,7,8,13,9],[3,6,10,11,19,12],[3,6,14,15,21,16],[3,6,18,20,22,25],[3,7,14,16,22,17],[3,7,18,19,24,20],[3,7,21,23,25,8],[3,8,14,16,24,17],[3,8,18,19,26,9],[3,9,14,16,23,17],[3,9,21,24,25,10],[3,10,14,16,26,17],[3,10,20,23,27,11],[3,11,16,17,21,24],[3,11,25,12,16,17],[3,12,20,21,26,22],[3,13,17,18,27,19],[3,13,22,23,26,15],[3,15,25,4,5,7],[4,5,8,9,16,10],[4,5,11,12,21,13],[4,5,14,17,22,18],[4,5,23,24,26,6],[4,6,7,8,17,9],[4,6,10,11,18,12],[4,6,13,14,25,15],[4,6,16,19,22,20],[4,6,21,7,13,16],[4,7,14,18,27,22],[4,8,13,14,21,15],[4,8,18,19,24,20],[4,8,22,25,26,9],[4,9,13,14,24,15],[4,9,19,21,27,10],[4,10,17,20,26,23],[4,11,16,17,27,19],[4,11,22,23,25,12],[4,12,16,17,24,19],[4,12,20,13,19,26],[4,13,23,15,20,27],[4,17,21,5,6,8],[5,6,9,10,14,11],[5,6,12,15,18,16],[5,7,10,11,19,12],[5,7,16,17,20,18],[5,7,21,24,27,8],[5,8,11,12,20,18],[5,8,19,9,12,22],[5,9,17,18,23,21],[5,9,25,26,27,10],[5,10,13,15,21,20],[5,10,22,11,15,24],[5,12,14,24,25,13],[5,13,19,14,20,23],[5,16,19,22,25,6],[6,7,10,11,15,12],[6,7,18,19,23,20],[6,7,24,25,26,8],[6,8,11,12,23,16],[6,8,18,19,27,9],[6,9,12,16,26,22],[6,9,23,10,13,16],[6,10,21,24,27,11],[6,11,13,12,20,27],[6,14,17,19,26,15],[7,9,16,20,21,22],[7,9,23,10,13,14],[7,10,16,17,25,18],[7,10,21,11,13,18],[7,11,14,16,26,23],[7,11,25,12,14,20],[7,12,16,17,26,22],[7,12,23,13,15,19],[7,13,25,14,19,21],[7,22,23,8,10,11],[8,10,12,13,19,14],[8,10,17,21,26,11],[8,11,13,14,27,15],[8,11,19,12,15,24],[8,12,17,25,27,13],[8,13,16,18,23,20],[8,14,18,20,22,15],[9,10,12,18,20,11],[9,11,13,15,16,17],[9,11,19,22,27,23],[9,11,24,12,14,21],[9,12,15,13,18,22],[9,14,18,15,23,25],[10,12,21,22,27,23],[10,12,24,13,17,22],[10,14,20,15,16,19],[10,15,17,18,26,23],[10,19,23,24,26,11],[11,13,25,15,20,26],[11,15,21,18,22,26],[11,18,24,12,14,26],[12,15,17,26,27,20],[12,20,23,13,16,22],[13,16,24,26,27,21],[14,20,24,23,27,15],[15,16,22,24,25,19],[16,20,25,23,27,17],[18,22,23,24,25,27]]
Die eigentliche Frage ist also, was die minimale Anzahl an Losen ist, die man kaufen kann, sodass diese Eigenschaft noch gegeben ist. Das ist eine sehr interessante Frage, aber ich sehe kein unmittelbares Argument, wie man sie beantworten könnte. Trotzdem wollte ich mal eine Antwort schreiben, damit du nicht ganz leer ausgehst. Vielleicht hat aber auch jemand anderes noch einen schlauen Einfall. (Ich hab das Gefühl, dass man vielleicht eine Verbindung zu endlicher projektiver Geometrie ziehen könnte, aber so ganz hat das noch nicht funktioniert.)
Ein paar Gedanken hab ich mir gemacht: Die "triviale" Strategie von oben benötigt \(\binom{27}3=2925\) Lose. Auf einem Los sind \(\binom63=20\) Tripel. Wäre es also möglich, die Tripel perfekt auf die Lose zu verteilen, so dass jedes Tripel auf genau einem Los vorkommt, dann bräuchte man nur noch \(147\) Lose. Dadurch, dass man gar nicht alle Tripel braucht, könnte die Zahl sogar noch weiter runtergehen. Ich würde also erwarten, dass die optimale Lösung irgendwo zwischen \(100\) und \(150\) liegt.
Ich habe ein kurzes Computerprogramm geschrieben, das solche Lose zusammensetzt. Dabei habe ich keinen schlauen Algorithmus verwendet, sondern immer das nächstbeste Los genommen, das mir weiterhilft (ein sog. Greedy-Algorithmus). Der hat eine Menge von \(177\) Losen geliefert, ich kopier die Ausgabe mal unten rein. Das ist sicher nicht das Optimum, aber schon eine sehr gute Verbesserung zu den \(2925\) Losen am Anfang und auch nicht sehr weit von meiner Schätzung der optimalen Lösung entfernt.
Ich denke noch weiter drüber nach, vielleicht fällt mir ja noch was Schlaues dazu ein. Dann melde ich mich natürlich nochmal.
Hier also die 177 Lose, sodass für jedes Quadrupel von Zahlen aus 1-27 mindestens 1 Los mit diesem Quadrupel 3 Zahlen gemeinsam hat:
[[1,2,3,4,5,6],[1,2,7,8,9,10],[1,2,11,12,13,14],[1,2,15,16,17,18],[1,2,19,20,21,22],[1,2,23,24,25,26],[1,3,7,8,11,9],[1,3,10,12,15,13],[1,3,14,16,19,17],[1,3,18,20,23,21],[1,3,22,24,27,4],[1,4,7,8,12,9],[1,4,10,11,15,13],[1,4,14,16,20,17],[1,4,18,19,23,21],[1,5,7,8,13,9],[1,5,10,11,16,12],[1,5,14,15,19,17],[1,5,18,20,24,21],[1,5,22,23,27,6],[1,6,7,8,14,9],[1,6,10,11,17,12],[1,6,13,15,20,16],[1,6,18,19,24,21],[1,7,15,16,21,17],[1,7,18,19,25,20],[1,7,22,26,27,8],[1,8,15,16,23,17],[1,8,21,9,15,22],[1,9,16,17,24,18],[1,9,19,20,26,25],[1,10,14,18,22,19],[1,10,20,21,25,11],[1,11,18,19,27,12],[1,12,21,22,25,13],[1,13,17,18,26,14],[1,14,21,25,27,2],[2,3,7,8,12,9],[2,3,10,11,15,13],[2,3,14,16,20,17],[2,3,18,19,23,21],[2,3,22,26,27,4],[2,4,7,8,11,9],[2,4,10,12,15,13],[2,4,14,16,19,17],[2,4,18,20,23,21],[2,5,7,8,14,9],[2,5,10,11,17,12],[2,5,13,15,20,16],[2,5,18,19,24,21],[2,5,22,6,7,13],[2,6,8,9,15,10],[2,6,11,12,16,14],[2,6,17,18,25,19],[2,6,20,21,26,24],[2,7,15,16,23,17],[2,7,18,19,26,20],[2,7,24,8,13,17],[2,8,16,18,22,19],[2,8,20,23,27,9],[2,9,13,16,21,17],[2,9,22,10,14,23],[2,10,16,18,27,11],[2,11,22,12,20,25],[2,12,24,13,19,27],[2,14,15,22,24,3],[3,4,7,8,10,9],[3,4,11,12,14,13],[3,4,15,16,18,17],[3,4,19,20,25,5],[3,5,7,8,15,9],[3,5,10,11,18,12],[3,5,13,14,21,16],[3,5,17,23,24,6],[3,6,7,8,13,9],[3,6,10,11,19,12],[3,6,14,15,21,16],[3,6,18,20,22,25],[3,7,14,16,22,17],[3,7,18,19,24,20],[3,7,21,23,25,8],[3,8,14,16,24,17],[3,8,18,19,26,9],[3,9,14,16,23,17],[3,9,21,24,25,10],[3,10,14,16,26,17],[3,10,20,23,27,11],[3,11,16,17,21,24],[3,11,25,12,16,17],[3,12,20,21,26,22],[3,13,17,18,27,19],[3,13,22,23,26,15],[3,15,25,4,5,7],[4,5,8,9,16,10],[4,5,11,12,21,13],[4,5,14,17,22,18],[4,5,23,24,26,6],[4,6,7,8,17,9],[4,6,10,11,18,12],[4,6,13,14,25,15],[4,6,16,19,22,20],[4,6,21,7,13,16],[4,7,14,18,27,22],[4,8,13,14,21,15],[4,8,18,19,24,20],[4,8,22,25,26,9],[4,9,13,14,24,15],[4,9,19,21,27,10],[4,10,17,20,26,23],[4,11,16,17,27,19],[4,11,22,23,25,12],[4,12,16,17,24,19],[4,12,20,13,19,26],[4,13,23,15,20,27],[4,17,21,5,6,8],[5,6,9,10,14,11],[5,6,12,15,18,16],[5,7,10,11,19,12],[5,7,16,17,20,18],[5,7,21,24,27,8],[5,8,11,12,20,18],[5,8,19,9,12,22],[5,9,17,18,23,21],[5,9,25,26,27,10],[5,10,13,15,21,20],[5,10,22,11,15,24],[5,12,14,24,25,13],[5,13,19,14,20,23],[5,16,19,22,25,6],[6,7,10,11,15,12],[6,7,18,19,23,20],[6,7,24,25,26,8],[6,8,11,12,23,16],[6,8,18,19,27,9],[6,9,12,16,26,22],[6,9,23,10,13,16],[6,10,21,24,27,11],[6,11,13,12,20,27],[6,14,17,19,26,15],[7,9,16,20,21,22],[7,9,23,10,13,14],[7,10,16,17,25,18],[7,10,21,11,13,18],[7,11,14,16,26,23],[7,11,25,12,14,20],[7,12,16,17,26,22],[7,12,23,13,15,19],[7,13,25,14,19,21],[7,22,23,8,10,11],[8,10,12,13,19,14],[8,10,17,21,26,11],[8,11,13,14,27,15],[8,11,19,12,15,24],[8,12,17,25,27,13],[8,13,16,18,23,20],[8,14,18,20,22,15],[9,10,12,18,20,11],[9,11,13,15,16,17],[9,11,19,22,27,23],[9,11,24,12,14,21],[9,12,15,13,18,22],[9,14,18,15,23,25],[10,12,21,22,27,23],[10,12,24,13,17,22],[10,14,20,15,16,19],[10,15,17,18,26,23],[10,19,23,24,26,11],[11,13,25,15,20,26],[11,15,21,18,22,26],[11,18,24,12,14,26],[12,15,17,26,27,20],[12,20,23,13,16,22],[13,16,24,26,27,21],[14,20,24,23,27,15],[15,16,22,24,25,19],[16,20,25,23,27,17],[18,22,23,24,25,27]]
Diese Antwort melden
Link
geantwortet
stal
Punkte: 11.27K
Punkte: 11.27K
Ich habe mir auch mal ein paar Gedanken für einen Algorithmus gemacht:
Am Anfang haben wir gegeben eine Liste A, die als Element jedes erdenkliche 4-Tupel hat.
Natürlich darf nix doppelt vorkommen usw.
Dann überführen wir die Liste A in eine Liste B, wobei jedes 4Tupel in A in die Liste seiner 3 Tupel überführt wird.
Also wenn bspw A[0]=(1,2,3,4) ist, dann ist B[0]=((1,2,3)(1,2,4)(1,3,4)(2,3,4))
so in etwa.
Nun bauen wir eine zu Beginn leere Liste aus 6Tupeln, die wir auffüllen indem wir ganze bestimme 3Tupl da rein quälen. nur wenn sich wirklich das Tripel nicht in den vorhandenen 6Tupel einfügen lässt, fangen wir ein neues 6Tupel an.
Konkret gehen wir nun Folgendermassen hin:
zuerst fügen wir eins (nicht alle, nur eins!) der tripel aus B[0] ein.
dann gehen wir zum nächsten und fügen ein Tripel aus B[1] ein.
dann ein tripel aus B[2].
usw. bis wir eben von jedem Eintrag in B jeweils genau 1 der 4 vorhandenen Tripel eingefügt haben.
Welches der 4 Tripel wir nehmen?
Keine AHnung, derzeit random.
Könnte mir aber was vorstellen wo man das Tripel danach aussucht welches sich "am besten" in unsere6tupelliste einfügen lässt.
will sagen , wenn ich ein Tripel habe, das nirgendswo reinpasst und wegen dem ich ein neues 6Tupel anfangen musss.
und ein anderes tripl, das sich einfügen lässt weil es mit einem der vorhandenen tripel eine oder mehrere zahlen gemein hat.
Dann nimmt man natürlich letzteres!
wäre zumindest sinnvoll so.
nur so der gedanke. was dann rauskommt, ist die liste aller zu tippenden 6tupel. ─ densch 10.05.2021 um 12:06
Am Anfang haben wir gegeben eine Liste A, die als Element jedes erdenkliche 4-Tupel hat.
Natürlich darf nix doppelt vorkommen usw.
Dann überführen wir die Liste A in eine Liste B, wobei jedes 4Tupel in A in die Liste seiner 3 Tupel überführt wird.
Also wenn bspw A[0]=(1,2,3,4) ist, dann ist B[0]=((1,2,3)(1,2,4)(1,3,4)(2,3,4))
so in etwa.
Nun bauen wir eine zu Beginn leere Liste aus 6Tupeln, die wir auffüllen indem wir ganze bestimme 3Tupl da rein quälen. nur wenn sich wirklich das Tripel nicht in den vorhandenen 6Tupel einfügen lässt, fangen wir ein neues 6Tupel an.
Konkret gehen wir nun Folgendermassen hin:
zuerst fügen wir eins (nicht alle, nur eins!) der tripel aus B[0] ein.
dann gehen wir zum nächsten und fügen ein Tripel aus B[1] ein.
dann ein tripel aus B[2].
usw. bis wir eben von jedem Eintrag in B jeweils genau 1 der 4 vorhandenen Tripel eingefügt haben.
Welches der 4 Tripel wir nehmen?
Keine AHnung, derzeit random.
Könnte mir aber was vorstellen wo man das Tripel danach aussucht welches sich "am besten" in unsere6tupelliste einfügen lässt.
will sagen , wenn ich ein Tripel habe, das nirgendswo reinpasst und wegen dem ich ein neues 6Tupel anfangen musss.
und ein anderes tripl, das sich einfügen lässt weil es mit einem der vorhandenen tripel eine oder mehrere zahlen gemein hat.
Dann nimmt man natürlich letzteres!
wäre zumindest sinnvoll so.
nur so der gedanke. was dann rauskommt, ist die liste aller zu tippenden 6tupel. ─ densch 10.05.2021 um 12:06
Im Prinzip, ja. Man kann sich im Wesentlichen immer zwei 4-Tupel suchen, die von den bisherigen Losen noch nicht abgedeckt sind, und davon jeweils ein Tripel aussuchen und damit das nächste Los bilden. Wie du schon erkannt hast, hat man dabei sehr viel Wahlmöglichkeit. Einmal die Reihenfolge der 4-Tupel und einmal die Wahl der Tripel. Man kann sich sinnvolle Gedanken dazu machen, aber eine optimale Lösung wird man damit wahrscheinlich nie finden.
─
stal
10.05.2021 um 13:07
Wenn ich für den Anfang eine halbwegs kleine Menge an Tippreihen hinkriege, bin ich schon mal zufrieden.
Dann kann ich es durch meinen optimierungsalgorithmus durchjagen und das Ganze perfektionieren lassen :-) ─ densch 10.05.2021 um 21:57
Dann kann ich es durch meinen optimierungsalgorithmus durchjagen und das Ganze perfektionieren lassen :-) ─ densch 10.05.2021 um 21:57
Habe mal ein Programm gebaut dass erst die 4tupel bildet, jedes 4tupel dann in seine tripel zerlegt, jeweils eins der 4 tripel nimmt.
und dann mit den gefundenen tripeln eine 6tupelliste baut.
komme da auf 536 6tupel. wohlgemerkt beim ziemlich kleinen 4aus27 lotto.
insofern also nicht allzu effizient hier :-/
ich traue mich nur nicht, das durch meinen optimierungsalgorithmus zu jagen, gab mir vorhin schon outofmemory errors :-( ─ densch 13.05.2021 um 12:18
und dann mit den gefundenen tripeln eine 6tupelliste baut.
komme da auf 536 6tupel. wohlgemerkt beim ziemlich kleinen 4aus27 lotto.
insofern also nicht allzu effizient hier :-/
ich traue mich nur nicht, das durch meinen optimierungsalgorithmus zu jagen, gab mir vorhin schon outofmemory errors :-( ─ densch 13.05.2021 um 12:18