Determine the maximum number of bishops that we can place in a $8 \times 8$ chessboard such that there are not two bishops in the same cell, and each bishop is threatened by at most one bishop. Note: A bishop threatens another one, if both are placed in different cells, in the same diagonal. A board has as diagonals the $2$ main diagonals and the ones parallel to those ones.
Problem
Source: Iberoamerican Olympiad 2016-P4
Tags: combinatorics, Iberoamerican, Iberoamerican 2016
always_correct
29.09.2016 01:47
I can't prove it yet, but I got $16$. If I'm right then I'll post an outline of a proof. In fact, any possible arrangement of safe bishops where you can't place any more has exactly $16$ of them. @below Can you describe the arrangement giving you twenty?
Gamamal
29.09.2016 01:54
Nope, its 20
bobthesmartypants
29.09.2016 01:58
Gamamal wrote: Nope, its 20 Really? Can you provide a construction please?
MellowMelon
29.09.2016 02:28
O.O...OO
O..O.O..
.O.....O
......O.
.O......
O.....O.
..O.O..O
OO...O.O
We show there are at most 10 bishops on one color of square. Turning all squares of one color 45 degrees, we get that they fit in a rectangle that is 8 by 7. Each pair of bishops that attack each other occupies 3 rows+columns (2 of one, one of the other) which no other bishops can occupy, and each bishop attacking no one else occupies two. So each bishop contributes at least 1.5 occupied rows+columns. There are 15 rows and columns, so there are at most 10 bishops on this color of square.
Gamamal
29.09.2016 03:09
Pretty easy for those that have seen egmo 2016 problem 3
Gamamal
29.09.2016 03:40
Alternative proof that $10$ is maximum number of white bishops (similar to EGMO 3). As before we rotate 45 degrees and we prove that an $8\times8$ board can have at most $10$ rooks if each rook shares line or columna with at most one rook. Create a bipartite graph, the columns and rows are the vertices and we add an edge between a column and a row if the corresponding square has a rook. Notice that each edge is adjacent to ar most one other edge. We conclude the connected components can be isolated vertices, an edge or a path with $3$ vertices. since there are $16$ vertices there can be at most $10$ edges.( Because $16\times 2/3<11$)
BG71
02.09.2019 14:29
Please correct my solution First note that if a pair of bishops is on the main diagonal, then the optimal disposition is when they are in the corners of this main diagonal. So we place the first four bishops on the corners. Then, for every other pair of bishops that attack each other notice that they block 3 diagonals: the one they are sharing (say /) and the other two where they belong that goes in the other direction (\). Then since there are 12+12 diagonals (remember we are not counting the main ones), then there can be at most 24/3=8 of these pairs. Hence there are at most 16 bishops, plus the 4 on the corners that's 20. For a disposition with 20 check @above.
baenanabread
04.10.2021 20:15
There can be at most 10 white bishops. To prove this is the greatest possible number, it is enough to prove that you can place at most 10 rooks on an 8x7 board such that each rook is threatened by at most one other rook, as described by others in this thread. We note that this condition is true for any given rook if and only if the rook can move in at least three directions (from among up, down, left, and right) such that they can leave the board without encountering another rook. This means the amount of possible rooks is bounded above by one third times the perimeter of the board, or $$n \le \frac{2(8+7)}{3} = 10 \text{ } \square$$ See the 2021 OMCC P3 for another problem where this idea can be applied.