Schubfachprinzip - Summe von Zahlen

17.06.2017, 15:04

Der_Apfel

Auf diesen Beitrag antworten »

Schubfachprinzip - Summe von Zahlen

Aufgabe: Wenn man beliebige 10 zweistellige Zahlen wählt dann gibt es mindestens 2 Teilmengen dieser Zahlen, die dieselbe Summe haben.

Mein Ansatz:

$\begin{eqnarray*} M = \{3,15,23,19,67,58,43,33,5,-9\} \end{eqnarray*}$

Die Kategorien sind die möglichen Summen der 10 Zahlen, dies ergibt sich aus der Kombinatorik in dem man aus einer 10-elementigen Menge eine Teilmenge $\begin{eqnarray*} T \end{eqnarray*}$ mit $\begin{eqnarray*} 1\leq|T|\leq 10 \end{eqnarray*}$

$\begin{eqnarray*} \sum_{i=1}^{10} \begin{pmatrix}10 \\ i\end{pmatrix} \end{eqnarray*}$

Die Objekte sind die Teilmengen von $\begin{eqnarray*} M \end{eqnarray*}$ :

$\begin{eqnarray*} \mathcal{P}(M) = 2^{10}=1024 \end{eqnarray*}$

Die oben genannte Menge an Summen ist deutlich größer als 1024 demnach gibt es mindestens 2 Teilmengen, die die selbe Summe aufweisen. Ist das richtig, was ich gemacht habe?

Grüße

17.06.2017, 17:13

HAL 9000

Auf diesen Beitrag antworten »

1) Wenn man von "zweistelligen Zahlen" spricht, meint man ganze Zahlen zwischen 10 und 99. Insofern sind einige der Elemente der von dir angeführten $\begin{align*} M \end{align*}$ -Beispielmenge ziemlich seltsam gewählt...

2) Was meinst du mit "Die oben genannte Menge an Summen ist deutlich größer als 1024" ?

Die Anzahl der möglichen Teilmengen ist 1024. Und zudem sollte man sich überlegen, welche Schranken für die Teilmengenelementsummen hier bestehen, dann erst greift das Schubfachprinzip.

17.06.2017, 21:10

Der_Apfel

Auf diesen Beitrag antworten »

Danke für deine Antwort,

Zu 1.)

Ich hatte vergessen zu erwähnen, dass auch eine führende $\begin{eqnarray*} 0 \end{eqnarray*}$ gültig ist (warum auch immer, seltsame Aufgabenstellung...), prinzipiell ist das aber egal für das Schubfachprinzip welche Beispielmenge ich mir ausdenke, es gilt ja für alle Mengen.

Zu 2.)

Ich meinte, dass

$\begin{eqnarray*} \sum_{i=1}^{10} \begin{pmatrix}10\\i\end{pmatrix} > 1024 \end{eqnarray*}$

Irgendwie komm ich hier nicht weiter, eigentlich müsste die Anzahl der verschiedenen Summen kleiner als 1024 sein damit das Schubfachprinzip aufgeht verwirrt

verwirrt

Edit: Okay, kompletter Mist was oben steht, ich hatte doch recht Big Laugh

Big Laugh

$\begin{eqnarray*} \sum_{i=1}^{10} \begin{pmatrix}10\\i\end{pmatrix} = 10+45+120+210+252+210+120+45+10+1= 1023 < 1024 \end{eqnarray*}$

Kaum rechnet man die Summe nach ist sie tatsächlich kleiner als 1024 Big Laugh

Big Laugh

18.06.2017, 08:54

HAL 9000

Auf diesen Beitrag antworten »

Das Thema mit der Anzahl der möglichen Teilmengen hast du ja nun langsam totgeritten: Ja, es sind $\begin{align*} 2^{10}=1024 \end{align*}$ , keiner bestreitet das, Punkt.

Komm jetzt besser zu dem anderen Punkt, nämlich inwieweit diese Anzahl in den Schluß per Schubfachprinzip eingeht.

Zitat:

Original von Der_Apfel
prinzipiell ist das aber egal für das Schubfachprinzip welche Beispielmenge ich mir ausdenke, es gilt ja für alle Mengen.

Das ist falsch: Nehmen wir für die Auswahl beliebige höchstens dreistellige Zahlen, so erfüllt die Menge

$\begin{align*} M = \{1,2,4,8,16,32,64,128,256,512\} \end{align*}$

die Behauptung nicht. Also überdenke nochmal dein "egal", es ist für die Beweisführung schon wichtig zu klären, welche Zahlen da überhaupt ausgewählt werden dürfen:

Wenn ich dein Beispiel richtig verstehe, dann sind es beliebige höchstens zweistellige Zahlen beiderlei Vorzeichens, also in Frage kommen ganze Zahlen zwischen -99 und 99, stimmt das jetzt so? verwirrt

verwirrt

18.06.2017, 10:15

Der_Apfel

Auf diesen Beitrag antworten »

Zitat:

Komm jetzt besser zu dem anderen Punkt, nämlich inwieweit diese Anzahl in den Schluß per Schubfachprinzip eingeht.

Wenn ich jedem Objekt (die Teilmengen und deren Summe) einer Kategorie (die möglichen Summen) zuordne, könnten 1023 Objekte 1023 Kategorien zugeordnet werden, ein Objekt muss demnach in eine Kategorie, in der bereits ein Objekt ist, demnach gibt es eine Summe die von zwei Teilmengen dargestellt wird.

Ist das richtig?

Zitat:

stimmt das jetzt so?

Ja, entschuldige, dass ich mich etwas unklar ausgedrückt habe.

18.06.2017, 11:11

HAL 9000

Auf diesen Beitrag antworten »

