# Professor Halfbrain and the dissection of a rectangle

Professor Halfbrain has spent his entire weekend with cutting rectangles into smaller rectangles. In particular, he proved the following deep theorem on such dissections.

Professor Halfbrain's rectangle dissection theorem: If a $5\times2$ rectangle is cut into ten smaller rectangles with integer side lengths, then two of these smaller rectangles must be congruent.

This puzzle asks you to improve the professor's theorem and to make it even deeper: Find the largest integer $n$, for which the following statement hold true.

If a $5\times n$ rectangle is cut into ten smaller rectangles with integer side lengths, then two of these smaller rectangles must be congruent.

Taking the 10 smallest possible distinct rectangles:

1x1 = 1
2x1 = 2
3x1 = 3
2x2 = 4
4x1 = 4
5x1 = 5
3x2 = 6
6x1 = 6
7x1 = 7
4x2 = 8

Their sum is 46. Therefore, for any total area smaller than 46, the professor's statement must necessarily hold.

The smallest possible area that's at least 46 is 50. Does the professor's statement hold for N=10?

No, it does not. A 5x10 rectangle can be split up into 1x1, 1x2, 1x3, 1x4, 1x5, 2x2, 2x3, 2x4, 1x7, 1x10 rectangles, none of which are congruent.

For a 5x9 rectangle, it can be split up into 9 rectangles of sizes 1x1, 1x2, 1x3, 1x5, 1x7, 1x9, 2x2, 2x3, 2x4. This allows one single rectangle to be added to produce 5xN for any N>10 (but not N=10 itself, since it would require two 5x1 rectangles). Picture for N=11:

So the professor's statement doesn't hold for N=10, nor for any N>10. That makes the answer 9.