Känguru-Aufgabe

18.03.2006, 10:27

ostfriese

Auf diesen Beitrag antworten »

Känguru-Aufgabe

Upps, pardon, hiermit bin ich in den falschen Thread geraten. Vielleicht kann ein Moderator, der sich im Matheboard besser auskennt als ich, diesen Beitrag samt zugehörigen Antworten an einen geeigneteren Ort verschieben!?

Eine Frage, für die ich eure gesammelte Intelligenz brauche (meine Kollegen Mathelehrer und ich konnten zusammen nicht genug davon aufbringen, um das Problem zu lösen, woraus entweder folgt, dass sich Intelligenz bei der Addition nicht akkumulativ verhält -- was wir ja auch von der Lichtgeschwindigkeit kennen -- oder dass wir einzeln zu unintelligent sind, um gemeinsam die Lösungsschwelle zu überwinden...^^):

Sie betrifft die Känguru-Aufgabe Nr. 27 aus Klassenstufe 11-13.

Wir haben die Menge {1,2,3,4,5,6,7,8,9,10,11,12} und fragen: Wie groß ist die Anzahl jener Teilmengen, bei denen die Summe aus kleinstem und größtem Element 13 ergibt?

Ich weiß, dass die Antwort (2^12-1):3 lauten muss, kann mir aber keinen Reim darauf machen, warum genau jede dritte nicht-leere Teilmenge die geforderte Eigenschaft hat. Gibt´s dafür eine einfache logische Erklärung?

Allgemein also: Beweise, dass für die Anzahl Z(n) derjenigen Teilmengen einer n-elementigen Menge M aufeinanderfolgender ganzer Zahlen, bei denen die Summe aus größtem und kleinstem Element gleich der Summe aus dem größten und dem kleinsten Element von M ist, gilt:
Z(n) = (2^n-1):3 für gerade n
Z(n) = (2^n-2):3 für ungerade n

18.03.2006, 10:56

AD

Auf diesen Beitrag antworten »

Da das evtl. eine aktuelle Wettbewerbsaufgabe ist, schließe ich hier mal prophylaktisch. Sollte es eine ältere Aufgabe sein, kann ja ein kundiger Moderator wieder öffnen.

18.03.2006, 11:16

AD

Auf diesen Beitrag antworten »

Ok, habe gerade gelesen, dass der Wettbewerb einheitlich am 16.03.2006 stattfand. Darum wieder geöffnet.

$\begin{eqnarray*} \frac{2^n-1}{3} \end{eqnarray*}$ für gerade $\begin{eqnarray*} n \end{eqnarray*}$ ist übrigens falsch, wie schon das Beispiel $\begin{eqnarray*} n=4 \end{eqnarray*}$ zeigt.

EDIT: Und überhaupt:

Zitat:

Original von ostfriese
Allgemein also: Beweise, dass für die Anzahl Z(n) derjenigen Teilmengen einer n-elementigen Menge M aufeinanderfolgender ganzer Zahlen, bei denen die Summe aus größtem und kleinstem Element gleich der Summe aus dem größten und dem kleinsten Element von M ist,

Da bist du generell schwer im Irrtum: Dieses Problem ist nicht verschiebungsinvariant - das klappt höchstens, wenn es um eine andere Fragestellung bzgl.Teilmengen mit einer fixen Mächtigkeit geht!

18.03.2006, 11:53

ostfriese

Auf diesen Beitrag antworten »

Das Beispiel n=4 widerlegt meine Behauptung nicht:

Von den 16 Teilmengen erfüllen (2^4-1):3 die Bedingung:

{1,2,3,4}
{1,2,4}
{1,3,4}
{1,4}
{2,3}

Und eigentlich müssten sich die Mengen auch verschieben lassen. Aber darum geht es mir nicht hauptsächlich. Wahrscheinlich wäre ein Beweis mittels Induktion auch gar nicht so schwierig. Aber da dies eine Känguru-Aufgabe war, muss es einen einfacheren Weg geben, sich den Zusammenhang plausibel zu machen.

18.03.2006, 12:03

AD

Auf diesen Beitrag antworten »

Ach ok, ich hatte mich verlesen - ich dachte, es geht um die Summe aller Teilmengenelemente...

18.03.2006, 12:03

ostfriese

Auf diesen Beitrag antworten »

Sorry, beim ersten Versuch schien das Abschicken meiner Antwort nicht geklappt zu haben. Ich muss mich wohl erst an die Besonderheiten dieses Forums gewöhnen...

