Zwei Gitter
Rainer Rosenthal
Seien G die Punkte des Gitters ZxZ und H die Punkte des um 45 Grad
um den Nullpunkt gedrehten Gitters. Sei Dreh die Drehung G -> H.
Es gilt Tatsache T:
Für jede Zahl K gibt es einen Punkt p in G, (T)
dessen Abstand zu Dreh(p) grösser ist als K.
Frage F:
Gibt es eine Bijektion Bij: G -> H und
eine Zahl K, so dass für alle p aus G (F)
der Abstand zu Bij(p) kleiner als K ist?
Schon immer haben mir diese Gitter Freude gemacht, z.B. beim Vorbeifahren
an den regelmässig aufgestellten Weinstöcken hier am See. Daher habe ich
mir zur Einstimmung eine Zeichnung gemacht getreu dem Motto M, das ein
Darmstädter Professor einst oft und gern verwendet haben soll:
Ist von Verständnis
keine Spur, (M)
zeichnet man
'ne Hilfsfigur.
Mit Maple 6 als modernem Millimeterpapier sieht das z.B. so aus:
--------------------------------------------------------------------------
restart:
with(plots):
G := pointplot({seq(seq([i,j],j=0..30),i=0..30)}):
Dreh := p -> [p[1]*cos(Pi/4)-p[2]*sin(Pi/4),p[1]*sin(Pi/4)+p[2]*cos(Pi/4)];
H := pointplot({seq(seq(Dreh([i+1/2,j+1/2]),j=0..30),i=0..30)},color=red):
display(G,H);
--------------------------------------------------------------------------
Die Figur etwas vergrössern und ... aaahh: da sind ja Kreise zu sehen. Geil, ey.
So, jetzt etwas in die Figur vertiefen: ist da Evidenz für die vage Vermutung,
dass es längs der Diagonalen nicht genügend nahe Nachbarn geben wird, so dass
F negativ zu beantworten ist?
Gruss,
Rainer R.
.
________________________________.___.___________________________________
Rainer Rosenthal . r.ros...@web.de
Hero
> Wieder eine wunderschöne Frage von Wolfgang Thumser:
>
> Seien G die Punkte des Gitters ZxZ und H die Punkte des um 45 Grad
> um den Nullpunkt gedrehten Gitters. Sei Dreh die Drehung G -> H.
> Es gilt Tatsache T:
>
> Für jede Zahl K gibt es einen Punkt p in G, (T)
> dessen Abstand zu Dreh(p) grösser ist als K.
>
> Frage F:
> Gibt es eine Bijektion Bij: G -> H und
> eine Zahl K, so dass für alle p aus G (F)
> der Abstand zu Bij(p) kleiner als K ist?
>
> Schon immer haben mir diese Gitter Freude gemacht, z.B. beim Vorbeifahren
> an den regelmässig aufgestellten Weinstöcken hier am See. Daher habe ich
> mir zur Einstimmung eine Zeichnung gemacht getreu dem Motto M, das ein
> Darmstädter Professor einst oft und gern verwendet haben soll:
>
> Ist von Verständnis
> keine Spur, (M)
> zeichnet man
> 'ne Hilfsfigur.
>
Die Weinstöcke befinden sich mit nur einem Punkt in der Ebene. Sollte
es da noch einen Raum geben, der "jenseits" der Ebene ist, sie aber
einbettet?
Mit freundlichen Grüssen
Hero
Markus Sigg
> Wieder eine wunderschöne Frage von Wolfgang Thumser:
>
> Seien G die Punkte des Gitters ZxZ und H die Punkte des um 45 Grad
> um den Nullpunkt gedrehten Gitters. Sei Dreh die Drehung G -> H.
> Es gilt Tatsache T:
>
> Für jede Zahl K gibt es einen Punkt p in G, (T)
> dessen Abstand zu Dreh(p) grösser ist als K.
>
> Frage F:
> Gibt es eine Bijektion Bij: G -> H und
> eine Zahl K, so dass für alle p aus G (F)
> der Abstand zu Bij(p) kleiner als K ist?
Hallo Rainer,
kann man nicht einfach die Ebene auf zwei Weisen A und B
kacheln, und zwar so, daß jede A-Kachel genau so viele
Punkte von G enthält wie jede B-Kachel Punkte von Dreh(G)?
Und dann geeignet kachelweise zuordnen?
Gruß,
Markus
Rainer Rosenthal
> kann man nicht einfach die Ebene auf zwei Weisen A und B
> kacheln, und zwar so, daß jede A-Kachel genau so viele
> Punkte von G enthält wie jede B-Kachel Punkte von Dreh(G)?
> Und dann geeignet kachelweise zuordnen?
Hallo Markus,
das klingt gut, und Du bist beim Denken offenbar schon
zwei bis drei Schritte voraus. Ich habe gerade ein Maple-
Projekt am Laufen, das mir in verschiedenen Regionen der
Ebene auszählen soll, wie das Verhältnis von G-Punkten zu
H-Punkten dort ist.
Im übrigen bin ich etwas allergisch gegen
"kann man nicht einfach...?".
Zum Glück(?) habe ich jetzt seit einem dreiviertel Jahr
keinen Chef mehr, der mich mit solchen Fragen nervt :-)
Gruss,
Rainer der Designer,
und Ritter der Gitter
.
___________________________.___.______________________________
Rainer Rosenthal . r.ros...@web.de
Markus Sigg
Rainer Rosenthal wrote:
> Markus Sigg schrieb:
>
>> kann man nicht einfach die Ebene auf zwei Weisen A und B
>> kacheln, und zwar so, daß jede A-Kachel genau so viele
>> Punkte von G enthält wie jede B-Kachel Punkte von Dreh(G)?
>> Und dann geeignet kachelweise zuordnen?
>
> Hallo Markus,
>
> das klingt gut, und Du bist beim Denken offenbar schon
> zwei bis drei Schritte voraus. Ich habe gerade ein Maple-
> Projekt am Laufen, das mir in verschiedenen Regionen der
> Ebene auszählen soll, wie das Verhältnis von G-Punkten zu
> H-Punkten dort ist.
ich denke etwa für G an eine quadratische Kachelung, für H an
eine mit gleicher Ausrichtung, Breite und Höhe, aber so
gestaltetem Randverlauf, daß eben gleich viele Punkte drin
liegen wie im gewählten Quadrat. Möglicherweise kann man
in G Mini-Quadrate mit nur einem Punkt nehmen, während für
H etwas komplizierte Objekte nötig sind. Ich hab nicht weiter
drüber nachgedacht, aber Escher läßt grüßen.
> Im übrigen bin ich etwas allergisch gegen
>
> "kann man nicht einfach...?".
Wir ersetzen das "einfach" durch "irgendwie".
> Zum Glück(?) habe ich jetzt seit einem dreiviertel Jahr
> keinen Chef mehr, der mich mit solchen Fragen nervt :-)
Diese ehrenvolle Aufgabe übernehme ich gerne. Herr Rosenthal,
das Modul können wir doch morgen an den Kunden ausliefern,
nicht wahr? Es war schließlich schon auf letzte Woche versprochen,
und wir wollen doch keine Vertragsstrafe riskieren!
Gruß,
Markus
Rainer Rosenthal
> das Modul können wir doch morgen an den Kunden ausliefern,
> nicht wahr?
Hallo Herr M.
selbstverständlich kriegen wir das hin. Wir haben bisher
noch immer alles hingekriegt. Ich habe da auch bereits
eine Idee. Sie muss *nur noch* ausgefeilt werden. Als
Projekt-Betreuer sind Sie ja an den Details vielleicht
nicht so interessiert, aber schon ein Blick auf die
übereinandergelegten Fliegengitter zeigt, dass die Haus-
frauenmethode zum Ziel führen muss, kreisförmig vorgehend
den jeweils nächsten ungepaarten Punkt zu nehmen und ihn
mit dem nächstgelegenen des anderen Gitters zu verbinden.
Ein paar erste Versuche zeigen, dass diese Methode sogar
zu einem K von sqrt(2) führen dürfte. Da wir in unserem
Angebot lediglich "K = endlich" versprochen hatten, können
Sie für morgen schon die Spedition bestellen. Notfalls
liefern wir das mit K=27 aus.
MfG,
Gitterritter
Markus Sigg
Rainer Rosenthal wrote:
> Ein paar erste Versuche zeigen, dass diese Methode sogar
> zu einem K von sqrt(2) führen dürfte. Da wir in unserem
aber nicht daß die Konkurrenz kurz darauf mit einem
kleineren K auf den Markt kommt und unser Geschäft
verdirbt. Nach all den Investitionen in dieses Projekt
müßtest Du Bekanntschaft mit Gittern anderer Art machen.
> Angebot lediglich "K = endlich" versprochen hatten, können
> Sie für morgen schon die Spedition bestellen. Notfalls
> liefern wir das mit K=27 aus.
K=27? Da reicht ja nicht mal ein Mega-LKW:
http://www.spiegel.de/auto/aktuell/0,1518,455471,00.html
Nee nee, ich will bis morgen einen sauberen Beweis für
K<=sqrt(2) sehen. Dann können wir mit einem Kleinwagen
ausliefern.
Gruß,
Markus
Rainer Rosenthal
>
> Nee nee, ich will bis morgen einen sauberen Beweis für
> K<=sqrt(2) sehen. Dann können wir mit einem Kleinwagen
> ausliefern.
>
Wie war das noch mit der Überstunden-Bezahlung? Könnten Sie
sich bitte mit der Finanzabteilung, H. Rudi Menter, in Verbindung
setzen? Aber *seufz* Sie spielen einfach mal wieder auf dem
Motivationsklavier und denken sich, dass unsereins ja auch
noch Spass an sowas hat. Womit Sie mal wieder - wie sich
das für Chefs gehört - Recht haben.
Gruss,
RR
Wolfgang Thumser
> Aber *seufz* Sie spielen einfach mal wieder auf dem
> Motivationsklavier und denken sich, dass unsereins ja auch
> noch Spass an sowas hat.
als weiteren Motivationsschub mag man zur Kenntnis nehmen,
dass die Aufgabe mit dem Schulwissen der elften oder
zwoelften Klasse durchaus fuer eine(n) intelligente(n)
SchuelerIn loesbar ist (na ja, heutzutage vielleicht
nicht mehr...).
Gruss Wolfgang
Ulrich Lange
Wenn das so ist, dann traue ich mich als numerischer Mathematiker auch
mal dran, zumal es sich um Gitter handelt :-)
Sei also G=ZxZ und H die um 45° gedrehte Punktmenge. Als Abkürzung
definiere ich mal:
K:=1/sqrt(2)
Weiter brauche ich die Definition:
dist(h,G) := min {|h-g|, g e G}
Behauptung 1:
Sei h e H beliebig. Es gibt genau ein g e G mit |h-g| = dist(h,G)
Beweis:
Offensichtlich gibt es ein eindeutiges Paar (k,l) e ZxZ gibt mit
h=1/K*(k+l,k-l)
Sei i = [1/K*(k+l)] und j=[1/K*(k-l)] ([]: Gaussklammer), dann liegt
h also innerhalb des Quadrats mit den Ecken (i,j),(i+1,j),(i+1,j+1)
und (i,j+1). Der Abstand von h zu (mindestens) einem dieser Eckpunkte
ist offenbar gleich dist(h,G). Das Zentrum des Quadrats ist aber der
einzige Kandidat für einen Punkt, der zu mehr als einer Ecke den
gleichen Abstand hat, ohne daß es eine andere Ecke gibt, zu der der
Punkt einen geringeren Abstand hat. Das Zentrum des Quadrats
(i+0.5,j+0.5) gehört aber nicht zu H (aufgrund einer Eigenschaft von
K, die man nicht oft genug wiederholen kann ;-) ).
Behauptung 2: Für alle h e H gilt dist(h,G) < K
(Beweis folgt direkt aus der Argumentation zu Behauptung 1)
Die Abbildung p:H -> G, die jedem h e H das p(h) e G mit
|p(h)-h| = dist(h,G) zuordnet ist nach Beh.1 wohldefiniert. Analog zeigt
man, daß die Abbildung q:G -> H, die jedem g e G das q(g) e H mit
|g-q(g)| = dist(g,H) zuordnet, wohldefiniert ist.
Behauptung 3:
Für beliebiges g e G gilt g=p(q(g)). Für beliebiges
h e H gilt h=q(p(h)). Die Abbildungen p,q sind also bijektiv.
Beweis:
Es gilt nach Definition von "dist":
dist(q(g),G)=|p(q(g))-q(g)| <= |q(g)- g|
dist(g,H)=|q(g)-g|<=|p(q(g))-q(g)|
also |p(q(g))-q(g)| = |q(g)-g| = dist(g,H) und nach Behauptung 1
g=p(q(g)).
--
Ulrich Lange
(ulrich punkt lange at mainz bindestrich online punkt de)
Rainer Rosenthal
> Wolfgang Thumser schrieb:
>>als weiteren Motivationsschub mag man zur Kenntnis nehmen,
>>dass die Aufgabe mit dem Schulwissen der elften oder
>>zwoelften Klasse durchaus fuer eine(n) intelligente(n)
>>SchuelerIn loesbar ist (na ja, heutzutage vielleicht
>>nicht mehr...).
Danke, wegen dieses Niveaus habe ich mich ja auch drangetraut :-)
> Sei also G=ZxZ und H die um 45° gedrehte Punktmenge. Als Abkürzung
> definiere ich mal:
> K:=1/sqrt(2)
>
> Weiter brauche ich die Definition:
> dist(h,G) := min {|h-g|, g e G}
>
> Behauptung 1:
> Sei h e H beliebig. Es gibt genau ein g e G mit |h-g| = dist(h,G)
> ... aufgrund einer Eigenschaft von K, die man nicht oft genug
> wiederholen kann ;-) ). *lach*
Ach ja, das ist *der* Trick. Sehr hübsch! Und ich hatte immer Angst,
ich bräuchte einen schlauen Algorithmus, der mir aus den zur Verfügung
stehenden nächsten Kandidaten in pfiffiger Weise einen herauspickt, so
dass ich nicht isolierte Punkte bekomme. Dazu habe ich bereits eine
hübsche Bilderserie, die mir zeigt, wie sich bei konzentrischen Kreisen
um den Ursprung mit den Radien r_{i,j} = sqrt(i^2+j^2)+epsilon die
Kandidaten einfinden, wenn man die Radien allmählich in diesen Stufen
vergrössert. Ich wollte daraus dann den Algorithmus bauen. Tja ...
> Behauptung 2: Für alle h e H gilt dist(h,G) < K
> (Beweis folgt direkt aus der Argumentation zu Behauptung 1)
Ja, das ist auch der Grund, der Christopher Creutzig und mich
auf dieses K = sqrt(2) als obere Schranke kommen liess, denke ich
mal.
> Die Abbildung p:H -> G, die jedem h e H das p(h) e G mit
> |p(h)-h| = dist(h,G) zuordnet ist nach Beh.1 wohldefiniert. Analog zeigt
> man, daß die Abbildung q:G -> H, die jedem g e G das q(g) e H mit
> |g-q(g)| = dist(g,H) zuordnet, wohldefiniert ist.
Statt "analog zeigt man" könnte man auch sagen "aus Symmetriegründen gilt",
aber das ist für Numerische Mathematiker vielleicht kein seriöses
Argument :-)
> Behauptung 3:
> Für beliebiges g e G gilt g=p(q(g)). Für beliebiges
> h e H gilt h=q(p(h)). Die Abbildungen p,q sind also bijektiv.
Ja, gut. Schön ausführlich bewiesen. Der Witz war aber die Idee, *dass* es
nur einen nächsten Nachbarn im anderen Gitter geben kann. Und der Witz
ist saugut. Nicht blamiert bis auf die Knochen aber sehr angerührt durch
die Beschäftigung mit den schön aussehenden Gittern, werde ich mir diese
Aufgabe samt Lösung sicher noch lange merken.
Ich kann jetzt meine Bildchen auch mit Genuss betrachten und mir ausmalen,
wie erfreut ich gewesen wäre, wenn ich den einfachen Algotithmus hätte
finden dürfen. Es ist so richtig schön zu sehen, wie bei dem Zwiebel-
Prinzip manchmal Kandidaten erscheinen, die sich gleich gegenseitig
neutralisieren und wie ein anderes Mal dann erst noch zu warten ist,
bis man mit den Kandidaten der nächsten Schicht die Verbindungen
herstellen kann. Aber alles schön paarweise machbar - daher die einfache
Lösung. Echt gut!
Dir und Wolfgang Thumser einen herzlichen Dank!
(Der Kunde dürfte zufrieden sein ...)
Gruss,
Rainer Rosenthal
r.ros...@web.de
Wolfgang Thumser
die Idee mit dem "nearest neighbour" scheint zunaechst ganz gut,
allerdings gibt es noch Probleme:
> Sei also G=ZxZ und H die um 45° gedrehte Punktmenge. Als Abkürzung
> definiere ich mal:
>
> K:=1/sqrt(2)
>
> Weiter brauche ich die Definition:
>
> dist(h,G) := min {|h-g|, g e G}
>
> Behauptung 1:
> Sei h e H beliebig. Es gibt genau ein g e G mit |h-g| = dist(h,G)
>
> Beweis:
> Offensichtlich gibt es ein eindeutiges Paar (k,l) e ZxZ gibt mit
> h=1/K*(k+l,k-l)
Das soll wohl h=K*(k+l,k-l) heissen, folglich sind die Punkte
h1 = K*(1,1) = (0.7071...,0.7071...) sowie
h2 = K*(2,2) = (1.4142...,1.4142...)
Elemente von H.
> Die Abbildung p:H -> G, die jedem h e H das p(h) e G mit
> |p(h)-h| = dist(h,G) zuordnet ist nach Beh.1 wohldefiniert.
p ist aber nicht injektiv, wegen p(h1) = p(h2) = (1,1). Mit
dem Beweis zu Behauptung 3 kann also etwas nicht stimmen.
Vielleicht kann Rainer mit seinem Maple Programm einmal
diese Ausreisser dingfest machen.
Gruss Wolfgang
Rainer Rosenthal
> Vielleicht kann Rainer mit seinem Maple Programm einmal
> diese Ausreisser dingfest machen.
Hoppla ...
Au ja, gerne! Wie gut, dass das noch vor der Auslieferung
morgen in der Qualitätskontrolle entdeckt wurde!
Gruss,
Rainer (der gerade auf elliptischem Papier Verschiedenes druckt)
Hero
Ja, das war auch mein Gedanke, stereographisch auf eine Kugel
(Ellipsoid) projizieren und
hier den Abstand geodätisch messen/definieren.
Mit freundlichen Grüssen
Hero
Rainer Rosenthal
>
> h1 = K*(1,1) = (0.7071...,0.7071...) sowie
> h2 = K*(2,2) = (1.4142...,1.4142...)
> p(h1) = p(h2) = (1,1). Mit
> Vielleicht kann Rainer mit seinem Maple Programm einmal
> diese Ausreisser dingfest machen.
Wunderbar, da ist tatsächlich was zu denken und es mus
mit Vorsicht verknüpft werden. Ich hatte ja gesagt, dass
ich nach dem Zwiebelprinzip vom Ursprung aus alle Punkte
(sowohl die von G als auch die von H) in Portionen
betrachte und sie zu "neutralisieren" versuche, also
die G-Punkte mit den H-Punkten zu verbinden, so dass
stets kleinste Verbindungen vorkommen.
Meine Befürchtung, dass man da vorsichtig sein müsse,
um nicht durch zu kurzsichtiges Verbinden Isolani zu
erhalten, hat sich bewahrheitet. Oder besser gesagt:
durch kurzgedachtes Verbinden geht die von Ulrich
Langes Ansatz mögliche einfache Struktur evtl. zum
Teufel.
Mit einer kostenlosen ASCII-Grafik erläutere ich gerne
die interessante Situation beim Punkt [1,1].
Da diese aber einen Moment Zeit in Anspruch nimmt und
ich noch kein Abendbrot gegessen habe, kan ich erst mal
nur husch-husch skizzieren (K=1/sqrt(2) wie gehabt):
:
:
: X W
: D C
:
:
:
: Y
:
:
: A B
:
: U V
:
:
:---------------------------------------------------
Aus Gitter G: A=[1,1], B=[2,1], C=[2,2], D=[[1,2]
Aus Gitter H: U=[K,K], Y=[2K,2K], V=[3K/2,K]
W=[3K/2,3K/2], X=[K,3K/2]
Hier ist A=[1,1] und U=h1, Y=h2.
Gut zu sehen: beim zwiebeligen Verbinden wird U,
der innerste Punkt, zuerst mit A verbunden. Dann kommt
Y zum Vorschein und muss noch auf Partner warten. Dieser
Partner kommt aber noch *nicht* direkt in der nächsten
Zwiebelhaut, denn dort neutralisiert man am besten
X mit D und B mit V.
Erst beim nächsten Schritt, wenn C als Kandidat erscheint,
darf (oder sollte) Y verbunden werden!
Eine sehr hübsche Schweinerei, die da ziemlich zu Beginn
der Konstruktion schon auftritt. Wieviel uriger wäre es
jetzt noch, wenn so eine Gemeinheit erst bei [4711,0815]
auftreten würde.
Ha, so durfte ich ja auch noch etwas mitspielen, Klasse!
Und der Zwölftklässler von damals würde auch ganz schön
staunen. Wie hätte wohl dessen wasserdichte Lösung ausgesehen?
Nochmals Dank für die anregende Knobelei,
Herzliche Grüsse,
Rainer
__________________________________________________________
Rainer Rosenthal r.ros...@web.de
Rainer Rosenthal
>>(der gerade auf elliptischem Papier Verschiedenes druckt)
>
>
> Ja, das war auch mein Gedanke, stereographisch auf eine Kugel
> (Ellipsoid) projizieren und
> hier den Abstand geodätisch messen/definieren.
Hihi, nee, so war das nicht gemeint. Ich bezog mich auf die
schönen Referenzen, die Franz Lemmermeyer zum Thema Elliptische
Kurven genannt hatte. Natürlich drucke ich auf recht eckigem
Papier (oder darf man das nach neuer Rechtschreibung noch zusammen
schreiben? (Was schreibe ich da bloss wieder zusammen?)).
Gruss,
Rainer
Rudi Menter
> Natürlich drucke ich auf recht eckigem Papier
> (oder darf man das nach neuer Rechtschreibung noch zusammen schreiben?
> (Was schreibe ich da bloss wieder zusammen?)).
Den Term "recht eckig" jedenfalls nicht, wenn du mich fragst...
fg
--
Wer die Geometrie begreift, vermag
in dieser Welt alles zu verstehen. Galileo Galilei
Rainer Rosenthal
>
> Den Term "recht eckig" jedenfalls nicht, wenn du mich fragst...
>
Ach nee ;-)
Wer die Geometrie begreift, vermag
in dieser Welt alles zu verstehen. Galileo Galilei
Deine Sprüche sind aber immer wieder ganz nett.
Gruss,
RR
--
Alles verstehen heisst alles verzeihen.
Rudi Menter
> Rudi Menter schrieb:
>> Den Term "recht eckig" jedenfalls nicht, wenn du mich fragst...
> Ach nee ;-)
> Wer die Geometrie begreift, vermag
> in dieser Welt alles zu verstehen. Galileo Galilei
> Deine Sprüche sind aber immer wieder ganz nett.
Meine?
> --
> Alles verstehen heisst alles verzeihen.
Na gut, dann geh' ich's mal f^-1 an: Ich verzeihe der Mathematik!
f°g
--
Rainer Rosenthal
>>Deine Sprüche sind aber immer wieder ganz nett.
>
> Meine?
>
"Deine" im Sinne von "Die von Dir verwendeten", wieso
kommst Du eigentlich immer so aus dem Mustopf?
Und "der Mathematik zu verzeihen" ist wieder so ein
Schwachsinn, der die besagte Höchststrafe voll verdient.
Gruss,
RR
Rainer Rosenthal
Ich habe mit mehreren Anläufen versucht, den Beweis der Bijektivität
zu verstehen, um dann die Stelle zu finden, wo er schief läuft.
Ich kapiere aber leider nicht, wie er überhaupt gemeint war :-(
Wieso soll z.B. aus der Definition von "dist" folgen, dass
dist(q(g),G)=|p(q(g))-q(g)| <= |q(g)- g|
gilt?
Und was ist der Grundgedanke des Beweises gewesen? Lass uns noch
einmal das Beispiel von Wolfgang Thumser aufgreifen, das ich so
skizziert hatte:
:
:
: X W
: D C
:
:
:
: Y
:
:
: A B
:
: U V
:
:
:---------------------------------------------------
Aus Gitter G: A=[1,1], B=[2,1], C=[2,2], D=[[1,2]
Aus Gitter H: U=[K,K], Y=[2K,2K], V=[3K/2,K]
W=[3K/2,3K/2], X=[K,3K/2]
Hier ist A=[1,1] und U=h1, Y=h2.
Wo ist hier das h im (i,j)-Quadrat, von dem Du oben
gesprochen hattest?
Ich sehe es nicht. Und ich hätte so gerne mit dem Finger auf
eine verständliche aber falsche Stelle gezeigt.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Wolfgang Thumser
> Ha, so durfte ich ja auch noch etwas mitspielen, Klasse!
> Und der Zwölftklässler von damals würde auch ganz schön
> staunen. Wie hätte wohl dessen wasserdichte Lösung ausgesehen?
tatsaechlich handelte es sich um eine Schuelerin, die sich
der lang vergessenen Strategie erinnerte, ein schwieriges
Problem zunaechst soweit zu vereinfachen, bis man eine
nicht ganz triviale Loesung erkennt. Unser Maedchen suchte
also nach Punktgittern, fuer die eine distanzbeschraenkte
Aequivalenz zum Ausgangsgitter offensichtlich war. Auf welche
Weise, so fragte sie sich, laesst sich das Ausgangsgitter
distanzbeschraenkt in ein anderes Gitter deformieren?
Dieses andere Gitter sollte dabei so einfach wie moeglich
bleiben, aber nicht einfacher. Folgen wir also ihrem Ansatz
erneut, und fragen uns: Gibt es ueberhaupt ein vom quadrati-
schen Ausgangsgitter verschiedenes periodisches Gitter,
auf das es distanzbeschraenkt und bijektiv abgebildet
werden kann?
Und diese Schluesselidee bereitete ihr schliesslich den
Weg zur Loesung: Da die endliche Hintereinanderausfuehrung
distanzbeschraenkter Deformationen wieder distanzbeschraenkt
ist, galt es in einer letzten Anstrengung, das gedrehte
Quadratgitter unter all den Deformationen zu finden...
Gruss Wolfgang
--
in lebendiger Erinnerung an ihre Idee
Rainer Rosenthal
> ..., so fragte sie sich, laesst sich das Ausgangsgitter
> distanzbeschraenkt in ein anderes Gitter deformieren?
> ..., galt es in einer letzten Anstrengung, das gedrehte
> Quadratgitter unter all den Deformationen zu finden...
Hach, das ist richtig schöne Mathematik.
Allerdings kommt nachher die Spedition und holt unsere
Lösung mit dem LKW ab. Und ich muss die Dokumentation noch
überarbeiten. Notfalls muss ich auf den Lieferschein
schreiben, dass die Beschreibung nachgeliefert wird. Das
ist wahrscheinlich nicht dramatisch, weil das Produkt
wohl eh mit anderen Komponenten zusammen eingesetzt
werden wird, die auch alle nicht so ganz fertig sind :-)
Anekdote dazu: wir hatten anno Schnee mal zwei PC's zur
Klima-Regelung in zwei Berufsschulen zu liefern. Als
wir mit Ach und Krach und auf den letzten Drücker dort
zur Inbetriebnahme antanzten, war der Rohbau noch nicht
mal soweit fertig, dass wir unser System dort in einem
abschliessbaren Raum deponieren konnten.
Ich werde die Geschichte von dem klugen Mädchen sicher
im Hinterkopf behalten, muss aber doch durch genaue
Betrachtung meiner "Zwiebelringe" zu einer ordentlichen
Bijektionsbeschreibung durchdringen.
Gruss,
Rainer .
. .
_________________________.___.___._______________________
Rainer Rosenthal . . r.ros...@web.de
.
Ulrich Lange
> Ulrich Lange schrieb:
>>Wolfgang Thumser schrieb:
[...]
Hallo Rainer, Hallo Wolfgang!
>
>>Die Abbildung p:H -> G, die jedem h e H das p(h) e G mit
>>|p(h)-h| = dist(h,G) zuordnet ist nach Beh.1 wohldefiniert. Analog zeigt
>>man, daß die Abbildung q:G -> H, die jedem g e G das q(g) e H mit
>>|g-q(g)| = dist(g,H) zuordnet, wohldefiniert ist.
>
> Statt "analog zeigt man" könnte man auch sagen "aus Symmetriegründen gilt",
> aber das ist für Numerische Mathematiker vielleicht kein seriöses
> Argument :-)
Leider scheint genau dieser Analogie- bzw. Symmetrieschluß tatsächlich
kein seriöses Argument gewesen zu sein, wie Wolfgangs Gegenbeispiel
zeigt. :-(
Mein Argument für die Wohldefiniertheit von p beruht ja darauf, daß nur
höchstens eine Ecke des "Integerquadrats" in dem h liegt, die
Minimaleigenschaft hat, denn sonst müsste h ja auf einer der
Mittelsenkrechten des Quadrats liegen, was nicht sein kann, da beide
Koordinaten von h -- im Gegensatz zu Punkten auf der Mittelsenkrechten
irrational sind.
Dieser Schluß läßt sich nicht so einfach "symmetrisch" auf dist(g,H)
anwenden, da der "Mittelwert" zweier rationaler Punkte natürlich immer
rational sein muß, aber der "Mittelwert" zweier irrationaler Punkte
durchaus auch rational sein kann, wie Wolfgangs Gegenbeispiel zeigt.
Der Fehler liegt also nicht im Beweis von Behauptung 3, sondern sogar
schon der Übertragung von Behauptung 1 auf dist(g,H). Mein p ist
wohldefiniert, mein q aber nicht.
Rainer Rosenthal
> Der Fehler liegt also nicht im Beweis von Behauptung 3, sondern sogar
> schon der Übertragung von Behauptung 1 auf dist(g,H). Mein p ist
> wohldefiniert, mein q aber nicht.
Hallo Ulrich,
ich würde das gerne mit Dir per Mail besprechen. Ich habe
nämlich auch die neue Argumentation nicht verstanden.
Es ging doch nicht um die Wohldefiniertheit sondern um
die Bijektionseigenschaft, denke ich.
Das Beispiel von Wolfgang, zu dem ich gerne noch einmal
meine kostenlose ASCII-Grafik dazugebe, ist:
===========================================================
:
:
: X W
: D C
:
:
:
: Y
:
:
: A B
:
: U V
:
:
:---------------------------------------------------
Aus Gitter G: A=[1,1], B=[2,1], C=[2,2], D=[[1,2]
Aus Gitter H: U=[K,K], Y=[2K,2K], V=[3K/2,K]
W=[3K/2,3K/2], X=[K,3K/2]
Hier ist A=[1,1] und U=h1, Y=h2.
===========================================================
U und Y gehören zum Gitter H und sie haben beide den Punkt A
als nächsten Nachbarn in H. Somit ist schon die Injektivität
von "Punkt in H ----> nächster Nachbar in G" nicht erfüllt.
Ich bin leider wegen anderer Geschäfte noch nicht dazu
gekommen, den Algorithmus wasserdicht zu bekommen, der ja
sehr wohl auf dem von Dir aufgezeigten Weg arbeiten kann,
halt mit passender Vorsichtsmassnahme und Geduld beim Verbinden.
Wenn Du Maple hast, dann schiebe ich Dir gerne auch mein
Arbeitsblatt per Mail zu. Schön aussehen tun die übereinander
gelegten Gitter allemal.
Ulrich Lange
> Ulrich Lange schrieb:
>
>
>>Für beliebiges g e G gilt g=p(q(g)). Für beliebiges
>>h e H gilt h=q(p(h)). Die Abbildungen p,q sind also bijektiv.
>>
>>Beweis:
>>
>>Es gilt nach Definition von "dist":
>>
>>dist(q(g),G)=|p(q(g))-q(g)| <= |q(g)- g|
>>dist(g,H)=|q(g)-g|<=|p(q(g))-q(g)|
>>
>>also |p(q(g))-q(g)| = |q(g)-g| = dist(g,H) und nach Behauptung 1
>>g=p(q(g)).
>>
>>
> Ich habe mit mehreren Anläufen versucht, den Beweis der Bijektivität
> zu verstehen, um dann die Stelle zu finden, wo er schief läuft.
Es ist auch kein Fehler im Beweis der Bijektivität. Mein Fehler war
schon vorher. Siehe meine andere Antwort an Dich.
> Ich kapiere aber leider nicht, wie er überhaupt gemeint war :-(
>
> Wieso soll z.B. aus der Definition von "dist" folgen, dass
>
> dist(q(g),G)=|p(q(g))-q(g)| <= |q(g)- g|
>
> gilt?
Das Problem ist, daß die Abbildung q (im Gegensatz zu p) nicht
wohldefiniert ist, wie mir Wolfgang klargemacht hat.
Falls q(g) eine wohldefiniertes Element aus H wäre, wäre obiger Schluß
allerdings trivial: Nach Definition von p ist p(q(g)) das Element von G,
daß zu q(g) e H den kleinsten Abstand ("dist(q(g),G)") hat. Alle anderen
Elemente von G - inklusive g - haben einen Abstand von q(g), der größer
oder gleich dist(q(g),G) ist.
> Und was ist der Grundgedanke des Beweises gewesen? Lass uns noch
> einmal das Beispiel von Wolfgang Thumser aufgreifen, das ich so
> skizziert hatte:
>
> :
> :
> : X W
> : D C
> :
> :
> :
> : Y
> :
> :
> : A B
> :
> : U V
> :
> :
> :---------------------------------------------------
> Aus Gitter G: A=[1,1], B=[2,1], C=[2,2], D=[[1,2]
> Aus Gitter H: U=[K,K], Y=[2K,2K], V=[3K/2,K]
> W=[3K/2,3K/2], X=[K,3K/2]
>
> Hier ist A=[1,1] und U=h1, Y=h2.
>
> Wo ist hier das h im (i,j)-Quadrat, von dem Du oben
> gesprochen hattest?
Das Quadrat ABCD in deiner Zeichnung ist z.B. in meiner Terminologie das
(i,j)-Quadrat für den Punkt Y. Der eindeutige nächste Nachbar von Y ist
A.
> Ich sehe es nicht. Und ich hätte so gerne mit dem Finger auf
> eine verständliche aber falsche Stelle gezeigt.
Hast Du ja: Gleich in Deiner ersten Antwort, als Du mich (scherzhaft)
gefragt hast, ob Symmetrieargumente seriös genug für numerische
Mathematiker sind :-(
Wolfgang Thumser
> Der Fehler liegt also nicht im Beweis von Behauptung 3, sondern sogar
> schon der Übertragung von Behauptung 1 auf dist(g,H). Mein p ist
> wohldefiniert, mein q aber nicht.
ich denke schon, dass der Fehler im Beweis zu Behauptung 3
liegt. Dein Symmetrieargument zu Behauptung 1 zieht, ansonsten
sollte sich ein g in G finden lassen, welchem kein eindeutiges
h aus H zugeordnet werden kann, und welches g sollte das sein?
Gruss Wolfgang
Rainer Rosenthal
>>Ich sehe es nicht. Und ich hätte so gerne mit dem Finger auf
>>eine verständliche aber falsche Stelle gezeigt.
>
>
> Hast Du ja: Gleich in Deiner ersten Antwort, als Du mich (scherzhaft)
> gefragt hast, ob Symmetrieargumente seriös genug für numerische
> Mathematiker sind :-(
>
Hallo Ulrich,
das war wirklich als Scherz gedacht und nicht als Kritik. Ich habe
darauf abgezielt, dass eine Argumentation, die Du für G in Bezug auf H
führst, automatisch auch umgekehrt gelten muss. Denn so wie H das
gegenüber G um 45 Grad gedrehte Gitter ist, so ist auch G das gegen-
über H um 45 Grad gedrehte Gitter. Und wenn "g --> h=next(g) in H"
was Schönes ist, dann ist auch "h --> g=next(h) in G" was Schönes.
Es ist die Bijektivität, die noch etwas quietscht. Das hat ja eben
auch Wolfgang Thumser nochmal bestätigt.
Was die Innereien und die Reparatur bzw. "Auslieferbarkeit" betrifft,
würde ich mich über Mail von Dir freuen. Es schwätzt sich da
bequemer als so in der Öffentlichkeit.
Ulrich Lange
> Ulrich Lange schrieb:
>
>
>>Der Fehler liegt also nicht im Beweis von Behauptung 3, sondern sogar
>>schon der Übertragung von Behauptung 1 auf dist(g,H). Mein p ist
>>wohldefiniert, mein q aber nicht.
>
>
> Hallo Ulrich,
>
> ich würde das gerne mit Dir per Mail besprechen. Ich habe
> nämlich auch die neue Argumentation nicht verstanden.
Gerne. Meine e-Mail-Adresse steht (mit offensichtlichen Ersetzungen) in
der Signatur. Für heute muß ich den Rechner allerdings gleich
ausschalten. Antworten kann ich also erst morgen.
> Es ging doch nicht um die Wohldefiniertheit sondern um
> die Bijektionseigenschaft, denke ich.
Wolfgang hat vermutet, daß der Bijektionsbeweis falsch ist. Das ist er
m.E. aber letztlich deshalb, weil ich darin die Abbildung q verwende,
die nicht wohldefiniert ist (Die Katze beißt sich hier etwas in den
Schwanz: q ist nicht wohldefiniert, weil p nicht injektiv ist).
> Das Beispiel von Wolfgang, zu dem ich gerne noch einmal
> meine kostenlose ASCII-Grafik dazugebe, ist:
>
>
> ===========================================================
> :
> :
> : X W
> : D C
> :
> :
> :
> : Y
> :
> :
> : A B
> :
> : U V
> :
> :
> :---------------------------------------------------
> Aus Gitter G: A=[1,1], B=[2,1], C=[2,2], D=[[1,2]
> Aus Gitter H: U=[K,K], Y=[2K,2K], V=[3K/2,K]
> W=[3K/2,3K/2], X=[K,3K/2]
>
> Hier ist A=[1,1] und U=h1, Y=h2.
> ===========================================================
>
> U und Y gehören zum Gitter H und sie haben beide den Punkt A
> als nächsten Nachbarn in H. Somit ist schon die Injektivität
> von "Punkt in H ----> nächster Nachbar in G" nicht erfüllt.
Ja. Wenn ich auch erstmal so ein Bild gemalt hätte, hätte ich auch
sofort gesehen, daß p zwar wohldefiniert, aber nicht injektiv ist. Und
das meine Idee hier schon zusammenbricht. Stattdessen habe ich mich auf
das dünne Eis "Die Abbildung q:G->H kann ich ja genauso konstruieren"
begeben, und hatte so plötzlich ein "Wundermittel" an der Hand, mit dem
ich die falschesten Sachen (eben die vermeintliche "Bijektivität" von p)
beweisen konnte.
> Ich bin leider wegen anderer Geschäfte noch nicht dazu
> gekommen, den Algorithmus wasserdicht zu bekommen, der ja
> sehr wohl auf dem von Dir aufgezeigten Weg arbeiten kann,
> halt mit passender Vorsichtsmassnahme und Geduld beim Verbinden.
> Wenn Du Maple hast, dann schiebe ich Dir gerne auch mein
> Arbeitsblatt per Mail zu. Schön aussehen tun die übereinander
> gelegten Gitter allemal.
>
Maple habe ich leider nicht. Meine Idee habe ich auch noch nicht völlig
aufgegeben. Ich habe so das Gefühl, daß es ausreichen könnte, die
"Diagonalen" in ZxZ (also die Punkte (k,k)) gesondert zu behandeln.
Wolfgang Thumser
> Was die Innereien und die Reparatur bzw. "Auslieferbarkeit" betrifft,
> würde ich mich über Mail von Dir freuen. Es schwätzt sich da
> bequemer als so in der Öffentlichkeit.
Ich halte das auch fuer eine gute Idee, vielleicht teilt ihr aber
am Ende mit, was bei Eurer Untersuchung herausgekommen ist.
Noch eins: Ich habe die groesste Hochachtung vor Ulrichs Bereitschaft,
konstruktiv an einer Loesung zu arbeiten und seine Ideen zu prae-
sentieren (etwas, was ich von vielen anderen nicht sagen kann). Wie
wir alle wissen, bestehen 95% aller mathematischer Ideen aus wilden
Vermutungen und abwegigen Ideen. Und wenn man schon an einer Diskussion
und keinen fertigen Ergebnissen interessiert ist, dann muss man auf
Korrekturen gefasst sein.
Gruss Wolfgang
Klaus Nagel
>
> Noch eins: Ich habe die groesste Hochachtung vor Ulrichs Bereitschaft,
> konstruktiv an einer Loesung zu arbeiten und seine Ideen zu prae-
> sentieren (etwas, was ich von vielen anderen nicht sagen kann).
Hallo Wolfgang,
dann will ich auch einmal meine unausgegorenen Gedanken zu diesem
Problem darlegen:
Ich zeichne die beiden Gitter in ein kartesisches Koordinatensystem,
wobei ich aus Symmetriegründen ein Gitter um 22.5° nach rechts, das
andere um 22.5° nach links drehe. Die Rasterpunkte sind blau und rot im
Bild
http://nagel-klaus.homepage.t-online.de/Zwei_Gitter.jpg
dargestellt.
Betrachte man Streifen
a < y <= a + cos(22.5°) für beliebiges a und ordnet man die Gitterpunkte
nach ihren x-Koordinaten, so wechseln fast immer die beiden Rastertypen
ab. Ein solcher Streifen ist im Bild weiß gezeichnet, die
hineinfallenden Gitterpunkte als Vollkreise in der entsprechende Farbe.
Wenn es das "fast" nicht gäbe und wenn das Abwechseln bewiesen wäre,
dann hätte man eine Bijektion.
Gruß,
Klaus Nagel
Klaus
[...]
> Noch eins: Ich habe die groesste Hochachtung vor Ulrichs Bereitschaft,
> konstruktiv an einer Loesung zu arbeiten und seine Ideen zu prae-
> sentieren (etwas, was ich von vielen anderen nicht sagen kann). Wie
> wir alle wissen, bestehen 95% aller mathematischer Ideen aus wilden
> Vermutungen und abwegigen Ideen. Und wenn man schon an einer Diskussion
> und keinen fertigen Ergebnissen interessiert ist, dann muss man auf
> Korrekturen gefasst sein.
Noch eine Idee:
http://home.wtal.de/klaus/idee3.png
Erlaeuterungen:
- die Gitter werden als Kreispackungen aufgefasst
- dargestellt ist der Dreh- bzw. Nullpunkt (grau) und der
anschliessende Teil einer Achtelsebene
- die Verhaeltnisse in allen 8 Achtelsebenen sollen symmetrisch bzw.
analog sein.
- das erste Bild zeigt die "gedrehte" Kreispackung
- die gedrehte Kreispackung soll Schritt fuer Schritt (Bild fuer Bild)
in eine ungedrehte Kreispackung verwandelt werden
- rote Kreise sind die, die nach oben (hier immer unter 45 deg)
verschoben werden
- blaue Kreise sind die, die nach unten verschoben werden
- Ziel ist es die Summe der Verschiebungen (d.h. bis der Kreis seine
Endposition erreicht hat) so gering wie moeglich zu halten.
- Vage Hypothese: ab einem bestimmten Schritt ergibt sich eine einfache
Strategie des Kreise-Schiebens mit entsprechend einfacher Eingrenzung
der maximal erforderlichen Verschiebung.
So weit, so fern :-)
Gruss
-- Klaus
Wolfgang Thumser
> Ich zeichne die beiden Gitter in ein kartesisches Koordinatensystem,
> wobei ich aus Symmetriegründen ein Gitter um 22.5° nach rechts, das
> andere um 22.5° nach links drehe. Die Rasterpunkte sind blau und rot im
> Bild
>
> http://nagel-klaus.homepage.t-online.de/Zwei_Gitter.jpg
>
> dargestellt.
> Betrachte man Streifen
>
> a < y <= a + cos(22.5°) für beliebiges a und ordnet man die Gitterpunkte
> nach ihren x-Koordinaten, so wechseln fast immer die beiden Rastertypen
> ab. Ein solcher Streifen ist im Bild weiß gezeichnet, die
> hineinfallenden Gitterpunkte als Vollkreise in der entsprechende Farbe.
>
> Wenn es das "fast" nicht gäbe und wenn das Abwechseln bewiesen wäre,
> dann hätte man eine Bijektion.
Als ich mit dem Problem erstmalig konfrontiert wurde, hatte ich eine
aehnliche Idee. Ich erinnere mich vage, dass es auf eine Bestimmung
der Folge a_j = {k*i|k in |N} n [j,j+1) mit irrationalem i hinauslief
(unter Verwendung der Kettenbruchentwicklung fuer i).
Ich konnte mit dieser Methode schliesslich die Aequivalenz der Gitter
G und {(sqrt(2)*i,1/sqrt(2)*j)|i,j in Z} zeigen. Fuer gedrehte Gitter
hatten wir damals nicht weiter darueber nachgedacht, aber vielleicht
ist da noch was zu machen.
Gruss Wolfgang
Rainer Rosenthal
> Noch eine Idee:
> http://home.wtal.de/klaus/idee3.png
>
> So weit, so fern :-)
>
Ich bin von meiner Zwiebelidee immer mehr begeistert.
Besonders jetzt, wo ich die dazukommenden Gitterpunkte von
G und von H sehr schön einfach beschreiben kann.
Dabei kann bei grösseren Radien durchaus was passieren,
was bedacht sein will. Wenn man z.B. knapp über Radius
von Wurzel aus 50 hinausgeht, dann bekommt man nicht nur
den G-Punkt [5,5] herein sondern wegen 5^2+5^2 = 1^2+7^2
auch die Punkte [1,7] und [7,1]. Ich habe mich dabei
auf den ersten Quadranten beschränkt.
Sehr nett ist die Beschreibung der hereinkommenden
H-Punkte als [0,10], [10,0], [8,6], [6,8]. Dabei
sind die Einträge mit sqrt(2)/2 multipliziert zu denken.
Für einen robusten Algorithmus zur Bijektionsherstellung
könnte ich mir vorstellen, dass die Kreismethode Vorzüge
hat vor der Streifenmethode. Es gibt weniger Überraschungen,
weil die beiden Gitter ja durch Drehung auseinander
hervorgehen.
Deine Idee, beide gleichberechtigt erscheinen zu lassen
mit der 22,5 Grad Methode hat auch was sehr Interessantes.
Es ist aber deutlich zu spät, um ausser Allgemeinplätzen
noch was loszuwerden.
Ulrich Lange
Hallo Wolfgang + Rainer,
danke für das Kompliment, Wolfgang. Ich würde wirklich gerne noch
verstehen, wo genau mein Beweis schiefgeht, denn man lernt ja aus seinen
eigenen Fehlern am meisten. Mittlerweile ist mir klar, daß ich gestern
gleichzeitig verwirrt und voreilig war: q:G->H ist natürlich genauso
wohldefiniert wie p:H->G. Man kann das Beweisargument (Punkte, die auf
dem Rand der "Voronoi-Zelle" eines Punkts aus ZxZ liegen, haben
mindestens eine rationale Koordinate) ja in gedrehten Koordinaten
anwenden. Also muß der Fehler im Beweis von Behauptung 3 liegen, den ich
hier nochmal detailliert rekapituliere:
1. Die beiden Bedingungen: p o q = id_G und q o p = id_H sind
hinreichend für Bijektion.
2. Sei g e G beliebig. Nach Definition von p ist p(q(g)) der nächste
Nachbar aus G des Punkts q(g) aus H: |p(q(g))-q(g)| = dist(q(g),G)
3. Wenn p(q(g)) der nächste Nachbar ist, hat jeder Punkt von G, also
auch g, größeren oder gleichen Abstand:
|p(q(g))-q(g)| <= |q(g)- g|
4. Nach Definition von q ist q(g) der nächste Nachbar aus H des Punkts
g aus G: |q(g)-g| <= dist(g,H)
5. Wenn q(g) aber der nächste Nachbar ist, hat jeder Punkt von G, also
auch p(q(g)), größeren oder gleichen Abstand:
|q(g)-g|<=|p(q(g))-q(g)|
6. Aus 3.+5. folgt |p(q(g))-q(g)| = |q(g)-g|
7. Da p(q(g)) das *nach Behauptung 1 eindeutige* Element von G ist, daß
zu q(g) minimalen Abstand hat, aber g den gleichen Abstand hat, muß
p(q(g)) = g gelten.
8. q o p = id_H zeigt man analog (mit Symmetrieargumenten bin ich jetzt
wieder mutiger :-) )
In welchem dieser 8 Schritte liegt der Fehler? Ich stehe auf dem Schlauch.
Klaus Nagel
> Ich zeichne die beiden Gitter in ein kartesisches Koordinatensystem,
> wobei ich aus Symmetriegründen ein Gitter um 22.5° nach rechts, das
> andere um 22.5° nach links drehe. Die Rasterpunkte sind blau und rot im
> Bild
>
> http://nagel-klaus.homepage.t-online.de/Zwei_Gitter.jpg
>
> dargestellt.
> Betrachte man Streifen
>
> a < y <= a + cos(22.5°) für beliebiges a und ordnet man die Gitterpunkte
> nach ihren x-Koordinaten, so wechseln fast immer die beiden Rastertypen
> ab. Ein solcher Streifen ist im Bild weiß gezeichnet, die
> hineinfallenden Gitterpunkte als Vollkreise in der entsprechende Farbe.
>
> Wenn es das "fast" nicht gäbe und wenn das Abwechseln bewiesen wäre,
> dann hätte man eine Bijektion.
Ich denke ich habe jetzt den Beweis nach diesem Ansatz gefunden.
Wegen der Symmetrie genügt es die Bijektion in der Halbebene x >= 0 zu
finden. Wir betrachten nur eines der Gitter.
Akkürzung: c = cos(22.5°), s = sin(22.5°).
(x_i, y_i) seien die Koordinaten der Gitterpunkte im Streifen
a < y <= a + c, mit x_0 < x_1 < x_2 ....
Die Koordinaten berechnen sich rekursiv:
/ x_i + c , wenn y_i+s < a+c;
x_(i+1) = (
\ x_i + c + s sonst
/ y_i + s , wenn y_i+s < a+c;
y_(i+1) = (
\ y_i - c + s sonst
Daraus ergibt sich
x_i = x_0 + i*c + k*s, wobei k die Anzahl der "sonst"-Fälle ist, also
y_i = y_0 + i*s - k*c oder k = (i*s + y_0 - y_i)/c
Daher
x_i = x_0 + i*c + (i*s + y_0 - y_i)*s/c
Für das andere Gitter (bezeichnet mit u und v) gilt das gleiche
Bildungsgesetz und daher
u_i = u_0 + i*c + (i*s + v_0 - v_i)*s/c
Die Differenzen |x_i - u_i| sind beschränkt, denn |y_i - y_0| und
|u_i - u_0| sind beide durch die Streifenbreite c beschränkt, während
die Anfangswerte x_0 und u_0 höchstens um c+s von einander abweichen.
Die Zuordnung der Gitterpunkte mit gleichen Indizes ist daher eine
abstandsbeschränkte Bijektion.
Gruß,
Klaus Nagel
PS: Normierung mit 1/c vereinfacht das Ganze.
Wolfgang Thumser
ich habe den Beweis kurz ueberflogen und denke, das sieht sehr gut aus.
Kannst Du vielleicht noch eine obere Schranke fuer den Abstand angeben,
dann koennen wir sie mit der Konstruktion, die das Maedchen damals vor-
schlug, vergleichen (ich werde diese dann auch noch angeben). Auf jeden
Fall gilt es, sqrt(5)/2 (der Wert fuer 45 Grad ist sogar noch etwas
kleiner, aber komplizierter) zu unterbieten.
Gruss Wolfgang
Ulrich Lange
Hallo Wolfgang, Klaus und Rainer,
ich habe Deinen (Klaus) Beweis noch nicht vollständig nachvollzogen,
aber Deine Ausgangsidee, zwei um +/- 22.5° gedrehte Gitter zu
betrachten, könnte auch meinen Beweisversuch mit den Voronoi-Zellen
"retten" (wenn ich nicht schon wieder einen Denkfehler mache, immerhin
habe ich diesmal zuerst ein Bild angeschaut):
Sei H das um 22.5° gedrehte Gitter, G das um -22.5° gedrehte Gitter.
Wir betrachten die Voronoi-Zellen(*) der *ungedrehten* Punktmenge ZxZ.
Vermutung: in jeder dieser Voronoi-Zellen liegt genau ein Element aus G
und genau ein Element aus H. Dies wäre dann die Bijektion G->H
Jetzt gilt es noch, die Vermutung zu beweisen...
(*) Die Voronoi-Zelle eines Punktes (i,j) sind diejenigen Punkte aus |R²
für die (i,j) der nächste Nachbar aus ZxZ ist. D.h. also: das Quadrat
mit den Ecken (i-0.5,j-0.5),(i-0.5,j+0.5),(i+0.5,j+0.5),(i+0.5,j-0.5)
Wolfgang Thumser
ich zitiere die Stellen, die einer genaueren Analyse beduerfen, alle
anderen Schritte sind klar. Ausserdem hebe ich kritische Stellen hervor
(mit '*...*').
> 2. Sei g e G beliebig. Nach Definition von p ist p(q(g)) der nächste
> Nachbar aus G *des Punktes q(g) aus H*: |p(q(g))-q(g)| = dist(q(g),G)
> 3. Wenn p(q(g)) der nächste Nachbar aus G *des Punktes q(g) aus H* ist, hat
> jeder Punkt von G, also auch g, größeren oder gleichen Abstand
> *vom Punkt q(g) aus H*: |p(q(g))-q(g)| <= |q(g)- g|.
Das sehe ich auch so. Jetzt wird's spannend:
> 4. Nach Definition von q ist q(g) der nächste Nachbar aus H *des Punktes
> g aus G*: |q(g)-g| = dist(g,H)
Exactly, the plot thickens:
> 5. Wenn q(g) aber der nächste Nachbar aus H *des Punktes g aus G* ist,
und hier muesste es weiter gehen:
hat jeder Punkt von H, also auch *... in H* groesseren oder gleichen
Abstand *von g*.
Aber das wuerde nicht helfen. Tatsaechlich geht es weiter:
> hat jeder Punkt von G, also auch p(q(g)), größeren oder gleichen Abstand
> *von was?*: |q(g)-g|<=|p(q(g))-q(g)|
Es ist exakt dieser Schluss, der nicht mehr gerechtfertigt ist.
Gruss Wolfgang
Klaus Nagel
> Kannst Du vielleicht noch eine obere Schranke fuer den Abstand angeben,
> dann koennen wir sie mit der Konstruktion, die das Maedchen damals vor-
> schlug, vergleichen (ich werde diese dann auch noch angeben). Auf jeden
> Fall gilt es, sqrt(5)/2 (der Wert fuer 45 Grad ist sogar noch etwas
> kleiner, aber komplizierter) zu unterbieten.
Hallo Wolfgang,
meine Schranke ist schlechter: 1.547061
Gruß,
Klaus Nagel
Ulrich Lange
Hallo Wolfgang,
vielen Dank, daß Du Dir die Mühe gemacht hast, das durchzugehen. Man
wird ja leicht ein bischen "betriebsblind", was die eigenen Fehlschlüsse
angeht...
>
>>5. Wenn q(g) aber der nächste Nachbar aus H *des Punktes g aus G* ist,
>
>
> und hier muesste es weiter gehen:
> hat jeder Punkt von H, also auch *... in H* groesseren oder gleichen
> Abstand *von g*.
Unfaßbar, daß ich da 'ne gute halbe Stunde draufgestarrt habe, und das
nicht gesehen habe...
> Aber das wuerde nicht helfen. Tatsaechlich geht es weiter:
>> hat jeder Punkt von G, also auch p(q(g)), größeren oder gleichen Abstand
>> *von was?*: |q(g)-g|<=|p(q(g))-q(g)|
>
>
> Es ist exakt dieser Schluss, der nicht mehr gerechtfertigt ist.
Ich tröste mich mit einem Spruch, den ich von einem Freund kenne, der
ein noch angewandterer Mathematiker als ich ist:
"A programmer is a person who rejoices if he finds an error in his work"
Außerdem habe ich Hoffnung, daß der neue Voronoi-Ansatz, auf den mich
Klaus' Beweis gebracht hat, funktioniert und dann sogar K=sqrt(2), also
etwas besser also Klaus' Schranke liefert.
(Plottet Euch mal das um 22.5° gedrehte Gitter und das um -22.5°
gedrehte Gitter in ein Linienraster mit horizontalen und vertikalen
Linien bei x=i+0.5 und y=j+0.5 (i,j e Z). In jedem Kästchen des
Linienrasters findet sich jeweils ein (und nur ein!) Punkt aus dem um
22.5° gedrehten Gitter und aus dem um -22.5 gedrehten Gitter. Ich
schicke Euch den Plot auch gerne per Mail, wenn gewünscht).
Gruß,
Ulrich
Wolfgang Thumser
>> Kannst Du vielleicht noch eine obere Schranke fuer den Abstand angeben,
>> dann koennen wir sie mit der Konstruktion, die das Maedchen damals vor-
>> schlug, vergleichen (ich werde diese dann auch noch angeben).
ich habe mir ihre Konstruktion noch einmal vergegenwaertigt. Sie ist
geradezu ein geometrischer Geniestreich. Wir gehen aus von dem
Standardgitter, welches durch die kanonischen Vektoren e1 und e2
aufgespannt wird; dieses gilt es in das um 45 Grad gedrehte Gitter
zu ueberfuehren, welches von den orthogonalen Vektoren b1 und b2
bestimmt wird. Solche Gitter sollen "wackelaequivalent" heissen,
wenn sie bijektiv und abstandsbeschraenkt aufeinander abbildbar
sind.
Zunaechst ueberlegt man sich, dass eine Scherung entlang einer
durch bspw. e1 bestimmten Scherachse ein Gitter in ein zu ihm
wackelaequivalentes ueberfuehrt. Zwar werden weit von der Scher-
achse entfernte Punkte durch die Scherung weit bewegt, allerdings
werden die zu bspw. e1 parallelen aequidistanten Punktreihen durch
die Scherung auf sich verschoben, so dass die Distanz nie groesser
als die Haelfte des Abstandes zweier benachbarter Punkte der Punkt-
reihe ausfaellt.
Es bleibt zu zeigen, wie Die Drehung D durch Hintereinander-
ausfuehrung von Scherungen zustande kommt (hier spielt
ebenfalls der Winkel von 22.5 Grad eine Rolle, und vielleicht ist
das kein Zufall). Zunaechst schert man entlang der durch e2 bestimmten
Scherachse e1 in e1', welcher mit e1 einen Winkel von 22.5 Grad
einschliesst (S1). e1' ist dann parallel zu b2-e2. Folglich kann
entlang der durch e1' bestimmten Scherachse e2 in b2 ueberfuehrt
werden (S2). Danach ist b2 parallel zu b1-e1' und es kann entlang
der von b2 bestimmten Scherachse der Vektor e1' in b1 ueberfuehrt
werden (S3). Es folgt D = S3 S2 S1 und da die Hintereinanderausfuehrung
distanzbeschraenkter Abbildungen diese Eigenschaft respektiert, ist
der Beweis erbracht (und alles ohne Rechnung).
>> Auf jeden Fall gilt es, sqrt(5)/2 (der Wert fuer 45 Grad ist sogar
>> noch etwas kleiner, aber komplizierter) zu unterbieten.
Die genaue Analyse des Verfahrens ergibt dann diese Schranke.
> meine Schranke ist schlechter: 1.547061
Vielleicht liegt noch Potential in Deiner Methode, auch Ulrich
arbeitet ja auch an einer Anpassung. Wir haben seinerzeit einen
Nachbarschaftsgraphen mit Distanzbeschraenkungen betrachtet
und eine Implementierung des Hall Algorithmus' auf einem 1000x1000
Gitter zeigte, dass die obere Schranke fast optimal ist. Genaueres
findet sich unter
<http://portal.acm.org/citation.cfm?id=971651.971657&coll=&dl=acm&CFID=15151515&CFTOKEN=6184618>,
aber ich hab' auch noch Kopien bei Interesse.
Gruss Wolfgang
Wolfgang Thumser
> vielen Dank, daß Du Dir die Mühe gemacht hast, das durchzugehen. Man
> wird ja leicht ein bischen "betriebsblind", was die eigenen Fehlschlüsse
> angeht...
Das geht mir auch so. Man sieht den sprichwoertlichen Splitter im Auge
des Bruders viel leichter...
>> Aber das wuerde nicht helfen. Tatsaechlich geht es weiter:
>>> hat jeder Punkt von G, also auch p(q(g)), größeren oder gleichen Abstand
>>> *von was?*: |q(g)-g|<=|p(q(g))-q(g)|
Die Tatsache, dass q(g) unter allen Kandidaten der mit kleinstem
Abstand zu g ist, verleitet zu der Annahme, auch g muesse unter
allen Kandidaten der mit kleinstem Abstand zu q(g) sein; aber das
muss nicht stimmen, wie das Gegenbeispiel zeigt.
> (Plottet Euch mal das um 22.5° gedrehte Gitter und das um -22.5°
> gedrehte Gitter in ein Linienraster mit horizontalen und vertikalen
> Linien bei x=i+0.5 und y=j+0.5 (i,j e Z). In jedem Kästchen des
> Linienrasters findet sich jeweils ein (und nur ein!) Punkt aus dem um
> 22.5° gedrehten Gitter und aus dem um -22.5 gedrehten Gitter. Ich
> schicke Euch den Plot auch gerne per Mail, wenn gewünscht).
Den wuerde mein Spam Filter nicht durchlassen, kannst Du ihn ins Netz
stellen?
Gruss Wolfgang
Klaus Nagel
> (Plottet Euch mal das um 22.5° gedrehte Gitter und das um -22.5°
> gedrehte Gitter in ein Linienraster mit horizontalen und vertikalen
> Linien bei x=i+0.5 und y=j+0.5 (i,j e Z). In jedem Kästchen des
> Linienrasters findet sich jeweils ein (und nur ein!) Punkt aus dem um
> 22.5° gedrehten Gitter und aus dem um -22.5 gedrehten Gitter. Ich
> schicke Euch den Plot auch gerne per Mail, wenn gewünscht).
>
Hallo Ulrich,
schick mir bitte den Plot. Ich habe an der Behauptung Zweifel, denn mit
c = cos(22.5°) und s = sin(22.5°) gilt:
59*c = 54.5089
60*c = 55.4328
59*s = 22.5783
60*s = 22.9610
Die Rasterpunkte (59, 59) und (60, 60) des selben Gitters liegen also im
gleichen Kästchen.
Gruß,
Klaus Nagel
Klaus Nagel
Auf Ulrichs Wunsch habe ich seine Zeichnung auf meine Homepage gestellt:
http://nagel-klaus.homepage.t-online.de/zxz.png
In meinem Gegenbeispiel ist ein Fehler, zu den angegebenen Koordinaten
gehören nicht die Rasterpunkte (59, 59) und (60, 60)
sondern (59, 0) und (60, 0).
Gruß,
Klaus Nagel
Rainer Rosenthal
>>Ulrich Lange schrieb:
>>
>>>(Plottet Euch mal das um 22.5° gedrehte Gitter und das um -22.5°
>>>gedrehte Gitter in ein Linienraster mit horizontalen und vertikalen
>>>Linien bei x=i+0.5 und y=j+0.5 (i,j e Z). In jedem Kästchen des
>>>Linienrasters findet sich jeweils ein (und nur ein!) Punkt aus dem um
>>>22.5° gedrehten Gitter und aus dem um -22.5 gedrehten Gitter. Ich
>>>schicke Euch den Plot auch gerne per Mail, wenn gewünscht).
>>>
>
> http://nagel-klaus.homepage.t-online.de/zxz.png
>
Es ist ein wahres Vergnügen, diesen Plot anzuschauen. Leider hatte ich
ausser ein paar mehr ins Menschlich-Allgemeine(*) zielenden Assoziationen
noch keine gute Idee ausser der, die ich heute verfolgen möchte:
Was geschieht eigentlich mit den Gittern G und H,
wenn man alle Punkte aus G und H entfernt, deren
Verbindung trivial ist? Die Verbindung von g aus G
und h aus H nenne ich trivial, wenn g der nächste
G-Punkt für h und h der nächste H-Punkt für g ist.
In der unten angegebenen Zeichnung mit G = {A,B,C,D} und
H = {U.V,W,X,Y} ist A der nächste G-Punkt sowohl für U
als auch für Y.
Gut, gut: so allgemein gefragt geht das nicht gut, denn dann
hätte ich ja die trivialen Verbindungen A-U, B-V, C-W und D-X
und schon wäre mein armes Y isoliert.
Geht man aber kreisförmig vom Mittelpunkt aus (Zwiebel-Idee)
und sorgt für Verbindungen in dem abgearbeiteten Bereich, dann
bleiben unverbundene Punkte nur am Rand. Im angegebenen Beispiel
kommen erst U, dann A ins Blickfeld. Sie werden verbunden. Dann
kommt Y und bleibt erst einmal unverbunden. Dann erscheinen X und
B und V, "wie füreinander geschaffen" scheinen und verbunden
werden. Da muss Y halt noch ein bisserl warten. Kommt dann C ins Blickfeld,
so wird es Zeit, Y zu verbinden - so bitter das auch für das
Traumpaar C-W sein mag :-)
(*) Die Punkte aus G und die aus H sollen sich ja "paarweise nahe kommen".
Und da ist ja nicht die heile Welt, dass jedem aus G genau ein Partner
aus H bestimmt. Das war Ulrich Langes erster Ansatz, der verkürzt
besagt: wenn jeder genau eine(n) im Sinn hat, und wenn das für beide
Grundmengen gilt, dann gibt es keine Dramen. Wir hatten aber gesehen,
dass es den Fall gibt, dass A aus G von U und Y aus H angeschmachtet wird,
selbst aber nur Augen für U hat. Dazu noch einmal die Zeichnung:
:
:
: X W
: D C
:
:
:
: Y
:
:
: A B
:
: U V
:
:
:---------------------------------------------------
Aus Gitter G: A=[1,1], B=[2,1], C=[2,2], D=[[1,2]
Aus Gitter H: U=[K,K], Y=[2K,2K], V=[3K/2,K]
W=[3K/2,3K/2], X=[K,3K/2]
Hier ist A=[1,1] und U=h1, Y=h2.
Diese Interpretation könnte dem Thema von Wolfgang Thumser eventuell
zu einem Auftritt in "Spektrum der Wissenschaft" verhelfen. Eventuell
braucht Christoph Pöppe auch für die Oktoberausgabe 2007 wieder ein
schönes Thema für seine mathematische Rubrik, so wie das 2005 der Fall
war :-)
Hero
> Klaus Nagel schrieb:
Nachdem ich Klaus erstes Bild sah, hab ich überhaupt erstmal kapiert,
worum es ging.
(Ich schwebte im Reich von Metriken und Abstände anders definieren).
>
> Was geschieht eigentlich mit den Gittern G und H,
> wenn man alle Punkte aus G und H entfernt, deren
> Verbindung trivial ist? Die Verbindung von g aus G
> und h aus H nenne ich trivial, wenn g der nächste
> G-Punkt für h und h der nächste H-Punkt für g ist.
>
> In der unten angegebenen Zeichnung mit G = {A,B,C,D} und
> H = {U.V,W,X,Y} ist A der nächste G-Punkt sowohl für U
> als auch für Y.
>
> Gut, gut: so allgemein gefragt geht das nicht gut, denn dann
> hätte ich ja die trivialen Verbindungen A-U, B-V, C-W und D-X
> und schon wäre mein armes Y isoliert.
>
> Geht man aber kreisförmig vom Mittelpunkt aus (Zwiebel-Idee)
> und sorgt für Verbindungen in dem abgearbeiteten Bereich, dann
> bleiben unverbundene Punkte nur am Rand. Im angegebenen Beispiel
> kommen erst U, dann A ins Blickfeld. Sie werden verbunden. Dann
> kommt Y und bleibt erst einmal unverbunden. Dann erscheinen X und
> B und V, "wie füreinander geschaffen" scheinen und verbunden
> werden. Da muss Y halt noch ein bisserl warten. Kommt dann C ins Blickfeld,
> so wird es Zeit, Y zu verbinden - so bitter das auch für das
> Traumpaar C-W sein mag :-)
>
Ich hatte dann auch so eine Vorstellung:
Zwei Fliesenleger legen mit ihren Fliesen zwei zueineinander verdrehte
Lagen von quadratischen Fliesen ( jede Fliese entspricht einem
Gitterpunkt). Und zwar abwechselnd, einer fängt an und darf so lange,
bis er eine Fläche hat, auf der der andere midestens eine Fliese
unterbringen kann und dieser macht solange weiter, bis der andere
mindestens eine fliesen kann. Nun gibt es eine einfache Zuordnung von
Fliesen: einer Fliese eines Rasters ordnen wir diejenige des anderen
zu, die mindestens zur Hälfte diese überdeckt. Das ist dann bijektiv,
nur dass man eben einige Fliesen hat, auf denen lauter Teile vom
anderen Raster liegen, die kleiner wie die Hälfte sind. Und hier
geht's dann richtig los.
Ich finde die Scherungslösung sehr schön. Klaus Lösung hat meine
Hochachtung.
Mit freundlichen Grüssen
Hero
.
Klaus Nagel
> Vielleicht liegt noch Potential in Deiner Methode
Die Methode scheint besser zu sein, als die grobe Abschätzung vermuten
läßt. Bei einem numerischen Test mit 100000 Streifen mit je 100000
Punktpaaren erhielt ich als größten Abstand 0.923878.
Gruß,
Klaus Nagel
Rainer Rosenthal
>
> Nachdem ich Klaus erstes Bild sah, hab ich überhaupt erstmal kapiert,
> worum es ging.
Wie heisst es doch so schön: ein Bild sagt mehr als
1000 Worte.
Von daher wäre es gar nicht so schlecht Bilder statt Worten
zu benutzen in den Cantor-Threads :-)
> Ich finde die Scherungslösung sehr schön. Klaus Lösung hat meine
> Hochachtung.
Ich finde alle Beiträge spannend. Und die Lösung, die mir bisher
eingeleuchtet hat und mir (jedenfalls was die Existenz einer nicht
zu grossen oberen Schranke anbelangt) wirklich genial einfach
erscheint, ist die von Ulrich Lange.
In meinem albernen Vermenschlichungswahn sehe ich die Paare
dabei allerdings in Plattenbauhäuser gesperrt :-)
Ich denke, dass seine Idee sogar ohne jede Drehung funktioniert.
Er benutzt ja auch Fliesen, so wie Du. Ich meine, seinen Beweis
verstanden zu haben, wobei mir dann die Vereinfachung einfiel,
dass man G und H so nehmen kann, wie sie sind, also ohne weitere
Drehung um 22,5 Grad oder ähnliches.
Ich klatsche Fliesen der primitivsten Art auf die Ebene:
: (i,j+1) (i+1,j+1)
:
: ..................
: I '
: I '
: I '
: I '
: I '
: I '
: I '
: A================'
:
: (i,j) (i+1,j)
:
Die Punkte einer solchen 1x1 grossen Fliese sind das Innere, der
untere Rand ohne den rechten Endpunkt und der linke Rand ohne den
oberen Endpunkt.
Fliese(i,j) = { [x,y] | i <= x < i+1 und j <= y < j+1 }
Jeder Punkt der Ebene gehört zu genau einer solchen Fliese.
(Komisch, wie kompliziert die Randbetrachtung ist!)
Jetzt betrachten wir unser Gitter G = { [i,j] | i und j ganze Zahlen}
und das Gitter H, das aus G durch Drehung um den Ursprung um 45 Grad
entsteht: H = { [WZH*(1+2*i),WZH*2*j] | i und j ganze Zahlen}, wobei
WZH=sqrt(2)/2 ist.
Ich habe sie gerade noch einmal frisch gezeichnet und betrachtet:
_________________________________________________________________
_____________________M___A___P___L____E__________________________
restart:
with(plots):
WZH := sqrt(2)/2:
xG := 15; yG := 15:
xH := 10; yH := 10:
G := { seq(seq([i,j],i=-xG+1..+xG),j=-yG..+yG) }:
H := { seq(seq([WZH*(1+2*i),WZH*2*j],i=-xH..+xH),j=-yH..+yH) }:
Ur := pointplot({[0,0]},axes=BOXED, symbol=CIRCLE,symbolsize=20);
Gp := pointplot(G,axes=BOXED):
Hp := pointplot(H,axes=BOXED,color=red):
display( {Ur,Gp,Hp});
__________________________________________________________________
Natürlich hat jeder Punkt [i,j] aus G eine Fliese, die ihn bedeckt,
nämlich Fliese(i,j), wie oben definiert.
Aber auch jeder Punkt aus H gehört zu genau einer dieser Fliesen.
Meine Begründung ist lustig, wenngleich noch eine gewisse Endpolitur
nötig ist:
1. Es kann nicht mehr als ein Punkt aus H von einer Fliese bedeckt
werden.
Beweis ist easy: die Punkte von H haben mindestens den Abstand
2*WZH = sqrt(2) voneinander. Einen so grossen Abstand können aber
Punkte einer Fliese nicht haben. Dazu müssten sie die Enden einer
Fliesen-Diagonale sein. Zur Fliese gehört aber nur eine, nämlich
die linke untere Ecke.
2. Jede Fliese bedeckt wenigstens einen Punkt aus H.
Beweis: was wäre denn, falls eine Fliese ohne H-Punkt wäre?
Betrachte einen "sehr grossen" Bereich in der Ebene. Weil G und
H ja kongruente Gitter sind, müssen "gleichviele" Punkte in diesem
Bereich sein. Das Defizit von der einen Fliese kann aber nie
mehr aufgeholt werden wegen Punkt 1.
Hmm ... naja, da braucht's noch ein Weilchen, bis das ein Beweis ist.
Aber wahr ist es sowieso.
(Ob mit ZFC oder ohne hyperbolische Geometrie :-) )
Wolfgang Thumser
> Die Methode scheint besser zu sein, als die grobe Abschätzung vermuten
> läßt. Bei einem numerischen Test mit 100000 Streifen mit je 100000
> Punktpaaren erhielt ich als größten Abstand 0.923878.
Die obere Schranke fuer die Scherkonstruktion fuer 45 Grad liegt
bei 1.070722, aber auch hier ist die Abschaetzung noch nicht aus-
gereizt.
Gruss Wolfgang
Klaus
[...]
> Ich klatsche Fliesen der primitivsten Art auf die Ebene:
>
> : (i,j+1) (i+1,j+1)
> :
> : ..................
> : I '
> : I '
> : I '
> : I '
> : I '
> : I '
> : I '
> : A================'
> :
> : (i,j) (i+1,j)
> :
>
> Die Punkte einer solchen 1x1 grossen Fliese sind das Innere, der
> untere Rand ohne den rechten Endpunkt und der linke Rand ohne den
> oberen Endpunkt.
>
> Fliese(i,j) = { [x,y] | i <= x < i+1 und j <= y < j+1 }
>
> Jeder Punkt der Ebene gehört zu genau einer solchen Fliese.
> (Komisch, wie kompliziert die Randbetrachtung ist!)
Hallo Rainer,
deine Fliesen-Idee hoert sich interessant auch wenn ich es noch nicht
ganz durchdrungen hab. Bekannt sind mir die Probleme mit Teilebenen und
den Randpunkten, mit ein Grund weshalb ich meine erste Idee verworfen
hab. Die neue sieht so aus (neu, sofern ich sie hier nicht ueberlesen
hab):
Grundidee: ein konzentrisches Gitter als Vermittelnde zwischen den
beiden Gittern. Bijektion von G und H auf Teilkreispunkte.
Etwas konkreter:
- konzentr. Kreisring gewaehlt
(ra-ri ca. 2, Mittelpunkt = Gitter-Drehpunkt)
- Bestimmung der Anzahl Gitterpunkte (n) in der Kreisringflaeche
- konzentr. Teilkreis gewaehlt (r ca. (ra+ri)/2) und n Punkten
- Zuordnung der G-Punkte im Kreisring ensprechend ihrem
Winkel (y/x) auf die Teilkreispunkte
- max. Abstand G-Punkt -- Teilkreispunkt => aG
- Dasselbe fuer Gitter H => aH
- Schranke fuer Gesamtabstand = aG + aH (fuer diesen Kreisring)
Die Teilkreisfolge betrachend laesst sich damit _eventuell_ eine
brauchbare globale Schranke herleiten. Ob sie wirklich brauchbar ist?
Angesichts der schon bekannten Werte um die Eins, darf gerne daran
gezweifelt werden :-)
Gruss
-- Klaus
Rainer Rosenthal
> Rainer Rosenthal schrieb:
>>Ich klatsche Fliesen der primitivsten Art auf die Ebene:
>
> Hallo Rainer,
>
> deine Fliesen-Idee hoert sich interessant auch wenn ich
> es noch nicht ganz durchdrungen hab.
Hallo Klaus,
nett von Dir, dass Du meinen Unsinn nicht nochmal zitiert
hast.
Hugo Pfoertner hat mich in einem freundlichen Brief darauf
aufmerksam gemacht, dass in der von mir betrachteten
Lage leider doch Fliesen mit zwei oder gar keinem Punkt
des gedrehten Gitters H existieren. Ich hatte absurderweise
den Minimalabstand von H-Punkten als sqrt(2) angenommen,
weil die kleinsten achsenparallelen Quadrate darin die
Seitenlänge sqrt(2) haben. Aber das ist natürlich irrelevant
für das Thema. Setzen, SECHS! *gumpffff* ... wie war das mit
den Knochen und dem Blamieren?
Ich habe noch nicht recht kapiert, wie Deine Idee funktio-
nieren soll, aber ich wünsche Dir Erfolg!
Von Hugo wurde ich auf die interessante Theta-Folge
http://www.research.att.com/~njas/sequences/A004018
aufmerksam gemacht. Ich war auch bereits im OEIS unterwegs,
weil meine Zwiebelschalen (genauer die Quadrate ihrer
Radien) durch die Folge
http://www.research.att.com/~njas/sequences/A001481
repräsentiert werden. Es wimmelt von interessanten Querver-
weisen bei den genannten OEIS-Folgen.
Ulrich Lange
> Klaus Nagel schrieb:
>
>>>Ulrich Lange schrieb:
>>>
>>>
>>>>(Plottet Euch mal das um 22.5° gedrehte Gitter und das um -22.5°
>>>>gedrehte Gitter in ein Linienraster mit horizontalen und vertikalen
>>>>Linien bei x=i+0.5 und y=j+0.5 (i,j e Z). In jedem Kästchen des
>>>>Linienrasters findet sich jeweils ein (und nur ein!) Punkt aus dem um
>>>>22.5° gedrehten Gitter und aus dem um -22.5 gedrehten Gitter. Ich
>>>>schicke Euch den Plot auch gerne per Mail, wenn gewünscht).
>>>>
>>
>>Auf Ulrichs Wunsch habe ich seine Zeichnung auf meine Homepage gestellt:
>>
>>http://nagel-klaus.homepage.t-online.de/zxz.png
>>
> Es ist ein wahres Vergnügen, diesen Plot anzuschauen.
Hallo Rainer, hallo Klaus (danke nochmal für das Uploaden meines Plots!),
Kurze Wasserstandsmeldung zu meinen Versuchen:
Klaus hat natürlich recht, daß es Gegenbeispiele zu meiner Vermutung
gibt. Der Plot zeigt ja nur das Gebiet [-5,5]x[-5,5]. Für größere
Teilmengen von ZxZ hört das Vergnügen beim Betrachten des Plots leider
sehr bald auf (genauer: Sobald der Punkt (4,19) dabei ist, das ist das
kleinste Gegenbeispiel).
Ich habe gestern mal für |i|,|j| < 1000 mal alle Voronoi-Zellen
(Vij = [i-0.5,i+0.5]x[j-0.5,j+05]) angeschaut. Ergebnis:
1. Für die "meisten" Vij gilt, das sie genau ein Punkt von G enthalten.
2. Es gibt Zellen Vij, die keinen Punkt von G enthalten
3. Es gibt Zellen Vij, die genau zwei Punkte von G enthalten (mehr als
zwei geht nicht, wie man sich auch leicht geometrisch überlegt).
Interessant ist jetzt, daß die Gegenbeispiele (Fälle 2.und 3.) ein
periodisches Muster bilden, und immer in der Nachbarschaft
(|i-i'|,|j-j'|<=2) einer leeren Zelle eine Zelle mit zwei Punkten liegt.
Man könnte die Bijektion also reparieren, indem man jeweils einen Punkt
aus einer Zelle mit zwei Punkten einer benachbarte leeren Zelle zuordnet.
Das wäre dann aber höchstens eine weniger elegante Variante von Klaus'
Beweis (Variante in dem Sinne, daß man zunächst "fast" eine Bijektion
konstruiert und dann die wenigen Ausnahmen verarztet), die zudem eine
schlechtere Konstante (K<3*sqrt(2)) liefert.
Klaus
[...]
> Ich habe noch nicht recht kapiert, wie Deine Idee funktio-
> nieren soll, aber ich wünsche Dir Erfolg!
>
> Von Hugo wurde ich auf die interessante Theta-Folge
> http://www.research.att.com/~njas/sequences/A004018
>
> aufmerksam gemacht. Ich war auch bereits im OEIS unterwegs,
> weil meine Zwiebelschalen (genauer die Quadrate ihrer
> Radien) durch die Folge
> http://www.research.att.com/~njas/sequences/A001481
>
> repräsentiert werden. Es wimmelt von interessanten Querver-
> weisen bei den genannten OEIS-Folgen.
Hallo Rainer,
Danke fuer die Hinweise, werde mir diese sicher mangels
Hardware-Literatur noch genauer anschauen.
Nochmals zu der Teilkreis-Geschichte (wenn Du sie weiter konkretisieren
willst, gerne).
Numerisch/algorithmisch, seh ich eigentlich kein groesseres Problem,
etwa so: Waehle eine Folge von Radien fuer ein konzentr. Gitter (ich
glaube Du hattest so was schon als Zwiebelschalen beschrieben), r=
(0.5, 2.5, 4.5, ...). i-ter Schritt: betrachte Kreisringflaeche
gebildet durch r(i) und r(i+1); bestimme Menge der Gitterpunkte auf
der Kreisringflaeche, d.h. alle Punkte G(i,j)=(x,y) mit r(i) <=
sqrt(x^2+y^2) < r(i+1), und speziell die Anzahl dieser Punkte (n(i)).
Bilde Teilkreis mit Radius (r(i)+r(i+1))/2. Verteile auf diesem
Teilkreis gleichmaessig n(i) Teilkreispunkte T(i,j). Bijektion aller
G(i,j) auf T(i,j): Sortierung der G(i,j) nach ihrem Winkel bezogen auf
x-Achse/Drehpunkt. Groesster Abstand aller Paare (G,T)(i,j) ergibt aG
bzw. aH (aG = aH, wenn Abschaetzung unabh. vom Winkeloffset). Der Weg
fuer jeden Punkt ist also G(i,j) --> T(i,j) --> H(i,j). Fuer durch
einen Kreis begrenztes Gitter sollte damit eine Schranke (abh. von r)
recht einfach berechenbar sein, die Schranke unabh. von r, sprich fuer
unbegrenztes Gitter, wird wohl das eigentliche Problem. Ggf. zu
optimieren: die Folge r(i) und die zugeordneten Teilkreisradien.
Gruss
-- Klaus
Klaus Nagel
>
> Die Methode scheint besser zu sein, als die grobe Abschätzung vermuten
> läßt. Bei einem numerischen Test mit 100000 Streifen mit je 100000
> Punktpaaren erhielt ich als größten Abstand 0.923878.
>
Weil ich Zweifel an diesem Wert hatte, habe ich die Bijektion gezeichnet:
http://nagel-klaus.homepage.t-online.de/bijekt.jpg
Die Streifen sind angedeutet, die Rasterpunkte sind rot und blau
gezeichnet, in den Streifen abwechselnd als als volle und leere Kreise.
Die zugeordneten Punkte sind durch Linien verbunden.
Bei der Gelegenheit habe ich einen Programmfehler gefunden; der größte
Abstand verschlechtert sich auf 0.9378.
Gruß,
Klaus Nagel
Klaus
Das vermittelnde Gitter muss nicht kreisfoermig sein, eine ganz andere
Gitterform, deren Bild (und damit Anzahl erfasster Gitterpunkte) bei
45 deg Drehung unveraendert bleibt ist denkbar, etwa ein
regelmaessiges Achteck oder ein achteckiger Stern. Das sollte
hilfreich sein fuer schmalere Ringe/Baender, die mehr Gitterpunkte
erfassen, und somit die Abstaende und Verschiebungswege verringern.
Die Schranke Eins rueckt wieder naeher! :-)
Gruss
-- Klaus
Klaus Nagel
> Wieder eine wunderschöne Frage von Wolfgang Thumser:
>
> Seien G die Punkte des Gitters ZxZ und H die Punkte des um 45 Grad
> um den Nullpunkt gedrehten Gitters. Sei Dreh die Drehung G -> H.
> Es gilt Tatsache T:
>
> Für jede Zahl K gibt es einen Punkt p in G, (T)
> dessen Abstand zu Dreh(p) grösser ist als K.
>
> Frage F:
> Gibt es eine Bijektion Bij: G -> H und
> eine Zahl K, so dass für alle p aus G (F)
> der Abstand zu Bij(p) kleiner als K ist?
>
Die von mir vorgeschlagene streifenweise Bijektion läßt sich einfach
erklären:
Die beiden Gitter G und H werden in ein kartesisches Koordinatensystem
gezeichnet, G um 22.5° nach links gedreht, H um 22.5° nach rechts. Die
Gitter sind in
http://nagel-klaus.homepage.t-online.de/bijekt.jpg
blau und rot dargestellt, die um 22.5° gegen die y-Achse verdrehten
Gitterlinien (g-Linie blau, h-Linie rot) sind eingezeichnet. Die ganze
Ebene ist in zur x-Achse parallele Streifen aufgeteilt, die
Streifenbreite c = cos(22.5°) ist so gewählt, daß jeder Streifen genau
einen Rasterpunkt jeder g-Linie und jeder h-Linie enthält. Die Streifen
sind oben offen, unten abgeschlossen: a <= y < a+c.
Falls sich eine g-Linie und eine h-Linie im Streifen kreuzen, werden
diese beiden Linien einander zugeordnet, falls nicht, wird einer g-Linie
die h-Linie zugeordnet, die ihr im Streifen am nächsten kommt.
Als Bijektion wird jedem Rasterpunkt der Punkt des anderen Gitters
zugeordnet, der auf der zugeordneten Linie liegt und im gleichen Streifen.
Der größtmögliche Abstand tritt auf, wenn ein g-Punkt in der Ecke des
Parallelogramms aus Streifen und zwei benachbarten g-Linien liegt, der
h-Punkt aber in der Mitte des Parallelogramms. Eine ungünstige
Konstellation ist in der Zeichnung durch einen grünen Stern gekennzeichnet.
Als obere Schranke erhält man 0.962692.
Gruß,
Klaus Nagel
Wolfgang Thumser
> Als obere Schranke erhält man 0.962692.
Ich habe die Scherkonstruktion nochmal ueberprueft
und festgestellt, dass Deine obere Schranke kleiner
ausfaellt, Gratulation!
Gruss Wolfgang
Rainer Rosenthal
> Die von mir vorgeschlagene streifenweise Bijektion läßt sich einfach
> erklären:
> Die beiden Gitter G und H werden in ein kartesisches Koordinatensystem
> gezeichnet, G um 22.5° nach links gedreht, H um 22.5° nach rechts. Die
> Gitter sind in
>
> http://nagel-klaus.homepage.t-online.de/bijekt.jpg
>
> Der größtmögliche Abstand tritt auf, wenn ein g-Punkt in der Ecke des
> Parallelogramms aus Streifen und zwei benachbarten g-Linien liegt, der
> h-Punkt aber in der Mitte des Parallelogramms. Eine ungünstige
> Konstellation ist in der Zeichnung durch einen grünen Stern gekennzeichnet.
> Als obere Schranke erhält man 0.962692.
Hallo Klaus,
diese himmlischen Einfälle kommen sicher daher, dass Du Dich so
viel mit Astronomie befasst. Deine Erklärung ist beeindruckend und
die Schranke, die deutlich unter 1 liegt, ist unglaublich toll!
Dass ich auf sowas leider nicht kommen würde, ist daran zu sehen,
dass ich selbst nach der deutlichen Beschreibung und trotz der
anschaulichen Zeichnung noch immer was Wesentliches nicht ver-
standen habe: sonst würde ich nicht so naiv fragen müssen, wieso
ausgerechnet "h-Punkt in der Mitte des Parallelogramms" so eine
fiese Konstellation ist. Ich kapiere nicht mal "Parallelogramm"
und hatte es erst mal sowieso als "in der Mitte des Streifens"
gelesen und zu verstehen gesucht.
An der von Dir mit einem "*" Stern markierten Stelle haben wir
ja die folgende Situation:
:
:
: ----------------------------------------------------
: ' . '
: . .
: '
: ' . B
: . .
: '
: ---------------R---------'------------------------------
:
:
Mit R und B bezeichne ich die beiden Punkte R=rot und B=blau
bei dem von Dir markierten grünen Stern.
Bitte hilf mir zu verstehen, wieso B nicht noch ein Stückchen
weiter obenauf seiner blauen Linie liegen kann.
Besten Dank,
Klaus Nagel
>
> Dass ich auf sowas leider nicht kommen würde, ist daran zu sehen,
> dass ich selbst nach der deutlichen Beschreibung und trotz der
> anschaulichen Zeichnung noch immer was Wesentliches nicht ver-
> standen habe: sonst würde ich nicht so naiv fragen müssen, wieso
> ausgerechnet "h-Punkt in der Mitte des Parallelogramms" so eine
> fiese Konstellation ist. Ich kapiere nicht mal "Parallelogramm"
> und hatte es erst mal sowieso als "in der Mitte des Streifens"
> gelesen und zu verstehen gesucht.
Hallo Rainer,
Deine Zweifel sind berechtigt und Wolfgangs Gratulation war wohl etwas
voreilig. Seit über einer Stunde denke ich genau über Deine Frage nach.
Weil die Schranke so gut mit meiner Simulation übereinstimmte, habe ich
mich täuschen lassen.
Das Parallelogramm im Bild ist der weiße Bereich, in dem dar grüne Stern
liegt und das durch zwei rote Linien begrenzt ist.
Gruß,
Klaus Nagel
Rainer Rosenthal
> Seit über einer Stunde denke ich genau über Deine Frage nach.
> Weil die Schranke so gut mit meiner Simulation übereinstimmte, habe ich
> mich täuschen lassen.
Hallo Klaus,
so leid es mir einerseits tut, dass Deine wunderschöne Lösung
noch nicht ganz wasserdicht präsentiert ist, bin ich andererseits
doch sehr froh, so mutig gewesen zu sein und die Blamage zu
riskieren, die darin lag, etwas ganz offenbar Tolles nicht zu
kapieren.
Die genaue Übereinstimmung mit Deinen Simulationsergebnissen
dürfte aber wohl doch noch die Oberhand behalten und es muss
"nur noch" ein Grund für Deine Beobachtung gefunden werden.
Donnerlattich - ist das mal wieder eine tolle Aufgabe!
Jetzt werde ich langsam doch mal einen Wink mit dem Zaunpfahl
in Richtung Christoph Pöppe machen :-)
Gruss,
Wolfgang Thumser
> Das Parallelogramm im Bild ist der weiße Bereich, in dem der
> grüne Stern liegt und das durch zwei rote Linien begrenzt ist.
kann es sein, dass der maximale Abstand zwischen einem roten und
blauen Punkt durch die kuerzere Seite des Parallelogramms gegeben
ist? Das ergibt 2*sqrt(2)*sin(22.5°) ~ 1.0823922, was mit der Scher-
schranke von ~ 1.070722 ganz gut zusammenpassen wuerde.
Gruss Wolfgang
Ulrich Lange
Hallo Wolfgang, Klaus und Rainer,
ich denke gerade über die andere Richtung, also eine Abschätzung der
bestmöglichen Schranke nach unten, nach. Bis jetzt habe ich:
Sei p:G->H eine beliebige Bijektion mit |p-p(g)| < Kp für alle g e G.
Dann gilt Kp > 0.8194955... = sqrt(7/2 - 2*sqrt(2))
Diese Abschätzung nach unten könnte man noch versuchen zu verbessern. Es
wäre doch interessant, wie "optimal" die beste konkret gefundene
Bijektion ist, oder?
Beweisskizze für meine Abschätung (Bei mit ist G=ZxZ und H positiv um
45° gedreht).
1. Zu beliebigen eps>0 gibt es ganze Zahlen i,k, so daß der Punkt
1/sqrt(2)*(k,k) aus H in der eps-Umgebung von (i-0.5,i-0.5) liegt.
(Betrachte die Newton-Iteration x-> x/2 + 1/x mit Startwert 1, die
ja quadratisch gegen sqrt(2) konvergiert. Wenn man hinreichend lange
iteriert hat, kann man k=q und i=(p-1)/2 wählen, wobei q der Nenner
und p der (immer ungerade) Zähler von x ist.
2. Der Punkt aus H in der eps-Umgebung von (i-0.5,i-0.5) braucht ein
Urbild unter p. Bei einer "guten" Bijektion kommen eigentlich nur
die Ecken des Quadrats (i-1,i-1),(i-1,i),(i,i),(i,i-1) in Frage, da
sonst Kp schon größer als sqrt(5/2) ist. Ich nehme O.B.d.A an, daß
das Urbild (i,i) ist. Die anderen Fälle sind symmetrisch.
3. Der Punkt (i,i) hat aber noch einen nächsten Nachbarn ( :-) ) aus H,
nämlich 1/sqrt(2)*(k+1,k+1). Die bestmöglichen Optionen für das
Urbild dieses Punktes sind die Punkte (i,i+1) bzw. (i+1,i). Sein
Abstand zu diesen Punkten beträgt sqrt(7/2-2*sqrt(2)) + O(eps).
Ulrich Lange
>
> Sei p:G->H eine beliebige Bijektion mit |p-p(g)| < Kp für alle g e G.
> Dann gilt Kp > 0.8194955... = sqrt(7/2 - 2*sqrt(2))
>
> Diese Abschätzung nach unten könnte man noch versuchen zu verbessern.
Erste Verbesserung: Kp > 0.878679... = sqrt(27/2 - 9*sqrt(2))
Die verbesserte Abschätzung habe ich durch wiederholtes Anwenden des
unten in Schritt 3 beschriebenen Prinzips gewonnen: Für den zuletzt
"verbrauchten" Punkt aus G sucht man den nächsten Nachbarn h unter den
verbliebenen Punkten aus H und schaut sich für diesen die
"Urbild-Optionen" an. Falls der Abstand von h zu allen "Urbild-Optionen"
größer als die aktuelle Abschätzung für Kp ist, hat man eine neue
Abschätzung für Kp gefunden. Falls es genau eine "Urbild-Option" mit
geringerem Abstand gibt, kann h dieser zugeordnet werden und man
wiederholt den Schritt für das nun "verbrauchte" Urbild.
Ausgehend von meinem unten in Schritt 1 beschriebenen Startpunkt kommt
man so in 5 Schritten (in denen jeweils nur eine Urbild-Option mit
geringerem Abstand als die alte Abschätzung existiert) zu einem Punkt,
für denen die nächstliegende Urbild-Option den Abstand 0.878679... hat.
Von diesem Punkt kann man noch 3 Schritte weitergehen (ohne eine neue
Abschätzung zu finden), dann verzweigt sich der Weg (d.h. es gibt zwei
Urbild-Optionen mit geringerem Abstand als die alte Abschätzung). Um
neue Abschätzungen zu finden, muß man jetzt beide beiden Wege jeweils
bis zu einer Stelle mit nur größeren Abständen verfolgen. Das war mir
auf Papier zu unübersichtlich. Morgen werde ich das Verfahren mal
programmieren und schauen, ob noch so eine Stelle kommt.
>
> Beweisskizze für meine Abschätzung (Bei mir ist G=ZxZ und H positiv um
Ulrich Lange
> Ulrich Lange schrieb:
>
>>
>> Sei p:G->H eine beliebige Bijektion mit |p-p(g)| < Kp für alle g e G.
>> Dann gilt Kp > 0.8194955... = sqrt(7/2 - 2*sqrt(2))
>>
>> Diese Abschätzung nach unten könnte man noch versuchen zu verbessern.
>
>
> Erste Verbesserung: Kp > 0.878679... = sqrt(27/2 - 9*sqrt(2))
Die Abschätzung muß warten, denn ich habe jetzt auch eine schöne
Bijektion gefunden, die dieselbe Konstante wie Klaus' Bijektion liefert.
Ist es sogar dieselbe Bijektion? Nach meinem Verständnis ist meine
Konstruktion zumindest völlig anders als Klaus' Methode (Meine ist das
Resultat meiner Versuche, meine nächste Nachbar-Idee zu "retten").
Sei G=ZxZ und H={(K*(k+l),K*(k-l)) mit k,l e Z}.
Ich betrachte lieber ein leicht verschobenes Gitter G', d.h.
zunächst mache ich mal die Bijektion:
V:G->G'
(i,j) -> (i+ex,j+ey)
Dabei ist ex=sqrt(3)*qx und ey=sqrt(3)*qy mit (sehr kleinen)
/rationalen/ Zahlen qx,qy, die zudem folgende Eigenschaften haben:
qx =/= qy und qx =/= - qy
haben sollen (Wozu das gut ist: siehe unten).
Mit G_ij bezeichne ich das Quadrat in G', dessen linke untere Ecke
(i+ex,j+ey) ist (die rechte obere Ecke ist also (i+1+ex,j+1+ey).
Mit H_kl bezeichnet ich das Quadrat in K mit "linker unterer" Ecke
(K*(k+l),K*(k-l), ("links" und "unten" werden hier über k und l
definiert: "rechts unten" ist also z.B. (K*((k+1)+l,K*(k+1)-l)))
Behauptung:
Seien (i,j) e ZxZ beliebig. Dann gibt es genau ein (k,l) e ZxZ,
so daß der Flächeninhalt der Schnittmenge der zugehörigen Quadrate
(G_ij n H_kl) maximal wird.
(Offensichtlich ist die dadurch induzierte Zuordnung G_ij -> H_kl eine
Bijektion zwischen den beiden "Quadrat-Mengen". Da ich die Quadrate mit
ihren linken unteren Ecken identifizieren kann, habe ich meine Bijektion
G' -> H.)
Beweis der Behauptung:
Sei (i,j) e ZxZ gegeben. Ich muß natürlich nur die H_kl betrachten, für
die der Schnitt G_ij n H_kl nicht leer ist. Es gibt drei Fälle:
1. G_ij enthält keine Eckpunkte von H_kl.
In diesem Fall hat G_ij auch - je nach Lage der Eckpunkte von H_kl -
mit 3 bzw.4 Nachbarquadraten von H_kl einen nichtleeren Schnitt. Die
Schnittmengen mit den Nachbarquadraten sind rechtwinklige Dreiecke,
die die Ecken von G_ij enthalten. Ihre Flächen sind aber immer
deutlich kleiner als die von G_ij n H_kl (das ist ein 7-eck bzw.
8-Eck).
2. G_ij enthält genau einen Eckpunkt (k',l') von H_kl.
In diesem Fall hat G_ij mit genau 3 Nachbarquadraten von H_kl
nichtleeren Schnitt. Je nach Lage des Eckpunkts sind die
Schnittmengen Vierecke oder Fünfecke. Eine der Nachbar-Schnittmengen
kann nur dann den gleichen Flächeninhalt wir G_ij n H_kl haben, wenn
der enthaltene Eckpunkt auf einer der beiden Diagonalen oder
auf einer der beiden Mittellinien von G_ij liegt .
Falls (k',l') auf der Mittelinie liegt, müßte gelten:
K*(k'+l') = i+0.5+ex oder
K*(k'-l') = j+0.5+ey
d.h. also:
k'+l' = (i+0.5)*sqrt(2) + qx*sqrt(6) oder
k'-l' = (j+0.5)*sqrt(2) + qy*sqrt(6)
Links steht jeweils eine ganze Zahl und und rechts eine
Irrationalzahl (Die rechte Seite kann nicht null sein, da
man sonst sqrt(3) als Bruch darstellen könnte).
(k',l') kann also nicht auf einer Mittellinie liegen.
Falls (k',l') auf der ersten Diagonalen liegt, müßte es ein s e
[0:sqrt(2)] geben, so daß:
K*(k'+l') = i + ex + s und:
K*(k'-l') = j + ey + s
also:
2*K*k' = i+j + ex + ey + 2*s
2*K*l' = i-j + ex - ey
Aus der zweiten Gleichung folgt:
2*l' = (i-j)*sqrt(2) + (qx-qy)*sqrt(6)
Dies ist (da qx =/= qy gewählt) wurde, auch dann unmöglich, wenn
i=j. Damit kann (k',l') nicht auf der ersten Diagonalen liegen. Die
zweite behandelt man genauso.
3. G_ij enthält genau zwei Eckpunkte von H_kl.
In diesem Fall kann nur dann eine der Nachbar-Schnittmengen gleichen
Flächeninhalt haben, wenn beide enthaltenen Eckpunkte auf einer
Diagonalen von G_ij liegen. Das habe ich bereits ausgeschlossen.
Damit ist alles gezeigt, bis auf die Abstandsabschätzung: Man kann sich
geometrisch leicht klarmachen, daß Folgendes der Extremfall ist: Die
beiden "oberen" Punkte von H_kl liegen in G_ij, der "rechte obere" liegt
(fast) auf der rechten oberen Ecke von G_ij. Der Absatand der "linken
unteren" Ecke von H_kl von der linken unteren Ecke von G_ij ist dann
sqrt(4 - 2*sqrt(2)) = 1.0823922...
Da man beliebig kleine qx,qy wählen kann, gilt die gleiche Abschätzung
auch für die zusammengesetzte Bijektion G -> G' -> H
Ulrich Lange
> Mit G_ij bezeichne ich das Quadrat in G', dessen linke untere Ecke
> (i+ex,j+ey) ist (die rechte obere Ecke ist also (i+1+ex,j+1+ey).
> Mit H_kl bezeichnet ich das Quadrat in K mit "linker unterer" Ecke
> (K*(k+l),K*(k-l), ("links" und "unten" werden hier über k und l
> definiert: "rechts unten" ist also z.B. (K*((k+1)+l,K*(k+1)-l)))
>
> Behauptung:
> Seien (i,j) e ZxZ beliebig. Dann gibt es genau ein (k,l) e ZxZ,
> so daß der Flächeninhalt der Schnittmenge der zugehörigen Quadrate
> (G_ij n H_kl) maximal wird.
>
> (Offensichtlich ist die dadurch induzierte Zuordnung G_ij -> H_kl eine
> Bijektion [...]
Offensichtlich ist natürlich gar nix. Die Zuordnung ist wohldefiniert,
das ist aber auch alles. Injektiv ist sie jedenfalls nicht.
Spätestens, wenn man denselben blöden Fehler zweimal hintereinander
macht, wirds peinlich :-(
Klaus Nagel
>
> kann es sein, dass der maximale Abstand zwischen einem roten und
> blauen Punkt durch die kuerzere Seite des Parallelogramms gegeben
> ist? Das ergibt 2*sqrt(2)*sin(22.5°) ~ 1.0823922, was mit der Scher-
> schranke von ~ 1.070722 ganz gut zusammenpassen wuerde.
>
Hallo Wolfgang,
was Du berechnest, ist die längere Seite des Parallelogramms, die
kürzere hat die Länge Eins. Die größte Entfernung in einer
Parallelogrammhälfte stimmt mit der Scherschranke 1.070722 überein.
Allerdings scheint es günstiger zu sein, die Streifen so zu legen, daß
die x-Achse in der Mitte eines Streifens (Zentralstreifen) liegt. Ich
habe das Bild entsprechend geändert:
http://nagel-klaus.homepage.t-online.de/bijekt.jpg
Die größten Abstände tauchen im Zentralstreifen auf, die Schranke ist
die Streifenbreite cos(22.5°) = 0.923880.
Das habe ich numerisch festgestellt, es wäre schön, wenn es jemand
nachrechnete. Es sollte sich doch auch beweisen lassen!
Gruß,
Klaus Nagel
Klaus
[...]
> Die größten Abstände tauchen im Zentralstreifen auf, die Schranke ist
> die Streifenbreite cos(22.5°) = 0.923880.
> Das habe ich numerisch festgestellt, es wäre schön, wenn es jemand
> nachrechnete. Es sollte sich doch auch beweisen lassen!
Hallo Klaus,
ob diese Schranke so stimmt, weiss ich noch nicht, denk aber bald die
Schranke fuer diese oder aehnliche Anordnungen konstruieren bzw.
beweisen zu koennen.
Gruss
-- Klaus
Klaus Nagel
> Klaus Nagel schrieb:
> [...]
>
>>Die größten Abstände tauchen im Zentralstreifen auf, die Schranke ist
>>die Streifenbreite cos(22.5°) = 0.923880.
>>Das habe ich numerisch festgestellt, es wäre schön, wenn es jemand
>>nachrechnete. Es sollte sich doch auch beweisen lassen!
>
> [...]
> ob diese Schranke so stimmt, weiss ich noch nicht, denk aber bald die
> Schranke fuer diese oder aehnliche Anordnungen konstruieren bzw.
> beweisen zu koennen.
>
Hallo Klaus,
schön, daß Du helfen willst. Ich habe inzwischen einen größeren Abstand
(0.930482) gefunden, der nicht im Zentralstreifen liegt!
Die Gitterkoordinaten des einen Punktes sind (592, 303).
Gruß.
Klaus Nagel
Klaus
[...]
> schön, daß Du helfen willst. Ich habe inzwischen einen größeren Abstand
> (0.930482) gefunden, der nicht im Zentralstreifen liegt!
> Die Gitterkoordinaten des einen Punktes sind (592, 303).
Hallo Klaus,
hier mal der bildliche Beweis fuer den einfachen Streifen (falls noch
doppelt hohe oder n-fach hohe Streifen kommen ;)):
http://home.wtal.de/klaus/gh10.png
Die Schranke ist: sqrt( ( 7 -4 *sqrt(2)) /( 4 -2 *sqrt(2)) = 1.071
(gerundet)
Das Bild zeigt drei spezielle Anordnungen des Streifens auf dem
Rautengitter.
1. Streifen liegt genau zwischen den Rautenspitzen
2. Streifenrand liegt genau auf den Rautenspitzen
3. Rautenspitzen liegen genau in der Mitte des Streifens
Bewegt man gedanklich einen transparenten Streifen auf dem Rautengitter
nach unten, sieht man nacheinander diese Bilder. Angegeben sind jeweils
alle Abstaende, die prinzipiell fuer die Schranke massgebend sein
koennen, also alle Kombinationen zwischen den Randpunkten der G- und
der H-Strecke.
Z.B. G(links/oben) - H (links/unten)
1.071 --> 1 --> 0.924 ( --> 1 --> 1.071 )
Bijektiert werden also immer die G- und H-Strecken, die eine gemeinsame
Rautenspitze haben und die ausserdem moeglichst nahe am Streifen liegt.
Liegt der Streifen genau zwischen den Rautenspitzen (1.) dann sind
beide moeglichen Bijektionen (G links, H rechts oder umgegekehrt)
gleichwertig. Wird die gesamte Ebene mit diesen Streifen abgedeckt,
koennen alle diese Bilder innerhalb eines Streifens auftreten,
unabhaengig von einem Offset.
Gruss
-- Klaus
Klaus Nagel
> Klaus Nagel wrote:
> [...]
>
>>schön, daß Du helfen willst. Ich habe inzwischen einen größeren Abstand
>>(0.930482) gefunden, der nicht im Zentralstreifen liegt!
>>Die Gitterkoordinaten des einen Punktes sind (592, 303).
Hallo Klaus,
dieses Dementi muß ich dementieren, nach meinem augenblicklichen Stand
kenne ich keinen Abstand, der die Streifenbreite cos(22.5°) überschreitet.
>
> [...]
> Hallo Klaus,
> hier mal der bildliche Beweis fuer den einfachen Streifen (falls noch
> doppelt hohe oder n-fach hohe Streifen kommen ;)):
>
> http://home.wtal.de/klaus/gh10.png
>
> Die Schranke ist: sqrt( ( 7 -4 *sqrt(2)) /( 4 -2 *sqrt(2)) = 1.071
> (gerundet)
>
> Das Bild zeigt drei spezielle Anordnungen des Streifens auf dem
> Rautengitter.
> 1. Streifen liegt genau zwischen den Rautenspitzen
Diese Schranke war bekannt, sie stimmt auch mit der aus dem
Scherverfahren überein, die Wolfgang Thumser angegeben hat. Nach meinen
bisherigen Beobachtungen ist diese Schranke zu schlecht, numerische
Untersuchungen bis zu 10000 mal 10000 Punktepaaren lieferten keine
Abstände größer als die Streifenbreite. Das unkommentierte C-Programm
sende ich gern zu.
Man sollte versuchen, ein Punktepaar G, H zu finden, dessen Abstand
Deiner Schranke nahe kommt. Am einfachsten scheint mir das in Deinem
zweiten Bild mit der Schranke 1 zu sein.
Dazu ist vermutlich die Kettenbruchentwicklung von tan(22.5°) hilfreich;
sie ist sehr einfach:
2/5
5/12
12/29
29/70
...
allgemein, auf A/B folgt B/(2B+A).
Gruß,
Klaus Nagel
Rainer Rosenthal
> Das unkommentierte C-Programm sende ich gern zu.
> Man sollte versuchen, ein Punktepaar G, H zu finden, dessen Abstand
> Deiner Schranke nahe kommt. Am einfachsten scheint mir das in Deinem
> zweiten Bild mit der Schranke 1 zu sein.
> Dazu ist vermutlich die Kettenbruchentwicklung von tan(22.5°) hilfreich;
> sie ist sehr einfach:
>
> 2/5
> 5/12
> 12/29
> 29/70
> ...
> allgemein, auf A/B folgt B/(2B+A).
>
***
1
***
Das hat mich neugierig gemacht, und ich wollte selbst nachprüfen, dass
das richtig ist. Bitte verrate dann anschliessend, wie Du das gerechnet
hattest.
( 1 - cos(a) )
Ich habe mit tan(a/2) = sqrt( ---------- ) gearbeitet und daraus
( 1 + cos(a) )
für 22,5° = Pi/8 = (Pi/4)/2 mittels a = Pi/4 und cos(a) = sqrt(2)
herausbekommen, dass für x = tan(Pi/8) gelten muss x = h/(1+h),
wobei h = sqrt(2)/2 ist.
Deine Kettenbruchdarstellung liefert Näherungsbrüche für einen Wert y,
der aus der Gleichung y = A/B und y = B/(2B+A) ermittelt werden kann.
Denn es ist ja y = B/(2B+A) = (B/B) / (2+A/B) = 1 / (2+y).
Tatsächlich erfüllt x diese Gleichung x = 1/(2+x).
Nachgeprüft habe ich das nun also. Aber wie geht "man" an sowas dran,
und insbesondere: wie bist Du dran gekommen?
***
2
***
Und hier noch eine Art kreativer Purzelbaum, betreffend das eigentliche
Thema der zwei Gitter G und H.
Ausgehend vom gemeinsamen Ursprungspunkt der beiden Gitter kann man
sich ja die Unter-Gitter G_k und H_k anschauen, die dadurch entstehen,
dass man nur jeden k-ten Gitterpunkt nimmt, oder evtl. auch nur jeden
2^k-ten. Diese Gitter G_k und H_k sind ja in völlig gleicher Weise
gegeneinander verdreht wie die Ausgangsgitter G und H.
Es ist also mit gewähltem Faktor f_k (z.B. f_k=k oder f_k=2^k):
G_k = {f_k*g | g aus G}
und (1)
H_k = {f_k*h | h aus H}.
Wie steht es da eigentlich mit den Nachbarschaftsverhältnissen bei
gegebener Bijektion zwischen G und H? Wenn Du eine Bijektion
b: G -> H (2)
konstruiert hast, dann gibt es sofort eine Bijektion
b_k: G_k -> H_k (3)
indem man den den Faktor f_k benutzt, mit dem diese Gitter aus den
Ursprungsgittern entstanden sind und dann definiert:
b_k(f_k*g) = f_k*b(g). (3')
In dieser Bijektion sind die längsten Abstände von Punkt und Bildpunkt
allerdings bis zu f_k*K lang, wenn K die berühmte Schranke ist, die
die Abstände von g zu b(g) in (2) nach oben beschränkt.
Wenn f_k*g und f_k*b(g) ganz eng beieinander liegen, dann wird auch
gelten
f_k*b(g) = b(f_k*g). (4)
Nun ja, ein Purzelbaum war es. Und irgendwie kreativ ja auch. Aber
ob es was nützt, diese Selbstähnlichkeit der Gitter zu nutzen, weiss
ich nicht so recht. Ich hatte da so gewisse Rosinen im Kopf, und als
ich die Idee fixieren wollte, blieb nur diese magere Beschreibung
übrig. Sollte jemand daraus einen Lösungsansazt basteln, dann werde
ich bestimmt rufen: "Ja, genau das hatte ich gemeint!" :-)
***
3
***
Das Programm möchte ich auch gerne zugesendet bekommen, Klaus!
Gruss,
Christopher Creutzig
>> Dazu ist vermutlich die Kettenbruchentwicklung von tan(22.5°) hilfreich;
>> sie ist sehr einfach:
> Das hat mich neugierig gemacht, und ich wollte selbst nachprüfen, dass
> das richtig ist. Bitte verrate dann anschliessend, wie Du das gerechnet
> hattest.
> für 22,5° = Pi/8 = (Pi/4)/2 mittels a = Pi/4 und cos(a) = sqrt(2)
> herausbekommen, dass für x = tan(Pi/8) gelten muss x = h/(1+h),
> wobei h = sqrt(2)/2 ist.
Also ist x algebraisch vom Grad 2, also ist die Kettenbruchdarstellung
periodisch. (Nebenbei bemerkt ist x=sqrt(2)-1, und die
Kettenbruchdarstellung von sqrt(2) ist nun wirklich einfach.)
Gruß,
Christopher
Klaus Nagel
Hallo Rainer,
da ich mich schon eine Weile mit dem Gitterproblem beschäftige, wußte
ich, daß tan(22.5°) = Wurzel(2) - 1 ist. Das folgt auch leicht aus dem
Additionstheorem:
2x
----- = 1 = tan(45°);
1-x*x
Für die Wurzel aus 2 kannte ich die Näherungen 7/5, 17/12, 41/29, 99/70.
Eins abgezogen ergibt 2/5, 5/12, 12/29, 29/70 und daraus erkennt man das
Bildungsgesetz.
Im Allgemeinen entwickle ich X in einen Kettenbruch mit dem Taschenrechner:
Schritt 1:
X eingeben
Schritt 2:
Den ganzzahligen Anteil als k[n] notieren.
n jedesmal erhöhen, mit 2 beginnen.
Schritt 3:
Den ganzzahligen Anteil abziehen.
Schritt 4:
Kehrwer t von X
Zu Schritt 2 gehen.
Aus den notierten Zahlen berechnen sich dann Zähler und Nenner nach
diesem Schema:
n k[n] A[n] B[n]
0 0 1
1 1 0
2 k[2] A[2] B[2]
3 k[3] A[3] B[3]
...
A und B berechnen sich nach
A[n] = k[n]*A[n-1] + A[n-2]
B[n] = k[n]*B[n-1] + B[n-2]
Beispiel x = 3.141592653
Ganzzahliger Anteil 3
Rest 0.141592653
Kehrwert 7.06251331
Ganzzahliger Anteil 3
Rest 0.141592653
Kehrwert 7.06251331
Ganzzahliger Anteil 7
Rest 0.06251331
Kehrwert 15.996593261
Ganzzahliger Anteil 15
Rest 0.996593261
Kehrwert 1.003418385
Ganzzahliger Anteil 1
k A B A/B
0 1
1 0
-----------------
3 3 1 3.000000
7 22 7 3.142857
15 333 106 3.141509
1 355 113 3.141593
Für Quadratwurzeln aus ganzen Zahlen gibt es eine bessere Methode, die
keine Numerik erfordert.
>
> ***
> 2
> ***
>
> Nun ja, ein Purzelbaum war es. Und irgendwie kreativ ja auch. Aber
> ob es was nützt, diese Selbstähnlichkeit der Gitter zu nutzen, weiss
> ich nicht so recht. Ich hatte da so gewisse Rosinen im Kopf, und als
> ich die Idee fixieren wollte, blieb nur diese magere Beschreibung
> übrig. Sollte jemand daraus einen Lösungsansazt basteln, dann werde
> ich bestimmt rufen: "Ja, genau das hatte ich gemeint!" :-)
An Ähnliches hatte ich gedacht, als ich noch glaubte, zeigen zu können,
dass es keine beschränkte Bijektion gibt :-)
>
> ***
> 3
> ***
>
> Das Programm möchte ich auch gerne zugesendet bekommen, Klaus!
Ich habe das Programm ein wenig kommentiert und auf meine Seite gestellt:
http://nagel-klaus.homepage.t-online.de/gyt.c
Gruss,
Klaus Nagel
Rainer Rosenthal
>> ***
>> 1
>> ***
>>
> ich, daß tan(22.5°) = Wurzel(2) - 1 ist.
Danke, dann trifft hier also zu, was Christoph Creuzig geschrieben
hatte, dass die Kettenbruch-Entwicklung von sqrt(2) zu Hilfe genommen
wird. Schön, dass Du trotzdem noch auf allgemeinere Fälle zu sprechen
gekommen bist, denn darum ging es mir ja auch.
>> ***
>> 2
>> ***
>
> An Ähnliches hatte ich gedacht, als ich noch glaubte, zeigen zu können,
> dass es keine beschränkte Bijektion gibt :-)
Ebenfalls :-)
Allerdings habe ich immer geglaubt, dass es eine geben müsse.
Wenn eine Menge dünner ist als die andere, dann geht's natürlich
nicht. Aber die beiden Gitter sind ja gleich dick.
Deswegen klappt die Bijetion in den um 22,5° geneigten Streifen
so gut: weil längs diesen Streifen beide Gitter gleich dick sind.
>> ***
>> 3
>> ***
>>
>>Das Programm ...
> http://nagel-klaus.homepage.t-online.de/gyt.c
Danke!
Klaus
[...]
> Man sollte versuchen, ein Punktepaar G, H zu finden, dessen Abstand
> Deiner Schranke nahe kommt. Am einfachsten scheint mir das in Deinem
> zweiten Bild mit der Schranke 1 zu sein.
Zum einem Fall in Schranken-Naehe.
http://home.wtal.de/klaus/gh10a.png
Aus den 0.224 wird 203 schwarze Rauten weiter unten ~0.01 (ohne
Kontrolle/Gewaehr).
Mir ist noch unklar, wieweit das vom Streifen-Offset abhaengt
(Streifenmitte auf Drehpunkt
bis Streifenrand auf Drehpunkt).
Gruss
-- Klaus
Klaus Nagel
> Zum einem Fall in Schranken-Naehe.
> http://home.wtal.de/klaus/gh10a.png
> Aus den 0.224 wird 203 schwarze Rauten weiter unten ~0.01 (ohne
> Kontrolle/Gewaehr).
Kannst Du bitte die Rasterkoordinaten angeben.
> Mir ist noch unklar, wieweit das vom Streifen-Offset abhaengt
> (Streifenmitte auf Drehpunkt
> bis Streifenrand auf Drehpunkt).
>
>
Bisher habe ich stillschweigend angenommen, daß der Drehpunkt der
gemeinsame Nullpunkt (ein Rasterpunkt) ist. Bei einer Verschiebung
findet man für jede Schranke epsilon > 0 zwei Punkte mit kleinerem
Abstand. Einen davon kann man als neuen Nullpunkt nehmen. Es ändert sich
nichts Wesentliches, man muß aber bei allen Rechnungen das epsilon
mitschleppen.
Über Nacht habe ich mein Gitterprogramm
http://nagel-klaus.homepage.t-online.de/gyt.c
mit N = 100000 laufen lassen. Es sind also 10 Milliarden
Rasterpunktpaare untersucht worden. Als größter Abstand wurde
0.99999381*cos(22.5°) gefunden bei den
G-Koordinaten 16730 73852 und den
H-Koordinaten -40391 64052
Das kann kein Zufall sein und spricht für die Streifenbreite als
Schranke. Es sollte doch zu beweisen sein!
Gruß,
Klaus Nagel
Rainer Rosenthal
> Über Nacht habe ich mein Gitterprogramm
>
> http://nagel-klaus.homepage.t-online.de/gyt.c
>
> mit N = 100000 laufen lassen. Es sind also 10 Milliarden
> Rasterpunktpaare untersucht worden. Als größter Abstand wurde
> 0.99999381*cos(22.5°) gefunden bei den
> G-Koordinaten 16730 73852 und den
> H-Koordinaten -40391 64052
>
> Das kann kein Zufall sein und spricht für die Streifenbreite als
> Schranke. Es sollte doch zu beweisen sein!
>
Hallo Klaus,
ich habe alles genau so vorgefunden, wie Du es beschrieben hast.
Ich habe Deine Abbildungsvorschrift
g ----------> h = partner(g)
in Maple nachgebildet und mit Zeichnungen garniert. Man kann sich
wirklich dumm und dämlich suchen und findet die meisten Abstände
deutlich kleiner als die Streifenbreite C = cos(22.5°) = 0.92388.
Als ich noch mit zu kleiner Präzision (nur Digits = 10 statt 20)
gerechnet hatte, hatte ich allerlei Fata-Morgana-Effekte wie z.B.
den, dass die Punkte g = [204,...] besonders oft besonders weit
entfernte Partner hätten.
Ich war dann doch sehr erstaunt, dass für Dein g = [16730,j]
nur sehr kleine Abstände für j von 0 bis 10000 herauskamen.
(Klein bedeutet kleiner als 72% von C.) Um so gewaltiger aber der
Treffer bei j=73852.
Man sieht: Mathematik ist doch eine Naturwissenschaft. Und - wenn
man die Punkte auf den Bildern betrachtet - nahe verwandt mit der
Astronomie. Noch ein Weilchen, und ich kann Sternbilder in den
Tapeten erkennen :-)
Wolfgang Kirschenhofer hat trotz dsm-Abstinenz noch geschrieben,
dass er sich die Gitter-Geschichte anschauen wollte.
Mal sehen, ob er dies langsam unheimliche Geheimnis lüftet.
Gruss,
Klaus Nagel
> ich habe alles genau so vorgefunden, wie Du es beschrieben hast.
> Ich habe Deine Abbildungsvorschrift
>
> g ----------> h = partner(g)
>
> in Maple nachgebildet und mit Zeichnungen garniert. Man kann sich
> wirklich dumm und dämlich suchen und findet die meisten Abstände
> deutlich kleiner als die Streifenbreite C = cos(22.5°) = 0.92388.
>
Hallo Rainer,
schön, daß Du das alles nachprüfen konntest. Ich bin an den
Maple-Zeichnungen interessiert. Inzwischen bin ich dem Geheimnis auf der
Spur. Wenn man ein Gegenbeispiel konstruieren will von zwei zugeordneten
Punkten in großem Abstand, wie die Punkte H und G in der Zeichnung
http://nagel-klaus.homepage.t-online.de/gyta.jpg
dann muß H nahe bei G' liegen. Je näher aber zwei Punkte zusammenfallen,
je näher liegen sie an der Streifenmitte; die Situation G'-H am
Streifenrand ist unmöglich. In
http://nagel-klaus.homepage.t-online.de/gyta.jpg
sind Paare mit weniger als 0.1 Abstand schwarz eingefärbt. Zum Beweis
dieser Eigenschaft benutzt man, daß T² = 1 - 2T gilt, für T = cos(22.5°).
Die genaue Abschätzung habe ich noch nicht durchgeführt.
Gruß,
Klaus Nagel
Rainer Rosenthal
> Spur. Wenn man ein Gegenbeispiel konstruieren will von zwei zugeordneten
> Punkten in großem Abstand, wie die Punkte H und G in der Zeichnung
>
> http://nagel-klaus.homepage.t-online.de/gyta.jpg
>
...
> Streifenrand ist unmöglich. In
>
> http://nagel-klaus.homepage.t-online.de/gyta.jpg
>
> sind Paare mit weniger als 0.1 Abstand schwarz eingefärbt.
Hallo Klaus,
das zweite Bild ist leider falsch benannt. Sage mir bitte den
richtigen Namen.
Danke und Gruss,
Rainer
Klaus Nagel
>
>
> das zweite Bild ist leider falsch benannt. Sage mir bitte den
> richtigen Namen.
>
'a' gestrichen:
http://nagel-klaus.homepage.t-online.de/gyt.jpg
Gruß,
Klaus Nagel
Klaus
> Klaus wrote:
>
> > Zum einem Fall in Schranken-Naehe.
> > http://home.wtal.de/klaus/gh10a.png
> > Aus den 0.224 wird 203 schwarze Rauten weiter unten ~0.01 (ohne
> > Kontrolle/Gewaehr).
>
> Kannst Du bitte die Rasterkoordinaten angeben.
Ja, ich werds heut abend versuchen. Vermutl. aber mit einem
Streifen-Offset != 0. Kannst du in deinem Programm eine Streifen-Offset
vorgeben? Wenn ja, waers vielleicht ausserdem interessant ob der
Maximalabstand eines mittelgrossen Gitterbereichs als Funktion des
Streifen-Offsets auf irgend eine Schranke konvergiert (evtl. durch
einfache Intervallhalbierungsmethode des Streifen-Offsets).
>
> > Mir ist noch unklar, wieweit das vom Streifen-Offset abhaengt
> > (Streifenmitte auf Drehpunkt
> > bis Streifenrand auf Drehpunkt).
> >
> >
> Bisher habe ich stillschweigend angenommen, daß der Drehpunkt der
> gemeinsame Nullpunkt (ein Rasterpunkt) ist. Bei einer Verschiebung
> findet man für jede Schranke epsilon > 0 zwei Punkte mit kleinerem
> Abstand. Einen davon kann man als neuen Nullpunkt nehmen. Es ändert sich
> nichts Wesentliches, man muß aber bei allen Rechnungen das epsilon
> mitschleppen.
>
Wenn ich das jetzt recht verstehe, koennte man also im Programm sogar
drei Offsets einfuehren: Exzentrischer Drehpunkt in x und y,
Streifen-Offset in y. Das heisst man koennte die drei Offsets (vor
allem die letzten beiden voneinander unabhaengig!) mit einer Toleranz
so vorgeben, dass sich 'ganz in der Naehe' Bijektionen mit Abstand > 1
ergeben, und dann mit der Toleranz den Drehpunkt _mit_ Streifen-Offset
= 0 zurueckrechnen -- oder evtl. genauer erkennen inwieweit diese
Offsets zusammenhaengen...
> Über Nacht habe ich mein Gitterprogramm
>
> http://nagel-klaus.homepage.t-online.de/gyt.c
>
> mit N = 100000 laufen lassen. Es sind also 10 Milliarden
> Rasterpunktpaare untersucht worden. Als größter Abstand wurde
> 0.99999381*cos(22.5°) gefunden bei den
> G-Koordinaten 16730 73852 und den
> H-Koordinaten -40391 64052
>
> Das kann kein Zufall sein und spricht für die Streifenbreite als
> Schranke. Es sollte doch zu beweisen sein!
>
Das klingt plausibel. Leider fehlt mir hierzu die Erfahrung und fuer
die es wissen, ist es vielleicht ein langweiliges Thema. Macht aber
nichts, denn noch ein Stueck selbst weiter kommen kann ja ganz spannend
und lehrreich sein :-).
> Gruß,
> Klaus Nagel
Klaus
Gx = 113;
Gy = 92;
Hx = 146;
Hy = -15;
xG= Gx *cosa -Gy *sina = 69.1915;
yG= Gx *sina +Gy *cosa = 128.24;
xH= Hx *sina -Hy *cosa = 69.73;
yH= Hx *cosa +Hy *sina = 129.146;
dx= xH -xG = 0.538463;
dy= yH -yG = 0.906015;
a= sqrt( dx^2 +dy^2) = 1.05395;
% Offset Streifenmitte / Drehpunkt
ym= 0.27;
% Streifenraender
y0= ym +138.5 *cosa = 128.227;
y1= ym +139.5 *cosa = 129.151;
% Scherenschnittpunkte
xs= (( yG -yH) *tana +xG +xH) /2. = 69.2731;
ys0= ( xs -xH) /tana +yH = 128.043;
ys1= ys0 +0.5 /sina = 129.35;
Den Streifenoffset wesentlich weiter gegen Null zu druecken ist mir
bisher (unter Voraussetz. a = 1.01 bis 1.07) nicht gelungen.
Gruss
-- Klaus
Hugo Pfoertner
Hallo Mathefreunde,
um wenigstens in der Endphase noch ein Koernchen zur 2-Gitterforschung
beizutragen, hab ich in den letzten Tagen ein bisschen empirische
Partnerforschung betrieben. Dazu hab ich das Klaussche gyt.c mit der
Rainerschen Zwiebelschalenidee verheiratet und die Partnersuche
beginnend am gemeinsamen Dreh- und Angelpunkt der beiden Gitter auf die
Gitterpunkte beschraenkt, die innerhalb aufeinanderfolgender Kreisringe
mit Radiendifferenz 1 liegen. Damit fallen die vermuteten
Rekordabstaende besser geordnet an, als wenn man entlang einzelner
Rasterlinien sucht.
Das Ergebnis der radialen Rekordjagd ist interessant:
G-Indices H-Indices cos(22.5Grad) Radius(G)
- dist(G,H)
-1 0 <-> -1 0 Abstand 0.1715729 1.00000000
-6 0 <-> -5 -4 Abstand 0.1391969 6.00000000
-6 2 <-> -6 -2 Abstand 0.0294373 6.32455532
-6 31 <-> -27 18 Abstand 0.0291309 31.57530681
-35 2 <-> -27 -23 Abstand 0.0243104 35.05709629
-35 14 <-> -35 -14 Abstand 0.0050506 37.69615365
-35 183 <-> -155 105 Abstand 0.0050418 186.31693428
-204 14 <-> -155 -134 Abstand 0.0041819 204.47982786
-204 84 <-> -204 -84 Abstand 0.0008666 220.61731573
-204 1069 <-> -901 612 Abstand 0.0008663 1088.29086186
-1189 84 <-> -901 -781 Abstand 0.0007178 1191.96350615
-1189 492 <-> -1189 -492 Abstand 0.0001487 1286.77309577
-6930 492 <-> -5249 -4552 Abstand 0.0001232 6947.44298285
-6930 2870 <-> -6930 -2870 Abstand 0.0000255 7500.78662541
Betrachtet man jetzt die Stellen, wo eine signifikante Annaeherung des
benoetigten Abstandes an die Streifenbreite cos(22.5Grad) erfolgt, so
passiert das bei folgenden Indexpaaren:
-6 2 <-> -6 -2
-35 14 <-> -35 -14
-204 84 <-> -204 -84
-1189 492 <-> -1189 -492
-6930 2870 <-> -6930 -2870
Wie immer in solchen Faellen hilft hier die OEIS:
6,35,204,1189 ->
http://www.research.att.com/~njas/sequences/A001109
0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, 46611179,
a(n)^2 is a triangular number: a(n) = 6*a(n-1) - a(n-2) with a(0)=0,
a(1)=1.
und
2,14,84,492, ->
http://www.research.att.com/~njas/sequences/A053141
0, 2, 14, 84, 492, 2870, 16730, 97512, 568344, 3312554, 19306982,
112529340
a(n) = 6*a(n-1)-a(n-2)+2, a(0) = 0, a(1) = 2;
G.f.2*x/((1-x)*(1-6*x+x^2)).
Die naechsten G-Index-Kandidaten fuer Gitterpunkte mit
Partner-Abstaenden naeher an der Streifenbreite sind demnach:
(6930,2870), (40391,16730), (235416,97512) usw.
Die Quotienten 2870/6930, 16730/40391, 97512/235416, ... sind
konvergente Naeherungen an sqrt(2)-1, was gerade der Tangens von 22.5
Grad ist.
Der Ball liegt jetzt auf dem Elfmeterpunkt - jetzt seid Ihr dran ;-)
Viel Spass
Hugo
Rainer Rosenthal
> Klaus Nagel schrieb:
>>Über Nacht habe ich mein Gitterprogramm
>>
>>http://nagel-klaus.homepage.t-online.de/gyt.c
>>
>>mit N = 100000 laufen lassen. Es sind also 10 Milliarden
>>Rasterpunktpaare untersucht worden. Als größter Abstand wurde
>>0.99999381*cos(22.5°) gefunden bei den
>>G-Koordinaten 16730 73852 und den
>>H-Koordinaten -40391 64052
>>
>>Das kann kein Zufall sein und spricht für die Streifenbreite als
>>Schranke. Es sollte doch zu beweisen sein!
> Wie immer in solchen Faellen hilft hier die OEIS:
> ... http://www.research.att.com/~njas/sequences/A001109
> ... http://www.research.att.com/~njas/sequences/A053141
> Die naechsten G-Index-Kandidaten fuer Gitterpunkte mit
> Partner-Abstaenden naeher an der Streifenbreite sind demnach:
> (6930,2870), (40391,16730), (235416,97512) usw.
>
> Die Quotienten 2870/6930, 16730/40391, 97512/235416, ... sind
> konvergente Naeherungen an sqrt(2)-1, was gerade der Tangens von 22.5
> Grad ist.
>
> Der Ball liegt jetzt auf dem Elfmeterpunkt - jetzt seid Ihr dran ;-)
Ich sitze noch auf der Ersatzbank bzw. stehe daneben und balanciere
den Ball ein wenig, um im Falle einer Einwechslung aufgewärmt zu sein.
Ich habe meiner Vorstellung mittels verbesserter Maple-Bilder auf die
Sprünge geholfen. Es zeigte sich, dass der Super-Punkt g = [16730,73852]
nach der Drehung um Pi/8 = 22,5° sagenhaft dicht am oberen Rand seines
Streifens liegt, der die Höhe C = cos(Pi/8) hat: die y-Koordinate ist
das 80782.4999978-fache von C. Und bei C*80782.5 beginnt bereits der
andere Streifen darüber.
Also habe ich Maple gebeten (es nudelt gerade noch, während ich Dein
ebenfalls spätes Posting lese), mir zu sagen, für welche g so etwas
passiert. Jedes bessere g soll mir angezeigt werden. Glücklicherweise
muss ich nicht in der Fläche suchen sondern es genügt, Punkte g = [i,0]
zu betrachten, da g = [i,j] gleichen Abstand zum Streifenrand hat wie
g = [i,0]. Die entsprechenden i-Werte purzeln heraus:
1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214
ein klein wenig schade ist es jetzt natürlich, dass ich ein paar Minuten
nach Dir zu http://www.research.att.com/~njas/sequences/A001109 komme :-/
Andererseits ist es doch auch wieder fantastisch, dass wir da ganz
nahe beieinander suchen und uns Bälle zuspielen können. Ich war nämlich
etwas erstaunt, mein i=16730 nicht in der Liste zu finden.
Allerdings habe ich längst schon die Streifen an der y-Achse gespiegelt,
um mir anzuschauen, wie es da aussieht. Netterweise wird bei dieser
Spiegelung aus einem G-Punkt ein H-Punkt des Streifend und umgekehrt!
Was ist wohl der Spiegelpunkt des Super-Punktes g = [16730,73852]?
Tja, es ist ... [40391,64052]. Und diese erste Koordinate kennen wir aus
der obigen Liste!
Es ist schon erstaunlich, was Du aus der Zwiebel pressen konntest. Die
habe ich längst als unbrauchbar beiseite gelegt. Die geniale Bijektion
von Klaus Nagel zirkelt den Ball schliesslich unhaltbar ins Tor!
Diese Bijektion arbeitet mit der Zerlegung der Ebene in diese C-breiten
Streifen S, in denen jeweils ein Bijektion b_S von den Gitterpunkten
G_S (in G und in S) auf die Gitterpunkte H_S (in H und S) definiert ist.
Diese Bijektion ist algorithmisch klar definiert (Funktion "partner" im
Programm gyt.c) und es genügt, sich alle Konstellationen anzuschauen,
die in einem Streifen vorkommen können. Die Ebene kann man dabei
getrost ausser Betracht lassen.
Dafür brauche ich aber jedenfalls noch etwas Zeit. Nach den letzten
Äusserungen von Klaus dachte ich schon, sein Beweis über die obere
Schranke sei schon wasserdicht. Es muss wohl noch was zu flicken sein,
oder es gibt gerade was Wichtigeres in der Astronomie oder Natur-
Fotografie zu tun.
Gruss,
Rainer
Rainer Rosenthal
> Wie immer in solchen Faellen hilft hier die OEIS:
>
> 6,35,204,1189 ->
>
> http://www.research.att.com/~njas/sequences/A001109
> 0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, 46611179,
> a(n)^2 is a triangular number: a(n) = 6*a(n-1) - a(n-2) with a(0)=0,
> a(1)=1.
>
Donnerwetter ... die Rekursion liess mich vermuten, dass ich mit
dieser Folge schon mal Berührung hatte. Und siehe da, in einem alten
Excel-Blatt, in dem ich meine Aufzeichnungen zur Tangentenaufgabe von
Ingmar Rubin stehen hatte (als hier "die Marginale" diskutiert wurde),
findet sich folgende Bemerkung:
===========================
Nachtrag: Der Punkt S hat den Abstand 1/6 zu M, also hat g den
Abstand g von M mit g = 1/4 * ( -s + sqrt( 8r^2 + s^2))
Und das ist ... 2/3 weil 8*6^2+1 = 17^2
Prima: Damit ist bewiesen, dass S nicht nur ungefähr auf der
y-Achse liegt sondern genau.
Wann ist 8m^2+1 ein Quadrat? 1 6 35 204 ... ist Folge A001109
Das führt mich geradewegs zurück zu A001110 = A001109^2
Also zu dem Beginn meiner Entdeckungsreise bei den R_r und S_r Folgen.
===========================
Das ist alles ein wenig viel für einen älteren Herrn. Ich ziehe mich
erst mal zurück. Besten Dank jedenfalls für die schönen Mitteilungen.
Morgen (äh, heute) gehe ich wieder auf Streife.
Gruss,
Klaus
Nach wenigen Substitutionen und Umformungen der Grundgleichungen
erhaelt man (gerundet):
z = 1.207 *Dx -k *0.924 mit z, Dx reell, k ganz
z: y-Differenz von Streifenmitte zur Mitte zwischen den
Bijektionspunkten G und H
Dx: x-Differenz der Bijektionspunkte G und H
Und dort, wo bei beliebigem Streifenoffset Abstaende bis auf 1.071
moeglich sind, reduzieren sich die Moeglichkeiten drastisch, alle
Bijektionen mit Abstand > cos(22.5 deg) entfallen!
Gruss
-- Klaus
Klaus Nagel
Hallo Klaus,
da Deine Überlegungen in die gleiche Richtung gehen wie meine, stelle
ich meinen augenblicklichen Stand dar:
Das Rastermaß wird so skaliert, daß der Streifenabstand zu eins wird,
die Seitenlänge also 1/cos(22.5°).
Das Gitter G (nach links geneigt) habe die Koordinaten i und j. Die
i-Achse weise nach links.
Das Gitter H (nach rechts geneigt) habe die Koordinaten k und l.
T = tan(22.5°)
Die xy-Koordinaten berechnen sich zu
Gx = -i -j*T Gy = -i*T + j
Hx = k + l*T Hy = -k*T + l
Für die Differenzen erhält man
delta = Hx - Gx = (i+k) + (l+j)*T
epsilon = Hy - Gy = (i-k)*T + (l-j)
Berücksichtigt man T² = 1 - 2*T dann folgt aus diesen beiden Gleichungen
Gy = m + eta
Hy = m + zeta, mit m = i+j+k+l, eta = -(delta/T + epsilon)/2 und
zeta = -(delta/T - epsilon)/2
Wenn delta und epsilon klein sind, dann auch eta und zeta, das sind aber
genau die Abstände von der Streifenmitte, denn m ist ganzzahlig und
wegen der Skalierung haben die Mittellinien ganzzahlige y-Werte.
Der Abstand Wurzel(delta² + epsilon²) läßt sich somit aus eta und zeta
berechnen.
Das erklärt die Beobachtung, daß nahe Begnungen immer in der
Streifenmitte stattfinden. Vergleiche dazu die schwarz markierten Punkte in:
http://nagel-klaus.homepage.t-online.de/gyt.jpg
Probleme habe ich noch damit, daß zeta und eta sich auch auf
Nachbarstreifen beziehen können.
Gruß,
Klaus Nagel
Rainer Rosenthal
> Der Ball liegt jetzt auf dem Elfmeterpunkt - jetzt seid Ihr dran ;-)
Hallo Hugo,
es gibt aber *drei* Aufgaben zu lösen:
1. Den Ball auf den Elfmeterpunkt zu legen.
3. Unhaltbar ins Tor zu donnern.
Dazwischen gibt es aber noch eine sehr schwierige Aufgabe,
für die man mehrere Leute benötigt:
2. Das Tor aufstellen.
Nee, im Ernst: irgendwas Geheimnisvolles ist da noch.
Ich habe mal die Situation um den Punkt [40391,64052]
skizziert und dann die drei Elemente
Gitter G
Gitter H
Streifen S
ein wenig gegeneinander verschoben: es lassen sich auf
diese Weise gemeinere Situationen herstellen, bei denen
eine Streifenbijektion grössere Abstände geben könnte.
Ich kann das gerne kurz skizzieren:
Xx
x
---------------------------C----------------------------
b e
B F
A c E
a
-------------------------------X------------------------
x x
x
Das ist ziemlich naturgetreu nachgemalt. Die Grossbuchstaben
bezeichnen die Punkter des Gitters G, wobei C = [40391,64052]
ist. Die entsprechenden Kleinbuchstaben bezeichnen ihre Bild-
punkte unter Klaus Nagels Streifenbijektion. Die mit X und x
bezeichneten Punkte gehören nicht mehr zum Streifen, sondern
dienen zur Vorstellung der Gitter in der Gegend.
Der Punkt C liegt brutal dicht am oberen Ende des Streifens.
Was aber daran so besonders toll sein soll, dass C so sehr eng
am Rand liegt, ist nicht einfach zu erkennen. Man kann das H-
Gitter problemlos um ein Epsilon herunterziehen - und schon
würden die Gummibänder der Bijektion sich leicht ändern, und
die Verbindung C-c wäre über cos(Pi/8) hinaus vergrössert.
Es muss an der speziellen Bauart der Gitter-Verdrehung liegen,
dass sowas niemals vorkommt.
Man kann übrigens auch im Nullstreifen(*) auf Jagd nach grossen
Abständen gehen. Ich habe das zwar noch nicht systematisch
gemacht, aber für g = [1000094, -414252] beispielsweise hat
man einen Abstand von 0.9210 zum Partner. Der Nullstreifen
ist besonders übersichtlich: alle Bijektions-Gummibänder sind
parallel und natürlich kann die Streifenbreite cos(Pi/8)
auch nicht überschritten werden. Sie kann nicht einmal genau
erreicht werden.
So wie dieser Nullstreifen aber eine klar zu Tage liegende
Struktur hat, aus der maximale Abstand(g,Partner(g)) mit einem
Blick hervorgeht, so *müssen* die anderen Streifen ebenfalls
eine Struktur haben, die den Abstand(g,Partner(g)) auf weniger
als cos(Pi/8) zwingt. Nur ist diese Struktur nicht so offen-
sichtlich. Noch nicht! Wir brauchen noch einen Tor-ero!
(*) Beim Korrekturlesen ist mir aufgefallen, dass dieser Ausdruck
zu erklären ist: Ich meine den Streifen um die x-Achse.
Rainer Rosenthal
> Das erklärt die Beobachtung, daß nahe Begnungen immer in der
> Streifenmitte stattfinden. Vergleiche dazu die schwarz markierten Punkte in:
>
> http://nagel-klaus.homepage.t-online.de/gyt.jpg
>
Hallo Klaus,
in meinem anderen Posting von eben habe ich auf die besondere Bauart
der Doppelgitter-Konstruktion hingewiesen, die sie von irgendwie
verschoben hingelegten Gittern G und H unterscheidet, selbst wenn
ihre Grundlinien sich unter dem Winkel von 45° schneiden.
Wie wäre das? Gitter H mit einem kleinen Offset zu versehen und dann
mal experimentell die maximalen Abstände anzuschauen. Die Streifen-
Bijektion muss ja auch dann noch funktionieren.
Ha, tolle Vermutung: dann könnte die Schranke sich vielleicht wieder
derjenigen von Wolfgang Thumser nähern!
Grossartige Schnapsidee:
Schranke C = cos(Pi/8) gilt genau für
die spezielle Gitterverdrehung um 45°
um den Ursprung.
Wird auch Translation von H zugelassen,
dann gibt es immer noch eine Schranke
für den Abstand, aber diese T-Schranke(*)
ist evtl. grösser als 1.
(*) T steht für Translation oder Thumser :-)
Hugo Pfoertner
>
> Hugo Pfoertner schrieb:
>
> > Der Ball liegt jetzt auf dem Elfmeterpunkt - jetzt seid Ihr dran ;-)
>
> Hallo Hugo,
>
> es gibt aber *drei* Aufgaben zu lösen:
>
> 1. Den Ball auf den Elfmeterpunkt zu legen.
> 3. Unhaltbar ins Tor zu donnern.
>
> Dazwischen gibt es aber noch eine sehr schwierige Aufgabe,
> für die man mehrere Leute benötigt:
>
> 2. Das Tor aufstellen.
[OT]-Antwort: Wer hat denn gesagt, dass jetzt ein Elfmeter geschossen
werden soll? Tatsaechlich hat es beim Elfmeterpunkt zuvor ein
Stuermerfoul gegeben, und der vom Torwart ausgefuehrte faellige
Freistoss wird in der Naehe der Mittellinie ins Seitenaus gehen. Wann
dann der Ball wieder in Tornaehe auftaucht, wissen wir noch nicht.
Noch was zur Sache: Dass ich in der langen Kommentarliste zur OEIS
A001109 auch noch die Bemerkung "One half the bisection of the Pell
numbers (A000129). - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Jan
08 2006" gefunden hab, fand ich angesichts meiner E-mail vom 18. Januar
zum Auftreten von Rekordabstaenden zum naechstliegenden Partner im
gedrehten Gitter witzig.
Hugo
Wolfgang Thumser
> Gx = -i -j*T Gy = -i*T + j
> Hx = k + l*T Hy = -k*T + l
als Ergaenzung zu den Transformationen vielleicht noch:
Zu gegebenem i bzw. k werden (i,j:=[i*T]+n) bzw. (k,l:=[k*T]+n)
durch diese Gleichungen in den n-ten Streifen abgebildet.
G(i,j) und H(k,l) werden in diesem Streifen genau dann auf-
einander abgebildet, falls zudem i+k+[n*sqrt(2)/2]=0 gilt.
Dabei bezeichnet [x] die "nearest integer" zu reellem x.
Koennt ihr das bestaetigen?
Gruss Wolfgang
Klaus
Hallo Wolfgang,
mein Weg ist wohl etwas anders, ob er aequivalent ist kann ich leider
noch nicht sagen.
Zunaechst wird die Menge aller moeglichen H-G-Koord.diff. (dx,dy)
unabh. von einem Streifenoffset betrachtet. Dann kommt die schon
erwaehnte "Offset-Null"-Gleichung, etwas umgeformt:
(yn'=Streifenmitte-Scherenschnittpunkt) = dx/tana - cosa *k
Unabh. von (dx,dy) muss aber im Fall yn' > cosa/2 gelten: yn' <
1(/4*sina).
==> die moeglichen dx gibt es nur auf bestimmten Intervallen,
dazwischen klaffen recht grosse Luecken! Zurueck in die Menge (dx,dy),
diese zusaetzl. Einschraenk. beruecksichtigen und die moeglichen
Bijkekt. sind sichtbar (in dx,dy).
Brauche allerdings noch etwas Zeit um alles etwas ordentlicher zu
notieren :-).
Gruss
-- Klaus
Rainer Rosenthal
> als Ergaenzung zu den Transformationen vielleicht noch:
>
> Zu gegebenem i bzw. k werden (i,j:=[i*T]+n) bzw. ...
> durch diese Gleichungen in den n-ten Streifen abgebildet.
> G(i,j) ... in diesem Streifen ...
> Dabei bezeichnet [x] die "nearest integer" zu reellem x.
>
> Koennt ihr das bestaetigen?
Herzlichen Dank dafür, Klaus Nagels faszinierender Bijektion
mit Formeln auf den Leib zu rücken. Ich träume auch von einer
Ramanujan-würdigen Identität, die hinter den Geheimnissen
steckt.
In Deiner Formulierung ist der Beginn aber falsch, den Rest
muss ich noch genauer betrachten. Ganz hübsch finde ich die
ASCII-Darstellung von [.x.] = floor(x). Sie wird statt
"nearest integer" oder [x] = round(x) benötigt. Und falls
wir jemals über die ceiling-Funktion sprechen werden,
schlage ich ['x'] = ceil(x) vor.
Hier die Korrektur:
Zu gegebenem i ist j = [.i*T.]+n zu wählen, um G(i,j) im
n-ten Streifen zu haben. Es ist ja G(i,j)=(Ci-Si,Cj+Sj).
Es bedeuten dabei: T=tan(Pi/8), S=sin(Pi/8) und C=cos(Pi/8),
und mit [.x.] bezeichne ich die grösste ganze Zahl k <= x.
Ein Punkt (x,y) "liegt im n-ten Streifen", wenn gilt
C*(n-1/2) <= y < (C*n+1/2),
also
n <= y/C+1/2 < n+1
oder
n = [.y/C.]
Gruss,
Rainer Rosenthal
r.ros...@web.de
Wolfgang Thumser
> Herzlichen Dank dafür, Klaus Nagels faszinierender Bijektion
> mit Formeln auf den Leib zu rücken. Ich träume auch von einer
> Ramanujan-würdigen Identität, die hinter den Geheimnissen
> steckt.
dann betrachte 'mal die Rekursion q0=1, q1=1, q{n+2}=2q{n+1}+qn
und vergleich' die Ergebnisse mit den Zeilen der schwarz markierten
Punkten in Klaus' Liste <http://nagel-klaus.homepage.t-online.de/gyt.jpg>.
Und dann denk' nochmal ueber die angegebenen Formeln nach.
> In Deiner Formulierung ist der Beginn aber falsch, [...]
Das wuerd' ich nicht zu laut sagen...
> Hier die Korrektur:
> C*(n-1/2) <= y < (C*n+1/2),
> also
> n <= y/C+1/2 < n+1
Wenn der Schiedsrichter schon den Ball auf den Elfmeterpunkt legt,
> oder
> n = [.y/C.]
sollte man ihn nicht um einen halben Meter verruecken, sondern verwandeln.
Gruss Wolfgang
Klaus Nagel
ich denke, Ihr benutzt unterschiedliche Rastergrößen. Ich skaliere
inzwischen mit 1/cos(22.5°). Dadurch bekommen die Streifen die Breite 1
und die Streifenmitten haben ganze Zahlen als y-Koordinaten. Sinus und
Kosinus tauchen nicht mehr auf, nur noch der Tangens. Wolfgang bezieht
sich auf die neue Skalierung, Rainer auf die ursprüngliche.
Gruß,
Klaus Nagel
Rainer Rosenthal
> Skalierung, Rainer auf die ursprüngliche.
Noch ein Schiedsrichter, wow :-!
Wolfgangs Posting las sich so, als hätte er jetzt alles schon
klar und wollte mich als Tip-Kick Figur benutzen: ein Knopfdruck
und Peng - verwandelt. Der Machanismus ist aber leider ausgeleiert.
.
Gruss, Ein
Rainer net tes
----------------------------ASCIIGitter----------------------------
Rainer Rosenthal bri ngt r.ros...@web.de
Fun
'
Rainer Rosenthal
>> n <= y/C+1/2 < n+1 (1)
>> oder
>> n = [.y/C.] (2-falsch)
>
> sollte man ihn nicht um einen halben Meter verruecken, sondern verwandeln.
Sorry, ich hatte da was falsch geschrieben. Ich hätte natürlich
nicht (2) in der falschen Form schreiben sollen sondern so:
n = [.y/C+1/2.] (2)
weil es dann zu (1) äquivalent ist.
Der wesentliche Punkt ist doch aber der, dass Du mit "nearest integer"
gearbeitet hattest. Es muss aber für die Streifenzugehörigkeit mit
"nearest integer below", also mit floor() gearbeitet werden.
Sehe ich das falsch?
Und das Vorzeichen bei Deiner Darstellung ist doch auch nicht OK
gewesen. G ist schliesslich leicht mathematisch positiv gedreht.
Und das ist erst mal unabhängig von der Skalierung.
Bitte um Hilfe.
Gruss,
Rainer