MathDB

C2

Part of 2017 Romanian Master of Mathematics Shortlist

Problems(1)

count partitions of sieves, rmm 2017 p5 the shortlist version

Source: RMM Shortlist 2017 C2

7/4/2019
Fix an integer n≥2n \ge 2 and let AA be an n×nn\times n array with nn cells cut out so that exactly one cell is removed out of every row and every column. A stick is a 1×k1\times k or k×1k\times 1 subarray of AA, where kk is a suitable positive integer. (a) Determine the minimal number of sticks AA can be dissected into. (b) Show that the number of ways to dissect AA into a minimal number of sticks does not exceed 100n100^n.
proposed by Palmer Mebane and Nikolai Beluhov
[hide=a few comments]a variation of part a, was [url=https://artofproblemsolving.com/community/c6h1389637p7743073]problem 5 a variation of part b, was posted [url=https://artofproblemsolving.com/community/c6h1389663p7743264]here this post was made in order to complete the post collection of RMM Shortlist 2017
combinatoricstilings