Problem des Monats Juni 2004

Mr. Jones wohnt und arbeitet in Manhattan, New York, genauer gesagt in der Upper East Side zwischen dem Central Park und dem East River. Der Ausschnitt aus dem Stadtplan von Manhattan zeigt das streng gitterförmige Muster der Straßen im südlichen Teil der Upper East Side und Mr. Jones' Arbeitsplatz:

Südlicher Teil der Upper East Side von Manhattan

Die (grob) von SW nach NO verlaufenden Straßen heißen Avenues:
   East End Avenue
   York Avenue
   First Avenue
   Second Avenue
   Third Avenue
   Lexington Avenue
   Park Avenue
   Madison Avenue
   Fifth Avenue
   (Die Forth Avenue gibt es hier nicht, sondern nur weiter südwestlich der Upper East Side.)

Die (grob) von NW nach SO verlaufenden Straßen heißen Streets und sind streng durchnummeriert. Der Kartenausschnitt zeigt den Bereich von East 59th Street bis etwa East 93rd Street.

Mr. Jones hat einen Bürojob und muss viel sitzen. Seine Wohnung liegt ebenfalls innerhalb des Kartenausschnitts. Um sich Bewegung zu verschaffen, geht er jeden Morgen und jeden Abend den Weg zwischen Wohnung und Büro zu Fuß. Dabei hat er viel Abwechslung, denn es gibt für ihn zahlreiche Möglichkeiten, welche Straßen er für seinen Gang wählt.

