Zum Inhalt springen
Inhaltsverzeichnis öffnen
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 0,1,,S0,1,\ldots,S enthält genau S+1S+1 mögliche Summen.

Gelöstes Beispiel

Den Schnitt auf beiden Seiten entfernen

Aus summengleichen A,BA,B werden ABA\setminus B und BAB\setminus A: disjunkt und weiterhin summengleich.

Gelöstes Beispiel

Binärgewichte kollidieren nicht

Die Gewichte 1,2,4,1,2,4,\ldots kodieren jede Teilmenge durch eine eindeutige Binärzahl.