Zweitausendundvier [gelöst]
Neue Frage »

10.02.2004, 18:04 Marcyman Auf diesen Beitrag antworten »
Zweitausendundvier [gelöst]
Ich poste mal hier eine Aufgabe aus Omega, eine Sonderausgabe zur Mathematik von Spektrum der Wissenschaft, die einige Rätsel zu bieten hat. Eines davon lautet:

Z W E I T A U S E N D U N D V
W E I T A U S E N D U N D V I
E I T A U S E N D U N D V I E
I T A U S E N D U N D V I E R

(Das ganze soll ein quadratisches Feld mit 4*15 Kästchen sein, in jedem Kästchen befindet sich ein Buchstabe.)

Wie viele Möglichkeiten gibt es, von Z nach R zu kommen. Regeln: Man darf sich nur nach rechts und nach unten bewegen und der Ablauf muss dergestalt sein, dass man jedes mal ZWEITAUSENDUNDVIER durchläuft.

Habe auch ein Ergebnis: 131100 Möglichkeiten. Allerdings habe ich recht umständlich gerechnet und bin mir gar nicht sicher, ob's richtig ist.
10.02.2004, 18:39 Steve_FL Auf diesen Beitrag antworten »

hm...ich glaube es sind:


das k sollte eigentlich auch hochgestellt sein, aber das klappt nicht...keine Ahnung wieso...

Jetzt klappts :-) Du musst solche Terme in {} einschliessen, da Mimetex ja ansonsten nach Punkt vor Strich arbeitet. Gruß, Thomas

für n = 15
das wären dann 21'523'360

aber ob das stimmen kann, weiss ich nicht...
ich hab von hinten angefangen und hab mir überlegt, wenn ich bei der hintersten Spalte runter geh, ist das 1 Möglichkeit. Wenn ich beim 2. Hintersten runter geh, hab ich noch 3 Möglichkeiten.
beim 3. Hintersten sind noch 3*3 und so weiter...
also 3^0 + 3^1 + 3^2 etc...
und so weiter, bis wir alle 15 Buchstaben durch haben.

mfg
10.02.2004, 19:05 fALK dELUXE Auf diesen Beitrag antworten »

Ich versuch es mal als binären Baum darzustellen, denn es gibt ja von einer Stelle aus nur 2 Wege, wie man weiter gehen kann. Das Wort hat 18 Buchstaben.

code: 
1:
2:
3:
4:
5:
6:
7:

                	       
                                     Z
                 W                                  W
        E                 E                E                 E      
    I        I        I        I        I        I        I        I        
                                    ...


Man sieht den rapiden Anstieg und kann, da sich die Anzahl der Möglichkeiten immer verdoppelt von ausgehen.
Da das Wort aus 18 Buchstaben besteht ist n =18 und somit existieren wohl Möglichkeiten, dieses Wort zu bilden.

2^17 = 131072

**EDIT**

Sorry, ist natürlich nicht richtig, weil es ja an dem unteren und rechten Rand keine zwei Möglichkeiten gibt weiter zu gehen. D. h. das Ergebnis ist wahrscheinlich kleiner als 2^17.
10.02.2004, 19:19 koller74 Auf diesen Beitrag antworten »

@ Steve_FL: Wenn man bei der drittletzten Zahl runtergeht sind es doch nur 10 Möglichkeiten und nicht 3^3=27 oder?

Meiner Meinung nach gibts also pro Spalte von hinten her gesehen (i*(i+1))/2 Möglichkeiten, das über alle Spalten summiert ergibt 680 Möglichkeiten. Was natürlich erheblich von den bis jetzt vorgestellten Lösungen abweicht. verwirrt
(Ist die Frage wer jetzt den Denkfehler gemacht hat? - Da ich bei so Aufgaben meistens irgendwas übersehe) Augenzwinkern

Grüsse, Koller
10.02.2004, 19:31 Anirahtak Auf diesen Beitrag antworten »

Hätte noch einen anderen Lösungsansatz:

Um von Z nach R zugelangen muss man 14 Schritte nach rechts und drei Schritte nach unten gehen.

Die Reihenfolge der Schritte nach oben und rechts ist egal.

Gesucht ist also der Anzahl x der Möglichkeiten drei Schritte nach unten bzw. 14 nach rechts auf die 17 Schritte die nötig sind zu verteilen:
10.02.2004, 19:37 koller74 Auf diesen Beitrag antworten »

@ Anirahtak: Danke für die Bestätigung, wobei Dein Ansatz natürlich noch besser ist (weil logischer)
 Anzeige 
 
10.02.2004, 19:48 Marcyman Auf diesen Beitrag antworten »

Ich sag' mal meine Überlegung: Die Analogie zum Baumdiagramm hab ich auch genutzt, nur dass ich eben das Fehlen einiger Äste mitberückstigt habe, oder zumindest versucht.

Also, von Z nach I hat man 2^3 Möglichkeiten wie das Baumdiagramm von oben schon zeigt. Normalerweise sollten jetzt nochmal 2^3 - also insgesamt 2^4 - Möglichkeiten dazukommen, wenn man davon ausgeht, dass von jedem Ast wieder zwei neue herausragen. Nur fällt wegen der Beschaffenheit des Feldes eine Möglichkeit weg: Wenn von Z auf das unterste I gelangt ist, gibt es nur noch eine Möglichgkeit weiter zumachen. Also kommen - statt 2^3 - 2^3-1 Möglichkeiten hinzu. Beim nächsten Schritt (von T auf A), würde es sich um ein normales Baumdiagramm handeln, kämen 2^4 Möglichkeiten hinzu. Aber wieder fällt eine weg (wenn man sich entscheidet, am untersten T entlang zu gehen) und zudem muss man berücksichtigen, dass aus dem Ast, der ein Schritt zuvor, weggefallen ist, eigentlich jetzt zwei Äste wären, die jetzt aber dann fehlen. Also 2^1 Möglichkeiten weniger. Also haben wir insgeamt um von Z nach A zukommen 2^3+2^3-1+2^4-2^1-1 = 28 Möglichkeiten. Soweit richtig? Am Ende muss man nochmal einige Äste eines normalen Baumdiagrammes absägen (vom letzten V gibt es z.B zwei - statt einen - Äste weniger.)

Habe übrigens selber gerade einen kleinen Fehler bei meiner Rechnung entdeckt, der aber am Grundgedanken nichts ändert. Werde den Rechenfehler so schnell wie möglich beheben.
10.02.2004, 19:50 Marcyman Auf diesen Beitrag antworten »

Mh ok, dann rechne ich lieber erst, wenn sich jmd. meinen Ansatz mal angeschaut hat...

Komme auf 196614 Möglichkeiten, allerdings glaube ich nicht, das meine Rechnung richtig ist, denn eigentlich habe ich die Anzahl aller Äste berechnet, und nicht die Anzahl der möglichen Wege.
10.02.2004, 21:23 Marcyman Auf diesen Beitrag antworten »

Habe gerade die Lösung bei www.spektrum.de/omega gefunden: 680 stimmt!
10.02.2004, 21:57 Steve_FL Auf diesen Beitrag antworten »

och mist... Augenzwinkern

@falkDeluxe:
die Idee hatte ich auch mal...hab ich dann aber wieder verworfen, aus dem gleichen Grund wie du Big Laugh

mfg
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Sonstiges » Rätsel & Wettbewerbe » Zweitausendundvier [gelöst]