Schubfachprinzip

04.12.2006, 13:04

Kathi111

Schubfachprinzip

Hallo,
ich muss wiedermal eine sehr seltsame aufgabe lösen, die ich erstmal garnich richtig verstehe:

Zeigen Sie, dass bei der Auswahl einer Menge X von 100 ganzen Zahlen aus {1, 2, 3,... , 200}, zwei Zahlen a, b enthalten sind mit a|b,
falls in X wenigstens eine Zahl c < 16 dabei ist.

Was bedeutet dabei a|b ??
is das die Mengendifferenz, also allso alles aus a ohne b, aber die wird doch eigentlich so bezeichnet: a\b.

ja hmm das ist erstmal meine erste frage.

04.12.2006, 13:10

therisen

Auf diesen Beitrag antworten »

Nein, das bedeutet, dass a ein Teiler von b ist. Hilft das weiter?

Gruß, therisen

04.12.2006, 13:17

Kathi111

Auf diesen Beitrag antworten »

achso, also quasi b durch a muss ne ganze zahl ergeben, dann ist a ein teiler von b?

Jetzt kenn ich zwar die aufgabe, aber so richtig ein anfang für das schubfachprinzip finde ich noch nicht..

04.12.2006, 14:11

Auf diesen Beitrag antworten »

Wesentlich angenehmer wäre die leicht modifizierte Variante

Zitat:

Zeigen Sie, dass bei der Auswahl einer Menge X von 101 ganzen Zahlen aus {1, 2, 3,... , 200}, zwei Zahlen a, b enthalten sind mit a|b.

so ist leider etwas Bastelei nötig.

EDIT: Die Sache ist wirklich ziemlich genau abgezirkelt - es gibt ein Gegenbeispiel von 100 Zahlen aus {1,2,...,200}, unter denen die 16 ist, und von denen keine eine andere teilt. Augenzwinkern

04.12.2006, 14:56

Kathi111

Auf diesen Beitrag antworten »

ja hmmm hilft mir auch nich wirklich weiter...
ich bräuchte mal irgend eine vorgehensweise

04.12.2006, 15:17

Auf diesen Beitrag antworten »

Ziehe mal aus jedem Element von $\begin{eqnarray*} x\in X \end{eqnarray*}$ die maximal darin enthaltene Zweierpotenz heraus, d.h. $\begin{eqnarray*} x=2^ky \end{eqnarray*}$ mit ungeradem $\begin{eqnarray*} y \end{eqnarray*}$ , und betrachte dann die Menge all dieser $\begin{eqnarray*} y \end{eqnarray*}$ , bezeichnet mit $\begin{eqnarray*} Y \end{eqnarray*}$ . Dann enthält $\begin{eqnarray*} Y \end{eqnarray*}$ nur ungerade Elemente aus $\begin{eqnarray*} \{1,3,5,\ldots, 197, 199\} \end{eqnarray*}$ . Die zugehörige Abbildung sei $\begin{eqnarray*} f:\;X\to Y \end{eqnarray*}$ , also mit $\begin{eqnarray*} f(x)=y \end{eqnarray*}$ .

Falls $\begin{eqnarray*} Y \end{eqnarray*}$ nun eine echte Teilmenge von $\begin{eqnarray*} \{1,3,5,\ldots, 197, 199\} \end{eqnarray*}$ ist, dann ist die Behauptung bewiesen - warum, überlegst du dir bitte selbst mit Schubfachprinzip.

Bleibt der Fall $\begin{eqnarray*} Y=\{1,3,5,\ldots, 197, 199\} \end{eqnarray*}$ mit dann bijektiven $\begin{eqnarray*} f \end{eqnarray*}$ übrig, der etwas verzwickt ist und wo man noch die Existenz dieses $\begin{eqnarray*} c\leq 15 \end{eqnarray*}$ mit $\begin{eqnarray*} c\in X \end{eqnarray*}$ verwenden muss...

P.S.: Jetzt bitte nicht sofort nachfragen, sondern erstmal nachdenken. Denn wenn du das nicht nachvollziehen kannst, hast du die Lösung der Aufgabe auch nicht verdient. Augenzwinkern

04.12.2006, 16:21

Kathi111

Auf diesen Beitrag antworten »

