Neues Spiel

19/07/2015 - 21:00 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
nxn-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,
k_z=0\} der kleinste Index echt kleiner als n 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, i\le j\le n} 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
19/07/2015 - 22:09 | Warnen spam
On 19.07.2015 21:00, 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
nxn-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)



Mh - also k = k_0 + k_1*2^1 + ... + k_{n-1}*2^{n-1} ?

die binàre Darstellung von k. Sei z = min\{z\ge 0 | z<n,
k_z=0\} der kleinste Index echt kleiner als n 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, i\le j\le n} 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.



Offenbar verstehe ich die Konstruktion noch nicht.
Die Matrizen haben einen Index 1 <= i <= n, sollten also
n x n -Matrizen sein (?) das kommt mit dem Beispiel nicht hin.

Beispiel: n=3.

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


Hàtte ich jetzt gedacht M_0 wàre:
+++
++
+

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


hier wàre dann z=0, und da alle Indizes i,j in M_{i,j}
von 1 bis n gehen wàre i,j <= z nie erfüllt:
nichts würde geflippt und M_1=M_0.

Sollen die Indizes i,j vielleicht von 0 bis n-1 gehen?

dann hàtte ich nun für M_1:
-++
++
+

für k=2 wàre z=1 und die "Flipp-Matrix" mit 1 an den Positionen, die
geflippt werden und 0 sonst wàre
110
10
0
und damit für M_2
+-+
-+
+
u.s.w.

Das sollte wohl noch geklàrt werden, bevor ich weiter
darüber nachdenke :)

Gruß,
Detlef

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

Ähnliche fragen