Q3 Matemática  (Romanian Masters of Mathematics Collection 2017)

Fixe um inteiro $n\ge 2$ e seja $A$ um array $n\times n$ com $n$ células cortadas de modo que exatamente uma célula seja removida de cada linha e de cada coluna. Um stick é um subarray $1\times k$ ou $k\times 1$ de $A$, onde $k$ é um inteiro positivo adequado. (a) Determine o número mínimo de varetas em que $A$ podem ser dissecados. (b) Mostre que o número de maneiras de dissecar $A$ em um número mínimo de varetas não excede $100^n$. proposto por Palmer Mebane e Nikolai Beluhov alguns comentários uma variação da parte a, foi o problema 5 uma variação da parte b, foi postado aqui este post foi feito para completar a coleção de posts do RMM Shortlist 2017