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
Problem
Source: Mexican Math Olympiad 2015 Problem 2
Tags: combinatorics, 2015
suli
29.11.2015 05:28
The white region is bounded by at most $k$ distinct vertical and at most $k$ distinct horizontal lines and is uniquely determined by them. Thus by choosing the lines from $n$ available vertical or horizontal lines (not $n+1$ as the rightmost line cannot be used), the answer is $$(\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{k})^2.$$EDIT: The problem has been edited, so this solution does not apply.
MexicOMM
29.11.2015 21:44
You are wrong, the answer is $\binom{n}{k}^2$
XmL
29.11.2015 22:59
Note that the resulting white figure is a one-directional staircase with exactly $k$ steps. Since there are $\binom{n}{k}$ ways to choose the vertal part of the stairs, and the same number of ways to choose the horizontal part of the stairs, thus there are $\binom{n}{k}^2$ total ways.
MexicOMM
29.11.2015 23:24
Sorry it is not that you are wrong, the question asked in this problem is different from the one asked in the actual exam.