Goswin
Senior Dabei seit: 18.09.2008 Mitteilungen: 1607
Wohnort: Chile, Ulm
Themenstart: 2021-03-06
*leichte Schülerknobelei*, Senioren bitte nicht teilnehmen!
In einem Koordinatensystem mit \(0\le x\le7,~0\le y\le7\) soll ein möglichst gleichseitiges Dreieck mit ganzzahligen Koordinaten der Ecken eingezeichnet werden. Die "Qualität" des Dreiecks wird gemessen durch den Bruch kürzeste_Seite/längste_Seite; die Länge der kürzesten Seite muss mindestens 95% die der längsten Seite betragen.
Finde die Koordinaten für so ein Dreieck und gebe seine Qualität an.
Antworten direkt posten, aber *BITTE VERDECKT*!
----------------- /Kyristo meu kimgei kom nhi cumgen ta Gendmogen. (Kol.2:9)
Dies ist eine Knobelaufgabe! Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst. Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
MartinN
Aktiv Dabei seit: 05.08.2016 Mitteilungen: 1269
Wohnort: Bayern
Mit rumprobieren hab ich:
A(0,0), B(1,4) und C(4,1) gefunden... damit ist die kurze Seite AB = AC = \(\sqrt{17}\) und die lange Seite BC = \(\sqrt{18}\) mit der Qualität \(\sqrt{\frac{17}{18}}\) = 0.9718...
Gleich gut (nur etwas gestreckt) ist A(0,0), B(6,0), C(3,5) mit AB = \(\sqrt{36}\) und AC = \(\sqrt{34}\).
Um einiges besser wäre A(0,0), B(8,0), C(4,7) mit AB = \(\sqrt{64}\) und AC = \(\sqrt{65}\) - immerhin \(\sqrt{\frac{64}{65}}\) = 0.9922...
$(2/2), (5/5), (6/1) $ und viele mehr 🙃
Komme insgesamt auf 552 mögliche Lösungen.
Kann das jemand bestätigen ?
@Goswin
Bei mir haben alle Lösungen die gleiche Qualität wie die
von MartinN $\approx 0,9718$
Meine erste Lösung kann man von A: (0,0) bis (3,3) verschieben = 16 Möglichkeiten (achsensymmetrisch aber zu einer Parallelen zur Diagonalen des Quadrates).
Meine zweite Lösung von A: (0,0) bis (1,2) verschieben = 6 Möglichkeiten.
Dies kann man aber noch spiegeln an der Diagonale des Quadrates = 6 Möglichkeiten.
haegar90s Lösung kann von A: (0,1) bis (3,4) verschieben = 16 Möglichkeiten. Hier auch eine Spiegelung an der Diagonalen jeweils möglich: weitere 16 Möglichkeiten.
Ergibt insgesamt 16+6+6+16+16 = 60 Möglichkeiten durch verschieben und diagonalen Spiegeln der bisherigen Lösungen. Jetzt kann man das Quadrat noch drehen (A in jede Ecke bringen) = 240 Möglichkeiten.
Fragt sich, welche Lösungen jetzt nicht auf diese 3 ursprünglichen Lösungen zurückzuführen sind xD
Ja, in der Anzahl 552 sind mehrfach gezählte Lösungen für die Punkte $A, B, C$ enthalten so wie z.B. die sechs Permutationen von $(2/1), (2/7), (7/4)$.
So betrachtet nur 92 verschiedene Lösungen ?
Für den Bereich $[0,n]^2 \subset \mathbb{N}_0^2$ liegt das optimale Dreieck für
$4 \le n \le 7$ bei $(0,0), (1,4), (4,1)$ mit $\frac{\text{kurz}}{\text{lang}}=0.9718253158075502$
$n \le 13$ bei $(0,0), (4,7), (8,0)$ mit $\frac{\text{kurz}}{\text{lang}}=0.9922778767136677$
Verschiebungen, Spiegelungen dieser Dreiecke sind natürlich uninteressant, was die Qualität der Dreiecke betrifft.
Höchstens zur Zählung aller möglichen Dreiecke mit der Minimaleigenschaft des Quotienten.
Goswin
Senior Dabei seit: 18.09.2008 Mitteilungen: 1607
Wohnort: Chile, Ulm
Beitrag No.6, vom Themenstarter, eingetragen 2021-03-07
Zur Motivation der Aufgabe:
Ursprünlich wollte ich möglichst regelmäßige aneinanderliegende Sechsqecke, also ein Wabenmuster, auf ein quadriertes Blatt Papier zeichnen, und ich war mir bewusst, dass ähnlich lange Sechsqeckseiten dafür nicht hinreichend sind. Aber dann habe ich gemerkt, dass man sechs gleiche *beliebig-quasi-gleichseitige* Dreiecke immer zu einem quasi-regelmäßigen Sechsqeck zusammenstellen kann; dass es also genügt, quasi-gleichseitige Dreiecke zu finden.
Für ein Koordinatensystem der Größe \(0\le x\le8,~0\le y\le8\) gibt es eine sehr genaue Lösung von Qualität 99.2%, wo die Unregelmäßigkeit mit (meinem) bloßem Auge nicht zu erkennen ist.
Ach ja, das Wabenmuster wollte ich, um so eine Akkord-Anqordnung zu entwerfen. Da war mir Hohner aber zuvorgekommen.
Goswin
Senior Dabei seit: 18.09.2008 Mitteilungen: 1607
Wohnort: Chile, Ulm
Beitrag No.8, vom Themenstarter, eingetragen 2021-03-07
Es kann ohne Beeinträchtigung des Allgemeinfalls angenommen werden, dass eine der Ecken des Dreiecks die Koordinaten \((0,0)\) hat.
Auch für Senioren:
Eine Dreieck sei hier pareto-optimal genannt, wenn kein *kleineres* oder *gleichgroßes* Dreieck von besserer Qualität existiert; wenn also alle besseren Dreiecke streng größer sind. Die in dieser Knobelaufgabe bisher gefundenen pareto-optimalen Dreiecke sind alle gleichschenklig. Ist das immer so? (Ich weiß nicht die Antwort)
Das von Hand gefundene Dreieck \(\big((0,0),~(56,15),~(15,56)\big)\) hat Qualität \(\sqrt{3361/3362}=99.985\%\,\). Der Bruch unter der Wurzel lässt mich glauben, dass es pareto-optimal ist. Aber es ist ja *auch* gleichschenklig.
Offensichtlich hat eine Lösung die Koordinaten:
\(A(0,0); B(x,y); C \approx (\frac{x}{2}-uy, \frac{y}{2}+vx)\)
Mit ganzzahligen Koordinaten von C und passenden Variablen u und v.
Dann ist:
\(AC = \sqrt{\frac{x^2}{4}-uxy+u^2y^2+\frac{y^2}{4}+vxy+v^2x^2} = \sqrt{x^2+y^2}\\
\to v-u = 0 \to v = u\\
\to \frac{1}{4} + u^2 = 1 \to u = \pm \frac{\sqrt{3}}{2}\)
Damit ist eine Lösung:
\(C \approx (\frac{x-\sqrt{3}y}{2}, \frac{y+\sqrt{3}x}{2})\)
Leicht ersichtlich ist dann auch BC = AB.
Nun soll C möglichst ganzzahlige Koordinaten haben...
Sei: \(\sqrt{3} \approx \frac{p}{q}\) ein guter Näherungsbruch, mit kleinstmöglichen q, so wäre eine mögliche Lösung, so dass:
\(\sqrt{3}y \approx n \in \IN \wedge \sqrt{3}x \approx n \in \IN\\
\to x = y = q \to \sqrt{3}x = \sqrt{3}y \approx p \in \IN\)
Also geht es hier um gute Näherungsbrüche von \(\sqrt{3}\) - also Kettenbrüche.
Und die Lösungen sind dann: \(A(0,0); B(q,q); C(\frac{q-p}{2},\frac{q+p}{2})\)
Wenn aber q+p ungerade ist, dann müsste man alle Koordinaten noch mit 2 multiplizieren - was zu größeren Koordinaten führen kann.
Da aber \(\sqrt{3} > 1 \to p > q\), wäre C negativ :S
Verschieben wir alles um: \((\frac{p-q}{2},0)\), so erhalten wir:
\(A(\frac{p-q}{2},0)\\
B(\frac{p+q}{2},q)\\
C(0,\frac{p+q}{2})\)
Jetzt einmal um \(M(\frac{p+q}{4},\frac{p+q}{4})\) um -90° drehen, so dass C auf den Koordinatenursprung fällt:
\(C(0,0)\\
A(\frac{p+q}{2},\frac{p-q}{2})\\
B(\frac{p-q}{2},\frac{p+q}{2})\)
Jetzt nach 0 verschoben, und alles in einem Quadrat mit Kantenlänge \(\frac{p+q}{2}\) ;)
Man erkennt auch gut, dass die besten Lösungen (mit den kleinsten Näherungen für sqrt{3}) alle gleichschenklig sind.
Man erkennt, dass durch das Verdoppeln manchmal Punkte entstehen, die weiter weg vom Koordinatenursprung liegen bzw. ein größeres Quadrat benötigen als die nächste, bessere Approximation von \(\sqrt{3}\).
Vielleicht kann man auch zeigen (durch die Periodizität des Kettenbruches), dass die Summe (p+q) immer ungerade,ungerade,gerade ist - und damit immer die erste ungerade, und die eine gerade Lösung (aber nicht die mittlere ungerade Lösung) die nächste, bessere Näherung liefert.
Bestimmen wir AB:
\(AB = \sqrt{2q^2} = \sqrt{2}q\)
Strecken wir also alles mit \(\frac{1}{\sqrt{2}}\), so kann man neue Punkte bestimmen mit:
\(A' (0,0); B'(q,0)\)
Jetzt müssen wir das C dazu finden... die Fläche von ABC (mit den Koordinaten berechnet: Dreieck + Trapez - Dreieck) ist:
\((ABC) = \frac{p^2-q^2}{8} + \frac{p}{2}q - \frac{p^2-q^2}{8}\\
= \frac{pq}{2}\)
Durch die Streckung ist dann:
\((A'B'C') = \frac{pq}{4}\)
Und damit die Höhe des gleichschenkligen Dreiecks mit Basis q:
\(h = \frac{p}{2}\\
\to C' (\frac{q}{2},\frac{p}{2})\)
Nun sind weder p noch q beide gerade, denn sonst wäre der Näherungsbruch mit 2 kürzbar. Damit also die Koordinaten von C' ganzzahlig werden, muss man alles verdoppeln:
\(A(0,0); B(2q,0); C(q,p)\)
Mit \(1 < \sqrt{3} < 2 \to q < p < 2q\), passen diese Koordinaten alle in ein Quadrat der Größe \(2q\).
Da \(q < p \to 2q < p+q\). Damit ist diese Lösung besser, also im letzten Post, wenn man die Koordinaten verdoppeln müsste.
Nun lässt sich auch leicht zeigen, mit der Rekursion für die Kettenbrüche von \(\sqrt{3}\):
\(\frac{p_{n+3}}{q_{n+3}} = 1 + \frac{1}{1+\frac{1}{1+\frac{p_n}{q_n}}}\\
= 1 + \frac{1}{1+\frac{q_n}{q_n+p_n}}\\
= 1 + \frac{q_n+p_n}{2q_n+p_n}\\
= \frac{3q_n+2p_n}{2q_n+p_n}\)
\(gcd(p,q) = 1 \to gcd(3q+2p,2q+p)=gcd(q+p,2q+p)=gcd(q+p,q)=gcd(q,p)=1\)
Dieser folgende Näherungsbruch ist also teilerfremd.
Damit haben wir die Rekursion:
\(p_0 = 1, q_0 = 1; p_1 = 2, q_1 = 1; p_2 = 3; q_2 = 2\\
p_{n+3} = 2p_n + 3q_n; q_{n+3} = p_n + 2q_n\\
\lim\limits_{n \to \infty} \frac{p_n}{q_n} = \sqrt{3}\)
Jetzt kann man auch leicht überprüfen, wie gerade und ungerade sich verteilt:
\(p_n,q_n \in U \to p_{n+3},q_{n+3} \in U\\
p_n \in G, q_n \in U \to p_{n+3} \in U, q_{n+3} \in G\\
p_n \in U, q_n \in G \to p_{n+3} \in G, q_{n+3} \in U\)
(1)
Also wenn der Bruch U/U ist, dann ist auch der dritt nächste U/U. Dies betrifft alle Indizes \(n = 3k\). Hierfür sind also die Koordinaten aus dem letzten Post möglich und besser als jene aus diesem Post:
\(A(0,0); B(\frac{p_{3k}+q_{3k}}{2},\frac{p_{3k}-q_{3k}}{2}); C(\frac{p_{3k}-q_{3k}}{2},\frac{p_{3k}+q_{3k}}{2})\)
In einem Quadrat der Größe \(\frac{p_{3k}+q_{3k}}{2}\)
(2)
Ist der Bruch G/U, dann ist der dritt nächste U/G, und weitere drei später wieder G/U. Wenn man mit U/G startet, dann verhält sich das entsprechend. Dies betrifft alle Indizes \(n \neq 3k\). Hierbei wäre \(p+q \in U\), und daher müsste man die Koordinaten aus dem letzten Post verdoppeln... dies führt dann aber zu einer Lösung mit größeren Koordinaten als nach der Methode in diesem Post. Somit wären hierbei die Koordinaten von oben besser:
\(A(0,0); B(2q_{n \neq 3k},0); C(q_{n \neq 3k},p_{n \neq 3k})\)
Und dies passt in ein Quadrat der Größe \(2q_n\)
Da bei den Näherungsbrüchen gilt (für i > 0):
\(q_i < q_{i+1}\)
passen die Lösungen für \(n = 3k+1\) immer in ein kleineres Quadrat als jene für \(n = 3k+2\).
Nun müsste man noch die Relationen für \(n = 3k\) bestimmen.
(3)
\(2q_{3k-1} < \frac{p_{3k}+q_{3k}}{2}\\
\frac{p_{3k}+q_{3k}}{2} < 2q_{3k+1}\)
Dies kann man vielleicht induktiv zeigen... muss ich mir mal überlegen ^^
Wenn es keine bessere Drehung, Verschiebung und Streckung/Stauchung der Koordinaten aus dem letzten Post gibt als jene, die ich oben vorgestellt habe, dann sollten dies beides jeweils (je nach Index des Näherungsbruch) die besten Lösungen sein.
Die Relation lässt sich hier nur schlecht abschätzen... kurzes berechnen paar Werte mit Excel lässt aber vermuten:
\(n \in \{ 3k, 3k+2 \}: 2q > \sqrt{p^2+q^2} \to r = \frac{\sqrt{p^2+q^2}}{2q}\\
n = 3k+1: 2q < \sqrt{p^2+q^2} \to r = \frac{2q}{\sqrt{p^2+q^2}}\)
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe! Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst. Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2021-03-06
Notiz
Profil
Quote
Link
