Handlungsreisender ohne Problem Rätsel ist gelöst

Rätsel, die zum Lösen einen größeren Zeitaufwand erfordern, wie z. B. schwierige Physik- und Matherätsel.

Handlungsreisender ohne Problem

Beitragvon Otmar » Mittwoch 20. Juli 2016, 23:34

Das Problem des Handlungsreisenden ist sicher bekannt. Kann man das Problem vermeiden und Punkte finden, bei denen alle möglichen Rundwege gleich lang sind? Diese Frage hat unser neues Mitglied MadMac gestellt und mich zu folgendem Rätsel inspiriert:

Es seien drei Punkte A, B und C gegebene, die nicht auf einer Gerade liegen. Gesucht ist die geometrische Konstruktion einer ebenen Figur mit Zirkel und Lineal, aus der man ablesen kann, wie viele Möglichkeiten es für einen weiteren, vierten Punkt D in der Ebene der gegebenen Punkte gibt, so dass alle möglichen Rundwege über die vier Punkte gleich lang sind. (Es ist nicht nötig, die Punkte, die für den vierten Punkt D in Frage kommen, zu konstruieren.)

Gesucht ist die Konstruktionsbeschreibung und eine Angabe, wie man aus der konstruierten Figur die Anzahl potenzieller Punkte D ablesen kann.

:spass:
Spoilersperre ist festgelegt - Spoiler sind geöffnet
Start: Mittwoch 20. Juli 2016, 23:34
Ende: Samstag 23. Juli 2016, 23:34
Aktuell: Freitag 21. Juni 2019, 00:10
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Musagetes » Donnerstag 28. Juli 2016, 18:09

Hallo Otmar,

der Handlungsreisende ist mir auch schon über dem Weg gelaufen,
als ich mit ihm ein paar Runden ging, waren seine Probleme etwas anders, als diese.

Aber du suchst ja einen „Handlungsreisenden ohne Problem“, dann hoffe ich auch,
dass das auch etwas einfacher ist.


Mehr ->
Problem des Handlungsreisenden.pdf
(78.86 KiB) 160-mal heruntergeladen


Wenn gewünscht, füge ich gerne zur besseren Verständnis noch eine Zeichnung an.

Liebe Grüße
Musagetes
Musagetes
Knobelfreak
Knobelfreak
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 253
Themen: 7
Registriert: Mittwoch 3. Februar 2010, 19:12
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Otmar » Donnerstag 28. Juli 2016, 22:50

Hallo Musagetes,

schön, mal wieder von dir zu hören. Zu deiner Lösung:

Mehr ->
Du hast Recht, dass es einen Punkt im Dreieck gibt, der das Problem des Handlungsreisenden eliminiert. Und zwar gibt es so einen Punkt in jedem Dreieck, was noch zu beweisen wäre. Im gleichseitigen Dreieck fallen ja fast alle interessanten Punkte im Dreieck auf den Schwerpunkt. So auch dieser. Aber in anderen Dreiecken ist das nicht so. Es könnte aber auch noch sein, dass es mehrere andere Punkte im oder außerhalb des Dreiecks gibt, die alle Rundwege gleich lang werden lassen. Die Frage war, wie viele solcher Punkte es für ein vorgegebenes Dreieck gibt. Die Antwort auf die Anzahl sollte durch eine Konstruktion gegeben werden. Wenn deine Antwort ist, dass nur der Schwerpunkt im gleichseitigen Dreieck als vierter Punkt in Frage kommt, dann darf ich keinen Haken setzen.


Du hast in deinem ersten Lösungsversuch den Punkt D tatsächlich konstruiert. Es lassen sich zwar alle möglichen Punkte D der richtigen Lösung konstruieren, aber das ist relativ kompliziert und ich habe das deshalb auch explizit nicht nachgefragt. Die gesuchte Konstruktion soll nur eine Aussage über die maximale Anzahl möglicher Punkte D liefern, nicht deren Lage widergeben.

Mehr ->
Also wenn du der Meinung bist, dass es so einen Punkt nur im gleichseitigen Dreieck gibt, dann hätte gereicht, nachzuweisen ob AB=AC=BC ist, was konstruktiv sehr einfach ist. Im Fall AB=AC=BC gäbe es dann einen Punkt D, sonst keinen Punkt D.

Diese Antwort wäre aber falsch.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Musagetes » Mittwoch 12. Oktober 2016, 11:43

