Kapitel 7Olympiade25 Min.
Teilmengen als exponentiell viele Objekte
Teilmengensummen und Summenkollisionen · Abschnitt 25 von 64
Gelöstes Beispiel
64 Teilmengen, nur 55 Summen
Sechs Zahlen bis 9 besitzen 64 Indexteilmengen, deren Summen höchstens von 0 bis 54 reichen.
Gelöstes Beispiel
Endpunkte mitzählen
Der ganzzahlige Bereich enthält genau mögliche Summen.
Gelöstes Beispiel
Den Schnitt auf beiden Seiten entfernen
Aus summengleichen werden und : disjunkt und weiterhin summengleich.
Gelöstes Beispiel
Binärgewichte kollidieren nicht
Die Gewichte kodieren jede Teilmenge durch eine eindeutige Binärzahl.