Wie viele mögliche Wege gibt es in einem nxn Gitter von (0,0) nach (n,n) mit folgenden Einschränkungen:?

Es sind nur Schritte nach rechts und nach oben erlaubt und alle gültigen Wege müssen genau EINMAL die Hauptdiagonale überschreiten,ansonsten bleiben sie strikt unterhalb/oberhalb der Hauptdiagonalen.

Meine Idee: Ohne sämtliche Einschränkungen gibt es ja (2n über n) möglichkeiten von (0,0) nach (n,n), wenn wir jetzt schritte nach oben als eine offene Klammer definieren "(" und Schritte nach rechts als eine schließende Klammer ")" dann entsprechen diese Möglichkeiten genau der Anzahl der perfekten Klammerungen (da die Anzahl öffnender und schließender Klammern n ist) und somit der n-ten Catalan Zahl := (1/n+1) (2n über n) https://de.wikipedia.org/wiki/Catalan-Zahl

Weil Catalan-Zahlen geben generell die Anzahl der möglichen Schritte von (0,0) nach (n,n) an,die strikt unter der Hauptdiagonalen verlaufen. Aber hier ist es ja genau dasselbe oder ? Weil ab einem beliebigen Schnittpunkt (i,j) mit der Hauptdiagonalen muss man oberhalb der Hauptdiagonalen bleiben, das ganze kann man dann aufgrund der symmetrie (nxn) spiegeln und hat wieder diesen Fall.

Also das wäre zumindest so meine Idee, aber wie beweist man das formal und kann man die Möglichkeiten auch ohne die Catalan-Zahlen bestimmen und so auf die Lösung kommen ?

Mfg

Studium, Schule, Mathematik, Logik, Physik, Statistik, Stochastik, Universität, Kombinatorik
Münzwurf via Telefon?

Alice und Bob können sich nicht einigen und wollen einen Münzwurf entscheiden lassen. Beide können ausschließlich telefonisch miteinander kommunizieren und haben kein Vertrauen ineinander. Auch steht keine dritte, unabhängige Schiedsrichterperson zur Verfügung. Wie könnte solch ein telefonischer Münzwurf aussehen?

In der Wissenschaft wird mit dem Commitment-Verfahren eine Lösung vorgeschlagen:

https://de.wikipedia.org/wiki/Commitment-Verfahren

"Eine klassische Anwendung für ein Commitment ist der Münzwurf via Telefon. Alice und Bob wollen eine Münze werfen, aber weil die beiden sich über die Telefonverbindung nicht sehen können und sich gegenseitig nicht vertrauen wollen, funktioniert das übliche Protokoll „einer sagt an, der andere wirft“ nicht. Eine mögliche Lösung wäre, dass Alice ihre Wahl einem vertrauenswürdigen Dritten mitteilt, der dann, nachdem Bob das Ergebnis mitgeteilt hat, den Gewinner bestimmt. Mit einem Bit-Commitment lässt sich das Problem ohne dritte Partei lösen, indem Alice ein Commitment auf ihre Wahl an Bob schickt. Bob kann aus dem Commitment nichts über Alices Wahl lernen, aber Alice ist nun festgelegt und kann ihre Wahl nicht nachträglich ändern. Nun wirft Bob die Münze und teilt Alice das Ergebnis mit, woraufhin Alice das Commitment öffnet."

Aber wie könnte Alice dieses "Commitment" telefonisch an Bob übermitteln und wie sähe so ein "Commitment" aus?

Welche anderen Möglichkeiten des "telefonischen Münzwurfs" gäbe es?

Entscheidung, Logik, Zufall

Meistgelesene Beiträge zum Thema Logik