Zahlen aus einer Menge auswählen - gleiche Summen

12.03.2010, 20:39

mathe760

Zahlen aus einer Menge auswählen - gleiche Summen

Edit (mY+): Wann du deine Arbeit hast, tut im Titel nichts zur Sache.

Hallo,

ich habe hier eine MO Aufgabe, bei der ich etwas Hilfe benötige:

421336
Eine positive ganze Zahl heiße zulässig, wenn sie im dekadischen Positionssystem
fünfstellig ist und jede der Ziffern 1; 3; 5; 7; 9 genau einmal enthält.
a) Man untersuche, ob es eine Menge M von sechs zulässigen Zahlen gibt,
aus der man einige so auswählen kann, dass ihre Summe gleich der Summe
der verbleibenden Zahlen der Menge M ist.
b) Man bestimme alle natürlichen Zahlen m, für die es eine Menge M von
genau m Zahlen mit der unter a) genannten Eigenschaft gibt.

Meine Ansätze:

bei a) dachte ich mir: Man muss genau 3 der 6 Zahlen auswählen, damit überhaupt die Reste der Summen modulo 9 gleich sind.
Dann ist 13579<S<97531 also kann S weniger als 83952 Werte annehmen.
Man kann nun aber $\begin{eqnarray*} \begin{pmatrix} 120 \\ 3 \end{pmatrix} =280840 \end{eqnarray*}$
Tripel auswählen, daher gibt es zwei Tripel die die gleiche Summe haben.

zu b) denke ich, das es für alle geraden zahlen<=120 geht, ich hätte dann einen ähnlchen Beweis wie oben, bevor ich diesen aber präsentiere möchte ich erst wissen, ob das überhaupt so geht.
Ist es richtig das wenn man eine Menge M mit 2n elementen hat, dann muss man genau n elemente auswählen damit die Summen gleich sein können?

Bis denn mathe760

\Edit: Das mit dem "Monatb war nicht Absicht" muss ich wohl ausversehen reinkopiert haben.

12.03.2010, 20:51

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Ist es richtig das wenn man eine Menge M mit 2n elementen hat, dann muss man genau n elemente auswählen damit die Summen gleich sein können?

Für genügend große $\begin{eqnarray*} n \end{eqnarray*}$ ist das mit dem "muss" nicht richtig - aber es ist ja hinreichend, wenn man so eine Auswahl mit n Elementen findet.

Zitat:

Original von mathe760
Man kann nun aber $\begin{eqnarray*} \begin{pmatrix} 120 \\ 3 \end{pmatrix} =280840 \end{eqnarray*}$
Tripel auswählen, daher gibt es zwei Tripel die die gleiche Summe haben.

Die Sache hat einen Haken: Wenn die beiden Tripel nicht disjunkt sind, dann ist das keine Lösung.

13.03.2010, 20:04

mathe760

Auf diesen Beitrag antworten »

Ok zu a):

man kann auf genau $\begin{eqnarray*} \begin{pmatrix} 120 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} 117 \\ 3 \end{pmatrix} \end{eqnarray*}$ verschiedene Weisen zwei disjunkte Tripel auswøhlen. Angenommen alle diese Summen der Tripel seien verschieden, dann gibt es genau $\begin{eqnarray*} 2 \cdot \begin{pmatrix} 120 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} 117 \\ 3 \end{pmatrix} \end{eqnarray*}$ verschiedene Summen. Für eine beliebige dieser summen gilt aber offenbar 3*13579<S<3*97531 also kann S weniger als
251856 verschiedene Werte annehmen.Widerspruch!

zu b)

da würde ich so rangehen, dass ich ein t-Tupel und ein dazu disjuktes k-Tupel auswähle. Dafür gibt es $\begin{eqnarray*} \begin{pmatrix} 120 \\ t \end{pmatrix} \cdot \begin{pmatrix} 120-t \\ k \end{pmatrix} \end{eqnarray*}$
Möglichkeiten. Angenommen alle Summen S sind verschieden, dann gibt es genau $\begin{eqnarray*} 2 \cdot \begin{pmatrix} 120 \\ t \end{pmatrix} \cdot \begin{pmatrix} 120-t \\ k \end{pmatrix} \end{eqnarray*}$ verschiedene Summen.
Nun teile ich die Menge der Summen in 2 Gruppen auf, in eine Gruppe kommen alle Summen die durch addition der Zahlen eines t-Tupels entstehen und in die andere kommen diejenigen die durch addition der Zahlen eines k-Tupels entstehen.
Für die erste Gruppe gilt:
t*13579<S_1<t*97531--> Es gibt weniger als 251856*t verschiedene Summen.
Für die zweite Gruppe analog gibt es analog weniger als 251856*k verschiedene Summen.
Insgesamt gibt es also weniger als (t+k)*251856 verschiedene Summen.
Nun dachte ich mir löse ich die Ungleichung $\begin{eqnarray*} 2 \cdot \begin{pmatrix} 120 \\ t \end{pmatrix} \cdot \begin{pmatrix} 120-t \\ k \end{pmatrix} \geq (t+k)*251856 \end{eqnarray*}$ .
Hierbei halte ich t fest und schaue für welche k die Ungl. erfüllt wird.

Ist das bis hierhin richtig?
Gibt es auch einen eleganteren Weg?

Bis denn mathe760 Wink

13.03.2010, 20:16

Auf diesen Beitrag antworten »

Der Reparaturversuch von a) ist gründlich schiefgegangen. Bist du deine Argumentation wirklich mal Punkt für Punkt durchgegangen, oder hast du nur (wie leider so oft) nur mal oberflächlich drüber weggewischt?

Zu a) gibt es übrigens eine viel einfachere Lösung:

$\begin{eqnarray*} 13579 + 13795 + 13957 = 13975 + 13759 + 13597 \end{eqnarray*}$

Bei b) muss man allerdings etwas gründlicher nachdenken.

13.03.2010, 20:47

mathe760

Auf diesen Beitrag antworten »

Ich weiß leider gerade nicht was an der Formel $\begin{eqnarray*} \begin{pmatrix} 120 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} 117 \\ 3 \end{pmatrix} \end{eqnarray*}$ für die Anzahl an Möglichkeiten für das Auswählen von zwei disjunkten Tripeln, falsch ist.
Ich wähle ja erst 3 aus 120 Zahloen aus und dann unter den übrigen 117 nochmal 3. Was genau ist daran falsch?

Bis denn mathe760 Wink

13.03.2010, 21:28

Auf diesen Beitrag antworten »

Es ist nicht zu sehen, in welcher Weise das Schubfachprinzip bei deinem Ansatz greifen soll. Erläutere das doch mal Punkt für Punkt - ich habe jedenfalls keine Ahnung, wie das funktionieren soll. unglücklich

13.03.2010, 21:58

mathe760

Auf diesen Beitrag antworten »

Ich habe mir das so gedacht, dass ich wie gesagt 2 disjunkte Tripel aus den 120 Zahlen (die 120 ergibt sich aus der Anzahl der Permutationen der Zahl 13579) auswähle. Dies ergibt denke ich $\begin{eqnarray*} \begin{pmatrix} 120 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} 117 \\ 3 \end{pmatrix} \end{eqnarray*}$
Möglichkeiten, oder ist das etwa schon falsch?
Jede dieser Möglichkeiten repräsentiert dann ja 2 Tripel. Nimmt man an, das es keine zwei Summen gibt die gleich sind, so muss es doch genau doppelt so viele verschiedene Summen geben wie es Möglichkeiten gibt (Ich denke mal hier liegt der Fehler??). S liegt in jedem Fall zwischen 3*13579 und 97531*3 kann also nur weniger als 251856 mögliche Werte annehmen verwirrt

??

Bis denn mathe760 Wink

13.03.2010, 22:28

Auf diesen Beitrag antworten »

Ok, du hast so viele Paare von Tripeln, und entsprechend dann so viele Paare $\begin{eqnarray*} (a,b) \end{eqnarray*}$ von Tripelsummen.

