and 
.
Let 
.
:![\[
2 \left( 5^x + 6^x - 3^x \right) = 7^x + 9^x.
\]](http://latex.artofproblemsolving.com/f/b/6/fb6d5ebb4f448d8eeb73cce3288fea3a56d7f528.png)
Y by Davi-8191, tenplusten, Adventure10, and 1 other user
2500 chess kings have to be placed on a 
chessboard so that
(i) no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex);
(ii) each row and each column contains exactly 25 kings.
Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.)
Proposed by Sergei Berlov, Russia
chessboard so that(i) no king can capture any other one (i.e. no two kings are placed in two squares sharing a common vertex);
(ii) each row and each column contains exactly 25 kings.
Find the number of such arrangements. (Two arrangements differing by rotation or symmetry are supposed to be different.)
Proposed by Sergei Berlov, Russia
matrix 
.
iff there is a king in the 
t
t
and 
.
equals either 
or 
.
where there are 
'
'
.![\[\begin{bmatrix}b_{ij}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j+1}\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix}\]](http://latex.artofproblemsolving.com/c/f/1/cf10297c1c0fa3a126c5eec52071dfdb7a665a0a.png)
are in 
and 
rectangles. Since ![\[\left\lfloor \frac{i-1+1}{2}\right\rfloor+\left\lfloor \frac{99-i+1}{2}\right\rfloor=49\]](http://latex.artofproblemsolving.com/3/2/a/32aa10fc890311322fcd4fe87aaafe4c3989c125.png)
kings. Hence, 
.
and 
which sum to ![\[v_1=(1,0,\hdots, 1,0,0,0,\hdots, 0,0)\\
v_2=(0,1,\hdots, 0,1,0,0,\hdots, 0,0)
\\v_3=(0,0,\hdots, 0,0,1,0,\hdots, 1,0)\\
v_4=(0,0,\hdots, 0,0,0,1,\hdots, 0,1)\]](http://latex.artofproblemsolving.com/2/0/b/20b0b85380fef136a67acd93869ac479235f7e94.png)
must also be one of those vectors.
,
and 
.
for all odd 
.
,
.
if 
is an even number and 
if 
is an even number. By the analogous lemma for columns, 
if 
if 
,
,
.
squares contains at most one king, and the whole pillar must contain 
or 
,
or 
each of 
switch and one 
switch, and these must be after the first 
.
square sections (so a 
grid of 
or 
,
and 
'
because of the last condition.
square formed by two adjacent rows and two adjacent columns. If the columns are 
from left to right and the rows are 
from top to bottom, then the top left and bottom right 
and the rows are 
,
and 
or 
and 
.
,
is tight. To see why, divide the board into 
as shown:![[asy]size(6cm);
usepackage("skak");
for(int i=0;i<3;++i){draw((0,i)--(2,i));draw((i,0)--(i,2));}
for(int i=0;i<3;++i){draw((3,i)--(5,i));draw((i+3,0)--(i+3,2));}
for(int i=0;i<3;++i){draw((6,i)--(8,i));draw((i+6,0)--(i+6,2));}
for(int i=0;i<3;++i){draw((9,i)--(11,i));draw((i+9,0)--(i+9,2));}
label("$\symking$",(0.5,1.5));label("$\symking$",(4.5,1.5));label("$\symking$",(6.5,0.5));label("$\symking$",(10.5,0.5));
label("LU",(1,0),S);label("RU",(4,0),S);label("LD",(7,0),S);label("RD",(10,0),S);
[/asy]](http://latex.artofproblemsolving.com/4/9/f/49fa8340fa05881758cb20c122f9c09c30988535.png)
thingy). The second column has exactly 
type (here 
can be 
or 
)
rows. In an analogous fashion, we can prove 
and others are ![[asy]size(7cm);usepackage("contour", "outline");
texpreamble("\contourlength{1.7pt}");
draw((0,0)--(0,-5)--(5,-5)--(5,0)--cycle);
draw((0,-1)--(5,-1)^^(0,-2)--(5,-2)^^(1,0)--(1,-5)^^(2,0)--(2,-5));
draw((0,-0.5)--(5,-0.5)^^(0,-1.5)--(5,-1.5)^^(0.5,0)--(0.5,-5)^^(1.5,0)--(1.5,-5),dotted);
label("R"+"$\rightarrow$",(0,-1.5),W);label("L"+"$\rightarrow$",(0,-0.5),W);
label("\contour{white}{RD}",(0.5,-1.5));label("\contour{white}{RU}",(1.5,-1.5));
draw(brace((-1,-5),(-1,0)));label(rotate(90)*"25 L's,25 R's",(-2,-2.5));
draw(brace((0,0.2),(5,0.2)));label("25 U's, 25 D's",(2.5,1.2));
[/asy]](http://latex.artofproblemsolving.com/a/0/5/a058a7e76c0fddcd6aa38f1b00828d9acf0649d0.png)
![[asy]usepackage("skak");size(6cm);draw((0,0)--(0,-5)--(5,-5)--(5,0)--cycle);
draw((0,-2)--(5,-2)^^(2,0)--(2,-5));
label("R",(0,-1.8),W);label("L",(0,-2.2),W);
label("D",(1.8,0),N);label("U",(2.2,0),N);
label("$\symking$",(2,-2),NW);label("$\symking$",(2,-2),SE);
[/asy]](http://latex.artofproblemsolving.com/b/b/2/bb2f4cac31466a9907980fd362d40bff6a4995ed.png)
in that order. In this case, if there's a ![[asy]usepackage("skak");size(6cm);draw((0,0)--(0,-5)--(5,-5)--(5,0)--cycle);
draw((0,-2)--(5,-2)^^(2,0)--(2,-5));
label("L",(0,-1.8),W);label("R",(0,-2.2),W);
label("U",(1.8,0),N);label("D",(2.2,0),N);
label("$\symking$",(2,-2),NE);label("$\symking$",(2,-2),SW);[/asy]](http://latex.artofproblemsolving.com/5/f/0/5f0f810a62847effe833840b75ba20cbf638e86a.png)
which is again bad. So the columns are 
.
board (the other one is simply a reflection of this):![[asy]size(5cm);usepackage("skak");
for(int i=0;i<9;++i){draw((i,0)--(i,8)^^(0,i)--(8,i));}
pair[] a={(2,1),(4,1),(2,3),(4,3),(1,5),(3,5),(1,7),(3,7),(6,2),(8,2),(6,4),(8,4),(5,6),(7,6),(5,8),(7,8)};
for(pair k:a){label("$\symking$",k+(-0.5,-0.5));}
[/asy]](http://latex.artofproblemsolving.com/f/1/8/f1870c548977c3ffd746dfe7ca6d76904c7f3956.png)
.
must have exactly 50 ones and at least one zero between any two adjacent ones. There is a set 
are both 
for any 
.
for any 
.
and 
.
is all zero, so 
,
and at least 49 
.
not belonging to either of them by the lemma, which is impossible.) So we conclude that there are exactly 49 of each that respectively form consecutive blocks, plus one 
through 
are 
through 
are 
.
and 
both need to have at least 25 ones, the only possible 
with the two consecutive zeros in the exact middle. This determines the entire state of the 100-by-100 grid. Because we have WLOGed one case out of two, we conclude that there are two valid arrangements in total.
cell contains no king, by pigeonhole some other 
,
and 
.
signifies that the king in some given cell is in the bottom left square. Define the \textit{signature} of a row of cells to be the string consisting of the 
-
,
.
and 
as substrings. The column signature contains at least one 
and 
as a substring. If there is an 
)
and 
and its reverse, while the column signature is one of 
and its reverse. If the row signature is 
,
;
,
.
or 
.
pieces.
instances of this. Let there be 
instances of them being the same type too. We count the number of kings in the second row (row defined in the normal sense here) as 
.
.
can never be above 
.
always has to be above 
.
must be neighbours. By claim 1 we know that the whole grid is filled with rows being the copies of the first one, or the first row with kings translated upwards. At some point the row must be translated ; we take a look at the adjacent 
types. By assuming the contrary one can easily see that two kings are neighbours in that case 
Divide the chessboard into 2500 
where 
of these 
of the leftmost wall, we can label it as either 
lies on (left or right). Similarly, for each box of the topmost layer, we can label each box as either 
where 
then every subsequent layer must follow the same labelling. Similarly for leftmost wall and subsequent walls.
Let 
denote the label of the 
layer. Then, if 
then 
lest the two kings then attack one another. As a result, 25 of the subsequent layer is fixed as 
and 
Similarly for the walls.
and 
then there can be no 
otherwise box 
and 
attack one another. Similarly, if 
and 
then there can be no 
As a result, if there ever exists a sequence of 
then the corresponding labelling of the wall must be 
Contradiction. Hence, it must be that 
occurs only once, proving the claim. Same goes for 
and 
then it must be true that 
and 
Likewise, if 
and 
then it must be true that 
and 
Hence, there's only two possible arrangements.
sparse if no two elements are consectutive. Note that only sparse set containing 
is odd numbers. Now consider the set 
of all rows which are same as some row containing 
similarly. Because of our previous observations, we obtain any number in a row of 
.
.
.
must be 
in some order. Lets assume 
t
.
and the 
.
chessboard into 2500 
blocks, each block cannot contain more than one king due to rule (i). However, as we need 
,
squares with R. However, if we rotate the large 100x100 square board 180 degrees and apply the. same argument, we obtain that there are at least 
squares with L. Thus, there are 
)
,
,
,
.
