Beweis

29.10.2018, 19:54

JG97

Beweis

Hallo

,

meine 3. Woche an der Uni und wir haben folgende Aufgabe bekommen.

"Ein Elektrogeschäft möchte die Prozesse beim Bezahlen optimieren. Zur Bezahlung ihrer Produkte werden Münzen im Wert von 3 Euro und 5 Euro eingeführt. Zudem sollen jegliche Produkte einen ganzzahligen Preis haben, welcher mindestens 8 Euro beträgt. Nun verspricht der Geschäftsführer, dass fortan kein Wechselgeld mehr benötigt werden würde, wenn die Kunden genügend von den neuen 3 Euro und 5 Euro Münzen jeweils mit sich führen.
Beweise die Behauptung des Geschäftsführers."

Mein Gedanke ist, dass ich eine Menge M = { x,y aus den natürlichen Zahlen } mit der Funktion f(x,y) = 3x + 5y auf P { p aus N: p größergleich 8 } abbilde und zeige, dass die Abbildung surjektiv ist.
Grundsätzlich weiß ich von der heutigen Vorlesung, wie man Surjektivität zeigt. Man nimmt ein p. Löst dann p = 3x + 5y nach x auf und setzt es in f(x,y) ein. Wenn dann f(x,y) = p rauskommt, dann ist die Abbildung surjektiv.

Nach dem Prinzip funktioniert es zumindest, wenn ich nur eine Variable habe. Was ist jetzt, wenn ich zwei habe? Dann geht das so nicht, oder?

Oder bin ich komplett falsch.

Kann mir jemand helfen? smile

29.10.2018, 20:05

HAL 9000

Auf diesen Beitrag antworten »

RE: Beweis

Zitat:

Original von JG97
Mein Gedanke ist, dass ich eine Menge M = { x,y aus den natürlichen Zahlen } mit der Funktion f(x,y) = 3x + 5y auf P { p aus N: p größergleich 8 } abbilde und zeige, dass die Abbildung surjektiv ist.

So geschrieben ist die Abbildung schon falsch definiert: Die Werte f(0,0)=0, f(1,0)=3, f(2,0)=6 und f(0,1)=5 liegen sämtlich nicht in deiner Zielmenge $\begin{eqnarray*} P \end{eqnarray*}$ . unglücklich

Repariert werden kann da ganze so: Es ist $\begin{eqnarray*} f:\;\mathbb{N}\times \mathbb{N}\to \mathbb{N} \end{eqnarray*}$ , und was du nachweisen musst ist, dass für dein $\begin{eqnarray*} P \end{eqnarray*}$ dann $\begin{eqnarray*} P\subset f(\mathbb{N},\mathbb{N}) \end{eqnarray*}$ gilt.

29.10.2018, 20:09

JG97

Auf diesen Beitrag antworten »

RE: Beweis
So eine Schreibweise haben wir noch gar nicht traurig

(also das mit dem N X N)
Ich verstehe nicht ganz, warum die Abbildung falsch definiert ist verwirrt

Wenn doch x,y aus den natürlichen Zahlen sind, dann kann das doch nicht 0 sein oder hat das was damit zu tun, dass (1,0) nicht bedeutet, dass x=1 und y=0.
Bin dritte Woche und Wiwi also nicht die Hellste smile

EDIT: Komplettzitat entfernt (klarsoweit)

29.10.2018, 20:14

HAL 9000

Auf diesen Beitrag antworten »

RE: Beweis

Zitat:

Original von JG97
Wenn doch x,y aus den natürlichen Zahlen sind, dann kann das doch nicht 0 sein

Ok, bei dir ist $\begin{eqnarray*} \mathbb{N} \end{eqnarray*}$ ohne Null - damit wird deine Beschreibung ja noch falscher als sie ohnehin schon ist: Du bist dann der Meinung, dass immer mindestens ein 3€- und zugleich mindestens ein 5€-Stück in der Bezahlsumme dabei sein muss: Wie willst du mit dieser Zusatzbedingung z.B. den Preis 9€ bezahlen? unglücklich

29.10.2018, 20:16

JG97

Auf diesen Beitrag antworten »

RE: Beweis
Ok, jetzt verstehe ichs. Ja das ist Quatsch.

EDIT: Komplettzitat entfernt (klarsoweit)

29.10.2018, 20:20

JG97

Auf diesen Beitrag antworten »

RE: Beweis
Eine generelle Frage hätte ich noch, dann lasse ich dich in Ruhe Mit Zunge

Wie zeigt man denn, dass eine Abbildung surjektiv ist, wenn die zwei Variablen hat?

