Source: Original.
1. For 1<=N<=8, divide an NxN square into the maximum number of non-overlapping rectangles with integral sides, such that each rectangle is unique in dimensions from any other. That is, between any two rectangles, the length or width or both must be different. For N=1, you can't cut it and remain integral, so the maximum is 1 rectangle. For N=2, there are two rectangles you can cut from the square (1x1 and 1x2) but not without leaving a duplicate 1x1, so the maximum is still 1. For N=3, you cannot cut 4 rectangles, because there is only one distinct rectangle of area 1, one of area 2, and one of area 3. The next distinct rectangle has area 4, and there are two of these. But any 4 distinct rectangles will have an area of at least 10, so the best you can do is one of the following ways of cutting it into 3 rectangles: AAA AAB AAA AAB BBC CCC For N=4, the maximum number of rectangles (by the same argument as above) is 5. This is possible as follows: AAAE BBCC BBCC BBDD At this point, I decided it was better for the purpose of calculating this upper limit if I write out a table of the possible rectangles: Area Rectangles Cumulative Area 1 1x1 1 2 1x2 3 3 1x3 6 4 1x4, 2x2 14 5 1x5 19 6 1x6, 2x3 31 7 1x7 38 8 1x8, 2x4 54 9 3x3 63 10 2x5 73 For the 5x5 square, 7 rectangles are just possible if you use the 1x1-1x5, 2x2, and 2x3. These fit as follows: AAABB AAABB CCCCC DDDDE FFFGG For the 6x6 square, no more than 8 rectangles are possible, and that can be done as follows, using 7 of the 8 smallest rectangles, but the 2x5 in place of the 1x5 to make the total area come out to 36: AAAAAA BBCDDD BBCDDD BBCEFF BBCEFF BBGGGH For the 7x7 square, the smallest 10 rectangles add to a total area of 46, and no more than 10 rectangles are possible. Here is a solution, using 9 of the smallest 10, replacing the 1x7 with a 2x5 to make the area come to 49: AAAAAAD BBBBBEE CCFFFEE CCFFFGH CCIIIGH CCJJJJH CCJJJJH For the 8x8, the smallest 12 rectangles come to an area of 63 and so the maximum is 12 rectangles. Using the 2x5 instead of the 3x3 is the only way to make the area come out to exactly 64 in 12 rectangles. It happens that this is the same set of rectangles as the 7x7 with the addition of the 1x7 and 1x8, so the solution is derived from that one: AAAAAADL BBBBBEEL CCFFFEEL CCFFFGHL CCIIIGHL CCJJJJHL CCJJJJHL KKKKKKKK 2. Same as number 1, with the added constraint that no rectangle can be a square. If we disallow squares, then N=1 and N=2 cannot be done at all, since the only allowable case above was to leave the square complete. Table of allowable non-square rectangles: Area Rectangles Cumulative Area 2 1x2 2 3 1x3 5 4 1x4 9 5 1x5 14 6 1x6, 2x3 26 7 1x7 33 8 1x8, 2x4 49 10 2x5 59 12 2x6, 3x4 83 For the 3x3, the 1x4 is not a possible rectangle, so the maximum number of rectangles is 2 and that can be done as follows: AAA AAA BBB For the 4x4, the 1x5 and 1x6 are not possible rectangles, so the maximum number or rectangles is 4: the 1x2, 1x3, 1x4, and 2x3, which add to an area of 15. However, incorporating the next larger rectangle, the 2x4, would increase the area to at least 17, so no set of four distinct non-square rectangles has area 16, so the best we can do is three, as follows: AAAA AAAA BCCC BCCC For the 5x5, the five smallest possible rectangles are the 1x2 - 1x5 and the 2x3, which add to an area of 20; the next larger is the 2x4 which would exceed 25, so 5 is the maximum, which can be achieved as follows: AABCC AABDD AABDD AABDD AAEEE For the 6x6, the seven smallest possible rectangles, the 1x2 - 1x6 and the 2x3 and 2x4, add to an area of 34 units; seven is the most rectangles possible, as follows: AAAAAA BBCDDE BBCDDE BBCDDE BBCFFE BBCGGG For the 7x7, the 1x8 is not a possible rectangle, so the maximum is 8 rectangles which can be achieved as follows: AAAAAAA BCCCCCC BCCCCCC BDDEEEE BDDEEEE BDDFFFG BHHHHHG For the 8x8, the ten smallest rectangles add to 59, so ten is the maximum possible: AAAAAAAA CDBBBBBB CDEEEEEE CDEEEEEE CFGGGGGH CFGGGGGH IIIIJJJH IIIIJJJH 3. Divide a checkerboard into the maximum number of unique rectangles. Here you have the added variable of color, so two rectangles of equal size can still vary by pattern. Here, the only difference from part 1 is with ODDxODD rectangles; any rectangles with an even dimension have two corners or one color and two corners of the other and can be rotated 180 degrees to make the "other" color pattern (though the corner color patterns differe depending on whether the rectangle has both dimensions even, or just one). For each ODDxODD rectangle, we have two possible rectangles now. So our possibles rectangles chart becomes: Area Rectangles Cumulative Area 1 1x1(2) 2 2 1x2 4 3 1x3(2) 10 4 1x4, 2x2 18 5 1x5(2) 28 6 1x6, 2x3 40 7 1x7(2) 54 8 1x8, 2x4 70 9 3x3(2) 88 10 2x5 98 The smallest 14 rectangles on this chart (up to one of the area-8 rectangles) add up to an area of 62, so 14 is the most possible. Below, I use capital and lower case letters to distinguish colors, and use a 2x4 instead of a 2x3 to make the area add to 64: AaAaAaAa bCdDdDdD BcEeEeEj bCfFfFfJ BcGhHiIj bCgHhIiK BcGhHlLk bCgHhMnK