Anzeige

18.03.2006, 12:12

AD

Auf diesen Beitrag antworten »

Gut, nachdem ich die Aufgabe richtig gelesen habe: Die Anzahlformell beweist man einfach durch vollständige Induktion. Im Induktionsschritt benutzt man die für $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ gültige Rekursion $\begin{eqnarray*} Z(n) = Z(n-2)+2^{n-2} \end{eqnarray*}$ , die man natürlich passend begründen muss.

18.03.2006, 12:22

ostfriese

Auf diesen Beitrag antworten »

Ja, der Beweis ist vermutlich gar nicht schwierig, aber dafür ist ja beim Känguru-Wettbewerb (30 Aufgaben in 75 Minuten) keine Zeit.

Also sollte es einen Weg geben, sich das Resultat irgendwie plausibel zu machen. Warum gerade jede dritte nicht-leere Teilmenge (bei geradem n)??

18.03.2006, 12:31

AD

Auf diesen Beitrag antworten »

Naja, zum Aufschreiben des Beweises mag keine Zeit sein, aber zum Überlegen dieser Rekursion schon:

Wie kommt man zu Summe n+1 ?

1.Fall: Die 1 ist in der Teilmenge. Dann muss auch die n drin sein, und der Rest ist dann beliebig. Nun gibt es von { 2,...,n-1 } genau $\begin{eqnarray*} 2^{n-2} \end{eqnarray*}$ Teilmengen.

2.Fall: Die 1 ist nicht in der Teilmenge drin. Dann darf auch die n nicht drin sein! Bleiben die Teilmengen von { 2,...,n-1 } zu zählen, wo Minimum+Maximum gerade n+1 ergibt, und das sind genau $\begin{eqnarray*} Z(n-2) \end{eqnarray*}$ .

18.03.2006, 16:34

ostfriese

Auf diesen Beitrag antworten »

Schon verstanden. Augenzwinkern

Augenzwinkern

Man wird sich während des Wettbewerbs ohnehin nicht damit plagen, wie ein Beweis zu führen wäre. Aber mich wundert, dass die Aufgabenautoren den gehetzten Teilnehmern tatsächlich zumuten, die Formel induktiv zu finden. Dazu muss man ja schon mindestens die Beispiele n=2 und n=4 bemühen und danach noch verifizieren, dass die entsprechende Vermutung für n=12 auf eine tatsächlich vorhandene Antwortmöglichkeit führt. Und zuallererst muss man sich von der Hoffnung verabschieden, dass es eine gedankliche Abkürzung gibt. Mich wundert jedenfalls nicht, dass an meiner Schule kein Schüler bei Nr. 27 das richtige Kreuz gesetzt hat, die meisten haben die Aufgabe ausgelassen...

18.03.2006, 18:22

AD

Auf diesen Beitrag antworten »

Dazu sind solche Wettbewerbe da, den Schülern auch schwierigere Aufgaben zuzumuten. Wenn deutschlandweit zigtausende Schüler volle Punktzahl haben würden, wo wäre dann der Wettbewerbsgedanke geblieben?

18.03.2006, 22:50

Thales

Auf diesen Beitrag antworten »

Also ich habe mir das am Donnerstag elementarer überlegt:
Man kann 13 als Summe zweier Mengenelemente nur so darstellen:
$\begin{eqnarray*} 13 = 12+1 = 11+2 = 10+3 = 9+4 = 8+5 = 7+6 \end{eqnarray*}$
Jedes Element, das zwischen diesen diesen Summanden liegt, kann in einer in der Aufgabe geforderten Teilmenge mit dem einen Summanden als größtes und dem anderen als kleinstes Element enthalten sein oder nicht, also gibt es je nach der Teilmenge "zugrundegelegter" Summandendarstellung $\begin{eqnarray*} 2^{10} \end{eqnarray*}$ , $\begin{eqnarray*} 2^8 \end{eqnarray*}$ , $\begin{eqnarray*} 2^6 \end{eqnarray*}$ , $\begin{eqnarray*} 2^4 \end{eqnarray*}$ , $\begin{eqnarray*} 2^2 \end{eqnarray*}$ oder $\begin{eqnarray*} 2^0 \end{eqnarray*}$ Teilmengen. Die Summe dieser Werte ist 1365 und gleich der Anzahl der gesuchten Teilmengen.

19.03.2006, 10:09

Mathespezialschüler

Auf diesen Beitrag antworten »

