Found problems: 178
Rectangles $1\times20$, $1\times 19$, ..., $1\times 1$ were cut out of $20\times20$ table. Prove that from the remaining part of the table $36$ $1\times2$ dominos can be cut
[I]Proposed by S. Berlov[/i]
Given are two polyominos, the first one is an L-shape consisting of three squares, the other one contains at least two squares. Prove that if $n$ and $m$ are coprime then at most one of the $n\times n$ and $m\times m$ boards can be tiled by translated copies of the two polyominos.
[i]Proposed by: András Imolay, Dávid Matolcsi, Ádám Schweitzer and Kristóf Szabó, Budapest[/i]
A board of $6\times 6$ is totally covered by $18$ dominoes (of $2\times 1$), that is, there are no overlaps, gaps, and the tiles do not come off the board. Prove that, regardless of the arrangement of the tiles, there is always a line that divides the board into two non-empty parts, and without cutting tiles.
Given are two positive integers $k$ and $n$ with $k \le n \le 2k - 1$. Julian has a large stack of rectangular $k \times 1$ tiles. Merlin calls a positive integer $m$ and receives $m$ tiles from Julian to place on an $n \times n$ board. Julian first writes on every tile whether it should be a horizontal or a vertical tile. Tiles may be used the board should not overlap or protrude. What is the largest number $m$ that Merlin can call if he wants to make sure that he has all tiles according to the rule of Julian can put on the plate?
Each square on a $ n \times n$ board, with $n \ge 3$, is colored with one of $ 8$ colors. For what values of $n$ it can be said that some of these figures included in the board, does it contain two squares of the same color.
[img]https://cdn.artofproblemsolving.com/attachments/3/9/6af58460585772f39dd9e8ef1a2d9f37521317.png[/img]
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.
A domino is a $1\times2$ or $2\times 1$ rectangle. Diego wants to completely cover a $6\times 6$ board using $18$ dominoes. Determine the smallest positive integer $k$ for which Diego can place $k$ dominoes on the board (without overlapping) such that what remains of the board can be covered uniquely using the remaining dominoes.
Let $n$ be a positive integer. An equilateral triangle with side $n$ will be denoted by $T_n$ and is divided in $n^2$ unit equilateral triangles with sides parallel to the initial, forming a grid. We will call "trapezoid" the trapezoid which is formed by three equilateral triangles (one base is equal to one and the other is equal to two).
Let also $m$ be a positive integer with $m<n$ and suppose that $T_n$ and $T_m$ can be tiled with "trapezoids".
Prove that, if from $T_n$ we remove a $T_m$ with the same orientation, then the rest can be tiled with "trapezoids".
Given a trapezium with two parallel sides of lengths $m$ and $n$, where $m$, $n$ are integers, prove that it is
possible to divide the trapezium into several congruent triangles.
John and Mary each have a white $8 \times 8$ square divided into $1 \times 1$ cells. They have painted an equal number of cells on their respective squares in blue. Prove that one can cut up each of the two squares into $2 \times 1 $ dominoes so that it is possible to reassemble John's dominoes into a new square and Mary's dominoes into another square with the same pattern of blue cells.
(A Shapovalov)
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]
For a positive integer $n$, we consider an $n \times n$ board and tiles with dimensions $1 \times 1, 1 \times 2, ..., 1 \times n$. In how many ways exactly can $\frac12 n (n + 1)$ cells of the board are colored red, so that the red squares can all be covered by placing the $n$ tiles all horizontally, but also by placing all $n$ tiles vertically?
Two colorings that are not identical, but by rotation or reflection from the board into each other count as different.
We have $10$ identical tiles as shown. The tiles can be rotated, but not flipper over. A $7 \times 7$ board should be covered with these tiles so that exactly one unit square is covered by two tiles and all other fields by one tile. Designate all unit sqaures that can be covered with two tiles.
[img]https://cdn.artofproblemsolving.com/attachments/d/5/6602a5c9e99126bd656f997dee3657348d98b5.png[/img]
A tiling of the plane with polygons consists of placing the polygons in the plane so that interiors of polygons do not overlap, each vertex of one polygon coincides with a vertex of another polygon, and no point of the plane is left uncovered. A unit polygon is a polygon with all sides of length one. It is quite easy to tile the plane with infinitely many unit squares. Likewise, it is easy to tile the plane with infinitely many unit equilateral triangles.
(a) Prove that there is a tiling of the plane with infinitely many unit squares and infinitely many unit equilateral triangles in the same tiling.
(b) Prove that it is impossible to find a tiling of the plane with infinitely many unit squares and finitely many (and at least one) unit equilateral triangles in the same tiling.
Several tiles congruent to the one shown in the picture below are to be fit inside a $11 \times 11$ square table, with each tile covering $6$ whole unit squares, no sticking out the square and no overlapping.
(a) Determine the greatest number of tiles which can be placed this way.
(b) Find, with a proof, all unit squares which have to be covered in any tiling with the maximal number of tiles.
[img]https://cdn.artofproblemsolving.com/attachments/c/d/23d93e9d05eab94925fc54006fe05123f0dba9.png[/img]
Poland
$15\times 36$-checkerboard is covered with square tiles. There are two kinds of tiles, with side $7$ or $5.$
Tiles are supposed to cover whole squares of the board and be non-overlapping.
What is the maximum number of squares to be covered?
You have an unlimited supply of square tiles with side length $ 1$ and equilateral triangle tiles with side length $ 1$. For which n can you use these tiles to create a convex $n$-sided polygon? The tiles must fit together without gaps and may not overlap.
A plane is tiled with regular hexagons of side $1$. $A$ is a fixed hexagon vertex.
Find the number of paths $P$ such that:
(1) one endpoint of $P$ is $A$,
(2) the other endpoint of $P$ is a hexagon vertex,
(3) $P$ lies along hexagon edges,
(4) $P$ has length $60$, and
(5) there is no shorter path along hexagon edges from $A$ to the other endpoint of $P$.
Find the smallest positive integer $n$ such that it is possible to paint each of the $64$ squares of an $8 \times 8$ board of one of $n$ colors so that any four squares that form an $L$ as in the following figure (or congruent figures obtained through rotations and/or reflections) have different colors.
[img]https://cdn.artofproblemsolving.com/attachments/a/2/c8049b1be8f37657c058949e11faf041856da4.png[/img]
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]
A unit square is removed from the corner of an $n \times n$ grid, where $n \geq 2$. Prove that the remainder can be covered by copies of the figures of $3$ or $5$ unit squares depicted in the drawing below.
[asy]
import geometry;
draw((-1.5,0)--(-3.5,0)--(-3.5,2)--(-2.5,2)--(-2.5,1)--(-1.5,1)--cycle);
draw((-3.5,1)--(-2.5,1)--(-2.5,0));
draw((0.5,0)--(0.5,3)--(1.5,3)--(1.5,1)--(3.5,1)--(3.5,0)--cycle);
draw((1.5,0)--(1.5,1));
draw((2.5,0)--(2.5,1));
draw((0.5,1)--(1.5,1));
draw((0.5,2)--(1.5,2));
[/asy]
[b]Note:[/b] Every square must be covered once and figures must not go over the bounds of the grid.
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?
A torpedo set consists of $2$ pieces of $1 \times 4$, $4$ pieces of $1 \times 3$, $6$ pieces of $1 \times 2$ and $ 8$ pieces of $1 \times 1$ ships.
a) Can one put the whole set to a $10 \times 10$ table so that the ships do not even touch with corners? (The ships can be placed both horizontally and vertically.)
b) Can we solve this problem if we change $4$ pieces of $1 \times 1$ ships to $3$ pieces of $1 \times 2$ ships?
c) Can we solve the problem if we change the remaining $4$ pieces of $1 \times 1$ ships to one piece of $1 \times 3$ ship and one piece of $1 \times 2$ ship? (So the number of pieces are $2, 5, 10, 0$.)
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.
Given a square side $1$ and $2n$ positive reals $a_1, b_1, ... , a_n, b_n$ each $\le 1$ and satisfying $\sum a_ib_i \ge 100$. Show that the square can be covered with rectangles $R_i$ with sides length $(a_i, b_i)$ parallel to the square sides.