Matroids Matheplanet Forum Index
Moderiert von Buri Florian Kay_S
Matroids Matheplanet Forum Index » 7. Matheplanet Challenge » Aufgabe 4
MPC7-Navigation: Allg P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 Downl Regeln
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J Aufgabe 4
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1368
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2008-03-19


Aufgabe 4 (7 Punkte)

Eine Bank veranstaltet einen Aktionstag. Das Umtauschen von Währungen ist zu besonders günstigen Konditionen möglich. Es wird angeboten,

52 Euro in 39 Pfund   bzw.   24 Euro in 35 Dollar
27 Dollar in 30 Franken   bzw.   60 Dollar in 41 Euro
23 Pfund in 45 Dollar   bzw.   33 Pfund in 73 Franken
75 Franken in 46 Euro   bzw.   31 Franken in 14 Pfund

umzutauschen. Die Bank weist ausdrücklich darauf hin, dass nur in den angegebenen Mengeneinheiten umgetauscht werden darf.

Leider ist der Bank bei der Planung ein Fehler unterlaufen. Es stellte sich nämlich heraus, dass man einen 100-Euro-Schein durch geschicktes Tauschen in einen höheren Eurobetrag umwandeln kann. Wieviele Konvertierungen sind dafür mindestens nötig?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
himbeersenf
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 29.03.2007
Mitteilungen: 16
Herkunft: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2008-03-19


Hallo,

muss ich den 100 €-Schein mit einem Mal umtauschen oder kann ich mir Wechselgeld in € geben lassen? Kann ich auch z.B. 2x27 Franken in 60 Dollar umtauschen?

MfG Julia



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1368
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2008-03-19


Es ist egal, ob man Scheine oder Münzen hat, es zählt nur der Betrag.

Man kann 2x27 Dollar in 2x30 Franken umtauschen, das entspricht dann aber 2 Konvertierungen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2008-03-21


Heuristische Herangehensweise:

Ohne Beachtung der konkreten Mengen, die in einem Schritt umgetauscht werden können, ergeben sich aus den Angaben die folgenden Zyklen mit einem zugehörigen Faktor, den man erhält, wenn man entlang des Zykluses beliebige Beträge zum angegebenen Kurs tauschen könnte. Zahlen > 1 heißen, daß wir Gewinn machen, Zahlen < 1 bedeuten einen Verlust.

Zweierzyklen:
Euro -> Dollar -> Euro : 0,9965
Franken -> Pfund -> Franken : 0,9990

Dreierzyklen:
Euro -> Dollar -> Franken -> Euro: 0,9938
Euro -> Pfund -> Dollar -> Euro: 1,0027
Euro -> Pfund -> Franken -> Euro: 1,01757  (++++)
Dollar -> Franken -> Pfund -> Dollar: 0,98177

Viererzyklen:
Euro -> Pfund -> Dollar -> Franken -> Euro: 1

Wenn man also Lösungen bastelt, sollte der mit (++++) markierte Zyklus bevorzugt werden, da er den größten Gewinn verspricht. Wir werden einiges an "Gewinn" brauchen, da durch die begrenzten Tauschmöglichkeiten wohl immer noch kleine Beträge in Fremdwährungen übrig bleiben.


Ausgehend von dieser Strategie habe ich eine Lösung in 80 Zügen gefunden, die aber sicher nicht optimal ist, da ich wertmäßig weit übers Ziel hinausschiesse und am Ende 111 Euro, 2 Pfund, 3 Franken und 1 Dollar zur Verfügung habe. Es ist aber ein obere Grenze, und da es insgesamt in jedem Schritt nur eine sehr kleine Zahl (meist sogar nur eine) von Zugmöglichkeiten gibt, sollte es in vertretbarem Rechenaufwand möglich sein, den Suchbaum bis zur Tiefe 50-60 vollständig zu durchsuchen, und in dieser Größenordnung wird wohl schätzungsweise maximal auch die Lösung liegen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2008-03-21


Noch eine Frage: Wird hier gefordert, dass am Ende des Tauschprozesses nur Euro überbehalten werden ? Ich denke mal eher nicht, es ist nur wesentlich, dass am Ende 100+x Euro und beliebig viel Kleingeld vorliegt. Sehe ich das richtig ?

