Uli Blumenthal: Alle Jahre wieder geben wir Ihnen an den Adventssonntagen im Dezember jeweils eine mathematische Nuss zu knacken. In diesem Jahr hatten wir an allen drei Sonntagen eine Rekordbeteiligung zu verzeichnen: 400 bis 700 Einsendungen auf unsere mathematische Nuss, die wir gemeinsam jedes Jahr mit dem Matheon, mit dem Forschungszentrum der TU Berlin, veranstalten. Gestern Vormittag haben wir dann den dritten Gewinner, die dritte Gewinnerin für die Adventsfrage gezogen, haben die Gewinnerin benachrichtigt, haben die Lösung ins Netz gestellt und haben einige Mails bekommen, die gesagt haben, liebe Leute von Forschung Aktuell, die Lösung ist falsch. Die Lösung ist nicht 17, sie kann nicht 17 sein. Ich bin jetzt mit Falk Ebert vom Matheon in Berlin verbunden. Herr Ebert, warum kann es nicht 17 sein, wie wir in der Lösung dann auch gezeigt haben?
Falk Ebert: Ich war auch erst ein wenig überrascht davon. Ich hab es dann sehr, sehr schnell auch ausprobiert: Ja, tatsächlich, es gibt Lösungen mit 16 - nicht nur eine, sondern auch gleich mehrere. Und das Problem lag daran, dass ich diese Aufgabe irgendwann mir überlegt hatte, ich hatte eine gewisse schöne Struktur darin gefunden gehabt - als Mathematiker ist man immer froh, wenn man Strukturen findet - und ich war mir nicht der Tiefe dieses Lochs hinter diesem Problem bewusst. Denn eigentlich ist es ein extrem schweres Problem, das man tatsächlich niemandem an einem Adventssonntag zumuten will.
Blumenthal: Nehmen wir es nochmal vor und zeigen auf, was unsere Frage am letzten Sonntag war: Wer schnell noch am letzten Adventswochenende seine Weihnachtseinkäufe erledigen muss, kommt ganz schön schnell ans Münzenzählen. Preise, die auf glatte Eurobeträge lauten, sind schließlich eher selten. Der Einzelhandel scheint geradezu darauf zu bauen, dass sich viele Leute beim Bezahlen verzählen. Eine Münzreform soll dem abhelfen, so unsere Frage. Sämtliche Münzwerte unter einem Euro, die es aktuell gibt, also 1, 2, 5, 10, 20 oder 50 Cent, werden über den Haufen geworfen, es sollen neue Münzen geprägt werden. Die Münzwerte sollen so sein, dass man alle Preise zwischen einem und 98 Cent mit maximal zwei dieser neuen Münzwerte bezahlen kann. Der Schwellenpreis von 99 Cent wird abgeschafft. Das war die Aufgabe. Warum kann jetzt nicht 17 rauskommen?
Ebert: Die Antwort darauf ist ganz einfach: Sobald jemand eine Lösung mit 16 gefunden hat und mit der tatsächlich alle Werte von 1 bis 98 abgedeckt werden, dann kann 17 nicht mehr das bestmögliche sein. Das ist eine ganz simple Möglichkeit.
Blumenthal: Jetzt haben wir Einsendungen bekommen, die sagen 16. Jetzt könnten wir sagen, unter diesen Einsendern, unter diesen Mails suchen wir den mit der richtigen Lösung, aber auch 16 muss nicht unbedingt die richtige Lösung sein.
Ebert: Ich habe mich jetzt nochmal ein ganzes Stück tiefer mit der Aufgabe auseinandergesetzt. Ich kann Ihnen nicht garantieren, dass 16 tatsächlich das bestmögliche ist. Ich hatte ja geglaubt zeigen zu können, dass 17 das beste ist. Dementsprechend kann es 16 sein, es kann auch deutlich weniger sein. Was ich Ihnen garantieren sein ist, dass es mindestens zehn Münzen sein müssen. Alles zwischen zehn und 16 könnte irgendwo richtig sein. Allerdings: sämtliche Möglichkeiten von Münzen bis dahin auszuprobieren, wäre definitiv nicht mehr schaffbar in diesem Jahr.
Blumenthal: Wir haben eine Mail von Thomas Hupfer bekommen, der sagt, das ist im Wesentlichen das Briefmarkenproblem. Kann man das nun nur durch Ausprobieren ermitteln oder kann man das wirklich irgendwie herleiten? Was geben Sie uns für einen Tipp, damit wir die Aufgabe richtig lösen können?
Ebert: Das Briefmarkenproblem und jetzt in unserem Fall auch diese Münzenproblem gehört in die Klasse der sogenannten NP-schweren Probleme. Das sind einige Probleme, mit denen man als Mathematiker wirklich zu kämpfen hat. Die sind üblicherweise sehr, sehr leicht formuliert, auch wie in diesem Fall. Und die Lösung läuft in den allermeisten Fällen darauf hinaus, dass man wirklich intelligent ausprobiert. Intelligentes ausprobieren heißt eben in unserem Fall zum Beispiel, wir müssen nichts suchen, was mehr als 16 Münzen beinhaltet. Wir müssen auch nichts suchen, was weniger als zehn Münzen beinhaltet. Jetzt könnte man meinen, dass man damit eigentlich den Raum der Möglichkeiten sehr, sehr weit eingeschränkt hat. Das Problem ist, es sind immer noch mehrere hundert Billiarden Möglichkeiten, die man sich testen müsste, um da drin irgendwo vielleicht ein Minimum zu finden.
Blumenthal: Wir kommen wir als Deutschlandfunk, wie kommen Sie als der, der die Aufgabe entwickelt hat, jetzt aus der Sache raus? Was würde der Mathematiker uns raten in Ihnen?
Ebert: Ich würde sagen, es sollte auf jeden Fall derjenige prämiert werden, der es tatsächlich schafft, bis, setzen wir uns einen Frist, Mitte Januar, sagen wir 15. Januar, eine möglichst kleine Lösung findet, wenn es tatsächlich irgendetwas kleineres als 16 Münzen geben würde, fände ich das natürlich toll. Ich kann es jetzt überhaupt noch nicht abschätzen. Mein Rechner läuft seit gestern Abend und sucht Möglichkeiten, hat noch keine gefunden. Und anderenfalls, wenn tatsächlich 16 das kleinstmögliche sein sollte, was wir bisher finden könnten, dann würde ich versuchen, denjenigen zu prämieren, der tatsächlich die insgesamt kleinsten Münzwerte hat, das heißt 16 Münzwerte, so dass die Summe aus diesen Münzwerten möglichst klein wird.
Falk Ebert: Ich war auch erst ein wenig überrascht davon. Ich hab es dann sehr, sehr schnell auch ausprobiert: Ja, tatsächlich, es gibt Lösungen mit 16 - nicht nur eine, sondern auch gleich mehrere. Und das Problem lag daran, dass ich diese Aufgabe irgendwann mir überlegt hatte, ich hatte eine gewisse schöne Struktur darin gefunden gehabt - als Mathematiker ist man immer froh, wenn man Strukturen findet - und ich war mir nicht der Tiefe dieses Lochs hinter diesem Problem bewusst. Denn eigentlich ist es ein extrem schweres Problem, das man tatsächlich niemandem an einem Adventssonntag zumuten will.
Blumenthal: Nehmen wir es nochmal vor und zeigen auf, was unsere Frage am letzten Sonntag war: Wer schnell noch am letzten Adventswochenende seine Weihnachtseinkäufe erledigen muss, kommt ganz schön schnell ans Münzenzählen. Preise, die auf glatte Eurobeträge lauten, sind schließlich eher selten. Der Einzelhandel scheint geradezu darauf zu bauen, dass sich viele Leute beim Bezahlen verzählen. Eine Münzreform soll dem abhelfen, so unsere Frage. Sämtliche Münzwerte unter einem Euro, die es aktuell gibt, also 1, 2, 5, 10, 20 oder 50 Cent, werden über den Haufen geworfen, es sollen neue Münzen geprägt werden. Die Münzwerte sollen so sein, dass man alle Preise zwischen einem und 98 Cent mit maximal zwei dieser neuen Münzwerte bezahlen kann. Der Schwellenpreis von 99 Cent wird abgeschafft. Das war die Aufgabe. Warum kann jetzt nicht 17 rauskommen?
Ebert: Die Antwort darauf ist ganz einfach: Sobald jemand eine Lösung mit 16 gefunden hat und mit der tatsächlich alle Werte von 1 bis 98 abgedeckt werden, dann kann 17 nicht mehr das bestmögliche sein. Das ist eine ganz simple Möglichkeit.
Blumenthal: Jetzt haben wir Einsendungen bekommen, die sagen 16. Jetzt könnten wir sagen, unter diesen Einsendern, unter diesen Mails suchen wir den mit der richtigen Lösung, aber auch 16 muss nicht unbedingt die richtige Lösung sein.
Ebert: Ich habe mich jetzt nochmal ein ganzes Stück tiefer mit der Aufgabe auseinandergesetzt. Ich kann Ihnen nicht garantieren, dass 16 tatsächlich das bestmögliche ist. Ich hatte ja geglaubt zeigen zu können, dass 17 das beste ist. Dementsprechend kann es 16 sein, es kann auch deutlich weniger sein. Was ich Ihnen garantieren sein ist, dass es mindestens zehn Münzen sein müssen. Alles zwischen zehn und 16 könnte irgendwo richtig sein. Allerdings: sämtliche Möglichkeiten von Münzen bis dahin auszuprobieren, wäre definitiv nicht mehr schaffbar in diesem Jahr.
Blumenthal: Wir haben eine Mail von Thomas Hupfer bekommen, der sagt, das ist im Wesentlichen das Briefmarkenproblem. Kann man das nun nur durch Ausprobieren ermitteln oder kann man das wirklich irgendwie herleiten? Was geben Sie uns für einen Tipp, damit wir die Aufgabe richtig lösen können?
Ebert: Das Briefmarkenproblem und jetzt in unserem Fall auch diese Münzenproblem gehört in die Klasse der sogenannten NP-schweren Probleme. Das sind einige Probleme, mit denen man als Mathematiker wirklich zu kämpfen hat. Die sind üblicherweise sehr, sehr leicht formuliert, auch wie in diesem Fall. Und die Lösung läuft in den allermeisten Fällen darauf hinaus, dass man wirklich intelligent ausprobiert. Intelligentes ausprobieren heißt eben in unserem Fall zum Beispiel, wir müssen nichts suchen, was mehr als 16 Münzen beinhaltet. Wir müssen auch nichts suchen, was weniger als zehn Münzen beinhaltet. Jetzt könnte man meinen, dass man damit eigentlich den Raum der Möglichkeiten sehr, sehr weit eingeschränkt hat. Das Problem ist, es sind immer noch mehrere hundert Billiarden Möglichkeiten, die man sich testen müsste, um da drin irgendwo vielleicht ein Minimum zu finden.
Blumenthal: Wir kommen wir als Deutschlandfunk, wie kommen Sie als der, der die Aufgabe entwickelt hat, jetzt aus der Sache raus? Was würde der Mathematiker uns raten in Ihnen?
Ebert: Ich würde sagen, es sollte auf jeden Fall derjenige prämiert werden, der es tatsächlich schafft, bis, setzen wir uns einen Frist, Mitte Januar, sagen wir 15. Januar, eine möglichst kleine Lösung findet, wenn es tatsächlich irgendetwas kleineres als 16 Münzen geben würde, fände ich das natürlich toll. Ich kann es jetzt überhaupt noch nicht abschätzen. Mein Rechner läuft seit gestern Abend und sucht Möglichkeiten, hat noch keine gefunden. Und anderenfalls, wenn tatsächlich 16 das kleinstmögliche sein sollte, was wir bisher finden könnten, dann würde ich versuchen, denjenigen zu prämieren, der tatsächlich die insgesamt kleinsten Münzwerte hat, das heißt 16 Münzwerte, so dass die Summe aus diesen Münzwerten möglichst klein wird.