Maths Olympiad Prep

Library / /17 of 19

Geometry Difficulty 7.1 National Olympiad, round 2 Prove it Soviet Union

Problem:

Half the cells of a 2m×n2m \times n board are colored black and the other half are colored white. The cells at the opposite ends of the main diagonal are different colors. The center of each black cell is connected to the center of every other black cell by a straight line segment, and similarly for the white cells. Show that we can place an arrow on each segment so that it becomes a vector and the vectors sum to zero.

Solution

Solution:

Suppose we have an odd number of arbitrary points A1,A2,,A2k+1A_1, A_2, \ldots, A_{2k + 1} then we claim that if we take the vector AiAjA_iA_j for i<ji < j and jij - i odd and the vector AjAiA_jA_i for i<ji < j and jij - i even, then we get the sum of the vectors zero. We prove the claim by induction. It is true for k=3k = 3 because we have A1A2+A2A3+A3A1=0A_1A_2 + A_2A_3 + A_3A_1 = 0. So suppose it is true for 2k12k - 1. The additional vectors when we move to 2k+12k + 1 are A2kA2k+1A_{2k}A_{2k + 1}, A2i+1A2k\sum A_{2i + 1}A_{2k}, A2iA2k+1\sum A_{2i}A_{2k + 1}, A2kA2i\sum A_{2k}A_{2i} and A2k+1A2i+1\sum A_{2k + 1}A_{2i + 1}. But A2i+1A2k+A2kA2i+A2iA2k+1+A2k+1A2i+1=A2i+1A2i+A2iA2i+1=0A_{2i + 1}A_{2k} + A_{2k}A_{2i} + A_{2i}A_{2k + 1} + A_{2k + 1}A_{2i + 1} = A_{2i + 1}A_{2i} + A_{2i}A_{2i + 1} = 0, leaving the three terms A2k+1A1A_{2k + 1}A_1, A1A2kA_1A_{2k} and A2kA2k+1A_{2k}A_{2k + 1} which also sum to zero. Hence the result is true for 2k+12k + 1 and hence for all odd numbers. Thus for mnmn odd we can number the centers of the black squares in an arbitrary fashion, use the rule given for the arrow directions and then the vectors for the black squares will sum to zero. Similarly for the white squares.

However, the same general result is not true for an even number of points. So we need something else for mnmn even. Let BB be the center of the black square at one end of the main diagonal and WW be the center of the white square at the other end. Let B1,B2,,B2k+1B_1, B_2, \ldots, B_{2k + 1} be the centers of the other black squares and W1,W2,,W2k+1W_1, W_2, \ldots, W_{2k + 1} the centers of the other white squares. Take vectors BBiBB_i, WWiWW_i and for BiBjB_iB_j and WiWjW_iW_j take the same rule as before (if i<ji < j take BiBjB_iB_j if jij - i is odd and BjBiB_jB_i if jij - i is even, similarly for WiWjW_iW_j). Now consider square centers XX, YY which are symmetric with respect to the center of the rectangle (in other words the center of the rectangle is the midpoint of XYXY). The pairs (X,Y)(X, Y) are of three types: opposite colors, both white and both black. The number of both white pairs must equal the number of both black pairs since the number of white and black squares is equal. For the first type we have BX+WY=0BX + WY = 0. For the second type we have WX+WY=WBWX + WY = WB and for the third type we have BX+BY=BWBX + BY = BW. Since they are equal in number the second and third type sum to zero.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.