# Count Restricted Frog Paths on a Grid A frog starts at (0, 0) and must reach (7, 4). Each step moves either one unit right or one unit up. The frog may not make three consecutive moves in the same direction, so neither RRR nor UUU may appear. Count the valid paths and justify the result. ### Constraints & Assumptions - The frog must make exactly seven right moves and four up moves. - Only the two forbidden length-three runs constrain the path. - Paths are distinguished by their complete move sequences. - The answer should include a recurrence or independently checkable counting argument. ### Clarifying Questions to Ask - Are coordinates inclusive so the displacement is exactly seven by four? - Does a change in direction reset the consecutive-run count? - Would a dynamic-programming state be acceptable instead of a closed form? ```hint Remember the run Counts of right and up moves alone do not determine whether the next move is legal. ``` ```hint Check a constrained tail If one direction is exhausted first, verify that all remaining moves still satisfy the consecutive-move rule. ``` ### What a Strong Answer Covers - A complete counting argument that distinguishes paths by their move sequences. - Correct treatment of the first move, direction changes, and the third-consecutive-move prohibition. - An independently checkable sanity check without exposing the requested count in the prompt. - Verification that every counted sequence has eleven moves with the required totals. ### Follow-up Questions - How would you count paths to (a, b) with no run of length k? - Can the recurrence be reduced using generating functions for bounded block sizes?