Post by Ulrich D i e z1. Angenommen, ein solcher Additionsturm habe k Stockwerke.
(Bei Deinen Additionstürmen ist k = 4.)
Es ist geschickt, das unterste Stockwerk als 1. zu bezeichnen,
die zweitunterste als 2. usw. Bei einem k-stöckigen Gebäude hat man
als Einträge der Reihe nach:
1. Stock: x_1, ..., x_k
2. Stock: x_1 + x_2, x_2 + x_3, ..., x_{k-1} + x_k.
3. Stock: x_1 + 2x_2 + x_3, x_2 + 2x_3 + x_4, ...,
x_{k-2} + 2x_{k-1} + x_k,
4. Stock: x_1 + 3x_2 + 3x_3 + a4, x_2 + 3x_3 + 3x_4 + x_5, ...
5. Stock: x_1 + 4x_2 + 6x_3 + 4x_4 + x_5, ...
...
Man erkennt das Schema: Der Koeffizient vor x_j im ersten Eintrag im
n-ten Stock ist n über j; hier bezeichnet als B(j, n).
Allgemeiner ist der m-te Eintrag im n-ten Stock
E_{m,n} = \sum_{j=1}^n B(j, n)x_{j + m - 1}
(Das lässt sich formal sicher über Induktion beweisen, aber es ist
ja offensichtlich; dazu bin ich jetzt zu bequem.)
Das sind (k - 1)k / 2 lineare Gleichungen für die
k Unbekannten x_1, ..., x_k.
Damit ist die Beantwortung der Fragen auf lineare Algebra
Post by Ulrich D i e zWie viele Zahlen eines solchen k-stöckigen Additionsturms muss man
mindestens vorgeben, damit die übrigen Zahlen, die man ausrechnen
soll, eindeutig bestimmt sind?
Da man ein lineares Gleichungssystem mit k Unbekannten hat, braucht
man mindestens k Gleichungen.
Post by Ulrich D i e zHängt diese Mindestanzahl von der Anzahl der Stockwerke, also vom
Wert von k, ab?
Offensichtlich: Sie ist k.
Post by Ulrich D i e zHängt diese Mindestanzahl auch davon ab, für welche Stockwerke des
Additionsturms man Zahlen vorgibt?
Die Frage ist außer für den 1. Stock nicht wohlgestellt, da kein
anderer Stock außer dem ersten zu k Gleichungen führen kann, man
also immer eine Kombination aus verschiedenen Stockwerken vorgeben
muss. Du meinst also: Welche Gleichungen muss man genau auswählen
(also die Kästchen vorgeben), damit k Stück bereits ausreichen.
Post by Ulrich D i e z2. Kann man einen Algorithmus angeben, der, egal, für welche Stockwerke
des Additionsturms man Zahlen vorgibt, immer
- entweder alle nicht vorgegebenen Zahlen berechnet,
- oder meldet, dass mit den vorgegebenen Zahlen kein Additionsturm
berechnet werden kann und in der Meldung dazu sagt, warum es nicht
geht?
Schauen wir uns mal die Koeffizientenmatrix für k = 3 an:
1 2 1
1 1
1 1
1
1
1
Und für k = 4:
1 3 3 1
1 2 1
1 2 1
1 1
1 1
1 1
1
1
1
1
Die Konstruktion der Matrix geht allgemein so, dass die unteren
k Zeilen die Einheitsmatrix bilden. Die nächsten k-1 Zeilen
(das zweite Stockwerk der Pyramide) sind die Summen über
je zwei aufeinanderfolgende Zeilen der Einheitsmatrix.
Die nächsten k-2 Zeilen (das dritte Stockwerk) sind die Summen
über je zwei aufeinanderfolge der vorherigen k-1 Zeilen
(des zweiten Stockwerks) usw.
In der jeweils obersten Zeile der dieser Untermatrizen wird
offensichtlich, weshalb hier die Binomialkoeffizienten
ins Spiel kommen.
Nun zur Frage:
Wir wählen also jeweils k Kästchen aus, also k Gleichungen,
also k Zeilen in der Koeffizientenmatrix.
Die Frage läuft jeweils darauf hinaus: Ist für diese Auswahl
die Determinante ungleich 0?
Danach kann man die eindeutige Lösung beispielsweise nach
dem Gauß-Algorithmus berechnen, oder
Post by Ulrich D i e z3. [Thematik: Rekursive Formel / explizite Formel.]
wahlweise nach dem Cramer-Schema.
Nach Konstruktion sieht man sofort, welche Zeilen man *nicht*
auswählen darf, weil man sonst sofort Determinante 0 hat:
Beispielsweise sind die Koeffizienten der oberste Zeile
(für jedes k > 1) die Summe der beiden nächsten, also erhält
man die Determinante 0, wenn diese beiden Zeilen in
den k Gleichungen hat, also wenn man die obersten beiden
Stockwerke vorgibt. Allgemein muss man aufpassen, dass man
nie Zahlen vorgibt, so dass sich eine der Zahlen aus
einem Teilturm der anderen Zahlen ergibt.
Mit anderen Worten: Es ist offensichtlich *notwendig*, die
k Kästchen so auszuwählen, so dass in keiner Unterpyramide
der Größe j mehr als j Zahlen vorgegeben werden.
Ist dieses triviale notwendige Kriterium gar schon hinreichend?
Für Türme der Größe <=2 ist es trivial, und für den Turm k = 3
stimmt es nach systematischem Probieren auch noch.
Das Probieren suggeriert, dass man es vielleicht per Induktion
für alle k beweisen kann, aber da bin ich nicht sicher.
Die verbleibende Frage ist also die: Gilt die
Vermutung: Gibt man k Werte vor, so ist die Lösung *genau* dann
eindeutig, wenn dabei in *keiner* kleineren Unterpyramide der
Größe j mehr als j Zahlen vorgegeben wurden.
Post by Ulrich D i e z+---+
| ? | ----- Gibt es eine explizite (Summen-)Formel, in der
+-------+ die Variablen k, B_1, B_2, B_3, ..., B_k
| | | vorkommen, mit der man ausrechnen kann, was
+-------+ ganz oben herauskommt?
. Falls ja: Wie lautet sie?
Das hatten wir oben schon: E_{1, k} = \sum_{j=1}^n B(j, k) x_j
(ich benutze x_j für das, was Du oben B_j nennst).