Forums Neueste Beiträge
 

Neues Spiel

19/07/2015 - 23:26 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 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 Andreas Leitgeb
20/07/2015 - 00:20 | Warnen spam
Axel Romihsita wrote:
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).



In Worten ist also z der Index des niederwertigsten 0-bits von k,
für gerade k also stets z=0, und, da z das meistwertige bit nicht
erreichen darf ("echt kleiner als n-1"), ergibt sich z undefiniert
nur für die Zahlen (2^n - 1) und (2^(n-1) - 1): in "little endian"
binàrdarstellung also: 111...111 und 111...110. Passt es mal soweit?

Wir bekommen die Matrix M_k=(M_k^{i,j})_{1\le i\le n-1, 1\le j\le i}



Für die mir gelàufige Matrix-indizierung (i,j):
(1,1) (1,2) ...
(2,1) (2,2) ...
... ... ...
wàre das aber eine linke *untere* Dreiecksmatrix, also:
(1,1)
(2,1) (2,2)
(3,1) (3,2) (3,3)
...
da ja j <= i sein soll

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.



Gemessen daran, dass dieser Algorithmus um die Hauptdiagonale symmetrisch ist,
und entweder die Folge-Matrix gleich der vorigen ist, oder sich jeweils in
einem am linken oberen Eck klebenden Teilquadrat von der vorigen unterscheidet,
scheint die Matrix insgesamt nicht mehr Information zu beinhalten, als ihre
erste Spalte.


Beispiel: n=3.
k=0, rückwàrts binàr 000:
++
+



Ok, für k=0 war's ja direkt so definiert...

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



z ist hier also 1, d.h. es dürfte doch nur das Matrix element (1,1)
invertiert werden. Warum ist hier aber auch (2,1) mit-invertiert worden?

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



Für k=2 wàre dann z also wieder 0, und somit dürfte gar nichts
invertiert werden, weil ja weder i noch j kleiner-oder-gleich 0
sein können.

Da steige ich jetzt aus, und warte auf Klàrung.

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.

Ähnliche fragen