Problem des Monats September 2002

Herr L. will an einer Hausecke den Boden mit quadratischen Platten belegen. Sie sollen ein "L" mit gleich langen "Armen" bilden:



Die Platten sind in 20er-Paketen geliefert worden. Herr L. hat schon mehrere davon ausgepackt, als sein Nachbar Professor S. (den kennen wir schon vom April 2001) vorbei kommt und zuschaut.

"Wie wollen Sie die Platten verlegen, Herr L.?"

"Am liebsten würde ich alle verlegen und keine übrig lassen. Wie viele Reihen ich legen soll, weiß ich noch nicht so recht."

"Wie viele Platten haben Sie denn?"

"Bisher habe ich 5 zerbrochene gezählt. Ich hoffe, es bleibt dabei."

"Dann haben Sie verschiedene Möglichkeiten für die Verlegung."

Herr L. ist erstaunt über diese Aussage, denn Professor S. hatte noch nicht einmal die Pakete gezählt. Offenbar genügte es für ihn zu wissen, dass jedes Paket 20 Platten enthält.

Herr L. packt auch den Rest aus und findet eine weitere zerbrochene Platte.

"Das ist Pech, Herr L. Jetzt können Sie Ihre Platten nicht mehr vollständig verlegen."

Woher konnte Professor S. das so schnell wissen?

Wenn Sie darüber nachdenken, kommen Sie schnell auf das allgemeine Problem, für welche Plattenzahlen es keine oder genau eine oder mehrere Lösungen gibt.

Welches ist die geringste Anzahl von Platten, die Herrn L.  2 (3, 4, 5) Verlegungsmöglichkeiten erlauben würde?

Etwas Probieren mit kleinen Plattenzahlen kann hier schon weiterhelfen; man erkennt schnell, wann es keine Lösung gibt.

Lösung

Was wusste Professor S., das Herr L. nicht wusste? Wenn man  n  Platten hat, kann es offenbar vorkommen, dass es keine Verlegungsmöglichkeit gibt (z.B. bei  n = 6) oder genau eine (z.B.  bei  n = 7) oder auch mehrere (dafür muss man allerdings etwas länger suchen; z.B.  n = 15  erlaubt zwei Lösungen). Professor S. wusste nun, wie man beliebige  n  einer dieser drei Kategorien zuordnet. Da ihm das quasi mit einem Blick auf Herrn L.'s Platten gelang, ist anzunehmen, dass die Regel nicht allzu schwer ist.

Die Plattenlegung des Herrn L. erfolgt in "L-Reihen", also in L-förmigen Plattenreihen; im Bild oben in der Aufgabenstellung sehen wir links eine L-Reihe und rechts drei L-Reihen. Da jede L-Reihe aus einer ungeraden Anzahl von Platten besteht, gibt es für (un)gerade  n  nur Lösungen mit einer (un)geraden Anzahl von L-Reihen (falls es überhaupt eine Lösung gibt).

Die entscheidende Überlegung zu einer systematischen Lösung ist nun, dass sich  n  als Differenz zweier Quadratzahlen darstellen lässt, also  n = a ² - b ²  mit  a, b  aus den natürlichen Zahlen. Am leichtesten sieht man das geometrisch:



In diesem Bild ist  n = 45,  a = 9  (großes Quadrat) und  b = 6  (kleines Quadrat).  a - b  ist immer die Anzahl der L-Reihen.

Somit ist das Problem des Herrn L. auf die folgende Frage zurückgeführt: Wieviele Darstellungen hat  n  als Differenz zweier Quadratzahlen?

Auf diese Fragestellung kommt man übrigens auch, wenn man die Platten in den einzelnen L-Reihen addiert, z.B. im Bild:  n = 13 + 15 + 17. Generell erhält man so  n  als Summe aufeinander folgender ungerader Zahlen. Nun ist aus der Mathematik aber bekannt, dass

1 + 3 + ... + 2k-1 = k ²  (schönes Beispiel für eine vollständige Induktion);

für unser Beispiel bedeutet das

n = (1 + 3 + ... + 17) - (1 + 3 + ... + 11) = 9 ² - 6 ² .

n ungerade

