Find all pairs of integers (m,n) such that an m×n board can be totally covered with 1×3 and 2×5 pieces.
Problem
Source: Argentina IMO 2005 TST, problem 1
Tags: combinatorics proposed, combinatorics
28.04.2005 06:04
one can work this out in a straightforward manner-first note that any n≥8 can be written in the form 3a+5b with both a,b≥0(and that 7 can't be writen so) and also that any integer n≥2 can be written as 2a+3b with a,b≥0.thus if m(or n)≥8 then writing m=3a+5b we note that 2×m can be tiled with tiles of the specified types.also since 3×m can always be tiled with 1×3 tiles, we see that writing n=2c+3d gives a tiling of the m×n square. what now remains is seeing which of the ones that have been left out(m,n≤7) can be tiled and which can't.wlog, assume m≤n.clearly 3×n,6×n can be tiled for all n≥1.if m=2 we have the following list: (2,3),(2,5),(2,6). for m=4 we have (4,5),(4,6)((4,7) can't be tiled and that is probably the only slightly nontrivial one in this listing,but one can argue that out rather easily since any potential tiling of it has to contain precisley one 2×5 tile and 6 1×3 tiles). finally one can check(!) that 5×5 and 7×7 can also be tiled(for the 5×5 note that this can be decomposed into a 2×5 and 3×5). the last case is that of 7×7 and this can also be tiled(form an outer layer of the 2×5 tiles using 4 of them;what remains inside is a 3×3 grid).
09.05.2013 18:23
Well, you just did de 4x7 wrongly: there is a covering, exactly with the 5x2 centered and the 3x1 surrounding it.
25.11.2016 20:47
Note that every 3×n can be covered by just the 1×3 piece. Now we prove that every 4×n board and every 5×n board can be covered for n≥5 by induction. By a simple check, we find that the 4×5, 4×6, and 4×7 boards can be covered, and that a 4×n board can be covered iff a 4×(n+3) board can be covered by adding or removing four 1×3 pieces. Hence by induction, we are done. Similarly, note that the 5×4, 5×5, and 5×6 boards can be covered, and a 5×n board can be covered iff a 5×(n+3) board can be covered by adding or removing five 1×3 pieces. Hence by induction, we are done. So, if n≥5, then every k×n board can be covered for k=3,4,5. Fix n≥5. Suppose all the k×n boards can be covered for k=3,4,5,...,m where m≥5. Then we may choose a k1 and k2 in the set {3,4,5,…,m} such that k1+k2=m+1. For such integers, we note that the k1×n and k2×n boards can be covered. By joining the tilings for these two boards along the common edge of length n, we obtain a tiling for the (m+1)×n board. Thus by strong induction, we have proven that for any m,n≥5, the m×n board can be tiled. It now remains to determine which boards cannot be tiled. We know that every 4×n board can be tiled if n≥5 (and thus the 5×4 board as well). By simply checking, we find that the 4×1, 4×2, and 4×4 boards cannot be tiled since an 2×5 tile cannot fit in these boards and the number of squares is not a multiple of 3 which would be required for it to be able to be tiled solely by 1×3 pieces. Every 3×n board can be tiled trivially. It is easy to see that a 2×n board can be tiled iff it can be tiled with 2×5 and 2×3 pieces in which case this is possible if and only if n=3a+5b for nonnegative integers a and b. By the Chicken-McNugget theorem, every integer n beyond 7 can be written in this way. It is easy to check, then, that the 2×1, 2×2, 2×4, and 2×7 boards cannot be tiled. Finally, any 1×n board can be tiled iff n is a multiple of 3 since the 5×2 piece cannot fit in this board. Thus the boards that cannot be covered are the 4×4, 2×2, 2×4, 2×7, 1×(3k+1), and 1×(3k+2) boards. And every other board can be covered.