Hans Walser, [20140818]
Anzahl Quadrate
Anregung: T. H. , A.
Gesucht ist die Anzahl der Quadrate, in ein quadratisches Gitter mit n×n Gitterpunkten eingezeichnet werden kšnnen. Die Quadratecken sollen Gitterpunkte sein. Ein Gitter mit n×n Gitterpunkten liegt in einem Quadrat der SeitenlŠnge n – 1.
Die Abbildung 1 zeigt ein Beispiel eines schrŠgen Quadrates in einem Gitter mit 6×6 Gitterpunkten.
Abb. 1: Quadrat im Gitter
Wir unterscheiden
A) Quadrate, deren Seiten parallel zu den Gitterlinien sind (bodenstŠndig)
B) Quadrate, deren Diagonalen parallel zu den Gitterlinien sind
C) Allgemein schrŠge Quadrate
Nachfolgend ein Maple-Programm (fźr n = 6):
n:=6: # Groesse
des n*n Gitters
# A:= Anzahl bodenstaendige Quadrate
A:=0:
for a
from 1 to n-1 do
A:=A+a^2:
end:
print("A"
=A);
# B:= Anzahl Quadrate mit
Steigungswinkel 45ˇ
B:=0:
for b
from 1 to n do
if n-2*b > 0
then B:=B+(n-2*b)^2 end:
end:
print("B"=B);
# C:= Anzahl schraege Quadrate
C:=0:
for c
from 2 to n-1 do
for d from 1 to c-1 do
if n-c-d >
0 then C:=C+(n-c-d)^2 end:
end:
end:
C:=2*C:
print("C"=C);
Total:=A+B+C
print("Total"=Total);
"A" = 55
"B" = 20
"C" = 30
"Total" = 105
Die Tabelle 1 gibt die ersten Werte.
n |
A |
B |
C |
|
1 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
1 |
3 |
5 |
1 |
0 |
6 |
4 |
14 |
4 |
2 |
20 |
5 |
30 |
10 |
10 |
50 |
6 |
55 |
20 |
30 |
105 |
7 |
91 |
35 |
70 |
196 |
8 |
140 |
56 |
140 |
336 |
9 |
204 |
84 |
252 |
540 |
10 |
285 |
120 |
420 |
825 |
Tab. 1: Werte
Die A-Folge ist als Summe der Quadratzahlen eine arithmetische Folge 3. Ordnung.
Wenn wir Kugeln aufschichten gemŠ§ Abbildung 2, ist die Gesamtzahl der Kugeln in einer Pyramide mit n Schichten die Zahl mit der Nummer n + 1 in der A-Folge.
Abb. 2: 140 Kugeln
Die B-Folge erscheint im Pascalschen Dreieck der Binomialkoeffizienten (Abb. 3).
Abb. 3: Im Pascalschen Dreieck
Sie ist ebenfalls eine arithmetische Folge 3. Ordnung.
Fźr die C-Folge habe ich keine Illustration gefunden. Sie ist eine arithmetische Folge 4. Ordnung.
Wegen der C-Folge ist auch die Folge eine arithmetische Folge 4. Ordnung. Sie hat die recht einfache Formel:
Diese Formel ist vorerst nur empirisch erhŠrtet.
Beweis mitgeteilt von T. H., A.
Der Beweis beruht darauf, dass jedes Quadrat in ein gitterparalleles Quadrat eingepackt werden kann (Abb. 4).
Abb. 4: Einpacken in gitterparalleles Quadrat
Zwischenbemerkung: In der Abbildung 4 haben wir die optische TŠuschung, dass wir das gitterparallele Quadrat (magenta) schief zu sehen glauben.
Umgekehrt kšnnen in ein gitterparalleles Quadrat der SeitenlŠnge k genau k Quadrate einbeschrieben werden (Abb. 5 fźr k = 4). Dabei wird das gitterparallele Quadrat mitgezŠhlt.
Abb. 5: Einbeschriebene Quadrate
Wir zŠhlen zunŠchst die gitterparallelen Quadrate ab. In einem n×n Gitter gibt es gitterparallele Quadrate der SeitenlŠnge k. Dabei ist .
Zu jedem solchen gitterparallelen Quadrat gibt es k einbeschriebene Quadrate.
Somit ist:
Einsetzen der einschlŠgigen Formeln fźr die Summe der natźrlichen Zahlen, der Quadratzahlen und der Kubikzahlen liefert:
Zu zeigen: fźr jede natźrliche Zahl n ist durch 12 teilbar.
Beweis
mit Faktorisierung:
Es sind drei aufeinanderfolgende natźrliche Zahlen als Faktoren im Spiel. Einer dieser Faktoren ist also durch 3 teilbar.
Und nun Fallunterscheideidung bezźglich der ParitŠt von n:
á Bei geradem n hat mindestens zweimal den Primfaktor 2.
á Bei ungeradem n sind und gerade, wir haben also auch mindestens zwei Primfaktoren 2.
Damit ist der Ausdruck durch teilbar.