Minimum number of square tiles needed to tile a square floor

excluding n. My bad, I mentioned it in my prev ans. I meant gcd among the numbers available.

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 :confused:

as @vijju123 said at n=9 how do you calculate no. of tiles?

@vijju123 can’t say if this is correct for all n’s but it’s atleast true for 5,7,9

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!! :slight_smile:

@vijju123 sure, maybe a picture or two will help (excuse my miserable Paint skills). 9x9 and 35x35.

1 Like

Thanks a lot dear!! It would be REALLY nice if you could do that!!! :slight_smile: :slight_smile: