IMO 2023 Shortlist C6
Let N be a positive integer, and consider an N ˆ N grid. A right-down path is a sequence of grid cells such that each ce...
Category: Combinatorics
Problem
Let N be a positive integer, and consider an N ˆ N grid. A right-down path is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A right-up path is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence. Prove that the cells of the N ˆ N grid cannot be partitioned into less than N right-down or right-up paths. For example, the following partition of the 5 ˆ 5 grid uses 5 paths. (Canada)