On the chessboard, $ 32$ black pawns and $ 32$ white pawns are arranged. In every move, a pawn can capture another pawn of the opposite color, moving diagonally to an adjacent square where the captured one stands. White pawns move only in upper-left or upper-right directions, while black ones can move in down-left or in down-right directions only; the captured pawn is removed from the board. A pawn cannot move without capturing an opposite pawn. Find the least possible number of pawns which can stay on the chessboard.
Problem
Source: Russian 2007
Tags: inequalities, combinatorics proposed, combinatorics
mszew
04.09.2007 20:51
Color the chess board black and white as the usual one, notice that each pawn can eat only one pawn from each file (no moving backwards) then the minimum is 8 from the different rows.
Put the white pawns in the bottom 4 white cells and the black pawns in the other 28 white cells, all those white pawns can eat those 28 black pawns. Similarly with the black cells.
quangchuc
08.09.2007 11:21
mszew wrote:
Color the chess board black and white as the usual one, notice that each pawn can eat only one pawn from each file (no moving backwards) then the minimum is 8 from the different rows.
Put the white pawns in the bottom 4 white cells and the black pawns in the other 28 white cells, all those white pawns can eat those 28 black pawns. Similarly with the black cells.
I think this answer is fasle. The answer must be 2.
lorincz
08.09.2007 15:33
Yes you are right, the answer is $ 2$. The coloring of the table with black & white only proves that the number is $ \ge2$, because one pawn must remain on a black and one must remain on a white square. And we have this example (0 - Black, 1 - White): 00000000 01111110 11111111 00111100 11000011 00000000 10000001 11111111 Take one color (red for example, so now we work just with the red pawns). First we capture with the 1-s at the bottom (without the corner) the 0-s until the diagonal. Then we capture with the 0-s at left the 1-s until the diagonal. Then we capture with the 1 in the corner the 0-s until the middle. We do the same with the other colors (blue, green, black). So we will have(* - Empty): ******** ******** ******** ***00*** ***11*** ******** ******** ******** Two more moves and we have $ 2$ pawns .