Several knights are arranged on an infinite chessboard. No square is attacked by more than one knight (in particular, a square occupied by a knight can be attacked by one knight but not by two). Sasha outlined a $ 14\times 16$ rectangle. What maximum number of knights can this rectangle contain?
Problem
Source: Tuymaada 2007, Problem 7
Tags: geometry, rectangle, analytic geometry, combinatorics proposed, combinatorics
04.08.2007 19:38
I know that the right answer is 32 knights.And i know one of the solutions,but i'm interesting in other solutions.I was surprised that nobody replied to this problem.
23.08.2011 21:28
if you have a solution please post it. I tried for a time to do it... I obtained only is <36. if you can post also the model ... I am very curious for the example that you'll give.
03.09.2011 02:01
We prove the following, which immediately establishes the upper bound of 32: -- no 4x7 rectangle can contain more than 2 knights located on the squares of the same color (i.e. 4x7 can not contain more than 4 knights total; we assume that infinite chessboard is colored in two colors in a standard way) First, consider any 5x5 square and put a knight in the upper left corner. The only two spaces inside the square of the same color as that corner where a knight can be placed so that these two knights do not attack a square in common are the center of the square and the lower right corner. In other words, if two knights of the same color satisfy conditions of the problem then either they are in opposite corners of a 3x3, opposite corners of a 5x5 or at least one of the differences of their coordinates is 5 or more. Second, notice that if knights A and B are in the opposite corners of a 3x3 and so are knights B and C then either A,B,C are collinear and are thus two corners and a center of a 5x5 or knights A and C are in violation of the conditions of the problem. Now, for the sake of contradiction, assume that a 4x7 rectangle contains 3 knights of the same color. Each of 7 columns has two possible spots for a knight and at most one of them can be occupied; therefore all 3 knights A,B,C have different x-coordinate, call them x,y,z in increasing order. Since a 5x5 square does not fit inside a 4x7 rectangle, it is not possible for configuration described in the previous paragraph to occur; therefore either A and B or B and C are at least 5 apart horizontally (they can not fit inside a 4x7 and be 5 apart vertically). WLOG, assume that these are knights A and B. That implies that knight B is in the two right-most columns of the 4x7 and then knight C does not have a place. (the closest it can be to B is in the other corner of a 3x3 that B is in and to the right of it and that would put it one column outside of our 4x7 rectangle). 16 knights of one color can be put inside the 16x14 as follows (assume excel-type cell numbering; rows 1-16, columns A-N): A3, C1 A11, C9, E7, G5, I3, K1 D16, F14, H12, J10, L8 L16, N14 ... with the other 16 knights on the different color in similar way (L1, N3, etc).