Hallo Otmar,

nach meinem ersten Lösungsvorschlag, der nur für eine bestimmte
Form des Rundweges eine Lösung bot, musste ich nun noch ein paar
Routen gehen. Die, hoffe ich auch, zu einer Lösung geführt haben.
Diese trage ich nun schon einige Wochen seit einer Südfrankreich
Rundreise mit herum.

Bei ähnlicher Vorgehensweise, wie bei meiner ersten Lösung,
gibt es für dieses Problem auch noch eine allgemeine Lösung,
die auf jedes allgemeine Dreieck als Teil des Rundkurses
anzuwenden ist.

Mehr ->
@Otmar:
„Es seien drei Punkte A, B und C gegebene, die nicht auf einer Gerade liegen.“

Wie schon angeführt können demzufolge die drei Punkte nur in einem
Dreieck (ABC) angeordnet sein. Fügt man nun einen vierten fiktiven
Ortspunkt (D) der aus dem Dreieck (ABC) resultiert hinzu, so sollen
alle möglichen Routen gleichlang sein.

Somit ergeben sich für die vier Ortspunkte (ABCD) nur drei mögliche Routen.

1. A – B – C – D – A
___ a__b__c__d

2. A – B – D – C – A
___ a__e__c__f

3. C – B – D – A – C
___ b__e__d__f


1.Dreieck mit Punkt D.pdf
(20.12 KiB) 131-mal heruntergeladen

Demzufolge ist:
a + b + c + d = a + e + c + f
______ b + d = e + f

a + e + c + f = b + e + d + f
______ a + c = b + d

a + b + c + d = b + e + d + f
______ a + c = e + f


Daraus folgt: a + c = e + f = b + d

Demzufolge wären alle drei Wege z. B. 2(e + f) lang.

Des Weiteren ist:
b + d = e + f  d = e + f – b
a + c = e + f  c = e + f – a


2. Dreieck mit Grundkeise.pdf
(10.78 KiB) 97-mal heruntergeladen

Um das zu verdeutlichen, kann man um die Ortspunkte A und C Grundkreise
mit den Radien [f - b] und [f - a] ziehen, die mit der Strecke e von D entfernt sind.

3.Dreieck Grundkreise.pdf
(35.28 KiB) 127-mal heruntergeladen


Da die maximale Anzahl von drei Dateianhängen erreicht ist, muss ich leider im nächsten Thread fortfahren!
Zuletzt geändert von Musagetes am Mittwoch 12. Oktober 2016, 12:07, insgesamt 1-mal geändert.
Musagetes
Knobelfreak
Knobelfreak
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 253
Themen: 7
Registriert: Mittwoch 3. Februar 2010, 19:12
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Musagetes » Mittwoch 12. Oktober 2016, 12:02

Hier geht es weiter, wenn man das Problem nicht anders lösen kann!


Mehr ->
Vergrößert man die beiden Grundkreise um die Ortspunkte A und C gleichmäßig, mit den Radien
r1= [f – b], und r2= [f – a], so ergeben sich z. B. die beiden Kreisschnittpunkte B und B´.

4.Schnittpunkte.pdf
(312.7 KiB) 124-mal heruntergeladen

Würde man nun die Größe beider Grundkreise gleichmäßig verkleinern oder vergrößern,
so würden die Schnittpunkte hier B und B´ den Verlauf einer Linie beschreiben.

Für die beiden Ortspunkte A und C sind alle Schnittpunkte, die hieraus entstehen,
mögliche Ortspunkte für D.
Der Verlauf dieser Schnittpunkte beschreibt eine Hyperbel.

Das ist so ähnlich wie bei einer Gärtnerkonstruktion einer Ellipse. Da muss die Summe der beiden Radien
immer gleich sein und die möglichen Punkte liegen dann auf einer Ellipse.
Bei einer Hyperbel ist die Differenz der beiden Abstände von B zu A und B zu C immer konstant,
was auf den Schnittpunkteverlauf der beiden Kreise zutrifft.

Die Differenz der beiden Radien mit r1= [f - b] und r2= [f - a]

(e + f – b) – (e + f – a) = – b + a sind konstant unabhängig von e.

Das gleiche Procedere muss man nun auch für die Ortspunkte A und B sowie auch für B und C machen.

Das ganze Konstrukt, habe ich nun mal mit dem Geometrie Programm Geonext konstruiert.

