Menge

[Gast]

Und wegen der Mächtigkeit:

Für endliche Mengen setzt man die Mächtigkeit gleich der Anzahl der Elemente der Menge, das ist eine natürliche Zahl.

(unter Wikipedia -> Mächtigkeit)

[XFame]

Nagut, dann stelle ich hier mal eine Aufgabe aus der Mathematikolympiade 2004 hinein.

Zitat:
Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 2004 positiven ganzen Zahlen, die alle kleiner als N sind, koennen
stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.

Ich versteh das nicht ganz. Sagen wir mal N = 2005 und M = {1,2,3,...,2004}.
Dann liegt doch jede Summe mit geeignet grossen Zahlen nicht mehr in M.
Es sind ja beliebige Zahlen und es soll jede Summe von 2 beliebigen Zahlen aus M wieder in M liegen.
Ich glaube man sagt, die Menge M ist unter der Addition abgeschlossen (Bitte korrigiert mich wenn es falsch ist).

[SG1]

<edit>Mist</edit>

[SG1]

Nâchster Versuch:

XFame schrieb:

es soll jede Summe von 2 beliebigen Zahlen aus M wieder in M liegen.

Nicht ganz: Es soll 2 Zahlen geben, deren Summe wieder in M liegt. (Existenz-, nicht Allquantor!)

[XFame]

Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 2004 positiven ganzen Zahlen, die alle kleiner als N sind, koennen
stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.

Ich glaube die beiden Zahlen sollen schon Elemente von M sein:

Aus jeder Menge M [...] koennen
stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.

[SG1]

Ja, klar. Gefordert ist aber Existenz dieser 2 Elemente, nicht, dass es für 2 beliebige Elemente gilt.

[pumuckl]

Es sollen auch nur zwei beliebige Zahlen sein, deren Summe in M liegt. Das bedeutet:
Es gibt in M drei Zahlen a,b,c, so dass a+b=c.
Es muss nur ein solches Tripel geben, das muss nicht für alle Zahlen gelten.
Bei der Menge {1,...,2004} gilt beispielsweise 1+2=3. Außerdem ist 2004 die einzige mögliche Menge für N = 2005, also ist das Kriterium für N=2005 erfüllt.

Wenn man versucht, sich aus zwei möglichst kleinen Anfangszahlen eine Menge zu basteln, die das Kriterium grade nicht mehr erfüllt, kommt man beim zweiten oder dritten Versuch darauf, dass die gesuchte Menge (für die das nicht mehr gilt) wohl die Menge der 2004 kleinsten ungeraden Zaheln ist: {1,3,5,7,...,4007}
ganz klar, die Summe zweier ungerader Zaheln ist immer gerade und daher nicht in der Menge.
Tja. Nun haben wir eine relativ kleine Zahl gefunden, für die das gewünschte nicht mehr gilt. (nämlich 4008) vielleicht gilts ja für N=4007?
Bleibt zu zeigen, dass die Mengen mit 2004 Elementen, die alle kleiner als 4007 sind, immer ein triplet besitzen mit a+b=c
nehmen wir die Menge mit den ungeraden Zahlen 1,3,..,4005 plus EINE einzige gerade zahl. nehmen wir an, die Zahl ist kleiner als 2004, z.B. 2002. Es gilt aber: 2002 + 1 = 2003, 2002 + 3 = 2005 usw., ich hab also ne Menge Probleme zu lösen. Ist die Zahl nun größer als 2004, z.b. 4004 dann gilt trotzdem noch 1 + 4003 = 4004, 3 + 4001 = 4004 usw. gibt also genausoviele probleme. Wenn man jetzt anfängt, die Problemzahlen unter den ungeraden in gerade Zahlen zu verwandeln, werden diese auch erstmal Probleme bereiten, bis man die Hälfte der ungeraden Zahlen in gerade verwandelt hat. Dann fangen die geraden an, tripletts zu bilden, die sich addieren. Beweis sei mal dahingestellt
Man kann also zumindest einsehn, dass N=4007 die gesuchte Zahl ist, wo in allen Mengen M mit 2004 Zahlen kleiner als 4007 zwei Zaheln findbar sind, deren Summe wieder in M liegt.
(Wer den Beweis vervollständigen möchte, hier ne Anregung: fang mit kleinen Mengen an, mit |M| = 1, |M| = 2, der Rest dann über Induktion...

[XFame]

Aber kann N nicht beliebig gross sein?
Man kann sich ja immer Elemente von M suchen in denen solche triplets existieren.
Meinetwegen N = 9999999999999 und M = {1,2,3,.....,2004}.
Da existieren doch die Triplets auch wieder.

[pumuckl]

Es soll für JEDE Menge M gelten, die aus 2004 kleineren zahlen besteht. Im fall 10000000 müsste es eben auch für {1,3,5,...,4007} gelten, und das tut es nicht.

[TGGC]

Machen wir mal Beispiel statt 2004 4 (Z=4).

Annahme N= 8. Falsch, in { 4, 5, 6, 7 } keine Summe möglich!
N=7?
{1,2,3,4};{1,2,3,5};{1,2,3,6} passt 1 + 2 = 3
{1,2,4,5} passt 1 + 4 = 5
{1,2,4,6} passt 2 + 4 = 6
{1,2,5,6} passt 1 + 5 = 6
{1,3,4,5};{1,3,4,6} passt 1 + 3 = 4
{1,3,5,6} passt 1 + 5 = 6
{1,4,5,6} passt 1 + 4 = 5
{2,3,4,5} passt 2 + 3 = 5
{2,4,5,6} passt 2 + 4 = 6
{3,4,5,6} keine Summe möglich! (Mist!)
also N=6 (siehe oben)

Vermutung: {N-Z, N-Z+1, ..., N-1 } ist die "kritische" Menge.

N - Z + N - Z + 1 = N - 1
N - Z + N - Z + 2 = N
2N - 2Z + 2 = N
N - 2Z + 2 = 0
N= 2Z - 2

So, jetzt braucht ihr nur noch den Beweis dazu.

Bye, TGGC

[TGGC]

@pumuckl: Sorry, deins noch nicht gelesen. Aber gleiches Ergebnis, muss also stimmen.

Bye, TGGC

[XFame]

Ahh, also alle moeglichen Mengen, die 2004 positive ganze Zahlen kleiner N enthalten.
Danke an alle.

[volkard]

Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 2004 positiven ganzen Zahlen, die alle kleiner als N sind, koennen stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.

die 2004 zu verfummeln, wie mein gegenspieler vorschlug, halte ich für gut.

---

Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 1 positiven ganzen Zahlen, die alle kleiner als N sind, koennen stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.
geht nicht, mann kann ja nicht zwei verschiedene auswählen.

---

Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 2 positiven ganzen Zahlen, die alle kleiner als N sind, koennen stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.
geht nicht, die summe liegt sicher nicht drin.

---

Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 3 positiven ganzen Zahlen, die alle kleiner als N sind, koennen stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.
N=4
{1,2,3} 1+2=3

N=5
{1,2,3} 1+2=3
{1,2,4} nee.
{1,3,4} egal
{2,3,4} egal

also N=4

---

Man bestimme die groesste natuerliche Zahl N, fuer die folgende Aussage gilt:
Aus jeder Menge M von 4 positiven ganzen Zahlen, die alle kleiner als N sind, koennen stets zwei verschiedene Zahlen ausgewaehlt werden, deren Summe ebenfalls in M liegt.

N=5
{1,2,3,4} 1+2=3
N=6
{1,2,3,4} 1+2=3
{1,2,3,5} 1+2=3
{1,2,4,5} 1+4=5
{1,3,4,5} 1+4=5
{2,3,4,5} 2+3=5
n=7
wie N=7 und
{1,2,3,6}
{1,2,4,5}
{1,3,4,5}
{1,3,4,6}
mann, da gibt es ja schon ganz schön viele. so wird das nix.

will ich mal versuchen, wie TGGC einen fall zu konstruieren, wo mit 4 zahlen ein möglichst kleines N nicht klappt.
ich nehme mal 1 und 2 in die menge auf und dann immer die nächste zahl, die nicht summe irgendeiner kombination der kleineren zahlen ist.

1,2
3 geht
4 geht nicht.
1,2,4
5 geht
6 geht
7 geht nicht.
1,2,4,7
8 geht
9 geht
10 nicht
1,2,4,7,10
11 geht
12 geht
13 nicht
1,2,4,7,10,13
ergibt das sinn?
jo, eigentlich schon.
2,3*0+1,3*1+1,3*2+1,3*3+1,...,3*irgendwas+1
egal, welche beiden man addiert, man kriegt 3*nochwas+2 (wenn die 2 nicht benutzt wurde) oder 3*nochwas (wenn die 2 benutzt wurde).

"1,2,4,7,10,13" ist auch schon lang genug für sloane.
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A033627
Name: 0-additive sequence: not the sum of any previous pair.

also ich kann eine menge mit 2004 zahlen bauen, die besteht aus
2,3*0+1,3*1+1,3*2+1,...,3*2002+1
mit N=6007

den wert, den TGGC für N hat, weiß ich nicht. habe sein posting nicht ganz verstanden. was hast du als N raus? was kleineres? ich sehe nämlich noch keinen weg, zu beweisen, daß es keine menge mit kleineren elementen gibt.

oder doch? wenn ich 3*2002+1 nicht nehme, sondern irgend eine kleinere zahl, dann ist sie ja 3*irgendwas(mit irgendwas>0) oder 3*irgendwas+2(mit irgendwas>=1)
eine 3*irgendwas(mit irgendwas>0) kriege ich als summe von 2 und 3*irgendwas+1

eine 3*irgendwas+2(mit irgendwas>=1) kriege ich als summe von 3*irgendwas+1 und 3*irgendwas+1

könnte stimmen. bitte um widerlegung.

edit:
ok, ist längst iderlegt mit
{1,3,5,...,4007}
man muß als erste beide zahlen nicht 1,2 wählen sondern 1,3.

[TGGC]

Ich habe gar kein Ergebnis raus, da der erwähnte Beweis fehlt. Was ich berechnet habe, ist nicht das gefragte N, sondern die Zahl N, für die es keine "kritische Menge" nach meiner Konstruktionsvorschrift gibt, weil die ersten beiden Zahlen als Summe die letzte ergeben.

Wobei ich grade sehe, das es doch nicht die Lösung von pumuckl ist:
{2003, 2004, ..., 4005, 4006 } sollte doch 4007 wiederlegen.

Nun noch der Beweis, das bei 4006 immer Summe dabei sein muss. Die grösste Zahl der Menge n= 4005 = 2 * N - 3 (klar warum...), d.h ungerade. Angenommen, die Summe liese sich nicht bilden. Ist nun die Zahl n1,1 < 4005 auch drin, so gäbe es mit Zahl n1,1 + n1,2 = n, d.h. n1,2 ist nicht drin, wenn sich die Summe sich nicht bilden lässt. Da n ungerade gilt n1,1 != n1,2. Wähle nun nz,1 so das alle nz,1 paarweise verschieden von nz,1 und nz,2 für z=1,2...N. Da aus nx,2 == ny,2 folgt, dass nx,1 == ny,1 sind auch alle nz,2 paarweise verschieden. D.h. wähle 2 * ( N - 1 ) paarweise verschiedene Zahlen aus für die gilt m < 2 * N - 3, es gibt aber nur 2 * ( N - 4 ) mögliche m, die das erfüllen. Widerspruch! Die Annahme "die Summe lässt sich nicht bilden" führt zu einem Widerspruch, die Summe lässt sich also bilden. q.e.d.

Klar?

Bye, TGGC

[b7f7]

wenn ihr N in Die Menge M legt und sagt, Ihr bildet aus M mit x<N und x Element M die Menge M1.
Mit 2*N-3 =max(M); // Soll in M liegen
ist
N=(max(M)+3)/2

Probe:
max(M)= 11
N= 7
Summe
N-1+N-2
6+5=11 in M