Bitte geh doch mal auf den Punkt ein, welche Schubfächer du betrachtest, und warum es im konkreten Fall hier weniger Schubfächer als zu verteilende Objekte gibt! Das von mir angeführte Beispiel einer Menge, wo es nicht zwei unterschiedliche Teilmengen mit gleicher Elementsumme zeigt doch, dass es dann doch irgendwie von den nur maximal zweistelligen Zahlen abhängen muss. (Warum nur drückst du dich so beharrlich um diesen Punkt?)

Anzeige

18.06.2017, 11:45

Der_Apfel

Auf diesen Beitrag antworten »

Die Schubfächer (Kategorien) sind die Möglichen Summen, die man aus einer 10-elementigen Menge bilden kann, da hab ich 1023 raus bekommen (ich hoffe das stimmt wenigstens)?

Warum es für Mengen, die dreistellige Zahlen enthalten, nicht geht, kann ich mir gerade leider nicht erschließen unglücklich

unglücklich

18.06.2017, 13:16

Huggy

Auf diesen Beitrag antworten »

Ja mei, ist das schwer mit dir!

Zitat:

Original von Der_Apfel
Die Schubfächer (Kategorien) sind die Möglichen Summen, die man aus einer 10-elementigen Menge bilden kann,

Ja.

Zitat:

da hab ich 1023 raus bekommen (ich hoffe das stimmt wenigstens)?

Nein!!!
1023 ist die Zahl der unterschiedlichen Teilmengen, die man aus einer Menge mit 10 Elementen auswählen kann, wenn man die leere Menge mal weglässt.

Es ist also die Frage von HAL noch immer offen, weshalb Zahl der möglichen Summenwerte (also die Zahl der Schubfächer) dieser 1023 Teilmengen kleiner 1023 ist, wenn man nur zweistellige ganze Zahlen als Elemente zulässt.

18.06.2017, 15:09

Der_Apfel

Auf diesen Beitrag antworten »

Zitat:

Es ist also die Frage von HAL noch immer offen, weshalb Zahl der möglichen Summenwerte (also die Zahl der Schubfächer) dieser 1023 Teilmengen kleiner 1023 ist, wenn man nur zweistellige ganze Zahlen als Elemente zulässt.

Hm, die maximale Summe wäre dann $\begin{eqnarray*} 99+98=197 \end{eqnarray*}$ , d.h. es gibt nur $\begin{eqnarray*} 197 \end{eqnarray*}$ verschiedene Summen?

18.06.2017, 15:15

HAL 9000

Auf diesen Beitrag antworten »

Nein, es sind 10 Zahlen in $\begin{align*} M \end{align*}$ , damit bestehen auch die Teilmengensummen nicht nur aus zwei, sondern aus bis zu 10 Summanden. Zudem hast du ja auch noch negative Zahlen in $\begin{align*} M \end{align*}$ zugelassen, womit die Summen auch negativ werden können. Das erschwert die Geschichte ein wenig, aber nicht viel.

18.06.2017, 15:27

Der_Apfel

Auf diesen Beitrag antworten »

D.h. im Intervall von $\begin{eqnarray*} [-99,99] \end{eqnarray*}$ darf ich 10 Zahlen wählen? Wie soll ich denn da die Anzahl verschiedener Summen bestimmen? traurig

traurig

18.06.2017, 16:09

HAL 9000

Auf diesen Beitrag antworten »

Menge $\begin{align*} M \end{align*}$ besteht aus 10 Zahlen aus $\begin{align*} \{-99,-98,\ldots,98,99\} \end{align*}$ , ja. Für eine beliebige Teilmenge von $\begin{align*} M \end{align*}$ ist deren Elementsumme offenbar eine ganze Zahl, soviel ist sofort klar. Jetzt wollen wir aber bestimmen, welche Schranken es für diese Elementsumme bei festem $\begin{align*} M \end{align*}$ gibt!

Betrachten wir mal den Fall, dass $\begin{align*} M \end{align*}$ aus genau $\begin{align*} n \end{align*}$ negativen und demzufolge dann $\begin{align*} (10-n) \end{align*}$ nichtnegativen Zahlen (d.h. positiv oder Null) besteht. Eine Teilmengenelementsumme ist genau dann minimal, wenn diese Teilmenge genau aus den $\begin{align*} n \end{align*}$ negativen Zahlen besteht, diese Elementsumme ist auf jeden Fall $\begin{align*} \geq -99n \end{align*}$ . Eine Teilmengenelementsumme ist genau dann maximal, wenn diese Teilmenge aus den $\begin{align*} (10-n) \end{align*}$ nichtnegativen Zahlen besteht, diese Elementsumme ist auf jeden Fall $\begin{align*} \leq 99(10-n) \end{align*}$ . Zusammenfassend liegt also die Elementsumme im Intervall $\begin{align*} [-99n,99(10-n)] \end{align*}$ . Als Schubfächer wählen wir nun alle ganzen Zahlen in diesem Intervall. Wie viele sind das?

18.06.2017, 16:35

Der_Apfel

Auf diesen Beitrag antworten »

Zitat:

Wie viele sind das?

$\begin{eqnarray*} 99n + 99(10-n) = 99 + 990 - 99n = 990 \end{eqnarray*}$ , also 990?

18.06.2017, 16:38

HAL 9000

Auf diesen Beitrag antworten »

Fast, es sind 991. Was bedeutet das nun?

18.06.2017, 16:43

Der_Apfel

Auf diesen Beitrag antworten »

Es gibt 1023 Teilmengen und nur 991 verschiedene Summen, d.h. es gibt mindestens eine Summe, die mehr als einer Teilmenge zugeordnet werden kann?

18.06.2017, 16:48

HAL 9000

Auf diesen Beitrag antworten »

Genau. Ende gut, alles gut.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »