Maths Olympiad Prep

Library / /699 of 740

, 2018

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:
Let SS be a subset with four elements chosen from {1,2,,10}\{1,2, \ldots, 10\}. Michael notes that there is a way to label the vertices of a square with elements from SS such that no two vertices have the same label, and the labels adjacent to any side of the square differ by at least 44. How many possibilities are there for the subset SS?
Proposed by: James Lin

Solution

Solution:
Let the four numbers be a,b,c,da, b, c, d around the square. Assume without loss of generality that aa is the largest number, so that a>ba > b and a>da > d. Note that cc cannot be simultaneously smaller than one of b,db, d and larger than the other because, e.g. if b>c>db > c > d, then a>b>c>da > b > c > d and ad+12a \geq d + 12. Hence cc is either smaller than bb and dd or larger than bb and dd.

Case 1: cc is smaller than bb and dd. Then we have ac8a - c \geq 8, but when ac=8a - c = 8, we have b=c+4=db = c + 4 = d, so we need ac=9a - c = 9, giving the only set {1,5,6,10}\{1, 5, 6, 10\}.

Case 2: cc is larger than bb and dd. Since a>ca > c and b,db, d are both at most c4c - 4, the range of possible values for cc is {6,7,8,9}\{6, 7, 8, 9\}. When c=9,8,7,6c = 9, 8, 7, 6, there are 1,2,3,41, 2, 3, 4 choices for aa respectively and (52),(42),(32),(22)\binom{5}{2}, \binom{4}{2}, \binom{3}{2}, \binom{2}{2} for bb and dd respectively (remember that order of bb and dd does not matter). So there are 110+26+33+41=351 \cdot 10 + 2 \cdot 6 + 3 \cdot 3 + 4 \cdot 1 = 35 sets in this case.

Therefore we have 1+35=361 + 35 = 36 possible sets in total.

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.