29.10.2018, 20:52

JG97

Auf diesen Beitrag antworten »

RE: Beweis
Okay ich habe einen neuen Ansatz, passt der? smile

Ich sage X={3a+5b: a,b $\begin{eqnarray*} \in \end{eqnarray*}$ "N mit 0"}
Und P={p $\begin{eqnarray*} \in \end{eqnarray*}$ "N mit 0": p >7}

Dann zeige ich, dass P $\begin{eqnarray*} \subset \end{eqnarray*}$ X. Ist das besser?

29.10.2018, 22:01

JG97

Auf diesen Beitrag antworten »

RE: Beweis

Zitat:

Original von HAL 9000

Zitat:

kann mir jemand sagen, was ich machen muss, wenn ichs so versuchen will. Ich weiß nur, dass ich zeigen muss, dass ("p aus P") dann folgt ("p aus f(N,N)) und ich kenne den direkten, indirekten und Widerspruchsbeweis.

30.10.2018, 00:27

JG97

Auf diesen Beitrag antworten »

RE: Beweis
Hey, ich denke ich habe jetzt eine Lösung.
Kann mal jemand drüber schauen.

f:NxN->N; ("N mit 0")
f(m,n) = 5m + 3n
P = {p aus N: p > 7 } Teilmenge von N.

Ich glaube es reicht Surjektivität zu zeigen. Also, für alle p aus P gibts ein (m,n) aus NxN;, sodass f(m,n) = p.
Wähle irgend ein p aus P: p = 5m + 3n. Man kann ja sagen m = 0. Dann ist p = 3n, das ist äquivalent zu n = p/3 (ist aus N weil p > 7)
Also ist (0, p/3) aus NxN; und f(0, p/3) = 0 + 3(p/3) = p.
--> Also gibts ein Element (o, p/3) aus NxN;, so dass f(0, p/3) =y. Also surjektiv.
Also stimmt die Behauptung des Geschäftsführers.

30.10.2018, 10:20

HAL 9000

Auf diesen Beitrag antworten »

Deine gedankliche Fixierung auf Surjektivität ist für mich schwer begreiflich. Es ist doch so:

Deine Funktion $\begin{eqnarray*} f:\;\mathbb{N}_0\times \mathbb{N}_0\to \mathbb{N}_0 \end{eqnarray*}$ mit Funktionsgleichung $\begin{eqnarray*} f(x,y) = 3x+5y \end{eqnarray*}$ hat folgende tatsächliche Wertemenge:

$\begin{eqnarray*} \left\{~{\color{red}0, 3, 5, 6}, 8, 9, 10, 11,\ldots \right\} := W \end{eqnarray*}$ .

Man hat hier also weder Surjektivität zu Wertemenge $\begin{eqnarray*} \left\{ 8, 9, 10, 11,\ldots \right\} \end{eqnarray*}$ (hier fehlen die Werte 0,3,5,6) noch zu Wertemenge $\begin{eqnarray*} \mathbb{N}_0 \end{eqnarray*}$ (hier tauchen die Werte 1,2,4,7 als Funktionswerte nicht auf) vorliegen. unglücklich

Also: Was soll das, was du da treibst? Es verlangt doch auch gar keiner, dass du hier Surjektivität nachweisen sollst, sondern nur, dass die Funktionswerte $\begin{eqnarray*} 8,9,10,\ldots \end{eqnarray*}$ alle auftauchen. Hier

Zitat:

Original von JG97
Ich sage X={3a+5b: a,b $\begin{eqnarray*} \in \end{eqnarray*}$ "N mit 0"}
Und P={p $\begin{eqnarray*} \in \end{eqnarray*}$ "N mit 0": p >7}

Dann zeige ich, dass P $\begin{eqnarray*} \subset \end{eqnarray*}$ X.

hattest du es so ziemlich getroffen, bevor du einen erneuten "Rückfall" erlitten hast.

Und was den "Beweis" ganz unten betrifft: Du behauptest allen Ernstes, dass du mit Münzpaaren $\begin{eqnarray*} (m,n) \end{eqnarray*}$ mit $\begin{eqnarray*} m=0 \end{eqnarray*}$ auskommst, um alle Geldbeträge >8 mit $\begin{eqnarray*} 5m+3n \end{eqnarray*}$ (also das ist dann ja nur $\begin{eqnarray*} 3n \end{eqnarray*}$ ) zu bezahlen??? Glaubst du das wirklich? Damit kannst du tatsächlich nur die durch 3 teilbaren Geldbeträge bezahlen. unglücklich

------------------------------

Ein Tipp zum Beweis: Die drei Geldbeträge 8, 9, 10 kann man mit

$\begin{eqnarray*} 8 = 1\cdot 3 + 1\cdot 5 \end{eqnarray*}$
$\begin{eqnarray*} 9 = 3\cdot 3 + 0\cdot 5 \end{eqnarray*}$
$\begin{eqnarray*} 10 = 0\cdot 3 + 2\cdot 5 \end{eqnarray*}$

bezahlen. Alle Geldbeträge >11 kann man nun in einfacher Weise auf einen dieser drei Beträge zurückführen - eine Idee, wie das gemacht werden könnte?

30.10.2018, 10:32

JG97

Auf diesen Beitrag antworten »

Erstmal vielen Dank für deine Hilfe. Stimmt, das ist gar nicht surjektiv. Damit es surjektiv wäre, müsste ich sagen, dass
f: NxN -> P ; f(m,n) = 3m +5n

Bei dem Beweis habe ich ein versucht Surjektivität mit 2 Variablen zu zeigen. Da habe auf Youtube ein Video dazu gesehen, aber das scheint auch falsch zu sein.

Video

Also, ich verstehe schon, dass wenn man 8,9,10 hat dann jede Zahl bilden kann, wenn man 3 addiert.
Das Problem ist, dass ich das nur beschreiben kann und nicht wirklich beweisen kann.
Ganz am Anfang als ich die Aufgabe zum ersten Mal gesehen habe, dachte ich
8 = 5 + 3
9 = 3 + 3 + 3
10 = 5 + 5
11= 8 + 3
12 = 9 + 3
...

Aber das ist ja kein Beweis unglücklich

30.10.2018, 10:51

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von JG97
Also, ich verstehe schon, dass wenn man 8,9,10 hat dann jede Zahl bilden kann, wenn man 3 addiert.

Dann knie dich doch da mal rein, das ordentlich aufzuschreiben, denn die Idee an sich ist richtig!!!

Z.B. so: Für jeden Wert $\begin{eqnarray*} p\geq 8 \end{eqnarray*}$ betrachte man den Rest $\begin{eqnarray*} r \end{eqnarray*}$ bei Division durch 3, d.h. es ist $\begin{eqnarray*} p=3k+r \end{eqnarray*}$ mit $\begin{eqnarray*} r\in\{0,1,2\} \end{eqnarray*}$ . Die mögliche Geldstückelung $\begin{eqnarray*} p = 3m+5n \end{eqnarray*}$ kann man nun basierend auf den o.g. Grundwerten wie folgt angeben:

$\begin{eqnarray*} r=0 \end{eqnarray*}$ : Hier wählt man $\begin{eqnarray*} m=k \end{eqnarray*}$ und $\begin{eqnarray*} n=0 \end{eqnarray*}$ , passt für alle $\begin{eqnarray*} k\geq 0 \end{eqnarray*}$ .

$\begin{eqnarray*} r=1 \end{eqnarray*}$ : Hier wählt man $\begin{eqnarray*} m=k-3 \end{eqnarray*}$ und $\begin{eqnarray*} n=2 \end{eqnarray*}$ , passt für alle $\begin{eqnarray*} k\geq 3 \end{eqnarray*}$ .

$\begin{eqnarray*} r=2 \end{eqnarray*}$ : Hier wählt man $\begin{eqnarray*} m=k-1 \end{eqnarray*}$ und $\begin{eqnarray*} n=1 \end{eqnarray*}$ , passt für alle $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ .

Der "worst" case ist also der mittlere Fall $\begin{eqnarray*} r=1 \end{eqnarray*}$ , das ist der einzige, der für k=2 noch nicht klappt. Das zugehörige $\begin{eqnarray*} 7=2\cdot 3+1 \end{eqnarray*}$ ist damit der größte Geldbetrag, der nicht in der geforderten Form bezahlt werden kann.

P.S.: Deine "symbolische Wankelmütigkeit" mit $\begin{eqnarray*} 3x+5y \end{eqnarray*}$ über $\begin{eqnarray*} 3a+5b \end{eqnarray*}$ , $\begin{eqnarray*} 5m+3n \end{eqnarray*}$ bis hin zu $\begin{eqnarray*} 3m+5n \end{eqnarray*}$ ist zwar nicht schlimm, bietet aber auch Potential zu Missverständnissen.

30.10.2018, 10:58

JG97

Auf diesen Beitrag antworten »

Wow, genial. Ich muss lernen, dass man sowas genau so aufschreibt.
Du bist hammer, danke Hal Mit Zunge

Neue Frage »

Antworten »

Beweis

Verwandte Themen