Olympiad problems

1955 Moscow Mathematical Olympiad, 306

Cut a rectangle into $18$ rectangles so that no two adjacent ones form a rectangle.

2006 Estonia Team Selection Test, 3

Tags: combinatorics , Tiling , table

A grid measuring $10 \times 11$ is given. How many "crosses" covering five unit squares can be placed on the grid? (pictured right) so that no two of them cover the same square? [img]https://cdn.artofproblemsolving.com/attachments/a/7/8a5944233785d960f6670e34ca7c90080f0bd6.png[/img]

1999 Poland - Second Round, 2

Tags: Tiling , combinatorial geometry , cube , combinatorics , geometry , 3D geometry

A cube of edge $2$ with one of the corner unit cubes removed is called a [i]piece[/i]. Prove that if a cube $T$ of edge $2^n$ is divided into $2^{3n}$ unit cubes and one of the unit cubes is removed, then the rest can be cut into [i]pieces[/i].

1995 North Macedonia National Olympiad, 4

Tags: combinatorics , combinatorial geometry , Tiling

On a $ 30 \times30 $ square board or placed figures of shape 1 (of 5 squares) (in all four possible positions) and shaped figures of shape 2 (of 4 squares) . The figures do not overlap, they do not pass through the edges of the board and the squares of which they are drawn lie exactly through the squares of the board. a) Prove that the board can be fully covered using $100$ figures of both shapes. b) Prove that if there are already $50$ shaped figures on the board of shape 1, then at least one more figure can be placed on the board. c) Prove that if there are already $28$ figures of both shapes on the board then at least one more figure of both shapes can be placed on the board. [img]https://cdn.artofproblemsolving.com/attachments/3/f/f20d5a91d61557156edf203ff43acac461d9df.png[/img]

1975 Dutch Mathematical Olympiad, 5

Tags: geometry , combinatorial geometry , Tiling , tiles

Describe a method to convert any triangle into a rectangle with side 1 and area equal to the original triangle by dividing that triangle into finitely many subtriangles.

1994 Austrian-Polish Competition, 3

Tags: rectangle , Squares , Tiling , combinatorial geometry , combinatorics

A rectangular building consists of $30$ square rooms situated like the cells of a $2 \times 15$ board. In each room there are three doors, each of which leads to another room (not necessarily different). How many ways are there to distribute the doors between the rooms so that it is possible to get from any room to any other one without leaving the building?

2016 Baltic Way, 12

Tags: Tiling , combinatorics

Does there exist a hexagon (not necessarily convex) with side lengths $1, 2, 3, 4, 5, 6$ (not necessarily in this order) that can be tiled with a) $31$ b) $32$ equilateral triangles with side length $1?$

2006 Singapore Junior Math Olympiad, 5

Tags: combinatorics , Tiling , hexagon , tiles

You have a large number of congruent equilateral triangular tiles on a table and you want to fit $n$ of them together to make a convex equiangular hexagon (i.e. one whose interior angles are $120^o$) . Obviously, $n$ cannot be any positive integer. The first three feasible $n$ are $6, 10$ and $13$. Show that $12$ is not feasible but $14$ is.

2019 India IMO Training Camp, P2

Tags: combinatorics , Tiling

Let $n$ be a natural number. A tiling of a $2n \times 2n$ board is a placing of $2n^2$ dominos (of size $2 \times 1$ or $1 \times 2$) such that each of them covers exactly two squares of the board and they cover all the board.Consider now two [i]sepearate tilings[/i] of a $2n \times 2n$ board: one with red dominos and the other with blue dominos. We say two squares are red neighbours if they are covered by the same red domino in the red tiling; similarly define blue neighbours. Suppose we can assign a non-zero integer to each of the squares such that the number on any square equals the difference between the numbers on it's red and blue neighbours i.e the number on it's red neigbhbour minus the number on its blue neighbour. Show that $n$ is divisible by $3$ [i] Proposed by Tejaswi Navilarekallu [/i]

2020 India National Olympiad, 5

Tags: number theory , Tiling , descent , trigonometry , Niven theorem , rational , Galois Theory

Infinitely many equidistant parallel lines are drawn in the plane. A positive integer $n \geqslant 3$ is called frameable if it is possible to draw a regular polygon with $n$ sides all whose vertices lie on these lines, and no line contains more than one vertex of the polygon. (a) Show that $3, 4, 6$ are frameable. (b) Show that any integer $n \geqslant 7$ is not frameable. (c) Determine whether $5$ is frameable. [i]Proposed by Muralidharan[/i]

2016 Miklós Schweitzer, 8

Tags: geometry , rectangle , combinatorics , Tiling , Miklos Schweitzer

For which integers $n>1$ does there exist a rectangle that can be subdivided into $n$ pairwise noncongruent rectangles similar to the original rectangle?

2013 Peru MO (ONEM), 4

Tags: combinatorics , dominoes , tiles , Tiling

The next board is completely covered with dominoes in an arbitrary manner. [img]https://cdn.artofproblemsolving.com/attachments/8/9/b4b791e55091e721c8d6040a65ae6ba788067c.png[/img] a) Prove that we can paint $21$ dominoes in such a way that there are not two dominoes painted forming a $S$-tetramino. b) What is the largest positive integer $k$ for which it is always possible to paint $k$ dominoes (without matter how the board is filled) in such a way that there are not two painted dominoes forming a $S$-tetramine? Clarification: A domino is a $1 \times 2$ or $2 \times 1$ rectangle; the $S$-tetraminos are the figures of the following types: [img]https://cdn.artofproblemsolving.com/attachments/d/f/8480306382d6b87ddb8b2a7ca96c91ee45bc6e.png[/img]

2002 Junior Balkan Team Selection Tests - Romania, 3

Tags: rectangle , Tiling , tiles , combinatorics , Coloring

Consider a $1 \times n$ rectangle and some tiles of size $1 \times 1$ of four different colours. The rectangle is tiled in such a way that no two neighboring square tiles have the same colour. a) Find the number of distinct symmetrical tilings. b) Find the number of tilings such that any consecutive square tiles have distinct colours.

2018 Argentina National Olympiad, 3

Tags: geometry , combinatorics , combinatorial geometry , tiles , Tiling

You have a $7\times 7$ board divided into $49$ boxes. Mateo places a coin in a box. a) Prove that Mateo can place the coin so that it is impossible for Emi to completely cover the $48$ remaining squares, without gaps or overlaps, using $15$ $3\times1$ rectangles and a cubit of three squares, like those in the figure. [img]https://cdn.artofproblemsolving.com/attachments/6/9/a467439094376cd95c6dfe3e2ad3e16fe9f124.png[/img] b) Prove that no matter which square Mateo places the coin in, Emi will always be able to cover the 48 remaining squares using $14$ $3\times1$ rectangles and two cubits of three squares.

2011 Peru MO (ONEM), 4

Tags: combinatorics , dominoes , Tiling , tiles

A domino is a $1 \times 2$ (or 2 $\times 1$) rectangular piece; namely, made up of two squares. There is an $8 \times 8$ board such that each domino can be cover exactly two of its squares. John places $n$ dominoes on the board, so that each one covers exactly two squares of the board and it is no longer possible to place a piece more without overlapping with any of those already placed. Determine the smallest value of $n$ for which the described situation is possible.

2006 Bosnia and Herzegovina Team Selection Test, 1

Tags: combinatorics , Tiling , tetrislike

Let $Z$ shape be a shape such that it covers $(i,j)$, $(i,j+1)$, $(i+1,j+1)$, $(i+2,j+1)$ and $(i+2,j+2)$ where $(i,j)$ stands for cell in $i$-th row and $j$-th column on an arbitrary table. At least how many $Z$ shapes is necessary to cover one $8 \times 8$ table if every cell of a $Z$ shape is either cell of a table or it is outside the table (two $Z$ shapes can overlap and $Z$ shapes can rotate)?

