Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » ** Min-Max-Wirrwarr
Autor
Kein bestimmter Bereich ** Min-Max-Wirrwarr
MartinN
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.08.2016
Mitteilungen: 1305
Wohnort: Bayern
  Themenstart: 2021-09-06

Zwei Studenten Anton und Bert (die vielleicht nicht immer den einfachsten Weg wählen) haben lauter Mengen mit m rationalen Zahlen gegeben: \(M_m = \{ x_1 \leq ... \leq x_m \}; x_i \in \IR\) (sie müssen nicht zwangsläufig geordnet sein, oBdA kann man schon annehmen sie wären es) Nun sollen sie daraus das Minimum und das Maximum bestimmen. Da sie nicht zwangsläufig geordnet sein müssen (man also nicht einfach den ersten und den letzten Wert ablesen kann), meint Anton: "Lass uns einfach ein Programm schreiben, welches uns das Minimum und das Maximum sucht. Du kannst doch programmieren?" Der andere, etwas faulere Student Bert erwidert: "Ja schon, aber gleich 2 Funktionen programmieren? So viel schaff ich nicht, das ist ja ein Mordsaufwand!" Anton beschwichtigt: "Es genügt mir, wenn du eine Funktion programmierst, welche das Minimum ausgibt. Mir fallen spontan 3 Möglichkeiten ein, wie ich mit dieser Funktion dann auch das Maximum ermitteln kann!" Bert soll also eine Funktion \(f_1\) programmieren, so dass auf obige Menge angewendet (wenn diese geordnet ist): \(f_1 (M_m) = x_1\) Nun kommt es wie es kommen muss... Bert macht einen Fehler beim Programmieren und seine Funktion gibt den zweitkleinsten Wert aus, also seine Funktion: \(f_2 (M_m) = x_2\) Aber Bert mag nicht noch einmal programmieren... Da kommt Anton die Idee: "Keine Angst, damit kann ich auch das Minimum bestimmen. Ich brauche wie bei den Methoden oben nur die vier Grundrechenarten und das Potenzieren, sowie deine Formel auf Mengen und Teilmengen angewendet..." Wie bestimmt Anton das Minimum mit Berts Funktion? Zusätzlich könnt ihr hier schreiben, welche 3 Methoden wohl Anton einfielen, wie er aus dem Minimum das Maximum einer Menge ermittelt. PS: Keine Angst, ich hab nix programmiert. Hab mich nur gefragt und herausgefunden, wie man mit einer Funktion, die das k-te kleinste (oder auch k-te größte) Element einer Menge M mit m >= k Elementen ausgibt, jedes andere t-te kleinste (oder auch t-te größte) Element dieser Menge mit 1 <= t <= m finden kann xD


   Profil
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!
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2999
  Beitrag No.1, eingetragen 2021-09-08

Ich habe eine Lösung ohne Potenzen, dafür mit Beträgen. Falls du unter Potenzen auch gebrochene Exponenten verstehst, könnte man das natürlich leicht umformen. Nur mit Grundrechenarten (inklusive natürlicher Potenzen) habe ich noch keinen Ansatz. Pseudolösung in Python: \sourceon Python \numberson def myMin(M): x2 = f2(M) M2 = {-(.5*((x-x2)-abs(x-x2))+x2) for x in M} return -f2(M2) \sourceoff


   Profil
MartinN
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.08.2016
Mitteilungen: 1305
Wohnort: Bayern
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-10

Interessante Idee... aber bei mir spuckt das x2 aus ;) Du machst aus M ja eine Menge \(M'_m\), die nun aus folgenden Elementen besteht: \(M'_m = \{ x'_1 = -x_2 \leq x'_2 = -x_2 \leq ... \leq x'_{m-1} = -x_2 \leq x'_m = -x_1 \}\) Also (m-1) Elemente mit demselben Wert (das negative vom zweitkleinsten Wert der ursprünglichen Menge) und als größtes Element mit dem Wert -x_1. Das "zweitkleinste" Element dieser Menge ist gemäß der Definition von f_2 aber immer noch -x_2 und nicht -x_1.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2999
  Beitrag No.3, eingetragen 2021-09-10

Also bei mir spuckt das Programm reproduzierbar das kleinste Element aus. Hier mal ein Beispiel: \sourceon Python \numberson def myMinVerbosive(M): print(f"Finding Minimum of {M}") x2 = f2(M) print(f"Second smallest Element {x2=}") M = {(x-x2)-abs(x-x2) for x in M} print(f"After applying (x-x2)-abs(x-x2) new {M=}") M = {-(.5*x+x2) for x in M} print(f"After 'Normalization' -(.5*x+x2) new {M=}") x1 = -f2(M) print(f"Least Element {x1=}") return x1 L = [-3,4,-5,6,2,1,-2] print(myMinVerbosive(L)) Finding Minimum of [-3, 4, -5, 6, 2, 1, -2] Second smallest Element x2=-3 After applying (x-x2)-abs(x-x2) new M={0, -4} After 'Normalization' -(.5*x+x2) new M={3.0, 5.0} Least Element x1=-5.0 -5.0 L = list(range(10)) print(myMinVerbosive(L)) Finding Minimum of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Second smallest Element x2=1 After applying (x-x2)-abs(x-x2) new M={0, -2} After 'Normalization' -(.5*x+x2) new M={-0.0, -1.0} Least Element x1=0.0 0.0 \sourceoff Ich wandle zunächst alle Elemente außer dem Minimum in 0 um. Für die zwei kleinsten Elemente kann ich das wieder rückgängig machen, wobei ich das Vorzeichen vertausche. Die Gegenzahl des Minimums ist jetzt das zweitkleinste (tatsächlich das Größte) Element der Menge und kann mit $-f_2$ ausgelesen werden.


   Profil
