Bundeswettbewerb Mathematik 2011 - Aufgabe 2

Neue Frage »

Anonymus-Psi Auf diesen Beitrag antworten »
Bundeswettbewerb Mathematik 2011 - Aufgabe 2
Meine Frage:
Da ja nun der Einsendeschluss hinter uns liegt, möchte ich dann doch einmal fragen, ob denn auch andere diese Lösungen für die verallgemeinerte Aufgabenstellung gefunden haben:

2 Plätze: 2 Anordnungen
4 Plätze: 9 Anordnungen
6 Plätze: 20 Anordnungen
8 Plätze: 49 Anordnungen
10 Plätze: 125 Anordnungen
12 Plätze: 324 Anordnungen
14 Plätze: 845 Anordnungen
16 Plätze: 2209 Anordnungen


Meine Ideen:
s.o.
chris95 Auf diesen Beitrag antworten »

Kannst du mal bitte die Aufgabenstellung schreiben bzw. einen Link zur Aufgaben angeben. Wäre cool smile
MathPhil Auf diesen Beitrag antworten »
Aufgabe 2
Aufgabe 2
An einem runden Tisch sitzen 16 Kinder. Nach der Pause setzen
sie sich wieder an den Tisch. Dabei stellen sie fest: Jedes Kind
sitzt entweder auf seinem ursprünglichen Platz oder auf einem
der beiden benachbarten Plätze.
Wie viele Sitzordnungen sind auf diese Weise nach der Pause
möglich?


Quelle:
http://www.bundeswettbewerb-mathematik.d...nblatt_11_1.pdf
PeterH Auf diesen Beitrag antworten »

Ich habe die gleiche Lösung raus (ich bin mir auch ziemliche sicher, dass das Ergebnis stimmt; habe mich schon mit "Profis" ausgetaucht). Wie bist du darauf gekommen?
Blauerschneeball Auf diesen Beitrag antworten »

Ich habe auch die gleiche Lösung smile allerdings nicht korrekt mathematisch bewiesen...

Ich habe die Möglichkeiten für 3, 4, 5, 6, 7 und 8 Stühle ausprobiert, geschaut, wie oft eine Person links neben ihrem Platz, auf dem gleichen Platz und rechts neben ihrem Platz sitzt. Da habe ich dann eine Regelmäßigkeit festgestellt: Für die Möglichkeit "rechts neben dem Platz" muss man die Möglichkeiten für "rechts neben dem Platz" von den zwei vorherigen Stuhlanzahlen addieren und eins abziehen, für "links neben dem Platz" das gleiche und für "gleicher Platz" muss man die Möglichkeiten für "gleicher Platz" von den zwei vorherigen Stuhlanzahlen addieren. UNd wenn man nun diese neuen Möglichkeiten für "links neben dem Stuhl", "rechts neben dem Stuhl" und "gleicher Stuhl" addiert kommt man auf die Gesamtmöglichkeiten. Bei 16 Stühlen sind das dann auch 2209 Möglichkeiten.

Denkt ihr die Aufgabe zähl bei mir als richtig gelöst? Das Ergebnis stimmt, aber korrekt mathematisch bewiesen ist es leider nicht. Wie habt ihr es denn bewiesen?
PeterH Auf diesen Beitrag antworten »

Dann werde ich wohl mal meinen "Monsterbeweis" für Aufgabe 2 online stellen; allerdings die optimierte Form. Ich selbst halte ihn nicht für besonders schön und ich habe zum Teil Vorgaben genutzt, bei denen ich mir nicht ganz sicher bin. Dennoch, hier ist er als Pdf-Datei zum Downloaden:

de.swoopshare.com/get/d/8fc34962c2be5308bcefbf8fa98a0178/800c0e0601eca754832481610781e8dd/1299489651/e165544e8314ff99e8ae86f2d49c4aa3/Aufgabe+2.pdf?queue

Wer Lust hat ihn sich mal durchzusehen: Bitte!

Mfg PeterH
 
 
Blauerschneeball Auf diesen Beitrag antworten »

Ich schau ihn mir mal an smile
Blauerschneeball Auf diesen Beitrag antworten »

Ok, es ist wirklich ein Monsterbeweis ^^ ich bin grad nicht in der Verfassung, ihn genau durchzulesen Big Laugh aber mir ist nur ein kleiner Fehler am Anfang aufgefallen, da schreibst du: Es ist eine Anzahl von 2.207 verschiedenen Sitzordnungen nach der Pause möglich.
Und zum Schluss kommst du dann auf die Richtigen 2209 Sitzordnungen... ich hoff mal für dich dass du den Bundeswettbewerbleuten 2.209 Sitzordnungen geschickt hast Augenzwinkern
PeterH Auf diesen Beitrag antworten »

Oh tatsächlich glaube ich, dass ich das nicht gemacht habe unglücklich
Ich habe zunächst einen fehlerhaften Lösungsansatz abgeschickt, in dem von 2207 Möglichkeiten die Rede ist. Diesen habe ich dann verbessert und die Verbesserung eingeschickt, ohne das am Anfang weggemacht zu haben. Meinst du das wird in die Bewertung mit einfließen? Irgendwie wäre das doch lächerlich, oder?
René Gruber Auf diesen Beitrag antworten »

Es ersetzt keinen Beweis, und ist nach Erkennung des Zusammenhangs zu Fibonacci auch keine Kunst mehr - aber dennoch hier mal als Ergänzung eine explizite Formel der gesuchten Anzahl Sitzordnungen:

,

allerdings erst für in dieser Form gültig.
Mystic Auf diesen Beitrag antworten »

Denken wir uns die Kinder mit den Zahlen 1 bis n durchnummeriert, so stellt sich für mich das Ganze so dar, dass es offensichtlich nur die neuen Sitzodnungen gibt, wo

