Kuhhandel-Probleme

Vorbemerkung: 0 ist in diesem Artikel keine natürliche Zahl, und alle Teilmengen sind nicht-leer.

Gewisse Aspekte von "Kuhhandel" lassen sich folgendermaßen vereinfacht darstellen:

Es gibt 10 Karten: A, B, C, D, E, F, G, H, I, K. Jede dieser Karten hat einen Wert. (Im Originalspiel: 10, 40, 90, 160, 250, 350, 500, 650, 800, 1000.) Am Ende des Spieles hat jeder Spieler einige dieser 10 Karten. Die Punkte für den Spieler ergeben sich nun aus (Summe der Kartenwerte) * (Anzahl der Karten).

Beispiel:

• Birgit hat B (40) und F (350). Punkte: (40 + 350) * 2 = 780.
• Martin hat A (10), C (90) und E (250) Punkte: (10 + 90 + 250) * 3 = 1050.

Ein weiteres Beispiel:

• Birgit hat C (90) und D (160). Punkte: (90 + 160) * 2 = 500.
• Martin hat G (500). Punkte: (500) * 1 = 500.

Wie wir im zweiten Beispiel sehen, kann es bei diesen Kartenwerten also ein Unentschieden geben.

Fragestellung

Man finde Werte für die 10 Karten, sodass kein Unentschieden möglich ist und der höchste Wert minimal ist.

Mathematisch formuliert: Man finde eine 10-elementige Menge natürlicher Zahlen mit möglichst kleinem maximalen Element, die folgende Bedingung erfüllt: Es existieren keine zwei disjunkten Teilmengen, sodass (Anzahl der Elemente in der Teilmenge) * (Summe der Elemente in der Teilmenge) für beide Teilmengen dasselbe Ergebnis liefert.

Oder: Man finde eine 10-elementige Menge natürlicher Zahlen mit möglichst kleinem maximalen Element, die folgende Bedingung erfüllt: Die Wertigkeiten ((Summe der Elemente) * (Anzahl der Elemente)) von 2 Teilmengen sind höchstens dann gleich, wenn mindestens 1 Element in beiden Teilmengen vorhanden ist.

Hinweis: Es gibt mindestens eine Lösung (1,10,100,1000,...,1000000000), daher muss es auch eine kleinste Lösung geben.

Bekannte [nicht optimale] Lösungen und Nichtlösungen

• 1,10,100,1000,...,1000000000 ist eine Lösung
• 1,2,4,8,...,512 ist keine Lösung: {2,4,16} = 66 = {1,32}
• 1,2,3,5,11,17,31,112,171,326 ist die Greedy-Lösung
• 1,4,6,7,8 ist eine optimale Lösung für n=5
• 1,4,7,12,13,14 ist eine optimale Lösung für n=6
• 1,2,3,13,19,22,25 ist eine optimale Lösung für n=7
• 1,2,3,22,32,38,42,45 ist eine Lösung für n=8
• 1,4,7,23,32,40,41,42 ist eine optimale Lösung für n=8
• 1,2,3,20,43,70,76,79,82 ist eine Lösung für n=9
• 1,2,3,43,61,70,76,79,82 ist eine Lösung für n=9

Verallgemeinerte Fragestellungen

• Man finde Kartenwerte für 10 bzw. n Karten, sodass kein Unentschieden möglich ist und der höchste Kartenwert möglichst klein ist. Und/oder:
• Man finde einen Algorithmus, der obiges Problem (für n=10) in < 24 Stunden berechnet.
• Vermutung (Birgit): Die Fragestellungen (*) und (**) (siehe unten) sind beide NP-vollständig (und folglich die obige erst recht).

(*): Gegeben eine Menge von n Zahlen. Man bestimme, ob es zwei Teilmengen dieser Menge mit gleichem Ergebnis ((Summe der Elemente) * (Anzahl der Elemente)) gibt.

(**): Für eine Zahl n bestimme man die kleinste Zahl Z(n), für die eine Menge von n natürlichen Zahlen existiert mit Z(n) als größter Zahl, sodass in der Menge keine Teilmengen mit gleichem Ergebnis ((Summe der Elemente) * (Anzahl der Elemente)) existieren.

(Problem posed by: Martin Windischer)

lG Birgit