MartinN
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.08.2016
Mitteilungen: 1305
Wohnort: Bayern
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-10

In Zeile 18 hat deine Menge nur noch 2 statt ursprünglich 7 Elemente. Du bräuchtest also noch eine Funktion die "gleiche" Elemente löschte/zusammenfasst und es müsste gewährleistet sein, dass das Minimum und das zweit kleinste Element verschieden sind, damit deine Methode funktioniert. Aber laut Aufgabe können in M auch Elemente mehrfach vorkommen. Also das kleinste und das zweit kleinste konnen gleichgroß sein. Aber dennoch eine interessante Methode, wenn man Mengen hat, in denen alle Elemente unterschiedlich sind und gleiche Elemente automatisch zu einem reduziert werden.


   Profil
MartinN
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.08.2016
Mitteilungen: 1305
Wohnort: Bayern
  Beitrag No.5, vom Themenstarter, eingetragen 2021-09-13

Da sich hier aktuell nicht viel tut, schonmal die 3 Ideen mit denen Anton aus dem Minimum das Maximum bestimmen wollte... so als Inspiration. \showon Die einfachste Variante wäre, die Menge \(M_m\) zu verändern, so dass der größte Wert der kleinste wird, zB: \(M'_m = \{-x_i \forall i \}\) Dann ist das Maximum \(f_m(M_m)\) [das m-kleinste Element einer Menge mit m Elemente] ähnlich dem Minimum \(f_1(M'_m)\) der veränderten Menge: \(f_m(M_m) = -f_1(M'_m)\) Eine zweite Methode wäre die Beobachtung, dass in einer Menge mit 2 Elementen gilt: \(f_1(\{a,b\}) \cdot f_2(\{a,b\}) = a \cdot b\) (das Minimum mal dem Maximum ist also das Produkt der beiden Elemente dieser Menge). So könnten wir eine rekursive Funktion aufstellen*: \(g_{i} = f_2(\{x_i,g_{i-1}\}) = \frac{x_i \cdot g_{i-1}}{f_1(\{x_i, g_{i-1}\})}; g_1 = x_1\) Man bestimmt also nacheinander immer das Maximum von 2 Elementen dieser Menge \(M_m\) bis man alle durch hat, und es gilt dann: \(f_m(M_m) = g_m\) Die dritte Methode würde die Lösung der Aufgabe vorausnehmen, und kommt später xD Nachtrag: * Bei dieser Methode muss man sicherstellen, dass das Minimum von 2 Elementen nie 0 ist. Dazu modifiziert man erst die Menge mit einem positiven k: \(M'_m = \{x_i - f_1(M_m) + k \forall i\}\) Dann das Maximum nach der rekursiven Methode bestimmten, und am Ende die Modifikation rückgängig machen: \(f_m(M_m) = g_m + f_1(M_m) - k\) \showoff


   Profil
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 910
Wohnort: Kiel, Deutschland
  Beitrag No.6, eingetragen 2021-09-14

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\) Hallo MartinN, \quoteon(2021-09-13 20:50 - MartinN in Beitrag No. 5) Eine zweite Methode wäre die Beobachtung, dass in einer Menge mit 2 Elementen gilt: \(f_1(\{a,b\}) \cdot f_2(\{a,b\}) = a \cdot b\) (das Minimum mal dem Maximum ist also das Produkt der beiden Elemente dieser Menge). So könnten wir eine rekursive Funktion aufstellen*: \(g_{i} = f_2(\{x_i,g_{i-1}\}) = \frac{x_i \cdot g_{i-1}}{f_1(\{x_i, g_{i-1}\})}; g_1 = x_1\) Man bestimmt also nacheinander immer das Maximum von 2 Elementen dieser Menge \(M_m\) bis man alle durch hat, und es gilt dann: \(f_m(M_m) = g_m\) * Bei dieser Methode muss man sicherstellen, dass das Minimum von 2 Elementen nie 0 ist. Dazu modifiziert man erst die Menge mit einem positiven k: \(M'_m = \{x_i - f_1(M_m) + k \forall i\}\) Dann das Maximum nach der rekursiven Methode bestimmten, und am Ende die Modifikation rückgängig machen: \(f_m(M_m) = g_m + f_1(M_m) - k\) \quoteoff Nette Behauptungen, die du da aufstellst. Aber überzeugt bin ich davon noch nicht. Das sind mir zu viele Symbole auf zu engem Raum, die zudem sauber eingeführt sein wollen. \quoteon(2021-09-13 20:50 - MartinN in Beitrag No. 5) \(g_{i} = f_2(\{x_i,g_{i-1}\}) = \frac{x_i \cdot g_{i-1}}{f_1(\{x_i, g_{i-1}\})}; g_1 = x_1\) \quoteoff Sind die \(g_i\) Zahlen oder Funktionen? mfg thureduehrsen\(\endgroup\)


   Profil
MartinN
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 05.08.2016
Mitteilungen: 1305
Wohnort: Bayern
  Beitrag No.7, vom Themenstarter, eingetragen 2021-09-15

\(g_i\) ist eine rekursiv definierte Folge ("rekursive Funktion" war wohl falsch geschrieben und lehnte eher an eine zu programmierenden "Funktion" an). Als Folge sind es somit Zahlen. Sie hat den Stratwert \(x_1\), und wird dann rekursiv definiert in Abhängigkeit vom letzten Folgeglied, der nächsten Zahl der betrachteten Menge und dem Minimum dieser beiden Zahlen (welches ja berechnet werden könne). Noch weitere Fragen ^^


   Profil
MartinN 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!

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]