Dreieck Geonext.png
Dreieck Geonext.png (136.34 KiB) 581-mal betrachtet

Für die Ortspunkte A und B „Rote Grundkreise“
Für die Ortspunkte B und C „Blaue Grundkreise“
Für die Ortspunkte C und A „Dunkelgrüne Grundkreise“

Mit der „Reglerfunktion“, kann man die Kreise gleichmäßig vergrößern oder verkleinern,
sodass die Schnittpunkte in einer fetten Spur einer Hyperbel wandern.

So haben bspw. der orange (A) und der hellgrüne (C) Kreis paarweise immer den gleichen Abstand
zu ihren jeweiligen gleichfarbigen Grundkreisen.
Die paarweisen Schnittpunkte der Kreise zeigen immer eine Spur einer Hyperbel auf.
Die gesuchten Ortspunkte für D befinden sich auf den jeweiligen drei Hyperbeln
und deren Hyperbelschnittpunkt.

Hyperbel A/C "Grün"
Hyperbel A/B "Orange"
Hyperbel B/C "Blau"

Wenn aus einer anderen Betrachtungsweise, aus der Aufgabenstellung heraus
z. B. der Ortspunkt B schon der Hyperbelschnittpunkt (D) wäre, dann liegt der
Ortspunkt (B) auf der Hyperbel A/C. Dies angewandt auf die Ortspunkte A und B
sowie auch auf B und C, so würden sich somit vier Ortspunkte für (D) definieren lassen.

Ich hoffe, dass meine Konstruktion den Kriterien der Lösung entspricht.


Liebe Grüße
Musagetes
Musagetes
Knobelfreak
Knobelfreak
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 253
Themen: 7
Registriert: Mittwoch 3. Februar 2010, 19:12
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Otmar » Freitag 14. Oktober 2016, 00:22

Hallo Musagetes,

Obwohl ich nicht jedes Detail überprüft habe, glaube ich, dass alles was du geschrieben hast, richtig ist. :zustimm:

Aber es ist leider noch keine Lösung, denn
Mehr ->
Hyperbeln lassen sich nicht mit Zirkel und Lineal konstruieren.
Es fehlt dann auch noch die Aussage über das Gesuchte. Zur Erinnerung, gesucht waren ja nicht der oder die möglichen vierten Punkte (mit D bezeichnet) sondern die Konstruktion sollte nur eine Aussage über die Anzahl solcher Punkte, bei gegebenen Punkten A, B und C liefern. Klar, wenn bei der Konstruktion alle Punkte D entstehen, braucht man die nur abzuzählen. Wahrscheinlich hast du das so gemeint.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Otmar » Samstag 15. Oktober 2016, 00:22

Hallo Musagetes, inzwischen glaube ich deinen letzten Satz verstanden zu haben.

Mehr ->
D1=B wäre eine, D2=A eine zweite, D3=C eine dritte Möglichkeit für D. Nun hatte ich explizit von einem vierten Punkt D gesprochen und damit diese drei Möglichkeiten von vornherein ausgeschlossen. Und selbst wenn z.B. D1=B erlaubt wäre, wäre der Rundweg A->B->D1->C->A kürzer als A->B->C->D1->A.

Es bleibt also nur noch ein Punkt D in der Mitte des Dreiecks übrig. Gibt es so einen Punkt in jedem Dreieck? könnte es weitere Punkte D innerhalb oder außerhalb des Dreiecks geben? Das sollte aus der Konstruktion hervorgehen.

Wahrscheinlich reicht hier sogar die Annäherung der Hyperbel durch Linienzüge, da sich in diesem Fall die Hyperbeläste (es ist ja immer nur ein Ast der Hyperbel möglich) tatsächlich in D schneiden. Das zu beweisen ist aber auch nicht einfach. Würden sich die Hyperbeläste in einem Punkt nur berühren, müsste man diesen Punkt tatsächlich konstruieren oder zufällig erwischen, da sich sonst die Linienzüge mit der die Hyperbeläste angenähert werden weder berühren noch schneiden. Dann müsste man sich noch mit der Frage auseinandersetzen, wie gut und wie lang man die Hyperbel durch Linienzüge annähert. Es könnte ja sein, dass es einen Punkt D in großer Entfernung außerhalb des Dreiecks gibt. In dem Fall würde die Anzahl der Punkte, die zu konstruieren sind von den gegebenen Ausgangspunkten A, B und C abhängen und eventuell über alle Maßen wachsen, wenn so ein Punkt D sehr weit außerhalb von ABC liegt. Ich glaube, dass ist auch ein Problem beim Konstruieren, denn da geht man von einer endlichen Anzahl von zu konstruierenden Schnittpunkten aus.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Musagetes » Donnerstag 3. November 2016, 18:10

