Forum:  Rätsel und Knobeleien (Knobelecke)
Thema: * Produkt durch Summe approximieren
Themen-Übersicht
Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3009
Themenstart: 2019-07-07 13:07
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\) Ein kleiner Zusatz zu Aufgabe 271246B aus dem Thread über alte Olympiadeaufgaben: Sei $n\geq 2$ eine natürliche Zahl. Man beweise oder widerlege, dass dann Funktionen $f_1,\ldots, f_n: [0,1]\to \IR$ existieren, so dass für alle $a_1,\ldots, a_n\in [0,1]$ gilt: \[\left|a_1\cdot a_2 \cdot \ldots \cdot a_n - \sum_{k=1}^n f_k(a_k)\right| \leq \frac 12 -\frac 1{2n}.\]\(\endgroup\)

Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3009
Beitrag No.1, vom Themenstarter, eingetragen 2019-07-13 22:13
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\) Da noch niemand eine Lösung eingereicht hat, hier als Tipp für den Anfang die Idee, die mich letztlich auf die richtige Spur gebracht hat: \showon Zumindest für $n=2$ kann man iterativ solche Funktionen $f_1,f_2$ finden: Starte mit $f_1(x)=0$ für alle $x\in[0,1]$. Wie sollte man dann $f_2$ wählen, so dass \[ \sup_{a_1,a_2\in[0,1]}\left|a_1 a_2 -f_2(a_2) \right| \] möglichst klein wird? \showoff \(\endgroup\)

Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3009
Beitrag No.2, vom Themenstarter, eingetragen 2019-07-21 15:29
Rätselt hier jemand, der einen weiteren Tipp will?

MartinN
Aktiv
Dabei seit: 05.08.2016
Mitteilungen: 1305
Wohnort: Bayern
Beitrag No.3, eingetragen 2019-07-22 19:11
Meine Idee ist zu ungenau xD Aber hab auch nicht wirklich weiter gerätselt... Zumindest auf 1/2 komme ich xD

Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3009
Beitrag No.4, vom Themenstarter, eingetragen 2019-07-23 18:37
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\) Kitaktus hat eine korrekte Lösung gefunden. Herzlichen Glückwunsch! \quoteon(2019-07-22 19:11 - MartinN in Beitrag No. 3) Zumindest auf 1/2 komme ich xD \quoteoff Wenn man immer $\frac 12$ als Wert des Produktes rät, dann irrt man sich höchstens um $\frac 12$, da das Produkt zwischen 0 und 1 liegt. ;-) Hier als Tipp eine Lösung für $n=2$, die auf meinem ersten Tipp beruht: \showon Angenommen es wäre immer $f_1(a_1)=0$. Sei $a_2\in [0,1]$ beliebig. Wir wollen $f_2(a_2)$ so definieren, dass der größte Wert, den $|a_1a_2 -f_2(a_2|$ annehmen kann, möglichst klein wird. Da $0\leq a_1a_2 \leq a_2$ gilt, sollten wir also $f_2(a_2)$ als das arithmetische Mittel der unteren und oberen Schranke wählen, also $f_2(a_2) = \frac 12 a_2$. Nehmen wir jetzt an, dass $f_2(a_2) =\frac 12 a_2$ für alle $a_2\in[0,1]$ gilt. Wie müssen wir dann die Funktion $f_1$ definieren, so dass der größte Wert, den $|a_1a_2 -f_1(a_1) -\frac 12 a_2|$ annehmen kann, möglichst klein wird? Es gilt $a_1a_2-\frac 12 a_2 = (a_1-\frac 12)a_2$. Für festes $a_1\geq \frac 12$ und beliebiges $a_2$ gilt also $0\leq a_1a_2-\frac 12 a_2 \leq a_1- \frac 12$. Für festes $a_1\leq \frac 12$ und beliebiges $a_2$ ist entsprechend $a_1-\frac 12\leq a_1a_2-\frac 12 a_2 \leq 0$. In jedem Fall sollten wir daher $f_1(a_1)$ definieren als $f_1(a_1)= \frac 12(0+a_1-\frac 12)= \frac 12a_1-\frac 14$. Eine weitere Iteration würde keine Änderung mehr bewirken. Und tatsächlich können wir mit obiger Rechnung zeigen, dass für $f_1(a_1)=\frac 12a_1-\frac 14$ und $f_2(a_2)=\frac 12 a_2$ die gewünschte Ungleichung \[|a_1a_2-f_1(a_1)-f_2(a_2)|\leq \frac 14 = \frac 12-\frac 1{2\cdot 2}\] gilt. \showoff Mit dieser Lösung könnte man jetzt folgende Vermutung für allgemeines $n$ aufstellen: \showon \[\left|a_1a_2\cdots a_n -\frac 1n\left(a_1+a_2+\ldots+a_n\right)+ \frac 12 -\frac 1{2n}\right| \leq \frac 12 -\frac 1{2n}\] \showoff Mehr Tipps gebe ich aber nicht. :-) \(\endgroup\)

Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3009
Beitrag No.5, vom Themenstarter, eingetragen 2019-07-31 23:29
Dank MartinN ist mir aufgefallen, dass in meinem letzten Tipp ein Fehler war, den ich jetzt behoben habe. Ich werde das Rätsel in einer Woche auflösen.

Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 3009
Beitrag No.6, vom Themenstarter, eingetragen 2019-08-16 18:12
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}}\) Sind jetzt doch zwei Wochen geworden, aber hier die Auflösung: \showon Ja, es gibt solche Funktionen. Wir beweisen dazu die Ungleichung \[0\leq \frac 1n (a_1+\ldots +a_n) -a_1\cdots a_n \leq 1-\frac 1n. \qquad (*)\] Sei $G(a_1,\ldots, a_n) := \frac 1n (a_1+\ldots +a_n) -a_1\cdots a_n$. Für fest gewählte $a_2,\ldots, a_n$ ist die Abbildung $g(a_1):= G(a_1,\ldots, a_n)$ affin linear in $a_1$. Daher nimmt $g(a_1)$ für $0\leq a_1 \leq 1$ nur Werte zwischen $g(0)$ und $g(1)$ an. Da $G$ symmetrisch in $a_1,\ldots, a_n$ ist, folgt, dass das Minimum und das Maximum, das $G$ auf der Menge $[0,1]^n$ annehmen kann, auf $\{0,1\}^n$ angenommen wird. Es gilt $G(1,1,\ldots, 1) = 0$. Wenn $a_1,\ldots, a_n \in \{0,1\}$ liegen, und mindestens ein $a_i=0$ ist, dann gilt offenbar \[0 \leq G(a_1,\ldots, a_n) \leq \frac{n-1}n = 1-\frac 1n. \] Damit ist (*) bewiesen. Durch Subtraktion von $\frac 12 -\frac 1{2n} =\frac{n-1}{2n} $ folgt aus (*), dass \[\left|\frac 1n (a_1+\ldots +a_n) -a_1\cdots a_n -\frac{n-1}{2n} \right|\leq \frac 12 -\frac 1{2n}.\] Daher können wir z.B. $f_1(x)=f_2(x)=\ldots = f_n(x) = \frac 1n x - \frac{n-1}{2n^2}$ wählen. $\square$ \showoff Die Schranke in der Aufgabe ist scharf: Den Beweis der anderen Richtung findet man hier. \(\endgroup\)



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=242641=6
Druckdatum: 2021-09-20 15:29