Found problems: 189
The cells of an $n \times n$ chessboard are coloured in several colours so that no $2\times 2$ square contains four cells of the same colour. A [i]proper path [/i] of length $m$ is a sequence $a_1,a_2,..., a_m$ of distinct cells in which the cells $a_i$ and $a_{i+1}$ have a common side and are coloured in different colours for all $1 \le i < m$. Show that there exists a proper path of length $n$.
An $n\times n$ chessboard is given, where $n$ is an even positive integer. On every line, the unit squares are to be permuted, subject to the condition that the resulting table has to be symmetric with respect to its main diagonal (the diagonal from the top-left corner to the bottom-right corner). We say that a board is [i]alternative[/i] if it has at least one pair of complementary lines (two lines are complementary if the unit squares on them which lie on the same column have distinct colours). Otherwise, we call the board [i]nonalternative[/i]. For what values of $n$ do we always get from the $n\times n$ chessboard an alternative board?\\ \\
[i](Alexandru Petrescu and Andra Elena Mircea)[/i]
What is the maximum number of rooks one can place on a chessboard such that any rook attacks exactly two other rooks? (We say that two rooks attack each other if they are on the same line or on the same column and between them there are no other rooks.)
Alexandru Mihalcu
[u]Chessboards [/u]
Joe B. is playing with some chess pieces on a $6\times 6$ chessboard. Help him find out some things.
[b]p1.[/b] Joe B. first places the black king in one corner of the board. In how many of the $35$ remaining squares can he place a white bishop so that it does not check the black king?
[b]p2.[/b] Joe B. then places a white king in the opposite corner of the board. How many total ways can he place one black bishop and one white bishop so that neither checks the king of the opposite color?
[b]p3.[/b] Joe B. now clears the board. How many ways can he place $3$ white rooks and $3$ black rooks on the board so that no two rooks of opposite color can attack each other?
[b]p4.[/b] Joe B. is frustrated with chess. He breaks the board, leaving a $4\times 4$ board, and throws $3$ black knights and $3$ white kings at the board. Miraculously, they all land in distinct squares! What is the expected number of checks in the resulting position? (Note that a knight can administer multiple checks and a king can be checked by multiple knights.)
[b]p5.[/b] Suppose that at some point Joe B. has placed $2$ black knights on the original board, but gets bored of chess. He now decides to cover the $34$ remaining squares with $17$ dominos so that no two overlap and the dominos cover the entire rest of the board. For how many initial arrangements of the two pieces is this possible?
Note: Chess is a game played with pieces of two colors, black and white, that players can move between squares on a rectangular grid. Some of the pieces
move in the following ways:
$\bullet$ Bishop: This piece can move any number of squares diagonally if there are no other pieces along its path.
$\bullet$ Rook: This piece can move any number of squares either vertically or horizontally if there are no other pieces along its path.
$\bullet$ Knight: This piece can move either two squares along a row and one square along a column or two squares along a column and one square along a row.
$\bullet$ King: This piece can move to any open adjacent square (including diagonally).
If a piece can move to a square occupied by a king of the opposite color, we say that it is checking the king.
If a piece moves to a square occupied by another piece, this is called attacking.
In an $m\times n$ rectangular chessboard,there is a stone in the lower leftmost square. Two persons A,B move the stone alternately. In each step one can move the stone upward or rightward any number of squares. The one who moves it into the upper rightmost square wins. Find all $(m,n)$ such that the first person has a winning strategy.
A chess-board $6\times 6$ is tiled with the $2\times 1$ dominos. Prove that you can cut the board onto two parts by a straight line that does not cut dominos.
Show that, in a chessboard, it is possible to traverse to any given square from another given square using a knight. (A knight can move in a chessboard by going two steps in one direction and one step in a perpendicular direction as shown in the given figure)
What maximal number of the men in checkers game can be put on the chess-board $8\times 8$ so, that every man can be taken by at least one other man ?
Two types of pieces, bishops and rooks, are to be placed on a $10\times 10$ chessboard (without necessarily filling it) such that each piece occupies exactly one square of the board. A bishop $B$ is said to [i]attack[/i] a piece $P$ if $B$ and $P$ are on the same diagonal and there are no pieces between $B$ and $P$ on that diagonal; a rook $R$ is said to attack a piece $P$ if $R$ and $P$ are on the same row or column and there are no pieces between $R$ and $P$ on that row or column.
A piece $P$ is [i]chocolate[/i] if no other piece $Q$ attacks $P$.
What is the maximum number of chocolate pieces there may be, after placing some pieces on the chessboard?
[i]Proposed by José Alejandro Reyes González[/i]
On a $999\times 999$ board a [i]limp rook[/i] can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A [i]non-intersecting route[/i] of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called [i]cyclic[/i], if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over.
How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit?
[i]Proposed by Nikolay Beluhov, Bulgaria[/i]
Originally, every square of $8 \times 8$ chessboard contains a rook. One by one, rooks which attack an odd number of others are removed. Find the maximal number of rooks that can be removed. (A rook attacks another rook if they are on the same row or column and there are no other rooks between them.)
[i](6 points)[/i]
How many squares different in size or location can be drawn on an $8 \times 8$ chess board? Each square drawn must consist of whole chess board’s squares.
On a board with $64$ ($8 \times 8$) squares, find a way to arrange $9$ queens and $ 1$ king so that every queen cannot capture another queen.
Jiiri and Mari both wish to tile an $n \times n$ chessboard with cards shown in the picture (each card covers exactly one square). Jiiri wants that for each two cards that have a common edge, the neighbouring parts are of different color, and Mari wants that the neighbouring parts are always of the same color. How many possibilities does Jiiri have to tile the chessboard and how many possibilities does Mari have?
[img]https://cdn.artofproblemsolving.com/attachments/7/3/9c076eb17ba7ae7c000a2893c83288a94df384.png[/img]
Given a chess-board $99\times 99$ with a set $F$ of fields marked on it (the set is different in three tasks). There is a beetle sitting on every field of the set $F$. Suddenly all the beetles have raised into the air and flied to another fields of the same set. The beetles from the neighbouring fields have landed either on the same field or on the neighbouring ones (may be far from their starting point). (We consider the fields to be neighbouring if they have at least one common vertex.) Consider a statement:
[i]"There is a beetle, that either stayed on the same field or moved to the neighbouring one".[/i]
Is it always valid if the figure $F$ is:
a) A central cross, i.e. the union of the $50$-th row and the $50$-th column?
b) A window frame, i.e. the union of the $1$-st, $50$-th and $99$-th rows and the $1$-st, $50$-th and $99$-th columns?
c) All the chess-board?
A rook starts moving on an infinite chessboard, alternating horizontal and vertical moves. The length of the first move is one square, of the second – two squares, of the third – three squares and so on.
a) Is it possible for the rook to arrive at its starting point after exactly $2013$ moves?
b) Find all $n$ for which it possible for the rook to come back to its starting point after exactly $n$ moves.
What is the number of ways in which one can choose $60$ unit squares from a $11 \times 11$ chessboard such that no two chosen squares have a side in common?
For an integer $m\geq 1$, we consider partitions of a $2^m\times 2^m$ chessboard into rectangles consisting of cells of chessboard, in which each of the $2^m$ cells along one diagonal forms a separate rectangle of side length $1$. Determine the smallest possible sum of rectangle perimeters in such a partition.
[i]Proposed by Gerhard Woeginger, Netherlands[/i]
A [i]lazy[/i] rook can only move from a square to a vertical or a horizontal neighbour. It follows a path which visits each square of an $8 \times 8$ chessboard exactly once. Prove that the number of such paths starting at a corner square is greater than the number of such paths starting at a diagonal neighbour of a corner square.
[i](7 points)[/i]
On a chessboard $5 \times 9$ squares, the following game is played.
Initially, a number of frogs are randomly placed on some of the squares, no square containing more than one frog. A turn consists of moving all of the frogs subject to the following rules:
$\bullet$ Each frog may be moved one square up, down, left, or right;
$\bullet$ If a frog moves up or down on one turn, it must move left or right on the next turn, and vice versa;
$\bullet$ At the end of each turn, no square can contain two or more frogs.
The game stops if it becomes impossible to complete another turn. Prove that if initially $33$ frogs are placed on the board, the game must eventually stop. Prove also that it is possible to place $32$ frogs on the board so that the game can continue forever.
Let be given an $n \times n$ chessboard, $n \in N$. We wish to tile it using particular tetraminos which can be rotated. For which $n$ is this possible if we use
(a) $T$-tetraminos
(b) both kinds of $L$-tetraminos?
$1\times 2$ dominoes are placed on an $8 \times 8$ chessboard without overlapping. They may partially
stick out from the chessboard but the center of each domino must be strictly inside the
chessboard (not on its border). Place on the chessboard in such a way:
a) at least $40$ dominoes, (3 points)
b) at least $41$ dominoes, (3 points)
c) more than $41$ dominoes. (6 points)
[i](Mikhail Evdokimov)[/i]
Bishops on a chessboard move along the diagonals ( that is , on lines parallel to the two main diagonals ) . Prove that the maximum number of non-attacking bishops on an $n*n$ chessboard is $2n-2$. (Two bishops are said to be attacking if they are on a common diagonal).
How many
a) bishops
b) horses
can be positioned on a chessboard at most, so that no one threatens another?
positive real $C$ is $n-vengeful$ if it is possible to color the cells of an $n \times n$ chessboard such that:
i) There is an equal number of cells of each color.
ii) In each row or column, at least $Cn$ cells have the same color.
a) Show that $\frac{3}{4}$ is $n-vengeful$ for infinitely many values of $n$.
b) Show that it does not exist $n$ such that $\frac{4}{5}$ is $n-vengeful$.