For a composite number n you can consider the problem identical to the problem for side length equal to the smallest prime divisor of n. Let n = a\times b where a is the smallest prime divisor of n. Then you can consider the n \times n block as an a \times a block where each unit tile is of dimension b \times b. This is the best way I have come up with for reducing n, but I am not completely sure this is the absolute best way. Also after doing such a reduction I am stuck with a prime n for which I can find no strict approach
This is a very intriguing problem by the way… will probably give me sleepless nights.
Correction: I realized it is not proper to use the term smallest prime divisor. Actually it is the smallest divisor of n excluding 1 (as dimension of usable tiles < n). This divisor will naturally always be prime. So the answer for a composite n is the same as the answer for its smallest divisor excluding 1, according to my proposition.
Yes. The optimal part took me 2 hrs to come up with, and the non-optimal part is as if professor took the problem out from a horror movie. Lol.
But regarding your logic, what answer does it give at 9? One thing to note is that all blocks need not of same size. So in a 9x9 blocks, we can fit 9 3x3 blocks, while if you try to fit a 1-6x6,and then 5-3x3, you’d get answer of 6. That’s what I could make out of this Q
I found lot of trouble verifying for n=9 onwards, esp 11 and 13. That’s why I asked you to cross check. The real problem is, when n is prime. This case is literally driving me nuts.
Here for a 9×9 tiles, n = 9 = 3*3 with the smallest prime divisor as 3. Hence the problem is identical to a 3×3 tile. For a 3×3 tile the answer is 6.
As another example, the answer for n = 35 is the same as the answer for n = 5, which is 8. This also applies when n is even as it reduces to a 2×2 square, the answer for which is 4.
@meow can you please explain a little more on how you derived the two cases as identical? Your ans is correct but i think i am not able to grasp how. Will appreciate if you could explain that!!
