Abrakadabra: Noch eine hübsche Aufgabe :-)

Freizeit & Hobby Rätsel
#1

Hallo Rätsel- und Denkspielfreude,

nachdem die meiner Meinung nach eher „zweifelhafte“ Aufgabe von zwei Threads weiter unten ja gelöst wurde, möchte ich Euch noch mit einer anderen aus diesem Test erfreuen, einer, die ich sehr reizvoll finde:

Auf wie viele verschiedene Weisen läßt sich im unten stehenden Diagramm das Wort ABRAKADABRA lesen? Die blauen Buchstaben zeigen ein Beispiel von vielen. [blau = eingeklammert]

 (A)
~
 R (B) R
~
 (K)(A)(R) A K
~
 D (A) K A K A D
~
 B A (D) A K A D A B
~
 A R (B)(A) D A D A B R A
~
 A (R) B A D A B R A
~
 (A) R B A B R A
~
 A R B R A
~
 A R A
~
 A

Die Lösung verrate ich erst später.

Viel Spaß!

Gruß
Martin

Hier nochmals das Schema ohne Klammern (falls es sich jemand ausdrucken möchte):
~
 A 
~
 R B R
~
 K A R A K
~
 D A K A K A D
~
 B A D A K A D A B
~
 A R B A D A D A B R A
~
 A R B A D A B R A
~
 A R B A B R A
~
 A R B R A
~
 A R A
~
 A
#2

Hallo,

zwei fragen dazu:
Ist auch Diagonal erlaubt oder nur wag- und senkrecht?
Wenn ja, darf derselbe Buchstabe auch 2mal vorkommen?

Gruß
Tom

#3

Hi Tom,

beide Fragen erübrigen sich!

Warum? Bitte selbst herausfinden :wink:!

Gruß
Martin

PS: Hier für alle, denen es mit Kästchen besser gefällt:

 +-----+
 | |
 | A |
 | |
 +-----+-----+-----+
 | | | |
 | R | B | R |
 | | | |
 +-----+-----+-----+-----+-----+
 | | | | | |
 | K | A | R | A | K |
 | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | |
 | D | A | K | A | K | A | D |
 | | | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | | | |
 | B | A | D | A | K | A | D | A | B |
 | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | | | |
| A | R | B | A | D | A | D | A | B | R | A |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | | | |
 | A | R | B | A | D | A | B | R | A |
 | | | | | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | |
 | A | R | B | A | B | R | A |
 | | | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+
 | | | | | |
 | A | R | B | R | A |
 | | | | | |
 +-----+-----+-----+-----+-----+
 | | | |
 | A | R | A |
 | | | |
 +-----+-----+-----+
 | |
 | A |
 | |
 +-----+
#4

beide Fragen erübrigen sich!

Warum? Bitte selbst herausfinden :wink:!

Hallo Martin!

Das mag sich mir nicht erschliessen, weil nämlich die von mir markierte Lösung nicht legal ist, wenn diagonal verboten ist, oder doch? (und wenn diagonal erlaubt ist, dann kann ich natürlich auch Buchstaben wiederverwenden, nur mit horizontal/vertikal stell sich die Frage natürlich nicht, aber das hat ja Tom auch schon festgestellt)

 +-----+
 | |
 | A |
 | |
 +-----+-----+-----+
 | | | |
 | R | **B** | **R** |
 | | | |
 +-----+-----+-----+-----+-----+
 | | | | | |
 | K | **A** | R | **A** | **K** |
 | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | |
 | D | A | K | A | K | **A** | **D** |
 | | | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | | | |
 | B | A | D | A | K | A | D | **A** | **B** |
 | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | | | | | | |
| A | R | B | A | D | A | D | A | B | **R** | **A** |
| | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | | | |
 | A | R | B | A | D | A | B | R | A |
 | | | | | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | | | | | | | |
 | A | R | B | A | B | R | A |
 | | | | | | | |
 +-----+-----+-----+-----+-----+-----+-----+
 | | | | | |
 | A | R | B | R | A |
 | | | | | |
 +-----+-----+-----+-----+-----+
 | | | |
 | A | R | A |
 | | | |
 +-----+-----+-----+
 | |
 | A |
 | |
 +-----+
#5

Das mag sich mir nicht erschliessen, weil nämlich die von mir
markierte Lösung nicht legal ist, wenn diagonal verboten ist,
oder doch?

Hi,

OK, wie Du gezeigt hast, gibt es doch Wege mit einem diagonalen Stück. Ich habe geglaubt, daß es keine gibt, daher diese Antwort von mir. Ich hätte besser genauer hingucken sollen, sorry.

Also: Diagonale Stücke sind NICHT zugelassen. Der Blaue-Buchstaben-Beispielweg soll dies sicher auch verdeutlichen.

Damit wäre das explizit geklärt :smile:.

Grüße
Martin

#6

Hallo,
auch wenn Martin jetzt schon selbst geantwortet hat, wäre an sich seine Aussage

beide Fragen erübrigen sich!

völlig ausreichend. Dies impliziert ja gerade, daß er davon ausgeht, daß keine „Diagonalen-Zusatzlsg.“ existieren.

Gruss
Enno

#7

Hallo Enno!

Iss ja schon gut, ich seh’s ein. Da hat der alte Besserwisser in mir wieder mal durchgeschlagen.

Gruß,
Martin *dersichjetztwiedermaleifriganszählenmacht*

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#8

Zu faul!
Hallo,

zum Selberzählen hatte ich keine Geduld, daher schrieb ich ein kleines C++ Programm, so dass Kollege Computer einspringen konnte. Als Antwort erhielt ich
503.

Gruß
Jens

Hier der Quellcode:

#include
using std::cout;
using std::endl;
using std::flush;
#include 
using std::vector;
#include 
using std::ifstream;
using std::ofstream;
#include 
using std::string;

const char\* STD\_FILENAME = "feld.dat";
const char\* STD\_OUTPUT\_FILE = "output.dat";
const char\* PATTERN = "ABRAKADABRA";
const int N=11;
struct Tzelle
{
 char letter;
 bool visited;
};
typedef vector Tzeile;
typedef vector Tfeld;

int initFeld( Tfeld& feld, char\* filename );
unsigned long searchFeld( Tfeld& feld, string& patern, int i, int j, int tiefe, ofstream& aus );
void printLoesung( Tfeld& feld, ofstream& aus );

int main(int argc, char \*argv[])
{
 cout 1)
 err = initFeld( feld, argv[1] );
 else
 err = initFeld( feld, (char\*)STD\_FILENAME ); 
 if (err)
 return err;
 cout \> zelle.letter;
 zelle.visited=false;
 zeile.push\_back( zelle );
 }
 else
 return 1;
 feld.push\_back( zeile );
 }
 return 0;
}

unsigned long searchFeld( Tfeld& feld, string& pattern, int i, int j, int tiefe, ofstream& aus )
{
 unsigned int anzahl=0;
 if ( tiefe0 )
 if ( !feld[i-1][j].visited && 
 feld[i-1][j].letter == pattern[tiefe] )
 {
 feld[i-1][j].visited = true;
 anzahl += searchFeld( feld, pattern, i-1, j, tiefe+1, aus );
 feld[i-1][j].visited = false;
 };
 if ( i0 )
 if ( !feld[i][j-1].visited && 
 feld[i][j-1].letter == pattern[tiefe] )
 {
 feld[i][j-1].visited = true;
 anzahl += searchFeld( feld, pattern, i, j-1, tiefe+1, aus );
 feld[i][j-1].visited = false;
 };
 if ( j
#9

Symmetrie
Hallo nochmal,

hätte ich mir das Buchstabenfeld etwas genauer angeschaut, wäre mir die hohe Symmetrie aufgefallen; dies hätte mir das Erstellen des C++ Programms erspart. Hier nun also ein etwas eleganteres alternatives Lösungsverfahren:

Zunächst einmal ist das Feld links-rechts-spiegelsymmetrisch. Ich betrachte zunächst nur die rechte Seite (einschließlich der Mittelspalte). Für diese rechte Seite gilt, das jede korrekte Lösung aus einer Folge von Schritten nach rechts ® oder nach unten (u) besteht. Zum Beispiel (u,u,r,u,r,r,u,u,u,r). Aufgrund der Geometrie des Feldes sind aber nicht beliebige solcher Folgen erlaubt. Zum Beispiel scheidet die Folge (r,r,r,r,r,r,r,r,r) aus. Allgemein gilt, dass die Anzahl der r-Schritte höchstens so groß sein darf wie die bisherigen u-Schritte.
Als nächstes stellt man fest, dass jede Lösungsfolge auf einem Randfeld (rechter unterer Rand) endet und jedes Randfeld des rechten unteren Randes das Ende einer Lösung ist (Aussage 1).
Mein Plan ist es nun, jedem Feld eine Zahl zuzuordnen. Diese Zahl soll die Anzahl der möglichen Verzweigungen angeben, die es von jenem Feld aus gibt. Wegen der Aussage 1 erhalten die 6 Randfelder des linken unteren Randes jeweils eine 1:

---
--- ---
--- --- ---
--- --- --- --- 
--- --- --- --- ---
--- --- --- --- --- -1-
--- --- --- --- -1-
--- --- --- -1-
--- --- -1-
--- -1-
-1-

Da nur Schritte nach unten und nach rechts zu Lösungen führen, ist die Zahl eines jeden Feldes bestimmt durch die Summe der Zahlen rechts und unterhalb des Feldes. Man kann also Schritt für Schritt die restlichen Felder ausfüllen:

---
--- ---
--- --- ---
--- --- --- --- 
--- --- --- --- ---
--- --- --- --- -2- -1-
--- --- --- -2- -1-
--- --- -2- -1-
--- -2- -1-
-2- -1-
-1-

und so weiter, bis schließlich herauskommt:

252
252 -70
182 -70 -20
112 -50 -20 -6- 
-62 -30 -14 -6- -2-
-32 -16 -8- -4- -2- -1-
-16 -8- -4- -2- -1-
-8- -4- -2- -1-
-4- -2- -1-
-2- -1-
-1-

Aufgrund der Spiegelsymmetrie gilt dies entsprechend für die linke Seite des Feldes. Die Gesamtzahl der Lösungen ist also durch das um 1 verminderte Doppelte der Zahl 252 gegeben. Um 1 vermindert deshalb, weil der senkrechte Weg (u,u,u,u,u,u,u,u,u,u) sonst doppelt gezählt würde. Als Lösung erhält man also

AnzahlLösungen = 2*252 - 1 = 503

genau wie bereits vom Computer vorhergesagt.

Viele Grüße
Jens

#10

Und noch eine Möglichkeit

Hallo,

da fällt mir ein: Man kann das Pferd auch von vorn aufzäumen. In meiner Antwort „Symmetrie“ hatte ich den Kästchen Zahlen zugeordnet, die angeben, auf wie viele Arten von dort aus noch Verzweigungen stattfinden können. Das oberste Kästchen gab dann die Anzahl der Lösungen für die rechte Seite des Buchstabenfeldes an.

Nun kann man aber auch in die Kästchen diejenige Zahl schreiben, die angibt, auf wie viele Arten man zu diesem Kästchen gelangen kann. Das oberste Kästchen erhält somit also eine 1 (Man muss ja schließlich dort beginnen). Außerdem erhalten sämtliche Kästchen der mittleren Spalte eine 1. Erhielt man bei der anderen Methode die Zahl eines Kästchen durch die Summe des rechten und des unteren Kästchens, so ist in unserem jetzigen Fall die Zahl eines Kästchen durch die Summe aus den Zahlen des oberen und des linken Kästchens gegeben (nach wie vor sind nur Schritte nach rechts oder nach unten möglich). Man erhält also folgendes Zahlenfeld:

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90
 1 7 27 75
 1 8 35
 1 9
 1

Da die Endpositionen durch die Kästchen im rechten unteren Rand gegeben sind, erhält man die Anzahl der Lösungen durch die Summe der Zahlen jener Kästchen:

n=1+9+35+75+90+42=252

und die Anzahl der Lösungen des gesamten Feldes durch

N=2*n-1=2*252-1=503.

Das Ganze erinnert ein bißchen an das Pascalsche Dreieck. Es würde mich nicht wundern, wenn die allgemeine Lösung mittels Binomialkoeffizienten angegeben werden könnte.

Viele Grüße
Jens

#11

That’s it! :wink: [LÖSUNG]
Hi Jens,

da hast Du ja einige Stufen der Erkenntnis durchlaufen… :wink: Den Ausführungen in Deinem letzten Posting ist aber nichts mehr hinzuzufügen. Nachdem man gerafft hat, daß alle Wörter bei dem „A“ an der Spitze beginnen müssen, und die Symmetrie des Schemas erkannt hat, kümmert man sich nur um eine Hälfte und zählt die Wege gemäß der von Dir beschriebenen Methode ab, indem man also beginnend bei dem „A“ oben kleine Zahlen in jedes Kästchen schreibt und Summen bildet gemäß „Zahl in Kästchen = Summe der Zahlen in den Kästchen, von denen ein Weg hinführt“. Zum Schluß bildet man die Diagonalensumme, verdoppelt sie und zieht vom Ergebnis 1 ab, weil der Weg senkrecht runter doppelt gezählt wurde. Fertig! Damit kommt man auf die Wege-Gesamtzahl von 2 * 252 – 1 = 503.

Das Ganze erinnert ein bißchen an das Pascalsche Dreieck. Es
würde mich nicht wundern, wenn die allgemeine Lösung mittels
Binomialkoeffizienten angegeben werden könnte.

Stimmt genau!

Für ein 3er-Schema („ABR“) gibt es 2\ *2 -1 Möglichkeiten,
für ein 5er-Schema („ABRAK“) 2\ *6 -1,
für ein 7er-Schema („ABRAKAD“) 2\ *20 -1,
für ein 9er-Schema („ABRAKADAB“) 2\ *70 -1, und
für ein 11er-Schema („ABRAKADABRA“) 2\ *252 -1.

Guckt man sich nun das Pascalsche Dreieck einmal scharf an…

 1
~
 1 1
~
 1 (2) 1
~
 1 3 3 1
~
 1 4 (6) 4 1
~
 1 5 10 10 5 1
~
 1 6 15 (20) 15 6 1
~
 1 7 21 35 35 21 7 1
~
 1 8 28 56 (70) 56 28 8 1
~
 1 9 36 84 126 126 84 36 9 1
~
1 10 45 120 210 (252) 210 120 45 10 1

…so sieht man sofort, daß die Folge

2, 6, 20, 70, 252…

die Mittellinie des Dreiecks bildet.

Da dort aber gerade die Binomialkoeffizienten (n–1 over (n–1)/2) mit n = Zeilenindex = 3, 5, 7, 9… stehen, lautet sich die allgemeine Formel für die Weganzahl:

 ( n–1 ) 
2 ( ) – 1 wobei n := Anzahl der Buchstaben in "ABRAK..."
 ( (n–1)/2 )

Für „ABRAKADA HU BRA“ (n = 13) gäbe es folglich 2 (12 over 6) – 1 = 1847 Möglichkeiten.

Da die Art des Schemas für n nur ungerade Werte zuläßt, gibt’s mit (n–1)/2 auch keine Probleme; es ist immer eine ganze Zahl.

Grüße zurück und ein schönes Wochenende
Martin