Maths Olympiad Prep

Library / /76 of 121

Combinatorics Difficulty 6.3 National Olympiad Prove it India

Problem:

A stromino is a 3×13 \times 1 rectangle. Show that a 5×55 \times 5 board divided into twenty-five 1×11 \times 1 squares cannot be covered by 16 strominos such that each stromino covers exactly three unit squares of the board and every unit square is covered by either one or two strominos. (A stromino can be placed either horizontally or vertically on the board.)

Solution

Solution:

Suppose on the contrary that it is possible to cover the board with 16 strominos such that each unit square is covered by either one or two strominos. If there are kk squares that are covered by exactly one stromino then 2(25k)+k=16×3=482(25-k)+k=16 \times 3=48 and hence k=2k=2. Thus there are exactly two squares which are covered by only one stromino.

We colour the board with three colours red, blue, green as follows. The square corresponding to the ii-th row and the jj-th column is coloured red if i+j0(mod3)i+j \equiv 0 \pmod{3}, green if i+j1(mod3)i+j \equiv 1 \pmod{3} and blue otherwise. Then there are 9 red squares, 8 green squares and 8 blue squares. Note that each stromino covers exactly one square of each colour. Therefore the two squares that are covered by only one stromino are both red. For each such square i+j0(mod3)i+j \equiv 0 \pmod{3} where ii and jj are its row and column number.

We now colour the board with a different scheme. We colour the square corresponding to the ii-th row and the jj-th column red if ij0(mod3)i-j \equiv 0 \pmod{3}, green if ij1(mod3)i-j \equiv 1 \pmod{3} and blue otherwise. Again, there are 9 red squares and hence the two squares covered by only one stromino are both red. For each such square ij0(mod3)i-j \equiv 0 \pmod{3} where ii and jj are its row and column number. Thus, each of the two squares covered by only one stromino satisfies i+j0(mod3)i+j \equiv 0 \pmod{3} and ij0(mod3)i-j \equiv 0 \pmod{3} where ii and jj are its row and column number. This implies that i=j=3i=j=3. This is a contradiction because there is only one such square.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.