Schöne Deko

Du hast dich entschlossen, bei der Gestaltung des diesjährigen Dorffestes mitzuhelfen. Über dem Rathausplatz soll ein Netz aus Ballons schweben, wobei je zwei Ballons immer mit einer Schnur verbunden sein können (natürlich ist das ganze Netz auch irgendwie mit dem Boden verbunden). Du bekommst die Aufgabe, die Ballons so anzumalen, dass je zwei Ballons, die durch eine Schnur verbunden sind, eine unterschiedliche Farbe bekommen und entscheidest dich für folgendes Vorgehen: Du stellst eine Ordnung für die (unbegrenzt vielen) Farben auf (z.b. rot, grün, blau, ...) und gehst dann die Ballons anhand ihrer Herstellungsnummer durch. Für jeden Ballon wählst du die erste Farbe aus, die du für die dazu verbundenen Ballons noch nicht verwendet hast. Zeige, dass dein Vorgehen mehr Farben benötigen kann, als du im besten/minimalen Fall brauchst, wenn die Herstellungsnummern schlecht verteilt sind!

Leider regnet es am großen Tag und ihr müsst das Dorffest und die gesamte Deko kurzfristig in die örtliche Sporthalle verschieben. Für diesen Anlass wird das Ballonnetz etwas verkleinert und dir fällt auf, dass sich keine Schnüre kreuzen, jetzt, wo das Netz an der Hallendecke zu sehen ist. Kannst du alle Ballons jetzt mit deiner Technik mit so wenig wie möglich Farben färben, egal wie die Herstellungsnummern verteilt sind?