Matrixgleichung mit Adjazenzmatrix bei Lottoproblem aufstellen?

Question

Aufgabe:
Hallo,
ich beschäftige mich gerade damit wie man (möglichst wenigen) Lottoreihen beim Lotto 6 aus 49 tippen kann um trotzdem 3 Richtige zu haben.

Dazu denke man sich eine Liste, die alle möglichen Kombinationen aus 6 Zahlen im Bereich 1-49 hat (jede Kombination aufsteigend sortiert, keine doppelten Zahlen in einer Kombi, etc. pp.).
Nennen wir die Liste P.

Weils das Leben einfacher macht, geben wir jeder Zahlenkombination in P eine Id, schlicht und ergreifend ihre Platznummer in der Liste.

Nun suchen wir eine Teilmenge S letztlich (anders gesprochen ein Element der Potenzmenge von P), die möglichst klein ist.
Und Wo aber folgendes erfüllt ist:
Für alle p in P existiert mindestens ein s aus S, sodass s und p mindestens 3 gleiche Zahlen haben
(Beachte, P und S enthalten ja 6-Zahlen-Kombinationen, die wir nur der EInfachheit halber über eine ID ansprechen)


Problem/Ansatz:

Zur Lösung will ich nun folgendes machen:
Erstmal eine entlang der Diagonalen gespiegelte, quadratische Matrix M machen.
wo gilt:
M_ij=1, wenn Element mit id i aus P und das ELement mit id j aus S mind. 3 gemeinsame Zahlen haben
ansonsten 0.


Im Endeffekt ist es sogar überflüssig die Teilmenge S zu erwähnen, wiel ich letzltich einfach die i te und die j te Zahlenkombi in P vergleiche und 1 in M_ij schreibe wenn die mind. 3 Zahlen gemeinsam , ansosnten 0.

Also ist M eine Matrix die mir für die Elemente in P untereinander angibt welche 3 Zahlen gemeinsam haben und "in Beziehung sind".

Haben wir also M, die letztlich eine Art Adjazenzmatrix darstellt.

Desweiteren will ich einen Vektor X=(x1,x2,x3,.....,x13983816) haben, der mir simpel angibt:
xi=1 -> Element i aus P wird benutzt
xi=0 -> element i aus P wird nicht benutzt.

Würden also die Elemente mit id=1,2,3,4,5,6 aus P benutzt,
dann wären x1 bis x6 gleich 1, alle anderen Werte in X 0.

Am Ende vom Lied ist X zu finden, wobei so wenige Einsen wie möglich darin vorkommen sollen.
Und aber eine Gleichung der Art
M*X=1
erfüllt wird (wobei 1 hier ein passend langer 1 Vektor bzw. eine mx1 Matrix mit 1 überall ist. der 1 Vektor muss genauso lang sein wie X. Naturgemäß ist M ebenso so lang/breit wie X lang ist. ).

Wir arbeiten heir übrigens mit Modulo 2, also mit 0+0=0,1+0=0+1=1,1+1=0.

ich bin mir nur total unsicher wie genau die Marix Gleichung aussehen muss
ob es nun
X*M=1 sein muss
oder M*X=1
oder X^T*M=1
oder M*X^t=1
oder noch was Anderes....

Vom problem her ist das so äjnlich wie beim ""LightsOut" spiel und dessen algebraischer Lösungsweise, siehe bspw. hier:
https://mathworld.wolfram.com/LightsOutPuzzle.html
Nur kriege ich es gedanklich gerade nicht übertragen
Kann mir da Jemand weiterhelfen?

Comments

Nach langem Überlegen kann ich es mir vermutlich selbst beantworten (bzw. kommentieren wiel man sich seine Frage ja nicht selbst beantworten darf...):
M ist ja symmetrisch, sit also egal, ob ich M oder M^t nehme.
Ich muss letztlich
M*x=1 schreiben.

Die Berehcnung für den ersten Wert des 1 Vektors, sozusagen die Berechnungen in der ersten Zeile
(erste Zeile von M mal die Spalte von x) geben mir Folgendes an:
ist x1=1 heißt das, das erste Tupel wird benutzt.
ist nun M11 auch 1, dann gibt das an, dass für das Tupel 1, das Tupel 1 mind. 3 Zahlen teilt (duh).

M11*x1 gibt dann an, dass ein Tupel benutzt wird, das mit dem Tupel 1 (Zeilennummer 1, wohlgemerkt) 3 Zahln teilt. LKurzum, dadurch die Bedingung für das Tupel 1 erfüllt wird.

Oder besser erklärbar an Zeile 2:
Betrachten wir Zeile 2 von M.
Sind M21 und M23 1, dann heißt das dass das Tupel 1 und 3 in beziehung zum Tupel 2 steht und umgekehrt.
ist nun beim multiplizieren x3=1, so heißt das M23*x3 dass das Tupel 3 benutzt wird.
und weil M23=1 ist, wissen wir ja dass Tupel 3 und 2 in Beziehung sind.
Also wird Tupel 3 benutzt und dadurch alleine shcon wird die Bedingung fürs Tupel 2 erledigt.

usw.

eine beliebige Zeile Mi in der Matrix M gibt einfahc an, für das Zupel i, welche Tupel könnte man nehmen um die Bedingung zu erfüllen.
Sobald dann irgendeins der Wette auch im x vektor 1 ist, wird die Bedingung für das i tupel erfüllt.


lange Rede kurzer Sinn:
Es muss M*x=1 heißen.

und die Werte von xi geben an welche Tupels benutzt werden.

Mir fiel übrigens auf dass wir uns nicht im F2 befinden da ja gerade nicht 2 einsen null ergeben sollen.
Vielmehr soll einfach 0=0 sein und alles >0 auf 1 abgebildet werden.

für multiplikation gilt dann das übliche 1*1=1, 0*1=1*0=0*0=0

Jetzt wäre nur die Frage wie man bei so einer matrix klärt ob sie invertierbar ist.
bzw. ob sie es ist, da ja recht sicher ist dass verschiedene Lösungen existieren.
bekanntlich gibt es ja eine x lösung, wo bestimmte 163 werte von x gleich 1 sind, rest 0.
würde man x=1 setzen, wäre auch das eine lösung, etc.

Also mehrdeutig lösbar.
dann ist ja glaube ich die amtrix nicht invertierbar und das ganze nciht nahc x so easy lösbar ohne lange gauss rechnerei, oder?