Am 1. Juni 2004 fällt ihm ein, dass er in gut zwei Jahren, nämlich Ende Juni 2006, pensioniert werden wird. Er rechnet ein bisschen und stellt fest, dass er es in dieser Zeit schaffen kann, jeden der möglichen Wege einmal zu gehen. Mr. Jones hat eine 5-Tage-Woche und 12 Urlaubstage pro Jahr (ja, das ist in Amerika so üblich, mehr bezahlten Urlaub gibt's in der Regel nicht). Außerdem hat er pro Jahr an 13 Feiertagen frei, die auf Werktage fallen. In seiner Rechnung ist nicht viel Spielraum, er kann sich nur den einen oder anderen Fehltag erlauben, wenn er seinen Plan verwirklichen will.

Was ist mit jedem möglichen Weg gemeint? Die rechtwinklige Anlage der Straßen und Wohnblöcke in Manhattan macht die Angelegenheit für Mr. Jones sehr übersichtlich. Er geht nur kürzeste Wege zwischen seiner Wohnung und seinem Büro bzw. zurück, macht also keine Umwege. Von diesen kürzesten Wegen gibt es allerdings viele, nicht etwa nur einen eindeutigen - davon kann man sich anhand des Stadtplans leicht überzeugen. Es soll keine Rolle spielen, in welche Richtung einer dieser Wege gegangen wird (morgens oder abends), d.h. Mr. Jones hat sich nicht vorgenommen, jeden möglichen Weg in beiden Richtungen je einmal zu gehen. Weiterhin ist unwichtig, auf welcher Straßenseite Mr. Jones geht oder wo er eine Straße überquert. Um es auf den Punkt zu bringen: Nur die Abfolge der Kreuzungen auf seinem Weg ist für Mr. Jones entscheidend. Dabei liegen lediglich die erste und die letzte Kreuzung fest, alle anderen sind variabel.

Wo wohnt Mr. Jones?

Lösung

Da Mr. Jones fast 1000 Gänge bis zu seiner Pensionierung machen kann, muss seine Wohnung ein gutes Stück nördlich und östlich seines Büros liegen. Da die Richtung seines Weges keine Rolle spielen soll, wollen wir sein Büro als Ausgangspunkt nehmen. Die Folge der Kreuzungen auf seinem Weg beginnt also mit Madison Av. / 64th Street. Von dort aus geht er er in wechselnder Reihenfolge  n  "lange Blocks" in Richtung Südosten (also entlang der Streets) und  m  "kurze Blocks" in Richtung Nordosten (also entlang der Avenues) bis zur letzten Kreuzung, von der aus er zu seiner Wohnung gelangt.


Bild 1

In Bild 1 sind die erste und die letzte Kreuzung in Rot eingezeichnet, alle dazwischen liegenden Kreuzungen in Grün. Hier wurde beispielhaft  n = 5  und  m = 8  angenommen; Mr. Jones würde also als letzte Kreuzung First Av. / 72nd Street erreichen.

Wieviele mögliche Wege gibt es bei bekannten  n  und  m ? Offenbar handelt es sich um ein Reihenfolgeproblem: Man muss  n  "Schritte" nach Südost (im folgenden mit  S  abgekürzt) und  m  "Schritte" nach Nordost (im folgenden mit  N  abgekürzt) anordnen. In Bild 1 ist eine dieser Anordnungen gezeigt:

NNNNSNSNNSSSN

Die Antwort ist aus der elementaren Kombinatorik bekannt. Es handelt sich um Permutationen (Anordnungen) mit Wiederholung von  n  Elementen  "S"  und  m  Elementen  "N" . Deren Anzahl beträgt

(n + m)! / (n! m!)

Im Beispiel von Bild 1 ist also ein möglicher Weg unter insgesamt  13! / (5! 8!) = 1287  Wegen dargestellt.

Auf das gleiche Ergebnis kann man auch kommen, wenn man nach der Anzahl der Möglichkeiten fragt, die  n  Elemente in die  m  Elemente "einzusortieren". (Im Beispiel von Bild 1 müsste man also 5  "S"  irgendwo in die Folge  NNNNNNNN  einfügen.) Dafür gibt es  m + 1  Plätze, da auch die Positionen am Anfang und am Ende in Frage kommen. Da an jeden dieser  m + 1  Plätze kein  S , ein  S  oder mehrere  S  einsortiert werden können, handelt es sich um Kombinationen mit Wiederholung (ungeordnete Stichproben mit Zurücklegen) von  n  aus  m + 1  Elementen. Deren Anzahl ist durch den Binomialkoeffizienten



gegeben, somit erhält man wie oben  (n + m)! / (n! m!)  mögliche Wege. Man beachte, dass  0! = 1  ist; theoretisch könnten ja bei Mr. Jones' Weg keine  "S"  oder keine  "N"  vorkommen.

Jetzt müssen wir nur noch etwas genauer nachrechnen, wie oft Mr. Jones seinen Weg zum Büro und zurück machen kann. Er hat bis zu seiner Pensionierung noch 544 Tage außerhalb der Wochenenden vor sich. Davon gehen 24 Urlaubs- und 26 Feiertage ab. Es bleiben also noch 494 Arbeitstage, d.h. maximal 988 Gänge. Welche Zahlen kommen für  n  und  m  in Frage? Wir schauen auf den oben gezeigten Stadtplan der Upper East Side und zählen 7 Avenues zwischen der Madison Avenue und dem East River und höchstens 29 Streets oberhalb der 64th Street. Hier ist eine Tabelle der Werte von  (n + m)! / (n! m!)  für  n = 0,...,7  und  m = 0,...,29 :



Am besten passt offenbar die Zahl 969 aus der Tabelle. Die nächst niedrigere Zahl ist 924; wäre das der richtige Wert, könnte Mr. Jones alle Wege gehen und hätte noch mehr als 6 Wochen (32 Arbeitstage) übrig, was der Problemstellung nicht entspricht. Zu 969 gehören  n = 3  und  m = 16  (d.h.  19! / (3! 16!) = 969 ).

Bevor wir Mr. Jones' Haustür suchen, soll noch darauf aufmerksam gemacht werden, dass die Tabelle das Pascal'sche Dreieck ist, gekippt um 45°. In diesem Dreieck steht an der  n-ten Stelle der  m-ten Zeile der Binomialkoeffizient



wobei die Zählung der  n  und  m  jeweils bei  0  beginnt:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10   10  5   1
1   6  15   20  15  6   1
....

Kippt man das Pascal'sche Dreieck um 45° nach links, werden die Diagonalen zu Zeilen und an der  n-ten Stelle der  m-ten Zeile steht jetzt



Das entspricht genau der Tabelle oben.

Wo wohnt also nun Mr. Jones?  n = 3  und  m = 16  bedeutet, dass er von seinem Büro aus 3 Blöcke nach Südosten und 16 Blöcke nach Nordosten geht, also zur Kreuzung Third Av. / 80th Street. Dies ist die letzte Kreuzung auf seinem Weg, also muss seine Wohnung in einem der dort angrenzenden Häuserblöcke liegen. Von der Kreuzung kann er seine Haustür nur nach Nordosten oder nach Südosten erreichen, weil er sonst einen Umweg gemacht hätte. Also wissen wir jetzt:

Mr. Jones wohnt entweder auf der Third Avenue zwischen der 80th und der 81st Street oder auf der 80th Street zwischen der Third und der Second Avenue.