Und so wie Thales werden es wohl so ziemlich alle anderen, die die Aufgabe richtig gelöst haben, auch gemacht haben. Ich hab es auch so gemacht und das schafft man in ca. 1 Minute.

Gruß MSS

19.03.2006, 10:42

AD

Auf diesen Beitrag antworten »

Ich seh keinen Unterschied zu meinem Zugang:

$\begin{eqnarray*} Z(12) = 2^{10}+Z(10) = \cdots = 2^{10}+2^8+\cdots+2^2+1 = \frac{2^{12}-1}{3} \end{eqnarray*}$

mit $\begin{eqnarray*} 1=Z(2) \end{eqnarray*}$ . Das läuft natürlich alles im Kopf ab.

P.S.: Wieso hatten eigentlich so wenige von euch letztes Jahr volle Punktzahl? Ist doch nur Multiple-Choice, muss also nicht mal begründet werden. Big Laugh

Big Laugh

20.03.2006, 09:10

Sciencefreak

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
P.S.: Wieso hatten eigentlich so wenige von euch letztes Jahr volle Punktzahl? Ist doch nur Multiple-Choice, muss also nicht mal begründet werden. Big Laugh

Big Laugh

Ich hatte letztes Jahr 146,25 Punkte, also hatte ich eine 3 Punkteaufgabe fasch. Das dumme ist, ich hatte sie richtig gelöst, aber das falsche gelesen.
Es ging in etwas darum, dass es im Januar 5 Montage und 5 Mittwochs gibt und man sollte den Wochentag vom 1.Januar bestimmen.
Ich habe mal so frei heraus den vom 1.Februar angekreuzt.
Also man muss auch richtig lesen können, was unter Zeitdruck nicht so leicht ist. Ich hoffe ich habe dieses Jahr alles richtig gemacht.

20.03.2006, 14:59

AD

Auf diesen Beitrag antworten »

Das P.S. war von mir auch mehr als Seitenhieb auf großspurige Aussagen à la "das schafft man in ca. 1 Minute" gedacht. smile

smile

Übrigens: Ich hab mir mal die Ergebnis-Statistik der Klassenstufe 11-13 vom Vorjahr angesehen:

Beim reinen "Raten" aller 30 Antworten kommt man ja bei der gewählten Konstruktion der Strafpunkte für falsche Antworten genau beim Erwartungswert 30 Punkte heraus, also genauso viel, als wenn man gar nichts angekreuzt hätte. Angesichts dessen finde ich den Anteil von ungefähr einem Drittel aller Teilnehmer, die weniger als 30 Punkte hatten, erschreckend hoch.

20.03.2006, 15:21

Mathespezialschüler

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Das P.S. war von mir auch mehr als Seitenhieb auf großspurige Aussagen à la "das schafft man in ca. 1 Minute" gedacht. smile

smile

Hmm, das war ja im Prinzip auch nur auf die Aufgabe bezogen. Die Aussage war eigentlich ernst gemeint, aber natürlich gab es auch Aufgaben, für die man etwas oder sogar wesentlich länger brauchte. Sollte keine Angeberei o.Ä. sein.

Gruß MSS

20.03.2006, 17:35

Sciencefreak

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Beim reinen "Raten" aller 30 Antworten kommt man ja bei der gewählten Konstruktion der Strafpunkte für falsche Antworten genau beim Erwartungswert 30 Punkte heraus, also genauso viel, als wenn man gar nichts angekreuzt hätte. Angesichts dessen finde ich den Anteil von ungefähr einem Drittel aller Teilnehmer, die weniger als 30 Punkte hatten, erschreckend hoch.

Es gibt selbst an meiner Schule Leute, die der Meinung sind Freistunden sind was schönes machen wir einfach mal mit und kreuzen dann irgendein Muster an. Das mit einem Drittel ist wirklich ganz schön arg, so könnte man vielleicht 5% oder so erklären.

Edit:Wo hast du die Zahl mit einem Dritel her?
Ich komme bei meinen Rechnungen auf etwa ein Siebtzehntel und das ist doch ein kleiner unterschied

22.03.2006, 19:11

AD

Auf diesen Beitrag antworten »

Argghh, ich bin in der Zeile verrutscht. Dann muss ich mich wohl bei der gesamten Teilnehmerschaft entschuldigen. Und dem betreffenden Siebzehntel wünsche ich das nächste Mal (so sie denn dabei sind): Mehr Glück beim Raten! Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »