Overlapping game

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

Overlapping game

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2023 Japan MO Finals 1

The post below has been deleted. Click to close.

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

95 posts

#1 h Feb 11, 2023, 11:03 AM • 2 Y

Y by GeoKing, itslumi

On $5\times 5$ squares, we cover the area with several S-Tetrominos (=Z-Tetrominos) along the square so that in every square, there are two or fewer tiles covering that (tiles can be overlap). Find the maximum possible number of squares covered by at least one tile.

This post has been edited 1 time. Last edited by Kei0923, Feb 11, 2023, 11:22 AM

Z K Y

The post below has been deleted. Click to close.

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

9042 posts

#2 h Feb 11, 2023, 11:40 AM • 2 Y

Y by SPHS1234, GuvercinciHoca

Answer
Solution

Z K Y

The post below has been deleted. Click to close.

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

344 posts

#4 h Jun 17, 2023, 8:56 PM • 1 Y

Y by GeoKing

Kei0923 wrote:

On $5\times 5$ squares, we cover the area with several S-Tetrominos (=Z-Tetrominos) along the square so that in every square, there are two or fewer tiles covering that (tiles can be overlap). Find the maximum possible number of squares covered by at least one tile.

$\color{blue}\boxed{\textbf{Answer: 24}}$
$\color{blue}\boxed{\textbf{Proof:}}$
$\color{blue}\rule{24cm}{0.3pt}$
$\text{Let us consider the following coloring:}$
$[asy] draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0)); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((0,1)--(5,1)); draw((0,2)--(5,2)); draw((0,3)--(5,3)); draw((0,4)--(5,4)); fill((1,1)--(2,1)--(2,2)--(1,2)--cycle, black); fill((1,3)--(2,3)--(2,4)--(1,4)--cycle, black); fill((3,3)--(4,3)--(4,4)--(3,4)--cycle, black); fill((3,1)--(4,1)--(4,2)--(3,2)--cycle, black); [/asy]$
$\text{Let's note that each tetromino covers exactly one black square, as there can be at most 2 tiles per square and there are 4 black squares}$ $\Rightarrow \text{Number of tiles}\le 2\times 4=8$ $\text{Let us consider the following coloring:}$
$[asy] draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0)); draw((1,0)--(1,5)); draw((2,0)--(2,5)); draw((3,0)--(3,5)); draw((4,0)--(4,5)); draw((0,1)--(5,1)); draw((0,2)--(5,2)); draw((0,3)--(5,3)); draw((0,4)--(5,4)); fill((0,0)--(1,0)--(1,1)--(0,1)--cycle, blue); fill((0,2)--(0,3)--(1,3)--(1,2)--cycle, blue); fill((0,4)--(0,5)--(1,5)--(1,4)--cycle, blue); fill((2,0)--(3,0)--(3,1)--(2,1)--cycle, blue); fill((2,2)--(3,2)--(3,3)--(2,3)--cycle, blue); fill((2,4)--(3,4)--(3,5)--(2,5)--cycle, blue); fill((4,0)--(5,0)--(5,1)--(4,1)--cycle, blue); fill((4,2)--(5,2)--(5,3)--(4,3)--cycle, blue); fill((4,4)--(4,5)--(5,5)--(5,4)--cycle, blue); [/asy]$
$\text{Let's keep in mind that each tetromino covers exactly one blue square, since there are 9 blue squares and there are at most 8 tiles,}$ $\text{then at least 1 square remains uncovered}$ $\text{Number of squares covered by at least one tile}\le 24$ $\color{blue}\rule{24cm}{0.3pt}$
$\color{blue}\boxed{\textbf{Example:}}$
$\color{blue}\rule{24cm}{0.3pt}$
$\text{We fill the board with two layers:}$
$[asy] draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0)); draw((1,0)--(1,1)--(0,1)); draw((0,3)--(1,3)--(1,2)--(2,2)--(2,0)); draw((2,2)--(2,4)--(1,4)--(1,5)); draw((5,0)--(4,0)--(4,1)--(3,1)--(3,5)); draw((4,5)--(4,4)--(5,4)); draw((3,3)--(4,3)--(4,2)--(5,2)); [/asy]$
$[asy] draw((0,0)--(5,0)--(5,5)--(0,5)--(0,0)); draw((0,1)--(1,1)--(1,2)--(3,2)--(3,1)--(2,1)--(2,0)); draw((3,2)--(5,2)); draw((5,1)--(4,1)--(4,0)); draw((1,5)--(1,4)--(0,4)); draw((0,3)--(2,3)--(2,4)--(3,4)--(3,5)); draw((2,3)--(4,3)--(4,4)--(5,4)); [/asy]$
$\text{Note that there are 24 squares that meet the order}$ $\color{blue}\rule{24cm}{0.3pt}$
$\color{green}\boxed{\textbf{Conclusion:}}$
$\color{green}\rule{24cm}{0.3pt}$
$\boxed{\textbf{There are at most 24 squares covered by at least one tile}}_\blacksquare$ $\color{green}\rule{24cm}{0.3pt}$

Z K Y

The post below has been deleted. Click to close.

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

457 posts

#6 h Apr 30, 2025, 3:57 AM

Y by

The answer is $24$ . Consider that two S-tetromino can form a $2\times 5$ rectangle that has two corners missing
Using four of those can cover everything but the center square.
Consider color the board like this

ABABA
CDCDC
ABABA
CDCDC
ABABA

then each piece would cover one of each A, B, C, D.
As there are only four Ds, we can use at most eight S-tetrominoes
As there are nine A's, there would at least be one uncovered A, so one cannot cover all squares.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a