-- Valentin




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1368
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2008-03-21


Korrekt, am Ende möchten wir wenigstens 101 Euro + irgendwas in der Tasche haben.

Kay



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 16.08.2003
Mitteilungen: 2867
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2008-03-21


Hi,

ich denke, es ist nicht im Sinne der Aufgabe, maximalen Gewinn zu machen (so verlockend so ein Banken-Fehler im realen Leben auch wäre), sondern in minimalen Zügen überhaupt ein Plus. Außerdem spielt ja die Stückelung eine Rolle - nur in den angegebenen Portionen darf getauscht werden.

@Kay_S: Ich hatte mir zuerst auch die Möglichkeit 100 Eur + irgendwas (auch in Fremdwährung) offengehalten, aber klar - auch hier ist die Aufgabenstellung eindeutig, es geht um einen höheren Eurobetrag.

bye trunx



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2008-03-21


Das ist richtig, aber jede Lösung wird diesen Zyklus trotzdem mehrere Male enthalten.

Denn auf der einen Seite gilt:
* man braucht mindestens 1% Gewinn (um auf 101 Euro zu kommen)
* man hat am Ende ziemlich sicher Fremdwährungspositionen übrig, deren Wert man auch erstmal rausarbeiten muß
* durch die eingeschränkten Möglichkeiten wird es sich nicht vermeiden lassen, andere Umtauschmöglichkeiten zu benutzen, die im Prinzip Verlust bedeuten

Auf der anderen Seite ist das aber der einzige Zyklus, der überhaupt einen nennenswerten Gewinn verspricht, nämlich grob gesagt 1,7% in 3 Zügen. Der einzige andere Zyklus, der überhaupt Gewinn erwirtschaftet schafft gerade mal 0,27% in 3 Zügen.

Ich habe auch nicht behauptet, daß ich eine optimale Lösung habe, sondern ich habe lediglich zum Vergleich eine von mir gefundene obere Grenze (80 Züge) angegeben und die Heuristik, mit der ich diese gefunden habe.