1. gegenüber der alten Sitzordnung alle um einen Platz nach links bzw. alle um einen Platz nach rechts rücken, d.h., das sind für konstant 2 Möglichkeiten
2. gegenüber der alten Sitzordnung jeder auf seinem alten Platz sitzt oder mit einem seiner 2 Nachbarn den Platz getauscht hat

Sei die Gesamtanzahl der Möglichkeiten nach Punkt 2 und die Anzahl der Möglichkeiten nach Punkt 2, wo die Kinder 1 und n nicht die Plätze getauscht haben, dann gilt offenbar



denn entweder bleibt 1 fest oder tauscht mit 2 den Platz... Ferner gilt



denn wieder bleibt 1 entweder fest oder tauscht mit 2 oder n den Platz... Daraus folgt aber sofort auch



Der Rest ist dann nur mehr "plain sailing" und führt auf die von René angegebene Formel für die Gesamtanzahl ... Für eine manuelle Rechnung würde ich allerdings die direkte Verwendung der Rekursion mit den Startwerten und klar vorziehen... Augenzwinkern
xparet0209 Auf diesen Beitrag antworten »

Hi
ich habe ebenfalls 2209 als Lösung. Jedoch hatte ich anfangs einen ziemlich umständlichen Beweis.
Mich würde nun interessieren, ob das Vorgehen als solches aktzeptabel gewesen wäre...
Hier das PDF-Doocument: [attach]19015[/attach]
Mystic Auf diesen Beitrag antworten »

Was mich betrifft, so muss ich leider sagen, es ist Sonntag und zugleich ein herrlicher Sonnentag draußen, sodass ich keine Lust verspüre, mir 6 Seiten zu einem Problem durchzulesen, wo aus meiner Sicht (s.o.) weniger als eine Seite gereicht hätte... Zumal die Frage, "ob das Vorgehen als solches akzeptabel gewesen wäre" sich eigentlich eh von selbst beantwortet: Ein Denkfehler führt i.d.R. auf ein falsches Ergebnis... Ausnahmen, die es natürlich auch gibt, bestätigen wie immer nur die Regel...Womit ich aber nicht kleinreden will, dass du immerhin am Ende - wenn auch offenbar ziemlich umständlich - auf das richtige Ergebnis gekommen bist... Freude

Sorry, ist jetzt nur meine Meinung dazu, vielleicht findet sich ja noch jemand, der das durchliest... Wink
rslz Auf diesen Beitrag antworten »

Ich habe eine, meiner Meinung nach sehr elementare Lösung gefunden, ich werde ihn hier einmal kurz skizzieren:

Gesucht: Gesamtsumme an Sitzordnungen bei n Kindern (n>2)

0. Vorüberlegung
Bevor die Kinder in die Pause stürmen sollen diese entgegen den Uhrzeigersinn durchnummeriert werden. Außerdem sollen sie nach der Pause nicht alle auf einmal, sondern wohlgeordnet entsprechend der Nummer in den Raum treten und sich hinsetzten. Dabei ändert sich die Lösungsmenge nicht.

1. Zeige die 2 Sonderfälle
-> alle Kinder rutschen einen Platz nach rechts oder links

2. Nun zerlege man
wobei die "2" die zwei Sonderfälle repräsentiert,
die Anzahl der restlichen Permutationen, in denen sich das erste Kind wieder auf den selben Platz setzt,
die, in denen es nach einen Platz nach links und
die, in denen es einen Platz nach rechts "rutscht".

Offensichtlich ist
, womit sich ergibt.

3. Überlegungen n->n+1
Für alle Permutationen in und gilt, dass nie 2 aufeinanderfolgende Kinder in dieselbe Richtung rutschen. Infolgedessen hat das letzte Kind nur 2 Möglichkeiten:
1. sich wieder auf denselben Platz setzen
2. einen nach links
Wie wirkt sich nun die Entscheidung des n-ten Kindes auf die Auswahlmöglichkeiten des n+1-ten aus?
nun soll dafür stehen, dass sich ein Kind wieder auf denselben Platz setzt, und dass es einen Platz nach links bzw. rechts rutscht.
Es ergibt sich augenscheinlich:


Was uns nun interessiert ist die Summe der und des letzten Kindes, da dieses ja wie bereits erwähnt innerhalb von und nie nach rechts rutscht.
Es ergibt sich:


welches man mit etwas umformen auf folgende Form bringen kann


4. Endbeweis
Nun ist die Relation zur Fibonnacifollge gezeigt.
Da und ist verhalten sich und logischerweise auch wie Fibonnacifolgen.
Für die Startwerte für und für ergibt sich und , wobei das n-te Glied der Fibonnacifolge ist.
Schlussendlich folgt:
womit sich für der Wer ergibt.
kleinerwolf Auf diesen Beitrag antworten »

Was meinst du bei:

3. Überlegungen n->n+1
Für alle Permutationen in und gilt, dass nie 2 aufeinanderfolgende Kinder in dieselbe Richtung rutschen. Infolgedessen hat das letzte Kind nur 2 Möglichkeiten:
1. sich wieder auf denselben Platz setzen
2. einen nach links
Wie wirkt sich nun die Entscheidung des n-ten Kindes auf die Auswahlmöglichkeiten des n+1-ten aus?
nun soll dafür stehen, dass sich ein Kind wieder auf denselben Platz setzt, und dass es einen Platz nach links bzw. rechts rutscht.
Es ergibt sich augenscheinlich:


mit dem
n n+1
O O und R
R L
L O und R ??

Der Rest ist bisher klar, aber diese Stelle verstehe ich nicht...

Gruß
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »