Die folgende Aufgabe stammt von der Internationalen Mathematikolympiade, die Mitte Juli in Bath stattfand, und sie ist erheblich schwieriger als man vielleicht zunächst denken würde.

Ein soziales Netzwerk hat 2019 Nutzer, von denen einige paarweise befreundet sind. Immer wenn der Nutzer A mit dem Nutzer B befreundet ist, dann ist auch der Nutzer B mit dem Nutzer A befreundet. Ereignisse der folgenden Art können wiederholt nacheinander stattfinden: Drei Nutzer A, B und C, von denen A mit B und C befreundet ist, aber B und C nicht befreundet sind, wechseln den Status ihrer Freundschaften so, dass jetzt B und C befreundet sind, aber A nicht mehr mit B befreundet ist und auch nicht mehr mit C befreundet ist. Der Status aller anderen Freundschaften bleibt unverändert. Anfangs sind 1010 Nutzer mit jeweils genau 1009 Nutzern befreundet und 1009 Nutzer mit jeweils genau 1010 Nutzern befreundet. Man beweise, dass es eine Folge solcher Ereignisse gibt, nach der jeder Nutzer höchstens mit einem anderen Nutzer befreundet ist.

Bei der Olympiade gewann übrigens Jonas Walter aus Rostock eine Goldmedaille. In der (deutschen) Presse scheint das Ereignis dieses Jahr völlig ignoriert worden zu sein.

Um einen Kommentar zu verfassen, müssen Sie sich einloggen bzw. kurz als Gast registrieren.