Maths Olympiad Prep

Library / /9 of 22

Combinatorics Difficulty 6.2 National olympiad Prove it South Africa

Consider 1616 points arranged as shown, with horizontal and vertical distances of 11 between consecutive rows and columns. In how many ways can one choose four of these points such that the distance between every two of those four points is strictly greater than 22?

Figure 1

Solution

Label the sixteen points AA, BB, CC, \ldots, PP, as shown below in Figure 1:

Figure 1

A selection of four points satisfying the condition that the distance between every two of the four points is greater than 22, will be called a valid selection.

Let us first consider a valid selection which includes one of the points of the inner square FGKJFGKJ. Clearly, only one of these points (FF, GG, KK, JJ) can be used; say we select FF. The only points from the outer square ABCDHLPONMIEABCDHLPONMIE at distance more than 22 from FF, are DD, LL, PP, OO and MM. If we choose either LL or OO, then there are not enough points left among the remaining ones on the outer square to form a valid selection. We are therefore forced to select DD, PP and MM, together with FF, to obtain a valid selection. Similarly, by symmetry, there are three further valid selections that contain points from the inner square: {G,P,M,A}\{G, P, M, A\}, {K,M,A,D}\{K, M, A, D\} and {J,A,D,P}\{J, A, D, P\}.

All that remains, is to consider valid selections using only points from the outer square. We note that the only way to choose two points in a valid selection from the same side of the outer square, is to choose two corner points, such as AA and DD. But then the only option for the other two points in the valid selection would be to choose the other two corner points of the outer square, PP and MM, giving the valid selection {A,D,P,M}\{A, D, P, M\}. Moving away from corner points, leaves us with the two remaining valid selections (where only one point from each of the sides of the outer square is selected), namely {B,H,O,I}\{B, H, O, I\} and {C,L,N,E}\{C, L, N, E\}.

Hence, there are seven possible valid selections.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.