Für ungerade  n  außer  n = 1  gibt es immer eine Lösung mit genau einer L-Reihe; es bleibt also die Frage, wann diese Lösung eindeutig ist. Wir schreiben  n  anders auf:

n = a ² - b ² = (a + b)(a - b) = p · q    ( p und  q  beide ungerade )

Kennt man nur die Zerlegung  n = p · q, so lassen sich  a, b  leicht rekonstruieren:

a = (p + q) / 2       b = (p - q) / 2

Nun ist man schon am Ziel: Die Zerlegung  n = p · q  mit  p >q   ist nur dann eindeutig, wenn es außer  p = n  und  q = 1  keine anderen Möglichkeiten gibt. Für Primzahlen  n  ist dies klar. Ist  n  nicht prim, so darf  n  nicht zwei verschiedene (ungerade) Faktoren  p > 1  und  q > 1  haben. Dies gilt aber genau für Primzahlquadrate.

Bei den eindeutigen Lösungen ist  a = b + 1 , was gleichbedeutend mit genau einer L-Reihe ist. Im linken Bild in der Aufgabenstellung oben ist  n = 9 , also ein Primzahlquadrat; eine andere Verlegungsmöglichkeit gibt es somit für 9 Platten nicht.

n gerade

p  und  q  unterscheiden sich durch  2b, müssen also beide gerade sein.  n  ist also durch 4 teilbar. Ist  n  gerade, aber nicht durch 4 teilbar, so gibt es keine Lösung.

Schreibt man  n = 4m  mit  m > 1 (denn auch für  n = 4  gibt es offenbar keine Lösung), so findet man leicht eine Lösung mit zwei L-Reihen:

p = 2m ,  q = 2 ,  d.h.  a = m + 1 ,  b = m - 1

(Beispiel: n = 40 = 20 · 2 = 11 ² - 9 ² )

Es bleibt wieder die Frage, wann diese Lösung eindeutig ist.

Inspiriert durch den Fall "n ungerade" sieht man, dass die Anzahl der Lösungen von  n = 4m = p · q  wieder von der Anzahl der Teiler von  m  abhängt. Ist  m  prim, so gibt es wegen  p > q  (beides gerade Zahlen) keine andere Zerlegung als  n = (2m) · 2. Das Gleiche gilt, wenn  m  ein Primzahlquadrat ist. In allen anderen Fällen lässt sich  m  als  m = r · s  mit  r > s > 1  schreiben; dann ist  n = (2r)(2s)  eine weitere Lösung.

Übersicht

Wie hat Professor S. gerechnet?

Die Platten waren in 20er-Paketen geliefert worden. Wenn 5 Platten zerbrochen sind, ist die Plattenanzahl  n  durch 5 teilbar. Die einzigen durch 5 teilbaren  n  mit einer eindeutigen Lösung sind aber 5 und 25.

Sind 6 Platten zerbrochen, so ist  n  nicht durch 4 teilbar.

Wie viele L-Reihen werden verlegt, welche Länge hat die erste?

Wenn Herr L. die Faktorisierung  n = p · q  kennt, kann er gleich mit der Verlegung der ersten L-Reihe anfangen, indem er  p - q + 1  Platten um die Hausecke legt. Denn in der ersten L-Reihe müssen  2b + 1  Platten liegen, und oben haben wir  b = (p - q) / 2  berechnet.

Die Anzahl der L-Reihen ist offenbar  q = a - b .

Wo treten erstmalig  2 (3, 4, 5) Lösungen auf?

Das ermittelt man am besten mit einem kleinen Programm. Die gesuchten kleinsten  n  sind:

n = 15     2 Lösungen

n = 45     3 Lösungen

n = 96     4 Lösungen

n = 192    5 Lösungen

Für den letzten Fall sollen die Lösungen angegeben werden: Wegen 192 = 2 ⁶ · 3 ergeben sich die Zerlegungen (man beachte  p > q, beide gerade):

192 = 96 · 2 = 48 · 4 = 32 · 6 = 24 · 8 = 16 · 12

Für  n = 1 ... 100  erhält man:

27 x keine Lösung

39 x eine eindeutige Lösung

26 x zwei Lösungen

7 x drei Lösungen

1 x vier Lösungen