Found problems: 80
The central square of the City of Mathematicians is an $n\times n$ rectangular shape, each paved with $1\times 1$ tiles. In order to illuminate the square, night lamps are placed at the corners of the tiles (including the edges of the rectangle) in such a way that each night lamp illuminates all the tiles in its corner.
Determine the minimum number of night lamps such that even if one of those night lamps does not work, it is possible to illuminate the entire central square with them.
Let $ n$ be a positive integer. A $4\times n$ rectangular grid is divided in$ 2\times 1$ or $1\times 2$ rectangles (as if it were completely covered with tiles of domino, no overlaps or gaps). Then all the grid points which are vertices of one of the $2\times 1$ or $1\times 2$ rectangles, are painted red. What is the least amount of red points you can get?
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?
(a) Prove that a square with sides $1000$ divided into $31$ squares tiles, at least one of which has a side length less than $1$.
(b) Show that a corresponding decomposition into $30$ squares is also possible.
[i](Walther Janous)[/i]
Given is a floor plan composed of $n$ unit squares. Albert and Berta want to cover this floor with tiles, with all tiles having the shape of a $1\times 2$ domino or a $T$-tetromino. Albert only has tiles from one color, while Berta has two-color dominoes and tetrominoes available in four colors. Albert can use this floor plan in $a$ ways to cover tiles, Berta in $ b$ ways. Assuming that $a \ne 0$, determine the ratio $b/a$.
On an infinite sheet of tiles, an infinite number of $1 \times 2$ tile rectangles are placed, their edges follow the lines of the tiles, and they do not touch each other, not even the corners. Is it true that the remaining checkered sheet can be completely covered with $1 \times 2$ checkered rectangles?
[hide=original wording]Uz bezgalīgas rūtiņu lapas ir novietoti bezgaglīgi daudzi 1 x 2 rūtiņu taisnstūri, to malas iet pa rūtiņu līnijām, un tie nesaskaras cits ar citu pat ne ar stūriem. Vai tiesa, ka atlikušo rūtiņu lapu var pilnībā noklāt ar 1 x 2 rūtiņu tainstūriem?
[/hide]
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.
We have a board of $ 2011 \times 2011$, divided by lines parallel to the edges into $1 \times 1$ squares. Manuel, Reinaldo and Jorge (at that time order) play to form squares with vertices at the vertices of the grid. The one who forms the last possible square wins, so that its sides do not cut the sides of any unit square. Who can be sure that he will win?
Consider a $2\times2$ square with one corner removed from $1\times1$ , leaving a shape in the form of $L$ .
[asy]
unitsize(0.5 cm);
draw((1,0)--(1,2)--(0,2)--(0,0)--(2,0)--(2,1)--(0,1));
[/asy]
We will call this figure [i]triomino[/i]. Determine all values of $m, n$ such that a rectangle of $m\times n$ can be exactly covered with triominos.
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.
Let $n$ be an integer greater than $3$. Show that it is possible to divide a square into $n^2 + 1$ or more disjointed rectangles and with sides parallel to those of the square so that any line parallel to one of the sides intersects at most the interior of $n$ rectangles.
Note: We say that two rectangles are [i]disjointed [/i] if they do not intersect or only intersect at their perimeters.
A $5\times 5$ board is covered by eight hooks (a three unit square figure, shown in the picture) so that one unit square remains free. Determine all squares of the board that can remain free after such covering.
[img]https://cdn.artofproblemsolving.com/attachments/6/8/a8c4e47ba137b904bd28c01c1d2cb765824e6a.png[/img]
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.
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.
An angle of size $n \times m$, where $m, n \ge 2$, is called a figure, resulting from a rectangle of size $n \times m$ cells by removing the rectangle size $(n - 1) \times (m - 1)$ cells. Two players take turns making moves consisting in painting in a corner an arbitrary non-zero number of cells forming a rectangle or square.
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]
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.
Let $n\geq 3$ a positive integer. In each cell of a $n\times n$ chessboard one must write $1$ or $2$ in such a way the sum of all written numbers in each $2\times 3$ and $3\times 2$ sub-chessboard is even. How many different ways can the chessboard be completed?
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 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.