2024 Czech and Slovak Olympiad III A, 3

Tags: combinatorics , Tiling , tiles

Find the largest natural number $n$ such that any set of $n$ tetraminoes, each of which is one of the four shapes in the picture, can be placed without overlapping in a $20 \times 20$ table (no tetramino extends beyond the borders of the table), such that each tetramino covers exactly 4 cells of the 20x20 table. An individual tetramino is allowed to turn and flip at will. [img]https://cdn.artofproblemsolving.com/attachments/b/9/0dddb25c2aa07536b711ded8363679e47972d6.png[/img]

2011 Dutch IMO TST, 2

Tags: combinatorics , Tiling , tiles , tilings

We consider tilings of a rectangular $m \times n$-board with $1\times2$-tiles. The tiles can be placed either horizontally, or vertically, but they aren't allowed to overlap and to be placed partially outside of the board. All squares on theboard must be covered by a tile. (a) Prove that for every tiling of a $4 \times 2010$-board with $1\times2$-tiles there is a straight line cutting the board into two pieces such that every tile completely lies within one of the pieces. (b) Prove that there exists a tiling of a $5 \times 2010$-board with $1\times 2$-tiles such that there is no straight line cutting the board into two pieces such that every tile completely lies within one of the pieces.

2006 Singapore Senior Math Olympiad, 4

Tags: combinatorics , Tiling , tiles , hexagon

You have a large number of congruent equilateral triangular tiles on a table and you want to fit $n$ of them together to make a convex equiangular hexagon (i.e. one whose interior angles are $120^o$) . Obviously, $n$ cannot be any positive integer. The first three feasible $n$ are $6, 10$ and $13$. Determine if $19$ and $20$ are feasible .

1979 Chisinau City MO, 177

Tags: combinatorial geometry , geometry , Squares , Tiling

Is it possible to cut a square into five squares?

2003 Estonia National Olympiad, 5

Tags: Chessboard , Tiling , combinatorics

Is it possible to cover an $n \times n$ chessboard which has its center square cut out with tiles shown in the picture (each tile covers exactly $4$ squares, tiles can be rotated and turned around) if a) $n = 5$, b) $n = 2003$? [img]https://cdn.artofproblemsolving.com/attachments/6/5/8fddeefc226ee0c02353a1fc11e48ce42d8436.png[/img]

2018 India IMO Training Camp, 1

Tags: rectangle , IMO Shortlist , combinatorics , Tiling

A rectangle $\mathcal{R}$ with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even. [i]Proposed by Jeck Lim, Singapore[/i]

2008 Switzerland - Final Round, 7

Tags: tiles , Tiling , combinatorics , geometry , rectangle

An $8 \times 11$ rectangle of unit squares somehow becomes disassembled into $21$ contiguous parts . Prove that at least two of these parts, except for rotations and reflections have the same shape.

2016 Indonesia TST, 1

Tags: combinatorics , Coloring , Tiling

Let $n \ge 3$ be a positive integer. We call a $3 \times 3$ grid [i]beautiful[/i] if the cell located at the center is colored white and all other cells are colored black, or if it is colored black and all other cells are colored white. Determine the minimum value of $a+b$ such that there exist positive integers $a$, $b$ and a coloring of an $a \times b$ grid with black and white, so that it contains $n^2 - n$ [i]beautiful[/i] subgrids.

1987 Tournament Of Towns, (135) 4

Tags: Tiling , combinatorics , combinatorial geometry

We are given tiles in the form of right angled triangles having perpendicular sides of length $1$ cm and $2$ cm. Is it possible to form a square from $20$ such tiles? ( S . Fomin , Leningrad)