Problem

Source: RMM Shortlist 2017 C2

Tags: combinatorics, tilings



Fix an integer $n \ge 2$ and let $A$ be an $n\times n$ array with $n$ cells cut out so that exactly one cell is removed out of every row and every column. A stick is a $1\times k$ or $k\times 1$ subarray of $A$, where $k$ is a suitable positive integer. (a) Determine the minimal number of sticks $A$ can be dissected into. (b) Show that the number of ways to dissect $A$ into a minimal number of sticks does not exceed $100^n$. proposed by Palmer Mebane and Nikolai Beluhov

HIDE: a few comments a variation of part a, was problem 5 a variation of part b, was posted here this post was made in order to complete the post collection of RMM Shortlist 2017