Beweis von Existenz eines Vielfachen

12.06.2020, 23:00

Bonbon2007

Beweis von Existenz eines Vielfachen

Meine Frage:
Hallo,

Wie kann ich am elegantesten beweisen, dass aus n ganzen Zahlen MINDESTENS eine Zahl als Vielfaches von n gibt?

Danke in voraus,
Bonbon

Meine Ideen:
irgendwas mit Schubfachprinzip?

12.06.2020, 23:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Bonbon2007
Wie kann ich am elegantesten beweisen, dass aus n ganzen Zahlen MINDESTENS eine Zahl als Vielfaches von n gibt?

So ist die Aussage sicher falsch. Hast du womöglich "aufeinander folgend" unterschlagen?

14.06.2020, 23:10

Bonbon2007

Auf diesen Beitrag antworten »

der originale Aufgabentext ist wie folgt:

beweise, dass man aus n beliebig gegebenen ganzen Zahlen stets einige Zahlen auswählen kann, deren Summe durch n teilbar ist, oder mindestens eine Zahl, die ein Vielfaches von n ist.

Also Summe einiger Zahlen durch n teilbar kann ich mit Restklasse 1 und n-1, 2 und n-2 usw. beweisen, aber MINDESTENS eine Zahl als Vielfaches von n ???

14.06.2020, 23:23

Helferlein

Auf diesen Beitrag antworten »

Nimm n=2 und zwei ungerade Zahlen. Keine der beiden ist durch 2 teilbar, ihre Summe aber schon.

Aussagenlogisch ist (A oder B) nur dann falsch, wenn weder A noch B zutrifft. Du hast also zwei Möglichkeiten: Entweder zeigst Du, dass eine der beiden Aussagen immer wahr ist, oder Du zeigst, dass wenn beide Aussagen nicht zutreffen ein Widerspruch zur Annahme, dass n ganze Zahlen vorliegen.

15.06.2020, 07:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Bonbon2007
Wie kann ich am elegantesten beweisen, dass aus n ganzen Zahlen MINDESTENS eine Zahl als Vielfaches von n gibt?

Zitat:

Original von Bonbon2007
beweise, dass man aus n beliebig gegebenen ganzen Zahlen stets einige Zahlen auswählen kann, deren Summe durch n teilbar ist, oder mindestens eine Zahl, die ein Vielfaches von n ist.

Dreifach

für den Meister der Verstümmelung.

Lösungisidee: Man ordne die Zahlen in irgendeiner Reihenfolge an, also $\begin{eqnarray*} a_1,\ldots,a_n \end{eqnarray*}$ und bilde dann

$\begin{eqnarray*} s_m = \sum_{k=1}^m a_k \end{eqnarray*}$ für $\begin{eqnarray*} m=1,\ldots,n \end{eqnarray*}$ zuzüglich der leeren Summe $\begin{eqnarray*} s_0=0 \end{eqnarray*}$ .

Dann liegen nach Schubfachprinzip mindestes zwei der $\begin{eqnarray*} (n+1) \end{eqnarray*}$ Zahlen $\begin{eqnarray*} s_0,s_1,\ldots,s_n \end{eqnarray*}$ in derselben Restklasse modulo n ...

15.06.2020, 10:13

Bonbon2007

Auf diesen Beitrag antworten »

Zitat:

Original von Helferlein
Nimm n=2 und zwei ungerade Zahlen. Keine der beiden ist durch 2 teilbar, ihre Summe aber schon.

Aussagenlogisch ist (A oder B) nur dann falsch, wenn weder A noch B zutrifft. Du hast also zwei Möglichkeiten: Entweder zeigst Du, dass eine der beiden Aussagen immer wahr ist, oder Du zeigst, dass wenn beide Aussagen nicht zutreffen ein Widerspruch zur Annahme, dass n ganze Zahlen vorliegen.

Vielen Dank :thumb

15.06.2020, 10:19

Bonbon2007

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Bonbon2007
Wie kann ich am elegantesten beweisen, dass aus n ganzen Zahlen MINDESTENS eine Zahl als Vielfaches von n gibt?

Zitat:

Dreifach

Jau... wenn danach mindestens zwei der Zahlen in der selben Restklasse 0 schliesst sich natürlich auch "mindestens eine" Fall, stimmt? Hammer

Vielen Dank HAL 9000

15.06.2020, 10:28

HAL 9000

Auf diesen Beitrag antworten »

Du hast immer noch nicht verstanden. Es ist so gemeint:

Nach Schubfachprinzip existiert eine Restklasse $\begin{eqnarray*} r \end{eqnarray*}$ sowie zwei Indizes $\begin{eqnarray*} i,j \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq i < j\leq n \end{eqnarray*}$ und $\begin{eqnarray*} s_i\equiv r\bmod n \end{eqnarray*}$ und $\begin{eqnarray*} s_j\equiv r\bmod n \end{eqnarray*}$ . Der Clou ist jetzt, dass man die Differenz dieser beiden Summen bildet:

Für die gilt zum einen $\begin{eqnarray*} s_j-s_i = \sum_{k=i+1}^j a_k \end{eqnarray*}$ , sie ist also eine Summe von Werten der Ausgangsmenge, zum anderen gilt aber auch $\begin{eqnarray*} s_j-s_i\equiv 0\bmod n \end{eqnarray*}$ , d.h. der Wert ist wie gefordert durch $\begin{eqnarray*} n \end{eqnarray*}$ teilbar.

D.h. nochmal: Wir wissen nicht, welche Restklasse dieses $\begin{eqnarray*} r \end{eqnarray*}$ wirklich ist, wir können daher auch keinesfalls annehmen, dass es $\begin{eqnarray*} r=0 \end{eqnarray*}$ ist. Nach dem obigen Beweisweg ist es aber auch völlig egal, wie groß $\begin{eqnarray*} r \end{eqnarray*}$ ist, wichtig ist nur dessen Existenz.

Neue Frage »

Antworten »

Beweis von Existenz eines Vielfachen

Verwandte Themen