1
$\begingroup$

A $23 \times 23$ square is tiled by $1 \times 1$, $2 \times 2$, and $3 \times 3$ tiles. Prove that at least one 1 x 1 tile must be used. Find such a tiling with exactly one $1 \times 1$ tile.

Hint: put a number in each $1 \times 1$ square of the big square so that $2 \times 2$ and $3 \times 3$ tiles cover a total divisible by $3$.

I'm not sure how to utilize the hint in solving this problem.

$\endgroup$
4
$\begingroup$

Further hint: $$ \matrix{1 & 0 & 1 & 0 & \ldots\\ 0 & 2 & 0 & 2 & \ldots\\ 1 & 0 & 1 & 0 & \ldots\\ 0 & 2 & 0 & 2 & \ldots\\ \ldots & \ldots & \ldots & \ldots & \ldots &\cr}$$ What is the total in the $23 \times 23$ square?

$\endgroup$
  • $\begingroup$ I want to say 386 but I'm not sure how that helps $\endgroup$ – Jebediah Nov 17 '13 at 20:56
  • $\begingroup$ Is it divisible by $3$? $\endgroup$ – Robert Israel Nov 17 '13 at 23:54
  • $\begingroup$ Nope. What can I conclude from that? $\endgroup$ – Jebediah Nov 18 '13 at 0:23
  • $\begingroup$ Could it be a sum of numbers each divisible by $3$? Note that the sum of the numbers in a $2 \times 2$ or $3 \times 3$ tile is divisible by $3$. $\endgroup$ – Robert Israel Nov 18 '13 at 0:52
  • $\begingroup$ I believe the sum of numbers should be divisible by 3, yes? $\endgroup$ – Jebediah Nov 20 '13 at 15:03
2
$\begingroup$

Put all ones in the top row, twos in the second row, ones in the third row and so on, every other row ones and twos.

You can check that wherever you put a big square, it has to cover a total that is divisible by 3. You can also check that the total in the entire grid is not divisible by 3. Hence you need small squares.

$\endgroup$
  • $\begingroup$ So without a 1 x 1 square, I cannot achieve an entire grid of squares with total sum divisible by 3? $\endgroup$ – Jebediah Nov 17 '13 at 21:25
  • $\begingroup$ @Jebediah Since neither of these answers has quite made it explicit: for either of these numberings, any 2x2 or 3x3 tile covers a set of numbers that adds to a multiple of 3. So if you could tile with only 2x2 and 3x3 tiles, then your total sum of numbers over the grid would have to be a multiple of 3. But the total sum of all numbers on the grid is one more than a multiple of 3, so... $\endgroup$ – Steven Stadnicki Jul 30 '14 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.