Maths Olympiad Prep

Track / Stage 5 / 304 of 400 #1384 of 2444

Problem 1384

AIME late
Combinatorics Difficulty 5.7 Prove it HMMT November · United States · 2018

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

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.