Tiling a grid

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Tiling a grid

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Singapore Open MO 2023 Round 2 2023 P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

676 posts

#1 h Jul 1, 2023, 12:32 PM

Y by

A grid of cells is tiled with dominoes such that every cell is covered by exactly one domino. A subset $S$ of dominoes is chosen. Is it true that at least one of the following 2 statements is false?
(1) There are $2022$ more horizontal dominoes than vertical dominoes in $S$ .
(2) The cells covered by the dominoes in $S$ can be tiled completely and exactly by $L$ -shaped tetrominoes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

167 posts

#2 h Jul 1, 2023, 2:25 PM • 1 Y

Y by Ngoyh

Routine coloring problem

Assume that it is possible for $S$ have $2022$ more horizontal dominoes than vertical dominoes, and the cells covered by the dominoes in $S$ can be fully tiled only with L-tetrominoes.
Let the number of vertical dominoes be $n$ . Thus there are $2022+n$ horizontal dominoes and we need $1011+n$ L-tetrominoes to tile $S$ completely.
We color each row black and white alternating, and we consider the difference of black and white cells in $S$ .
Vertical dominoes have one black and one white cells; they make up no difference in the number of black and white cells.
Horizontal dominoes are either fully black or white. Let $m$ be the number of white horizontal dominoes. Then there are $2(m-(n+2022-m)=4m-2n-4044$ more white cells than black.
When $S$ is completely tiled with $n+1011$ L-tetrominoes, each L-tetromino has two more white cells than black, or the other way around. Let $k$ be the number of L-tetrominoes with more white cells. Then there are $2(k-(n+1011-k)=4k-2n-2022$ more white cells than black.
Here $4m-2n-4044=4k-2n-2022$ , and $2(m-k)=1011$ ; $2|1011$ . This is a contradiction. Therefore the two statements can't be both true.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

beansenthusiast505

26 posts

beansenthusiast505

#3 h Jul 3, 2023, 10:38 PM

Y by

AAAAAAAAAAAAAAAAAAAA i'm so dumb why didnt i see this in smo

We define horizontal parity as a colouring of each row with alternate colours (i.e. odd rows black even rows white) and vertical parity to be its vertical colouring (odd columns black even columns white)

Each horizontal domino decreases horizontal parity by 2 and keeps vertical parity constant, vice versa for the vertical domino. For each L-tetromino, it decreases both horizontal and vertical parity by 2.

Now suppose $n$ vertical dominoes and $n+2022$ horizontal dominoes. We know that if this set $S$ can be supposedly tiled with L-tetrominoes, it can be tiled with $n+1011$ of them. Then the horizontal parity is $2n+4044$ (mod 4) $=$ $2n$ (mod 4) and the vertical parity is also $2n$ (mod 4) if tiled by the horizontal and vertical dominoes. If tiled by L-tetrominoes though, the horizontal and vertical parities would be $2n+2022$ (mod 4). Since 2022 $\equiv$ 2 (mod 4), contradiction and at least 1 statement has to be false.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#4 h Jul 27, 2023, 2:00 PM • 1 Y

Y by asdia

Solution with just 1 coloring:

Let $(i,j)$ be colored $0$ if $i$ and $j$ are even, $1$ if $i$ is odd and $j$ is even, $3$ if $i$ is even and $j$ is odd, and $2$ if both $i$ and $j$ are odd.

Assume for contradiction that both (1) and (2) can be true. Each horizontal domino covers squares such that the sum of numbers on them is $1 \pmod 4$ and each vertical domino covers squares such that the sum of numbers on them is $-1 \pmod 4$ , so the total sum of numbers on covered squares is $2022 \equiv 2 \pmod 4$ . But each L-shape, which can be tiled with $1$ horizontal and $1$ vertical domino, contributes $0 \pmod 4$ , so we have $0 \equiv 2 \pmod 4$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3 posts

#5 h Sep 16, 2024, 6:12 PM • 3 Y

Y by BR1F1SZ, kiyoras_2001, Akeyla

This problem was proposed by me, along with Q4. Solution is attached below.

Also, here is the story of how I came up with this problem. It is quite interesting.

As we all know, all Singaporean males have to go through 2 years of National Service, and like most others I did mine in the army. When I was doing my Basic Military Training (BMT), there was once I had to fall out of a conduct due to injury, and so I was sitting on the side while the rest were doing exercises on the parade square. Being bored with nothing to do, I decided why not try to come up with a problem. So I looked around to try to find inspiration.

It was then I noticed that the parade square was tiled with bricks in the following pattern:

https://fastly.4sqi.net/img/general/200x200/40417116_IiHFPsBl595cttYLNmkrKt0r3qsEZQGqNkuoMftEUso.jpg

(Basically alternating sets of 2 horizontal dominoes by 2 vertical dominoes)

Noticing this pattern, I decided why not try to come up with a combi problem that involved this particular tiling of dominoes? So I got to work exploring this particular pattern of dominoes to try and find nice properties I could create a problem around.

The exact details behind how L-shaped tetrominoes came into the picture has largely been lost to time, but I think it was because of observing how a pair of adjacent horizontal and vertical dominoes can be paired to form an L-shaped tetromino, and so I thought whether it is possible to expand on this idea and create sets of dominoes which can be replaced by L-shaped tetrominoes in this manner. Then I realised there were sets of dominoes which can be tiled by L-shaped tetrominoes but this one-to-one domino-pair-to-tetromino mapping doesn't exist (e.g. 4x2 rectangle with 2 horizontal dominoes on the left and 2 vertical dominoes on the right). Also, if such a one-to-one mapping exists, it basically guarantees that the number of horizontal and vertical tetrominoes in the set are the same, so I thought about exploring sets where the number of horizontal and vertical tetrominoes are not the same, but it can still be tiled by L-shaped tetrominoes.

The exact details of what happened after that have also been lost to time, but I think I did some trial and error and found that #horizontal dominoes - #vertical dominoes has to be divisible by 4, so I went about exploring why values not divisible by 4 do not work. When exploring the case where the difference is 2 mod 4, I found a solution that made it a nice problem to work out. So eventually, that was the problem I proposed.

Notice that until now I have been using the tiling from the parade square, and in fact in the original version of the problem I specified that to be the tiling used for the infinite grid. It was only afterwards that I realised that the solution worked for all tilings, not just this one, so I removed the condition and generalised it to all tilings, which gives the final version of the problem you see above.

Edit: I found an older version of the problem, attached below. If you want you can try it, but it doesn't differ that meaningfully from the original problem.

Attachments:

My Problem 4.pdf (87kb)

This post has been edited 1 time. Last edited by ESCmath, Sep 16, 2024, 6:44 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a