Problem:
In a list of one or more consecutive integers, there are p multiples of 2 and q multiples of 3. How many ordered pairs (p,q) are possible for this list if p and q are between 0 and 100, inclusive?
Answer Choices:
A. 232
B. 233
C. 234
D. 235
E. 236
Solution:
Let the list have length L=6k+r with 0β€rβ€5. Any 6 consecutive integers contain exactly 3 multiples of 2 and 2 multiples of 3. So the first 6k integers of the list contribute (3k,2k), and the last r integers contribute some pair (u,v) that depends on where they start:
(p,q)=(3k+u, 2k+v).
The possible (u,v) for each r. Checking the six possible starting residues mod 6:
r=0r=1r=2r=3r=4r=5β: (0,0): (0,0), (1,0), (0,1), (1,1): (1,0), (1,1): (1,1), (2,1): (2,1), (2,2): (2,1), (3,1), (2,2), (3,2)β
For example, with r=5, the list 1,2,3,4,5 gives (2,1), 4,5,6,7,8 gives (3,1), 3,4,5,6,7 gives (2,2), and 2,3,4,5,6 gives (3,2).
Since (3k,2k)+(3,2)=(3(k+1),2(k+1))+(0,0), the pair (3,2) adds nothing new. So the possible pairs are exactly
(3k,2k)+(u,v),(u,v)β{(0,0),(1,0),(0,1),(1,1),(2,1),(2,2),(3,1)},kβ₯0,
and these 7 offsets give different pairs for different k (two offsets never differ by a multiple of (3,2)). Note that (0,0) is achieved by the one-term list 1.
Counting. The condition qβ€100 is automatic whenever pβ€100, because qβ€2k+2 and 3kβ€100 forces kβ€33.
- For 0β€kβ€32, we have 3k+3β€99, so all 7 offsets work: 33β
7=231 pairs.
- For k=33, 3k=99, so we need uβ€1: the offsets (0,0),(1,0),(0,1),(1,1) give 4 pairs.
The total is 231+4=(D) 235.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions