Problem:
Let S be the set {1,2,3,…,19}. For a,b∈S, define a≻b to mean that either 0<a−b≤9 or b−a>9. How many ordered triples (x,y,z) of elements of S have the property that x≻y,y≻z, and z≻x ?
Answer Choices:
A. 810
B. 855
C. 900
D. 950
E. 988
Solution:
Consider the elements of S as integers modulo 19. Assume a≻b. If a>b, then a−b≤9. If a<b, then b−a>9; that is b−a≥10 and so (a+19)−b≤9. Thus a≻b if and only if 0<(a−b)(mod19)≤9.
Suppose that (x,y,z) is a triple in S×S×S such that x≻y,y≻z, and z≻x. There are 19 possibilities for the first entry x. Once x is chosen, y can equal
x+i for any i,1≤i≤9. Then z is at most x+9+i and at least x+10, so once y is chosen, there are i possibilities for the third element z.
The number of required triples is equal to 19(1+2+⋯+9)=19⋅21⋅9⋅10= 19⋅45=855
The problems on this page are the property of the MAA's American Mathematics Competitions