Neues Spiel

20/07/2015 - 01:42 von Axel Romihsita | Report spam
Hallo zusammen,

Wir betrachten folgendes Spiel. Sei n eine positive ganze Zahl. Zu jeder
ganzen Zahl k zwischen 0 und 2^n - 1 konstruieren wir eine linke obere
(n-1)x(n-1)-Dreiecksmatrix M_k mit Eintràgen aus {+,-} rekursiv wie folgt.

Für k=0 sei die Matrix M_0 aus lauter + zusammengestellt.
+...+
+...
...
+

Ist ein k \ge 1 gegeben, so sei k_0...k_{n-1} (die wichtigsten Stellen
zuletzt) die binàre Darstellung von k. Sei z = min\{z\ge 0 | z<n-1,
k_z=0\} der kleinste Index echt kleiner als n-1 mit k_z=0 (oder
undefiniert, wenn es den Index nicht gibt). Wir bekommen die Matrix M_k
=(M_k^{i,j})_{1\le i\le n-1, 1\le j\le n-i} aus M_{k-1}, indem wir im
definierten Falle alle Eintràge mit Indizes (i,j) so dass i,j\le z
invertieren, d.h. + mit - vertauschen, und im undefinierten Falle die
Matrix kopieren.



Beispiel: n=3.

k=0, rückwàrts binàr 000:
++
+

k=1, rückwàrts binàr 100:
-+
-

k=2 = (010)_2:
+-
-

k=3 = (110)_2:
+

k=4 = (001)_2:
+

k=5 = (101)_2:
+-
-

k=6 = (011)_2:
-+
-

k=7 = (111)_2:
++
+


Frage bei diesem Spiel: entwirf eine nichtrekursive, erststufige Formel
für jeden Eintrag M_k^{i,j}.

Ideen?

Axel.
 

Lesen sie die antworten

#1 Detlef Müller
20/07/2015 - 10:04 | Warnen spam
On 20.07.2015 01:42, Axel Romihsita wrote:
Hallo zusammen,

Wir betrachten folgendes Spiel. Sei n eine positive ganze Zahl. Zu jeder
ganzen Zahl k zwischen 0 und 2^n - 1 konstruieren wir eine linke obere
(n-1)x(n-1)-Dreiecksmatrix M_k mit Eintràgen aus {+,-} rekursiv wie folgt.



[...]

Ist ein k \ge 1 gegeben, so sei k_0...k_{n-1} (die wichtigsten Stellen
zuletzt) die binàre Darstellung von k. Sei z = min\{z\ge 0 | z<n-1,
k_z=0\} der kleinste Index echt kleiner als n-1 mit k_z=0 (oder
undefiniert, wenn es den Index nicht gibt).



Finde ich irgendwie unschön, z als "undefiniert" zu definieren [das
ruft evt. unsere Philosophen-Front auf den Plan :) ]
...
geht nicht auch
z:= max\{ t \ge 0 | 2^t teilt k \},

dann ist evtl. z >= n-1, was unserem "undefinierten Fall"
entspricht.
Ist aber nicht so wichtig.

Wir bekommen die Matrix M_k
=(M_k^{i,j})_{1\le i\le n-1, 1\le j\le n-i} aus M_{k-1}, indem wir im
definierten Falle alle Eintràge mit Indizes (i,j) so dass i,j\le z
invertieren, d.h. + mit - vertauschen, und im undefinierten Falle die
Matrix kopieren.


Beispiel: n=3.

k=0, rückwàrts binàr 000:
++
+

k=1, rückwàrts binàr 100:
-+
-



Warum wurden die Eintràge bei (1,1) und (2,1) getauscht?

Es ist doch hier z=0 und die Aussage "1<=0 und 2<=0" ist
falsch ?!

Selbst wenn die Indizes bei 0 losgehen, wàre bei (0,0) alles
ok, aber in (1,0) die Bedingung 1 <= 0 verletzt.

Und dürften nicht nur symmetrische Matrizen auftauchen, da
(i,j <=1) <=> (j,i <= 1) ?

Ist mit "i,j <=1" vielleicht etwas anderes gemeint als
"i<=1 und j<=1"?

Gruß,
Detlef

Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

Ähnliche fragen