Maths Olympiad Prep

Library / /222 of 348

Combinatorics Difficulty 5.0 AIME Find the answer

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 S such that no two vertices have the same label, and the labels adjacent to any side of the square differ by at least 4 . How many possibilities are there for the subset S$ ?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 for band and drespectively(rememberthatorderof respectively (remember that order of band and d does not matter). So there are 1 \cdot 10+2 \cdot 6+ 3 \cdot 3+4 \cdot 1=35setsinthiscase.Thereforewehave sets in this case. Therefore we have 1+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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.