Die ungerade Pyramide

Es ist ja mittlerweile umstritten, in Bewerbungsgesprächen für Softwareentwickler Programmieraufgaben zu stellen, da sie höchstens ein recht verzerrtes Bild von den Programmierfähigkeiten des Kandidaten widerspiegeln.

Dabei mochte ich es eigentlich sehr, Aufgaben wie diese zu stellen, denn sie sagt mir, wie der Programmierer denkt, bevor er eine Aufgabe anfängt zu programmieren. Denn genau diese Fähigkeit entscheidet hier darüber, wie schnell man zu einer Lösung kommt.

Aufgabe

Die ungeraden Zahlen werden wie folgt zu einer unendlichen Pyramide zusammengestellt: In der ersten Zeile steht die erste ungerade Zahl, also die 1. In der zweiten die nächsten zwei ungeraden Zahlen, also die 3 und die 5. In der dritten die nächsten drei und so weiter.

Schreibe ein Programm, das die Summe der Zahlen in Zeile \(i\) berechnet.

Lösung

Ich mag diese Aufgabe sehr. Sie wirkt zunächst so, als wäre sie umständlich und kompliziert, bis man einmal für die ersten Zeilen es per Hand durchführt.

Das ergibt dann die folgenden Ergebnisse:

Für die Zeile \(i\) ist die Lösung scheinbar \(i^3\) - programmiertechnisch also sehr simpel. Eine Lösung in Python, die auch gleich eine Tabelle mit den ersten 10 Zeilen aufbaut, sähe in Python wie folgt aus:

 1def solution(i):
 2         return i ** 3
 3
 4def nth_odd(n):
 5         return 2 * n - 1
 6
 7def sum_i(i):
 8         return i * (i + 1) // 2
 9
10def gen_line(i):
11         k = sum_i(i - 1) + 1
12         return [nth_odd(k + j) for j in range(i)]
13
14def gen_line_str(i):
15         return " ".join(map(str, gen_line(i)))
16
17return [["*Zeile*", "*Zahlen*", "*Ergebnis*"], None] + [[i,gen_line_str(i), solution(i)] for i in range(1, 11)]

Dieser Code enthält auch Methoden um die Tabelle selber zu generieren, etwas, was gar nicht gefordert ist - genau diese Fragestellung bringt die Kandidaten daher auch ins Schwitzen, bis man ihnen den freundlichen Hinweis gibt, sich doch erst einmal die ersten Zahlen anzusehen und zu schauen, ob ihnen die Ergebnisse bekannt vorkommen.

Was ich nicht erwarte, das ist ein Beweis, dabei ist die Art, wie man die Pyramide erzeugen kann, bereits der halbe Weg, um diesen Zusammenhang nachzuweisen.

Doch dafür zunächst ein Ausflug in die Zahlentheorie.

Beweis

Zunächst brauchen wir eine Formel, mit der die Summe aller natürlichen Zahlen bis einschließlich \(n\) berechnet werden kann. Dafür gibt es eine Formel, die von Gauß entwickelt wurde: \(\frac{n(n+1)}{2}\) - hier der Beweis des Zusammenhangs:

Lemma Gauß

Gegeben sei eine Funktion \(S : \mathbb{N} \rightarrow \mathbb{N}\) definiert als

\[ S(n) := \sum_{i=1}^n = 1 + \ldots + n \]

Zu zeigen: \(S(n) = \frac{n \cdot (n + 1)}{2}\)

Beweis durch Induktion

• Induktionsanker

  Für \(n = 1\) gilt:

  \[ S(1) = \sum_{i=1}^1 = 1 = \frac{1 \cdot 2}{2} \]

  was zu zeigen war.

• Induktionsannahme

  Angenommen, der Zusammenhang gilt für alle Zahlen bis \(n - 1\).

• Schritt

  Dann gilt:

  \[ S(n) = n + S(n - 1) = n + \frac{(n - 1) \cdot ((n - 1) + 1)}{2} \]

  \[ = \frac{2n + n \cdot (n - 1)}{2} \]

  \[ = \frac{2n + n^2 - n}{2} \]

  \[ = \frac{n + n^2}{2} \]

  \[ = \frac{n \cdot (n + 1)}{2} \]

  Was zu beweisen war.

Lemma Summe der ersten n ungeraden Zahlen

Es gibt den folgenden überraschenden Zusammenhang: die Summe der ersten \(n\) ungeraden Zahlen ist immer \(n^2\) - sprich, alle Quadratzahlen lassen sich als Summe der ungeraden Zahlen abbilden:

Beweis durch vollständige Induktion

• Behauptung

  Gegeben sei die Funktion \(T : \mathbb{N} \rightarrow \mathbb{N}\) definiert als

  \[ T(n) := \sum_{i=1}^n 2i - 1 = 1 + 3 + 5 + \ldots + 2n - 1 \]

  also die Summe der ersten \(n\) ungeraden Zahlen. Zu zeigen ist, dass \(T(n) = n^2\).

• Anker

  Für \(n = 1\) gilt:

  \[ T(1) = \sum_{i=1}^1 (2i - 1) = 2 - 1 = 1 \]

  und damit auch \(T(1) = 1^2\).

• Induktionsannahme

  Angenommen, es gilt für \(T(n-1)\)

• Induktionsschritt

  Da

  \[ T(n) = 2n - 1 + T(n-1) \]

  gilt:

  \[ T(n) = 2n - 1 + (n - 1)^2 \]

  \[ = n^2 - 2n + 1 + 2n - 1 \]

  \[ = n^2 \]

  was zu beweisen war.

Beweis ursprünglicher Zusammenhang

Man muss sich einmal vor Augen halten: Die Summe der Zahlen in Zeile i ist die Summe aller Zahlen bis zur Zeile i minus der Summe der Zahlen bis zur Zeile i - 1.

Die Anzahl der ungeraden Zahlen bis Zeile i ist genau die Summe aller natürlichen Zahlen bis i. Damit ergibt sich für unser Problem folgendes:

\[ P(i) = T(S(i)) - T(S(i - 1)) = S(i)^2 - S(i-1)^2 \]

Nach dem Einsetzen von \(S\) ergibt sich für \(P\):

\[ P(i) = \frac{i² \cdot (i + 1)²}{4} - \frac{i² \cdot (i - 1)²}{4} \]

\[ = \frac{i² \cdot ((i² + 2i + 1) - (i² - 2i + 1))}{4} \]

\[ = \frac{i² \cdot 4 \cdot i}{4} \]

\[ = i³ \]

Und damit ist der Zusammenhang bewiesen.