Eine Suchaufgabe

Aus einer Hausaufgabenrunde der Mathematikolympiade im Schuljahr 1995/96, Klasse 9


Uwe berichtet, er habe an einer Straßenkreuzung während einer Grünphase genau folgende Autos die Kreuzung passieren gesehen: Genau zwei VW, genau zwei Audi, genau zwei Opel und genau zwei BMW. Zwischen den beiden VW fuhr genau ein anderes dieser Autos; zwischen den beiden Audi fuhren genau zwei andere; zwischen den beiden Opel fuhren genau drei andere; und zwischen den beiden BMW fuhren genau vier andere der Autos. Finde alle Möglichkeiten für die Reihenfolge, in der nach Uwes Bericht die Autos gefahren sein könnten.

Wir kürzen VW mit V, Audi mit A, Opel mit O, BMW mit B ab.

Die Reihe besteht aus 8 Autos. Im folgenden geben wir an, welche Plätze von 1 bis 8 die Autos jeweils belegen könnten. Dabei bedeutet z.B. V (1,3) dass auf den Plätzen 1 und 3 sich die beiden VW’s befinden könnten.

V (1,3) (2,4) (3,5) (4,6) (5,7) (6,8)

A (1,4) (2,5) (3,6) (4,7) (5,8)

O (1,5) (2,6) (3,7) (4,8)

B (1,6) (2,7) (3,8)

Die möglichen Besetzungen kann man wie folgt finden. Man beginnt mit dem Zahlenpaar (1,6) für B. Dann sucht man in der darüber liegenden Zeile, welche Zahlenpaare für O dann noch möglich sind; das sind nur (3,7) und (4,8). Geht man nun von (3,7) aus in die nächst höhere Zeile, so bleiben nur die Paare (5,8) oder (2,5). Wählt man (5,8), so bleibt in der obersten Zeile noch (2,4) . So hat man eine Lösung gefunden. (2,5) für O führt nicht zu einer Lösung, weil dann in der ersten Zeile in jedem Paar ein Platz vorkommt, der bereits besetzt ist.

Der Weg über (1,6) für B, (4,8) für O führt zu (2,5) für A, und dann ist man am Ende, weil in der ersten Zeile kein Paar mehr in Frage kommt. (1,3) scheidet aus, da die 1 schon besetzt ist, (2,4) weil die 4 besetzt ist, (3,5) und (5,7) wegen der Besetzung von 5, (4,6) und (6,8) wegen der Besetzung von 6.

Beim Durchgehen aller Möglichkeiten fand ich die beiden folgenden Lösungen

B: (1,6) O : (3,7) A: (5,8) V : (2,4), als Reihe geschrieben: BVOVABOA

B: (3,8) O: ( 2,6) A: (1,4) V : (5,7) , als Reihe geschrieben: AOBAVOVB

Ein Blick auf die Reihen zeigt, dass beide Reihen durch Umkehrung auseinander hervorgehen; die eine ist das Spiegelbild der anderen: BVOVABOA | AOBAVOVB

Eine Probe zeigt, dass es sich tatsächlich um Lösungen handelt.