Edit: Ich konnte mich auf 56 Züge verbessern, und habe am Ende 108 Euro, 3 Pfund und 1 Franken. Dabei habe ich sämtliche Tauschmöglichkeiten, an denen der Dollar beteiligt ist, außer acht gelassen.
[ Nachricht wurde editiert von Realshaggy am 21.03.2008 14:06:21 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
spitzwegerich
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.06.2005
Mitteilungen: 1327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2008-03-21


Ich habe eine Lösung in 28 Zügen gefunden, und es dürfte eine Optimallösung sein:

1. Tausche 52 Euro in 39 Pfund
Bestand: 48 Euro, 0 Dollar, 0 Franken, 39 Pfund
2. Tausche 33 Pfund in 73 Franken
Bestand: 48 Euro, 0 Dollar, 73 Franken, 6 Pfund
3. Tausche 31 Franken in 14 Pfund
Bestand: 48 Euro, 0 Dollar, 42 Franken, 20 Pfund
4. Tausche 31 Franken in 14 Pfund
Bestand: 48 Euro, 0 Dollar, 11 Franken, 34 Pfund
5. Tausche 24 Euro in 35 Dollar
Bestand: 24 Euro, 35 Dollar, 11 Franken, 34 Pfund
6. Tausche 33 Pfund in 73 Franken
Bestand: 24 Euro, 35 Dollar, 84 Franken, 1 Pfund
7. Tausche 75 Franken in 46 Euro
Bestand: 70 Euro, 35 Dollar, 9 Franken, 1 Pfund
8. Tausche 52 Euro in 39 Pfund
Bestand: 18 Euro, 35 Dollar, 9 Franken, 40 Pfund
9. Tausche 33 Pfund in 73 Franken
Bestand: 18 Euro, 35 Dollar, 82 Franken, 7 Pfund
10. Tausche 75 Franken in 46 Euro
Bestand: 64 Euro, 35 Dollar, 7 Franken, 7 Pfund
11. Tausche 52 Euro in 39 Pfund
Bestand: 12 Euro, 35 Dollar, 7 Franken, 46 Pfund
12. Tausche 33 Pfund in 73 Franken
Bestand: 12 Euro, 35 Dollar, 80 Franken, 13 Pfund
13. Tausche 75 Franken in 46 Euro
Bestand: 58 Euro, 35 Dollar, 5 Franken, 13 Pfund
14. Tausche 52 Euro in 39 Pfund
Bestand: 6 Euro, 35 Dollar, 5 Franken, 52 Pfund
15. Tausche 33 Pfund in 73 Franken
Bestand: 6 Euro, 35 Dollar, 78 Franken, 19 Pfund
16. Tausche 75 Franken in 46 Euro
Bestand: 52 Euro, 35 Dollar, 3 Franken, 19 Pfund
17. Tausche 24 Euro in 35 Dollar
Bestand: 28 Euro, 70 Dollar, 3 Franken, 19 Pfund
18. Tausche 24 Euro in 35 Dollar
Bestand: 4 Euro, 105 Dollar, 3 Franken, 19 Pfund
19. Tausche 60 Dollar in 41 Euro
Bestand: 45 Euro, 45 Dollar, 3 Franken, 19 Pfund
20. Tausche 24 Euro in 35 Dollar
Bestand: 21 Euro, 80 Dollar, 3 Franken, 19 Pfund
21. Tausche 60 Dollar in 41 Euro
Bestand: 62 Euro, 20 Dollar, 3 Franken, 19 Pfund
22. Tausche 24 Euro in 35 Dollar
Bestand: 38 Euro, 55 Dollar, 3 Franken, 19 Pfund
23. Tausche 24 Euro in 35 Dollar
Bestand: 14 Euro, 90 Dollar, 3 Franken, 19 Pfund
24. Tausche 60 Dollar in 41 Euro
Bestand: 55 Euro, 30 Dollar, 3 Franken, 19 Pfund
25. Tausche 27 Dollar in 30 Franken
Bestand: 55 Euro, 3 Dollar, 33 Franken, 19 Pfund
26. Tausche 31 Franken in 14 Pfund
Bestand: 55 Euro, 3 Dollar, 2 Franken, 33 Pfund
27. Tausche 33 Pfund in 73 Franken
Bestand: 55 Euro, 3 Dollar, 75 Franken, 0 Pfund
28. Tausche 75 Franken in 46 Euro
Bestand: 101 Euro, 3 Dollar, 0 Franken, 0 Pfund

Ich schreibe gleich noch mehr dazu.

[ Nachricht wurde editiert von spitzwegerich am 21.03.2008 15:21:02 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
spitzwegerich
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.06.2005
Mitteilungen: 1327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2008-03-21


fed-Code einblenden
[ Nachricht wurde editiert von spitzwegerich am 21.03.2008 16:14:26 ]

[ Nachricht wurde editiert von spitzwegerich am 22.03.2008 01:38:08 ]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2008-03-21


Hallo, ich habe eine Breitensuche implementiert, und komme ebenfalls auf eine Lösung mit 28 Konvertierungen.

Gruß,
SirJective



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
spitzwegerich
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.06.2005
Mitteilungen: 1327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2008-03-21


Noch was:

2008-03-21 13:06 - Realshaggy schreibt:
Das ist richtig, aber jede Lösung wird diesen Zyklus trotzdem mehrere Male enthalten.
(gemeint war der Zykel Euro -> Pfund -> Franken -> Euro)

Das was Realshaggy vorhergesagt hat, ist eingetreten. Wenn ich die Umtauschvorgänge wieder von 1 bis 8 durchnummeriere (erst die linke, dann die rechte Spalte der Tabelle der Aufgabenstellung), dann schreibt sich der Zykel als 1,7,4,1,7,..., und meine Lösung als:

1,7,8,8,5,7,4,1,7,4,1,7,4,1,7,4,5,5,6,5,6,5,5,6,2,8,7,4

Der Zykel ist deutlich zu erkennen.

2008-03-21 13:06 - Realshaggy schreibt:
* man hat am Ende ziemlich sicher Fremdwährungspositionen übrig, deren Wert man auch erstmal rausarbeiten muß
* durch die eingeschränkten Möglichkeiten wird es sich nicht vermeiden lassen, andere Umtauschmöglichkeiten zu benutzen, die im Prinzip Verlust bedeuten

Auch das stimmt, der Zykel kommt in der Lösung ziemlich in der Mitte und die Umtauschvorgänge vor und hinter dem Zykel kann man als "Vorbereitung" und "Aufräumen" interpretieren.



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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
spitzwegerich
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.06.2005
Mitteilungen: 1327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2008-03-21


2008-03-21 16:05 - SirJective schreibt:
Hallo, ich habe eine Breitensuche implementiert, und komme ebenfalls auf eine Lösung mit 28 Konvertierungen.

Sehr gut, dann scheint es wirklich zu stimmen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
SirJective
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.09.2004
Mitteilungen: 1787
Herkunft: Münchner Norden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2008-03-21


Einige Informationen, die zur Lösung der Aufgabe nichts beitragen...

Die kleinste Anzahl an Konvertierungen, bei denen man einen Euro-Gewinn und keine Fremdwährungen erhält, ist 34, mit einem Ergebnis von 101 Euro.

Mit 97 Konvertierungen kann man auf 122 Euro kommen (das höchste mit maximal 100 Konvertierungen), und dabei wird der Dollar nicht benötigt.

Da der Suchgraph sehr schnell anwächst, habe ich einige Berechnungen auch unter Ausschluss des Dollar gemacht. Ohne Dollar braucht man 55 Konvertierungen, um zu den 108 Euro zu kommen, die Realshaggy bekommen hat. Im Kleinen bringt die Verwendung des Dollars einen Vorteil, aber langfristig wird man sich auf den von Realshaggy beschriebenen Zyklus konzentrieren (wobei man am Anfang und am Ende durchaus von der Verwendung des Dollars profitieren könnte).

Euro|Doll|Fran|Pfun|Konvertierungen
(mit Dollar)
101E   0D   0F   0P 34
122E   0D   2F   1P 97
125E   0D   0F   0P 114
127E   3D   0F   0P 123

(ohne Dollar)
108E   0D   1F   3P 55
126E   0D   8F   0P 126
202E   0D   7F   3P 420
302E   0D   2F   3P 769
402E   0D   1F   1P 1138
500E   0D   7F   3P 1502
600E   0D   2F   3P 1851

Gruß,
SirJective




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
matroid
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.03.2001
Mitteilungen: 14341
Herkunft: Solingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2008-03-21


@spitzwegerich: so hatte ich das Problem dann auch formuliert. Und Du hast es schon gelöst.
@SirJective: sagst Du noch etwas dazu, was Du gemacht hast?



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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
matroid
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.03.2001
Mitteilungen: 14341
Herkunft: Solingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2008-03-21


@SirJective: Danke, Du hast es schon gemacht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Realshaggy
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.03.2008
Mitteilungen: 1293
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2008-03-22


Als Student mit Schwerpunkt Optimierung bin ich von der Lösung mittels Formulierung als ganzzahliges Optimierungsproblem schwer begeistert. Wobei ich mir nicht sicher bin, ob es nicht ziemliches Glück ist, eine Lösung des Optimierungsproblems in eine Lösung der Aufgabe überführen zu können, ich hätte zumindest nicht vermutet, daß das realistische Chancen hat.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
spitzwegerich
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.06.2005
Mitteilungen: 1327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2008-03-22


2008-03-22 00:31 - Realshaggy schreibt:
 Wobei ich mir nicht sicher bin, ob es nicht ziemliches Glück ist, eine Lösung des Optimierungsproblems in eine Lösung der Aufgabe überführen zu können, ich hätte zumindest nicht vermutet, daß das realistische Chancen hat.

Ich war auch skeptisch. Mein Ziel war zunächst, mit dem Optimierungsproblem erstmal eine untere Schranke für die Zahl der nötigen Züge herzubekommen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1368
Herkunft: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2008-03-29


Lösung
fed-Code einblenden



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kay_S hat die Antworten auf ihre/seine Frage gesehen.
Kay_S hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 

 MPC7-Navigation: Allg P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 Downl Regeln

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]