I was asked the following question. Suppose there is an nxn checkerboard, and we have enough 2x2 and 3x3 checkerboards at hand. We need to fill the nxn checkerboard with the 2x2 and 3x3's without any overlaps. What requirement should the number n obey? Why? I claimed the right conclusion that n should be multiples of 2 or 3, but I failed to show the reason. Could you pls help me? Thank you very much. URGENT

Yes, n has to be a multiple of 2 or 3 for it to work. There might be an easier way to prove this, but I did it in the following way. Color the checkerboard like the following:1 3 1 3 1 3 1 ...2 4 2 4 2 4 2 ...3 1 3 1 3 1 3 ...4 2 4 2 4 2 4 ...1 3 1 3 1 3 1 ...2 4 2 4 2 4 2 ...... ... ... ... ...Note that any 2x2 square contains exactly one 1, 2, 3, and 4. Also, the 3x3 squares can cover in one of the 4 patterns, R, S, T, or U: R S T U1 | 3 1 3 22 | 2 3 1 33 | 3 2 3 14 | 1 3 2 3Now if n is even, clearly we can cover it. If n is 1 mod 4, looking at the picture, we see that there will be an equal number of 1's, 2's, 3's, and 4's in the first n-1 rows (since n-1 is divisible by 4). In the bottom row there will be (n+1)/2 1's and (n-1)/2 3's. This means that however many 3x3 squares we have, we must have an equal number of squares of type R and T (since there are an equal number of 2's and 4's), call that number a. Moreover if we call b the number of squares of type S, there must be b+1 squares of type U (since there's one more 1 than there are 3's). Then the number of 1's is 3a + b + 3a + 2(b+1) = 6a + 3b + 2 and the number of 2's is 2a + 3b + a + 3(b+1) = 3a + 6b + 3. Hence (n+1)/2 = (6a + 3b + 2) - (3a + 6b + 3) = 3(a-b)-1 which implies that n = 6(a-b)-3, hence n is a multiple of 3.The case where n is 3 mod 4 proceeds similarly, but here you need 1 more 2 than there are 4's, an equal number of 1's and 3's, and (n+1)/2 more 1's than 4's. Thus if c is the number of T's, there have to be c+1 R's, and there have to be an equal number d of S's and U's, and we find that (6c+3+3d)-(3c+1+6d) = (n+1)/2 which implies that n = 6(c-d) + 3, which is also a multiple of 3.

It just occurred to me that it's much easier if we cover it like: 1 3 1 3 1 3 1 ...2 4 2 4 2 4 2 ...1 3 1 3 1 3 1 ...2 4 2 4 2 4 2 ...1 3 1 3 1 3 1 ...2 4 2 4 2 4 2 ...... ... ... ... ...Then in this case, every 3x3 square contains either an equal number of 1's and 4's, 3 more 4's than 1's, or 3 more 1's than 4's, and every 2x2 square of course contains an equal number of 1's and 4's. So the difference between the number of 4's and 1's must always be a multiple of 3. But when n is odd, there are n more 1's than 4's, hence n must be a multiple of 3 to tile it.

Thank you very much, mhughes.

Isn't this problem just a variation on the earlier problem 'Rectangles' on this forum.So, define a function that is periodic in both x and y, with period of 2 along x and a period of 3 along y. That is: . Then the surface integral over a square is zero iff the length of the square is either a multiple of 2 or 3. After tiling the big square with 2x2 and 3x3 squares, the surface integral over the big square should be equal to zero!

For what it is worth, here is another way of looking at it. Assume n is not a multiple of 2 or 3, so n is 6k+1 or 6k-1. Color the nxn board by making the leftmost column red, the next column green and the next white and repeat. It suffices to look at the parity of the number of squares of each color. They are not all the same. For example, they are odd,even,even, respectively, in the case of n=6k+1. What happens when we start covering up the board with 2x2 and 3x3 squares? A 2x2 will cover 2 squares each of 2 colors (and therefore the parities of the remaining squares does not change). A 3x3 square will always cover 3 of each color (thus turning odd,even,even into even,odd,odd). There is no way to get to 0,0,0 (even,even,even).

Correct answer: n >= 2.Proof: By Bezout's Identity, if p and q are relatively prime, then there exist integers k and m such that k*p + m*q = 1. The integers k and m can be explicitly found by the extended Euiclidean algorithim. It follows that n = n * (k*p + m*q) for any natural number n. Now restricting k and m to the non-negative integers, it follows that n = n * (k*p + m*q) for any natural number n greater than or equal to (p-1)*(q-1).Now, 2 is relatively prime to 3, so let p=2, q=3. Then n must be greater than or equal to (2-1)*(3-1) = 2. This proves that for any natural number n >= 2, there exist non-negative integers k and m such that n = n*k*2 + n*m*3. SO, for ANY n >= 2, we can tile an nxn checkboard with n*k 2x2 tiles and n*m 3x3 tiles, where k and m are given by the extended Euclidean algorithim.This isnt a brainteaser btw, it's a pure number theory problem.

You seem to have given the answer to the different question: given an n x 1 checkerboard and as many 2 x 1 and 3 x 1 dominoes as you want, for which n can you successfully tile the checkerboard? This answer is clearly n >= 2, by obvious intuition or by your lengthy proof (which isn't even 100% accurate, though the gist is clear). How your demonstration pertains to the n x n checkerboard case I fail to see, perhaps because you've given no indication as to how they're related.For example, using your proof, how would you tile a 5 x 5 checkerboard using 2 x 2 and 3 x 3 squares?

Oh. You're right.

Pannini,it seems that you cannot use Bezout's Identity is this problem, as you would need either k or m to be negative.And as mhughes pointed out, it's easy to see that the 5x5 checkerboard is not filled with the tiles provided.

MCarreira, I think you can use Bezout because it works for non-negative k and m as long as n is sufficiently large. But it was a big mistake to think that it applies to nxn just because it works for nx1.

Yes, this is why I said the proof wasn't 100% accurate. Even though you stated it without proof, you were right in saying that you can write n = k*p + m*q with m, k >= 0 as long as n >= (q-1)(p-1), but m and k are no longer multiples of n as you implied. Of course, m and k being multiples of n is not at all necessary for what followed, which is why I said the gist was clear.

Pannini, k*p + m*q = 1 works only, as you pointed out, with p=q=1 ... that's why I said it you could not use it in this problem. Sorry if I did not express it correctly.