Look like horse steps
Two chessman at lattice points (a,b) and (c,d) form a "pseudohorse pair" if and only if one of abs(a-b) and abs(c-d) is 1 and the other is an integer greater than 1. For example, (2,5) forms a "pseudohorse pair" with (3,8) but not with (10,5) nor (3,4). Now, Hermes place k chessman such that any 2 of them form a "pseudohorse pair".
Find the maximum possible value of k.
The answer is 4.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
First consider that every "pseudohorse pair" lies on either adjacent rows or adjacent columns, so the number of "pseudohorse pairs" must not exceed number of pairs of chessman lying on adjacent rows or columns. Then, by definition of "pseudohorse pair", none of the k chessman lie on the same row or column, so there are exactly k rows with chessman, and each of them has exactly 1 chessman on it, so there are at most k-1 pairs of chessman lying on adjacent rows (when the k chessman lie on k adjacent rows). Likewise, there are at most k-1 pairs of chessman lying on adjacent columns. As there are kC2=k(k-1)/2 pairs of "pseudohorse pairs", we have
k(k-1)/2 ≤ #pairs of chessman lying on adjacent rows or columns = 2(k-1)
Which is equivalent to k^2-5k+4 ≤ 0. Hence 4≤k.
The configuration of 4 chessman at (2,1), (1,3), (4,2), (3,4) satisfy the requirement.