hmmm, so ganz versteh ichs nicht:

Also die Menge X besteht aus 100 ganzen zahlen aus {1,2,3,...,200}.
Nehmen wir an das ist die Menge X={2,4,6,...200} also alle geraden zahlen.
Aus diesen elementen soll ich nun die maximale zweierpotenz ziehen.
Dann wäre für x element X z.B.:
x=2 ->k=1,y=1
x=4 ->k=2,y=1
x=6 ->k=1,y=3
x=8 ->k=3,y=1
.....
x=200 -> k=3,y=25

Wenn y element Y und die Menge Y eine echte Teilmenge von {1,3,5..199} ist, also Y ungleich {1,3,5,..,199}, dann gilt die aussage, denn nach dem Schubfachprinzip gibt es zwei Zahlen x,y element X mit f(x)=f(y) (Funktion von vorhin) mit x ungleich y.
Wir wissen a=2^k*f(a) und b=2^k*f(a)...also ist b vielfaches von a..Beweis erbracht..

Ist das soweit richtig?

Wenn nun Y={1,3,5,...,199}, wieso sollte es da nicht genauso sein? das kapier ich noch nich so richtig

04.12.2006, 16:48

Auf diesen Beitrag antworten »

Die Menge $\begin{eqnarray*} \{1,3, \ldots, 199\} \end{eqnarray*}$ enthält genau 100 Zahlen. Wenn du auch 100 Funktionswerte hast, greift das Schubfachprinzip noch nicht!

Zitat:

Original von Arthur Dent
Bleibt der Fall $\begin{eqnarray*} Y=\{1,3,5,\ldots, 197, 199\} \end{eqnarray*}$ mit dann bijektiven $\begin{eqnarray*} f \end{eqnarray*}$ übrig, der etwas verzwickt ist und wo man noch die Existenz dieses $\begin{eqnarray*} c\leq 15 \end{eqnarray*}$ mit $\begin{eqnarray*} c\in X \end{eqnarray*}$ verwenden muss...

Da musst du eben noch etwas nachdenken - ich werd doch nicht alles verraten. Ohne das $\begin{eqnarray*} c \end{eqnarray*}$ wird das jedenfalls nix, betrachte doch nur mal das Gegenbeispiel $\begin{eqnarray*} X=\{ 101, 102, \ldots, 200 \} \end{eqnarray*}$ .

04.12.2006, 17:12

Kati111

Auf diesen Beitrag antworten »

Naja in der menge X={101,102,...200} gibt es keine zwei zahlen a,b mit a|b im bereich der ganzen Zahlen, da z.B. 101 oder 103 eine primzahl ist...
würde man die mengen abändern und die 101 mit 1 ersetzen also X={1,102,103,104,..199} würde es wieder stimmten und die zahl c wäre nachgewiesen.??

04.12.2006, 17:20

Auf diesen Beitrag antworten »

Zitat:

Original von Kati111
würde man die mengen abändern und die 101 mit 1 ersetzen also X={1,102,103,104,..199} würde es wieder stimmen und die zahl c wäre nachgewiesen.??

Ja, die Satzaussage stimmt dann für dieses ganz spezielle X. In Hinsicht auf den allgemeinen Beweis der Aussage hast du damit wenig gekonnt - oder willst du alle knapp $\begin{eqnarray*} \binom{200}{100} \approx 9 \cdot 10^{58} \end{eqnarray*}$ möglichen Teilmengen einzeln auflisten? Augenzwinkern

04.12.2006, 17:36

Kathi111

Auf diesen Beitrag antworten »

naja natürlich nich.

also unter den 100 zahlen, muss MINDESTENS eine zahl dabei sein die kleiner als 16 ist, sonst gilt a|b nicht mehr...

bei x={16,17,18,..., 115} gilts nich weil so eine zahl fehlt..

ich weiss einfach nicht wie ich das beweisen oder aufschreiben soll, ach man..

vielleicht weil alle zahlen von 1 bis 200 als produkte von a und b darstellbar sind...ich weiss es einfach nicht...

04.12.2006, 17:37

Auf diesen Beitrag antworten »

Ich sehe leider zu viele Defizite, du bist der Aufgabe einfach nicht gewachsen, das muss ich mal so hart sagen. Die ist aber auch wirklich schwer - ist das eine "Bonusaufgabe"?

