Lösung eines interessanten Problems, das an der Freien Universität Berlin gestellt wurde.
Am Donnerstag, den 22. November 2007 wurde an der Freien Universität Berlin im Rahmen einer Vorlesung folgende Aufgabe gestellt und mit einem Preisgeld dotiert:
Gegeben ist eine Menge von 90 Zahlen. Gesucht sind zwei disjunkte Teilmengen, die die gleiche Summe haben.
Ein Vergleich der Anzahl der Teilmengen mit der Anzahl möglicher Summen zeigt via Schubfachprinzip, dass es zwei Teilmengen gleicher Summe geben muss (siehe Beweis in englischer Sprache). Doch es ist schwer, solche Teilmengen konkret anzugeben.
Am Freitag, den 11. Januar 2008 fand ich endlich solche zwei Teilmengen. Mein Verfahren errechnete sie auf einem Computer mit 2,2 GHz in unter 13 Stunden und benötigte weniger als 10 MB RAM. Ein bisschen Glück war auch dabei.
Erste Teilmenge:
299217582989230036751837 880016501852078856080635 946937165954033988788424 1578162492977450664126944 1812879178768006647235301 2971744582923874049523742 4091474885269966517294879 4943815057818965902712248 5692360253366837692855083 6234741001182606643532181 6245204080460602087652559 7120742867939246902694149 7733650334383259168598095 7747065949059587127983387 8279949847077321547947668 8599907651245936274235011 8830799594854106724079801 9353107892210566969889749 9395599504828327447842303 9647858044168603043583573 9987260063384478692770831 --------------------------- 122392494532715086986178400
Zweite Teilmenge:
271421581991306487222635 347210985514203543494151 844211877858888899575802 858113459448281134464318 932105819382609874540832 1021909632877056162522230 1492845928328613952413181 1578316156809978343861270 2028605977888681784691506 3159810959653867741168701 3364583159258485665818747 3829382062288197495585493 5274393751963791216707924 5557433944866232834271571 6109799501102929064894494 7113888145901322259202502 7495519447874567191609824 8116842585410897780195903 8512563823990276478199266 8746090017816284717018883 8897886080683405948729770 8905127244710061692528848 9030730515728049113458849 9179170804759779289641072 9724531066607318314360628 --------------------------- 122392494532715086986178400