Aufgabe:
Die Schüler*innen einer Schule haben insgesamt genau 2n verschiedene Hobbys, wobei jede*r Schüler*in genau 2 Hobbys hat und jedes Paar von Schüler*innen höchstens ein gemeinsames Hobby hat. Für jedes k mit 1<=k<=n-1 ist die Anzahl der Hobbys, die von höchstens k Schüler*innen betrieben werden, kleiner als k.
Man zeige, dass es 2n Schüler*innen gibt, die zusammen alle 2n Hobbys betrieben, wobei jedes Hobby von genau zwei Schüler*innen betrieben wird.
Problem/Ansatz:
Mein erster Gedanke bei dieser Aufgabe war sofort Graphentheorie, einfach weil es nach einem typischen Problem in dieser Richtung aussieht. Damit bin ich aber bisher noch nicht richtig voran gekommen. Die Knoten dürften die Schüler*innen und die Kanten die Hobbys sein, wobei man die dann am besten wohl mit 2n Farben färbt. Allerdings habe ich es damit noch nicht geschafft, dem Problem wirklich näher zu kommen.
1.) Haltet ihr Graphentheorie und insbesondere meine Abstraktion für sinnvoll, oder hättet ihr eine ganz andere Idee diese Aufgabe anzugehen.
2.) Hättet ihr einen Ansatz, wie man damit weiterkommt?
Vielen Dank!!!