04.12.2006, 17:43

Kathi111

Auf diesen Beitrag antworten »

ja is ne zusatzaufgabe, ich will die aber verstehn und auch machen..

04.12.2006, 18:27

Auf diesen Beitrag antworten »

Hab ich mir gedacht, das mit der Zusatzaufgabe. Nachdem ich ca. 70% des Lösungswegs verraten habe, geb ich dir mal noch das oben angesprochene Gegenbeispiel für c=16 mit auf den Weg. Auch das ist ganz lehrreich für den (Rest-)Beweis der eigentlichen Aussage:

X = { 16, 24, 36, 40, 54, 56, 60, 81, 84, 88, 90, 100, 101, 102, 103, 104, 105, 106, 107, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 126, 127, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 161, 163, 164, 165, 166, 167, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 193, 194, 195, 196, 197, 198, 199 }

04.12.2006, 18:35

Kathi111

Auf diesen Beitrag antworten »

Danke,
ich gebs auf, bin kein hund dem hingeworfene bröck'chen gefallen, dachte jemand kann mir das richtig und plausibel erklären, dabei war mir die eigentliche lösung dieser aufgabe nicht so wichtig...

04.12.2006, 18:49

Auf diesen Beitrag antworten »

Und ich bin keiner, der Leuten, die nichts aber auch gar nichts zu einer anspruchsvollen Aufgabe beitragen, einfach die Lösung bis in die kleinsten Einzelheiten erkläre.

Zitat:

Original von Kathi111
dabei war mir die eigentliche lösung dieser aufgabe nicht so wichtig...

Das war mehr als deutlich: Du bist nur auf die Zusatzpunkte scharf, die du bei anderen weniger schweren Aufgaben versemmelst. böse

04.12.2006, 19:19

Kathi111

Auf diesen Beitrag antworten »

boooor, jetzt wird man hier auch noch richtig angegriffen...
1. das is eine klausur-nacharbeitung...also wenn, dann hab ich alle punkte schon versemmelt...
2. wollte ich keine lösung...ich wollte einen ansatz, vielleicht weil ich das schubfachprinzip nicht wirklich verstanden hab...so wie ichs am anfang auch geschrieben hab... an da bringen mir bruchstücke aus einer Lösung garnix...

Also für jemanden der angibt das er 38 jahre alt ist, is dein verhalten glaube nich wirklich passend...aber vielleicht machst du dir ja nur ein spass daraus...naja was solls.

04.12.2006, 19:24

Auf diesen Beitrag antworten »

Den Ansatz habe ich bereits in meinem zweiten Post hier im Thread geliefert, und noch viel mehr. Aber du nutzt ihn ja nicht, und das ist, was mich ärgert. Dabei habe ich bereits in meinem ersten Post gesagt, dass ich Mitdenken erwarte - übrigens ganz gemäß Boardprinzip.

Da du - wie zuletzt angegeben - sowieso nicht an der Lösung interessiert bist, kann ich hier jetzt übrigens schließen. Wenn du andere nichtfachliche Dinge, wie z.B. mein Alter, diskutieren willst, mach das doch bitte im Off-topic. Augenzwinkern

Geschlossen

04.12.2006, 19:27

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von Kathi111ich wollte einen ansatz, vielleicht weil ich das schubfachprinzip nicht wirklich verstanden hab...so wie ichs am anfang auch geschrieben hab... an da bringen mir bruchstücke aus einer Lösung garnix...

Wenn du das Schubfachprinzip noch nicht ganz verstanden hast, ist das sicher nicht die richtige Aufgabe, um deine Defizite aufzubessern. Diese Aufgabe hat eine ganz andere Zielgruppe Augenzwinkern

Außerdem wurden dir schon Ansätze geliefert. Eigentlich ist es von dir unverschämt, gleich darauf weiterzufragen. Über so eine Aufgabe darf man schon mal ein paar Tage im stillen Kämmerlein grübeln Augenzwinkern

Desweiteren lege ich dir das Prinzip "Mathe online verstehen!" ans Herz.

Gruß, therisen

Neue Frage »

Antworten »

Schubfachprinzip

Verwandte Themen