Proposition - Parking Function als Mengenabschätzung

• Involvierte Definitionen:
  • Parking Function
• Veranstaltung:
  • AlMa
• Referenz:
  • Eigener Beweis

⠀

Proposition: Parking Function als Mengenabschätzung

ist genau dann eine Parking Function, wenn

Beweis

Bezeichne hierzu einen der durchnummerierten Parkplätze .

Da es genauso viele Parkplätze wie Autos gibt, muss jeder Parkplatz genau einmal belegt werden. Andernfalls handelt es sich definitionsgemäß nicht um eine PF. Ein Parkplatz kann zwar mehrfach angefahren werden - er kann aber nicht mehrfach belegt werden.

Diese Gedanken wollen wir jetzt formalisieren. Hierzu betrachten wir die ersten paar Fälle im Detail und gehen schließlich zu einer Rekursion über.

Erster Fall ()

Angenommen, alle Parkplätze stehen zur Verfügung. Dann können noch genau Autos parken - schließlich gibt es ja auch genau Parkplätze.

Zweiter Fall ()

Angenommen, Parkplatz steht nicht mehr zur Verfügung.

• Entweder, weil er bereits belegt ist
• oder, weil es gar kein Auto gibt, das Parkplatz präferiert belegen möchte.

Wir betrachten nun die Parkpräferenzen der Autos, die uns durch das Tupel zur Verfügung stehen. Dabei interessiert uns, wie viele Autos auf einem Parkplatz parken wollen.

Stellt sich heraus, dass alle Autos auf einem Parkplatz parken möchten, wissen wir, dass es sich bei nicht um eine PF handeln kann. Dann gibt es nämlich Autos, die Parkplätze belegen müssten.

Dritter Fall ()

Angenommen, Parkplatz und stehen nicht mehr zur Verfügung.

• Entweder, weil sie bereits belegt sind
• oder, weil es gar kein Auto gibt, das Parkplatz oder präferiert belegen möchte.

Wir betrachten wieder die Parkpräferenzen der Autos. Insgesamt stehen jetzt noch Parkplätze zur Verfügung.

Stellt sich heraus, dass mehr als Autos auf einem Parkplatz parken wollen, wissen wir, dass es sich bei nicht um eine PF handeln kann. Dann gibt es nämlich mindestens Autos, die Parkplätze belegen müssten.

-ter Fall

Angenommen, Parkplatz bis stehen nicht mehr zur Verfügung.

• Entweder, weil sie bereits belegt sind
• oder, weil es gar kein Auto gibt, das die Parkplätze präferiert belegen möchte.

Wir betrachten nun wieder die Parkpräferenzen der Autos. Insgesamt stehen jetzt noch Parkplätze zur Verfügung.

Stellt sich heraus, dass mehr als Autos auf einem Parkplatz parken wollen, wissen wir, dass es sich bei nicht um eine PF handeln kann.

Das würde nämlich bedeuten, dass mindestens Autos auf Parkplätzen parken wollen.

Die Menge der Autos, die auf einem Parkplatz größer parken wollen, erhalten wir durch

Uns interessiert also, ob

wobei die Anzahl noch verfügbarer Parkplätze ist. Falls also die Anzahl der noch zu parkenden Autos kleiner/gleich der Anzahl freier Parkplätze ist, so kann es sich potenziell um eine Parking Function handeln. Andernfalls können wir ausschließen, dass es sich um eine PF handelt.

Schluss

• Alle Parkplätze konnten belegt werden, wenn in jedem der Fälle immer galt.

• Mindestens ein Parkplatz konnte nicht belegt werden, wenn in einem der Fälle galt

Es folgt also, dass eine Parking Function ist, wenn

gilt, was zu zeigen war.