Was du brauchst, ist ein Tripelsummenpaar, wo beide Werte gleich sind, d.h. $\begin{eqnarray*} (a,a) \end{eqnarray*}$ . Inwieweit soll dabei das Schubfachprinzip helfen??? Das ist weit und breit nicht zu sehen. unglücklich

Was das Schubfachprinzip (bei entsprechend stimmenden Anzahlen) allenfalls liefern kann ist, dass es zwei gleiche Tripelpaare gibt, d.h. $\begin{eqnarray*} (a,b) = (a',b') \end{eqnarray*}$ . Aber das bringt nichts, aber auch gar nichts in Bezug auf die zwei gesuchten disjunkten Tripel. Du kennst vermutlich die Indianerweisheit: "Wenn Du entdeckst, dass Du ein totes Pferd reitest, steig ab!" - das solltest du im Fall deiner hartnäckig verfolgten Schubfachlösung wirklich tun.

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

Idee zu b), basierend auf der oben von mir angegebenen Lösung zu a) (also für m=6):

Zunächst mal klappt es für alle ungeraden $\begin{eqnarray*} m \end{eqnarray*}$ nicht, da die Gesamtsumme der $\begin{eqnarray*} m \end{eqnarray*}$ Werte dann ungerade ist und somit nicht in zwei gleichgroße Teilsummen aufgeteilt werden kann.

Im folgenden geht es also nur noch um gerade Anzahlen $\begin{eqnarray*} m \end{eqnarray*}$ . Es ist

$\begin{eqnarray*} abcde + abdec + abecd = abedc + abdce + abced \qquad (*) \end{eqnarray*}$ ,

das gilt für alle $\begin{eqnarray*} 5\cdot 4 = 20 \end{eqnarray*}$ Auswahlen $\begin{eqnarray*} ab \in \{ 13, 15, \ldots, 59, 79 \} \end{eqnarray*}$ . Damit hat man schon mal b) für alle Fälle $\begin{eqnarray*} m=6k \end{eqnarray*}$ mit $\begin{eqnarray*} k=1,2,\ldots,20 \end{eqnarray*}$ positiv beantwortet.

Weiterhin gilt

$\begin{eqnarray*} 13579 + 13975 = 13759 + 13795 \end{eqnarray*}$
$\begin{eqnarray*} 19357 + 19753 = 19537 + 19573 \end{eqnarray*}$

also kann man eine oder beide dieser Lösungen mit einer beliebigen Anzahl der Lösungen (*) kombinieren, wobei allerdings bei letzteren offenbar die Fälle $\begin{eqnarray*} ab=13 \end{eqnarray*}$ bzw. $\begin{eqnarray*} ab=19 \end{eqnarray*}$ ausgeschlossen werden müssen. Damit sind nun auch die Fälle $\begin{eqnarray*} m=6k+4 \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,\ldots,19 \end{eqnarray*}$ sowie $\begin{eqnarray*} m=6k+8 \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,\ldots,18 \end{eqnarray*}$ in b) positiv beantwortet.

Für $\begin{eqnarray*} m=2 \end{eqnarray*}$ gibt es keine passende Auswahl, also negative Antwort. Welche Anzahlen $\begin{eqnarray*} m \end{eqnarray*}$ im Bereich bis 120 sind nun durch die bisherigen Betrachtungen noch nicht erfasst, d.h. harren noch einer Antwort für b) ?

14.03.2010, 14:24

mathe760

Auf diesen Beitrag antworten »

Vielen Dank Arthur Dent jetzt wird das ganze viel klarer.
Also mit deiner Methode bleibt keine Gerade Zahl mehr aus. (Wenn man will dann wurde 0 dadurch nicht erfasst, aber es ist ja Unsinn zu sagen man wählt 0 Zahlen aus...)
Kombinatorik und ähnliches ist im Augenblick nicht so mein Ding unglücklich

Bis denn mathe760 Wink

Neue Frage »

Antworten »

Zahlen aus einer Menge auswählen - gleiche Summen

Verwandte Themen