Forum:  Rätsel und Knobeleien (Knobelecke)
Thema: * Dreiecke mit Ganzzahlkoordinaten
Themen-Übersicht
Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1607
Wohnort: Chile, Ulm
Themenstart: 2021-03-06 17:16

*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*!


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1265
Wohnort: Bayern
Beitrag No.1, eingetragen 2021-03-07 01:56


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...



haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 616
Wohnort: Gog
Beitrag No.2, eingetragen 2021-03-07 12:17

...oder auch
$(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$


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1265
Wohnort: Bayern
Beitrag No.3, eingetragen 2021-03-07 14:10

Interessante Lösung...

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



haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 616
Wohnort: Gog
Beitrag No.4, eingetragen 2021-03-07 15:56

@MartinN
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 ?


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27783
Wohnort: Hessen
Beitrag No.5, eingetragen 2021-03-07 19:28
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Optimale Lösungen
MartinN liegt mit seinen beiden Lösungen richtig.

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.

\(\endgroup\)

Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1607
Wohnort: Chile, Ulm
Beitrag No.6, vom Themenstarter, eingetragen 2021-03-07 20:23

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.


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 616
Wohnort: Gog
Beitrag No.7, eingetragen 2021-03-07 21:25

Hallo zusammen,


[0, 0] [1, 4] [4, 1]
4.123105625617661
4.242640687119285
4.123105625617661
0.9718253158075502
 
Ist eine der beiden optimalen Lösungen neben

[0, 0] [3, 5] [6, 0]
5.830951894845301
5.830951894845301
6.0  
0.9718253158075502

Die beiden Dreiecke haben unterschiedliche Seitenlängen, aber zumindest
recht genau (16 Kommastellen) das gleiche Seitenverhältnis.

Das dritte mögliche Dreieck schneidet etwas schlechter ab.

[0, 0] [2, 7] [7, 2]
7.280109889280518
7.0710678118654755
7.280109889280518  
0.9712858623572642




Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1607
Wohnort: Chile, Ulm
Beitrag No.8, vom Themenstarter, eingetragen 2021-03-07 23:33

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.



MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1265
Wohnort: Bayern
Beitrag No.9, eingetragen 2021-03-08 00:45

Die erste Lösung von haegar90 lässt sich nicht zu (0,0) verschieben ;)
Aber zu (7,0) und dann kann man es ja drehen.

Mal etwas systematische Überlegungen und warum die besten Lösungen immer gleichschenklig sind...

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.

Mal paar Näherungen:
\(2/1 \to A(1.5,0.5) \to A(3,1)\\
3/2 \to A(2.5,0.5) \to A(5,1)\\
5/3 \to A(4,1)\\
7/4 \to A(5.5,1.5) \to A(11,3)\\
12/7 \to A(9.5,2.5) \to A(19,5)\\
19/11 \to A(15,4)\\
26/15 \to A(20.5,5.5) \to A(41,11)\\
45/26 \to A(35.5,9.5) \to A(71,19)\\
71/41 \to A(56,15)\)

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.


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 616
Wohnort: Gog
Beitrag No.10, eingetragen 2021-03-08 10:28

...interessante Überlegungen.
Hier als Datenreferenz bis 100 die steigende Qualität:
Text
[0, 0] [0, 6] [5, 3] 6.0 5.830951894845301 5.830951894845301 0.9718253158075502
[0, 0] [0, 8] [7, 4] 8.0 8.06225774829855 8.06225774829855 0.9922778767136677
[0, 0] [0, 14] [12, 7] 14.0 13.892443989449804 13.892443989449804 0.9923174278178432
[0, 0] [0, 22] [19, 11] 22.0 21.95449840010015 21.95449840010015 0.9979317454590977
[0, 0] [0, 30] [26, 15] 30.0 30.01666203960727 30.01666203960727 0.9994449069791543
[0, 0] [0, 52] [45, 26] 52.0 51.97114584074513 51.97114584074513 0.9994451123220217
[0, 0] [0, 82] [71, 41] 82.0 81.98780397107853 81.98780397107853 0.9998512679399821
 




MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1265
Wohnort: Bayern
Beitrag No.11, eingetragen 2021-03-08 10:54

Ich glaube man kann auch besser die Koordinaten Verschieben/Drehen/Strecken...
Hier ein Nachtrag zu gestern xD


\(C(0,0)\\
A(\frac{p+q}{2},\frac{p-q}{2})\\
B(\frac{p-q}{2},\frac{p+q}{2})\)

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 Antwort wurde nach Beitrag No.9 begonnen.]


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1265
Wohnort: Bayern
Beitrag No.12, eingetragen 2021-03-08 11:14

Mit den letzten Koordinaten lässt sich leicht die Qualität berechen:

\(AB = 2q; AC = \sqrt{p^2+q^2}\)

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}}\)


haegar90
Aktiv
Dabei seit: 18.03.2019
Mitteilungen: 616
Wohnort: Gog
Beitrag No.13, eingetragen 2021-03-08 12:03

Es scheint vermutlich ein recht einfacher Zusammenhang zu bestehen:

Mit $A:=(0/0), B:=(0/b_y), C:=(c_x/c_y)$

Ausgehend von den 3 Startdreiecken:
\[(0/0), (0/6), (5/3)\] \[(0/0), (0/8), (7/4)\] \[(0/0), (0/14), (12/7)\]
erhält man mit:
\[b_{y_{i+1}}= 4 b_{y_{i}} - b_{y_{i-1}}\] \[c_{x_{i+1}}= 4 c_{x_{i}} - c_{x_{i-1}}\] \[c_{y_{i+1}}= 4 c_{y_{i}} - c_{y_{i-1}}\] immer das Dreieck mit der nächstbesseren Qualität.

Optimale Qualität
ax	ay		bx	by		cx	cy	
				2		1	1	Startwerte
0	0		0	6		5	3	Startdreieck
0	0		0	22		19	11	
0	0		0	82		71	41	
0	0		0	306		265	153	
0	0		0	1142		989	571	
0	0		0	4262		3691	2131	
 
 
 
ax	ay		bx	by		cx	cy	
				2		2	1	Startwerte
0	0		0	8		7	4	Startdreieck
0	0		0	30		26	15	
0	0		0	112		97	56	
0	0		0	418		362	209	
0	0		0	1560		1351	780	
0	0		0	5822		5042	2911	
 
 
 
ax	ay		bx	by		cx	cy	
				4		3	2	Startwerte
0	0		0	14		12	7	Startdreieck
0	0		0	52		45	26	
0	0		0	194		168	97	
0	0		0	724		627	362	
0	0		0	2702		2340	1351	
0	0		0	10084		8733	5042	
 


Beispiel:

Mit $(0/0),  (0/4262), (3691/2131)$ ergibt sich $0.9999999449479974$

[Die Antwort wurde nach Beitrag No.11 begonnen.]


MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1265
Wohnort: Bayern
Beitrag No.14, eingetragen 2021-03-08 17:53

Kann ich bestätigen... meine Excel-Tabelle

p        q        Size        Quality
1        1        1        0,707106781186548
2        1        2        0,894427190999916
3        2        4        0,901387818865997
5        3        4        0,971825315807550
7        4        8        0,992277876713668
12        7        14        0,992317427817843
19        11        15        0,997931745459098
26        15        30        0,999444906979154
45        26        52        0,999445112322022
71        41        56        0,999851267939982
97        56        112        0,999960142689157
168        97        194        0,999960143748199
265        153        209        0,999989320289847
362        209        418        0,999997138356186
627        362        724        0,999997138361645
989        571        780        0,999999233224975
1351        780        1560        0,999999794543127
2340        1351        2702        0,999999794543155
3691        2131        2911        0,999999944947997
5042        2911        5822        0,999999985248860
8733        5042        10084        0,999999985248860
13775        7953        10864        0,999999996047444
18817        10864        21728        0,999999998940916
32592        18817        37634        0,999999998940916
51409        29681        40545        0,999999999716219
70226        40545        81090        0,999999999923961
121635        70226        140452        0,999999999923961
191861        110771        151316        0,999999999979625
262087        151316        302632        0,999999999994541
453948        262087        524174        0,999999999994541
716035        413403        564719        0,999999999998537
978122        564719        1129438        0,999999999999608
1694157        978122        1956244        0,999999999999608
2672279        1542841        2107560        0,999999999999895
3650401        2107560        4215120        0,999999999999972
6322680        3650401        7300802        0,999999999999972
9973081        5757961        7865521        0,999999999999992

Für die Quadrat-Größe 4 ist n = 3 besser als n = 2. Die erste Zeile ist der 0-te Kettenbruch.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=252711=6
Druckdatum: 2021-05-12 10:22