BreizhCTF 2023 - Smoll Grid

Challenge details

Event	Challenge	Category	Points	Solves
BreizhCTF 2023	Smoll Grid	Programming	???	???

You start in the top-left corner of a 6 × 6 grid and your goal is to move to the bottom-right corner. You can only move in two directions: right or down. Diagonal and backward moves are forbidden.

How many different ways are there to get from the start to the end? (3 example paths are provided in the associated file).

The flag is of the form BZHCTF{N} where N is a positive non-zero integer.

Author: Zeecka

TL;DR

A combinatorial approach, or one using Pascal’s triangle, yields the result 252.

Methodology

A detailed article from Geeks for Geeks lays out the problem.

The Pascal’s triangle approach is as follows:

If we know the number of possible paths to reach the cell to the left and the cell above a given cell, then the number of paths to reach the given cell will be the sum of the two.

As the figure shows, we can reach the cell to the left in A different ways and reach the upper blocks in B different ways, so the total answer for our new cell will be A+B. Repeating this principle produces the following diagram:

The number of possibilities is therefore 252.

Flag

BZHCTF{252}

Author: Zeecka