Problem

Source: Mexican Math Olympiad 2015 Problem 2

Tags: combinatorics, 2015



Let $n$ be a positive integer and let $k$ be an integer between $1$ and $n$ inclusive. There is a white board of $n \times n$. We do the following process. We draw $k$ rectangles with integer sides lenghts and sides parallel to the ones of the $n \times n$ board, and such that each rectangle covers the top-right corner of the $n \times n$ board. Then, the $k$ rectangles are painted of black. This process leaves a white figure in the board. How many different white figures are possible to do with $k$ rectangles that can't be done with less than $k$ rectangles? Proposed by David Torres Flores