Solution

ID: past-exam-of-the-mathematics-course-of-the-year-1-of-the-natural-sciences-course-of-the-university-of-cambridge/2025/paper-2/12/c/ii/solution

Suppose the first draw is green. The excess of green over red must remain positive after draws one through five and return to zero at draw six. After deleting the first green and final red, the remaining four steps must form a Dyck path: they have equal colour counts and never go below zero relative to the new starting level. There are such orders, and , giving and in the original game.
Interchanging green and red gives and . Thus there are
orders. More generally, the Catalan number counts each sign of excursion with first return time .

New to topics? Read the docs here!