Hallo Otmar!

Mehr ->
@Otmar:
„D1=B wäre eine, D2=A eine zweite, D3=C eine dritte Möglichkeit für D. Nun hatte ich explizit von einem vierten Punkt D gesprochen und damit diese drei Möglichkeiten von vornherein ausgeschlossen. Und selbst wenn z.B. D1=B erlaubt wäre, wäre der Rundweg A->B->D1->C->A kürzer als A->B->C->D1->A“

Genauso ist das gemeint und wollte nur alle Varianten aufzeigen!
Bei jeder Variante, sind dann die Routen gleich lang und der
Ortspunkt „D“ wird von den Hyperbeln Schnittpunkt eindeutig konstruiert.


Liebe Grüße
Musagetes
Musagetes
Knobelfreak
Knobelfreak
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 253
Themen: 7
Registriert: Mittwoch 3. Februar 2010, 19:12
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon Otmar » Donnerstag 3. November 2016, 23:52

Hallo Musagetes,

schön, dass es auch hier wieder weiter geht.
Mehr ->
Aber mal abgesehen davon, dass D kein vierter Punkt ist, wenn er mit A, B oder C zusammenfällt (denn dann gibt es ja nur drei Punkte), wäre D = A oder D = B oder D = C keine Lösung des Problems. Angenommen es wäre D = A, dann wäre ein Rundweg von D nach A nach B nach C und zurück nach D genau so lang, wie der Umfang vom Dreieck ABC. Ein anderer Rundweg geht von D nach B nach A nach C nach D und wäre gleich DB + BA + AC + CD = (AB + AC) + (AB + AC) > AB + AC + BC wegen der Dreiecksungleichung (AB+AC > BC). Dieser Rundweg ist also in jedem Fall länger, als der Umfang von ABC. D.h. irgendwo muss in deiner Überlegung, dass D mit einem der Eckpunkte A, B oder C zusammenfallen kann, noch ein Fehler drin sein.

Zu den Hyperbelschnittpunkten. Mit der Methode die du oben vorgestellt hast, kann man die Hyperbelschnittpunkte selbst nicht konstruieren. Ggf. könnte man mit etwas Aufwand derart auf jedem Hyperbelast zwei Punkte konstruieren und durch Strecken verbinden und einen Hyperbelschnittpunkt annehmen, wenn sich diese Strecken schneiden. Leider ist es so, dass bei dieser Art der Konstruktion von vornherein nicht klar ist, wie viele solche Strecken konstruiert werden müssen, bis man sicher weiß, wieviel Punkte D möglich sind. Dennoch würde ich die Lösung akzeptieren, wenn du beschreiben kannst, wie viele Schnittpunkte mindestens und höchstens zu erwarten sind und wo man die in etwa konstruieren muss.
Liebe Grüße, Otmar.
Benutzeravatar
Otmar
Schlaumeier
Schlaumeier
 
MitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahreMitgliedsjahre
 
Beiträge: 1618
Themen: 120
Registriert: Dienstag 10. Mai 2011, 22:10
Wohnort: München
Geschlecht: männlich

Re: Handlungsreisender ohne Problem

Beitragvon MadMac » Mittwoch 3. Mai 2017, 16:28

Ich weiß ja was Otmar sucht - drum möchte ich mit aller Gewalt eine komplett andere Lösung entwickeln, die dann halt ein wenig komplizierter ist.

Mehr ->
Es gibt drei verschiedene Rundwege durch alle 4 Punkte

ABCD
ABDC
ADBC

deren weitere Unterscheidung durch Startpunkt und Umlaufrichtung die theoretischen 4! Rundwege ergeben.

Faktisch sind diese Rundwege gleich lang, wenn

|BC|+|AD| = |BD|+|AC|
=> ABCD gleich lang wie ABDC
|AB|+|CD| = |AD|+|BC|
=> ABDC gleich lang wie ADBC
womit dann zwangsweise alle drei Rundwege gleich lang sind und somit zwangsweise
|AB|+|CD| = |BD|+|AC|

Umgeformt kann man schreiben

|AC|-|BC| = |AD|-|BD| = const.

woraus sich schlussfolgern lässt, dass C und D auf eine Hyperbelast mit Fokussen A und B liegen müssen.
Das gleiche gilt für B und D bezüglich A und C, und, wenn beides gilt, zwangsweise auch für A und D bezüglich B und C.

Beginne ich mit 3 Punkten A, B und C, so sind diese drei Hyperbeläste wohldefiniert, und D liegt auf einem ihrer Schnittpunkte (und, lässt sich durch Umformen zeigen, sind alle Bedingungen für die neuen Hyperbeläste mit Fokus D und A, B, oder C erfüllt).

Die Betrachtung zweier Hyperbeläste ist hinreichend, wie ich bereits belegt habe. Bei gleichschenkligen Dreiecken können die Hyperbeläste teils zu Geraden werden.

Otmars Handlungsreisender.png
Otmars Handlungsreisender.png (26.23 KiB) 418-mal betrachtet


Ich lege nun meine Punkte ABC so vor mich hin, dass das Dreieck, das sie bilden, auf seiner längsten Seite liegt und die zweitlängste oben links (o.b.d.a, sonst spiegele ich; Abb. 1).

Mit dem Zirkel konstruiere ich |AC| - |BC| und |AB| - |BC| (Abb. 1) sowie die Seitenmittelpunkte Mab und Mac (Ich hätte D statt B als einen der Drei Punkte wählen sollen ... dann hätten wir jetzt Mad Mac ;-) Abb. 2, ohne Konstruktion, da trivial). Mit den Durchmessern 2b und 2c (Abb. 1) lege ich zwei Kreise um Mab und Mac. Aus diesen ermittele ich schon mal die zwei Scheitelpunkte Sab und Sac der beiden Hyperbeln.

Mit je zwei Tangenten (Abb. 3) von B an den Kreis um Mab mit Radius b bzw. von C an den Kreis um Mac mit Radius c konstruiere ich die Asymptoten gab1, gab2, gac1, gac2 der beiden Hyperbeln.

Für die folgende Diskussion müsste ich jeweils mit der Stetigkeit und der Monotonie der Hyperbel-Halbäste und ihrer ersten Ableitungen argumentieren - und das Achsensystem einmal nach AB und einmal nach AC ausrichten - ausführliche Betrachtungen spare ich mir mal an dieser Stelle.
Vereinfacht gesprochen: Am Scheitelpunkt (wenn die Hauptachse waagrecht liegt) ist die Steigung unendlich, sie nimmt streng monoton ab (oberer rechter Halbast), und ist stets größer als die Steigung der Asymptoten. Kippe ich die Hauptachse so, dass die Asymptote immer noch eine positive Steigung hat, so ändert sich prinzipiell nix außer der Unendlichkeit am Scheitelpunkt.

Mit dieser Argumentation lässt sich zeigen: Im Inneren des Dreiecks gibt es IMMER GENAU EINEN Schnittpunkt, d.h. einen möglichen Punkt D1.

Ferner: Außerhalb gibt es theoretisch bis zu zwei mögliche weitere Punkte, und zwar dann und GENAU dann, wenn sich zwei Asymptoten (Achtung: Nur die Halbgeraden!) irgendwo schneiden. Da ich diese mit Zirkel konstruiert habe, lässt sich auch deren Winkel zueinander bestimmen.
Aber:

- Es lässt sich zeigen, dass gab2 immer steiler ist als gac2 (da |AB| die längere Seite ist), so dass es unterhalb von AB keinen Schnittpunkt geben wird.
- gab1 und gac2 können sich schneiden, das ist im Einzelfall zu ermitteln.

Klitzekleine Ungenauigkeit: Ich habe noch nicht explizit bewiesen, dass sich die beiden Hyperbel-Halbäste, die sich an gab1 und gac2 annähern, nur einmal schneiden können.


Gruß,
MadMac
MadMac
Denksportler
Denksportler
 
MitgliedsjahreMitgliedsjahre
 
Beiträge: 173
Themen: 6
Registriert: Freitag 8. Juli 2016, 14:09
Geschlecht: männlich

Nächste

  • Ähnliche Themen
    Antworten
    Zugriffe
    Autor

Zurück zu Harte Nüsse

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste