Determine all positive integers $ n$ such that it is possible to tile a $ 15 \times n$ board with pieces shaped like this: [asy][asy]size(100); draw((0,0)--(3,0)); draw((0,1)--(3,1)); draw((0,2)--(1,2)); draw((2,2)--(3,2)); draw((0,0)--(0,2)); draw((1,0)--(1,2)); draw((2,0)--(2,2)); draw((3,0)--(3,2)); draw((5,0)--(6,0)); draw((4,1)--(7,1)); draw((4,2)--(7,2)); draw((5,3)--(6,3)); draw((4,1)--(4,2)); draw((5,0)--(5,3)); draw((6,0)--(6,3)); draw((7,1)--(7,2));[/asy][/asy]
Problem
Source: Central American Olympiad 2000, problem 2
Tags: modular arithmetic
Sepp
08.08.2007 12:22
Clearly we can cover every $ 5 \times 3$ or $ 3 \times 5$. So we can also cover a $ 15 \times n$ with: $ n \equiv 0 \pmod 3$ (all $ 3 \times 5$ pieces), $ n \equiv 2 \pmod 3$ and $ n > 2$ (a column of $ 5 \times 3$ and all the others $ 3 \times 5$), $ n \equiv 1 \pmod 3$ and $ n > 7$ (two columns of $ 5 \times 3$ and all the others $ 3 \times 5$). Then it's easy to see we cannot cover the board if $ n = 1, 2, 4, 7$.
NuncChaos
27.12.2010 17:55
But how can we prove it is impossible to tile without purely 3 by 5s?
panamath
01.07.2012 05:33
See $n=1, 2, 4, 7$ are not achievable. Now, are achievable those $n's$ that can be written as $n=3a+5b$ with $a, b$ non negative integers. Do your cases and see that $n=3, 5, 6, 8, 9, 10 ...$ are achievable; now I'll prove if $n$ is achievable, $n+1$ is achievable. If $b \ge 1$ and $n=3a+5b$ we can achieve $n+1=3(a+2) + 5(b-1)$, if $b=0$, since we proved all cases until $10$, we have $a > 3$ so we can achieve $n+1=3(a-3)+5(b+2)$ and we are done, $n=1, 2, 4, 7$ are not achievable, every other $n$ is achievable.
MOLYMATHSS89
18.10.2018 12:03
Sepp wrote: Clearly we can cover every $ 5 \times 3$ or $ 3 \times 5$. So we can also cover a $ 15 \times n$ with: $ n \equiv 0 \pmod 3$ (all $ 3 \times 5$ pieces), $ n \equiv 2 \pmod 3$ and $ n > 2$ (a column of $ 5 \times 3$ and all the others $ 3 \times 5$), $ n \equiv 1 \pmod 3$ and $ n > 7$ (two columns of $ 5 \times 3$ and all the others $ 3 \times 5$). Then it's easy to see we cannot cover the board if $ n = 1, 2, 4, 7$.
-[]-
23.04.2019 10:15
Sepp wrote: Then it's easy to see we cannot cover the board if $ n = 1, 2, 4, 7$. HOW do you prove that $n=4,7$ are not possible?