2022 AIME II Problem 8

Attempt Problem 8 of the 2022 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2022 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

8.

Find the number of positive integers n600n \le 600 whose value can be uniquely determined among all positive integers when the values of n4,\left\lfloor \frac{n}{4} \right\rfloor, n5,\left\lfloor \frac{n}{5} \right\rfloor, and n6\left\lfloor \frac{n}{6} \right\rfloor are given, where x\lfloor x \rfloor denotes the greatest integer less than or equal to the real number x.x.

Answer: 80
Concepts:floor and ceiling functionsdivisibilitymodular arithmetic
Difficulty rating: 2840
Solution:

The set of positive integers sharing a given triple (n4,n5,n6)\left(\left\lfloor \frac{n}{4} \right\rfloor, \left\lfloor \frac{n}{5} \right\rfloor, \left\lfloor \frac{n}{6} \right\rfloor\right) is an intersection of three intervals, hence a block of consecutive integers. So nn is uniquely determined exactly when neither n1n - 1 nor n+1n + 1 gives the same triple: some floor must drop at n1,n - 1, meaning 4,5,4, 5, or 66 divides n,n, and some floor must jump at n+1,n + 1, meaning 4,5,4, 5, or 66 divides n+1.n + 1.

Since nn and n+1n + 1 cannot both be even, the divisor pairs for (n,n+1)(n, n + 1) are (4,5),(4, 5), (5,4),(5, 4), (5,6),(5, 6), and (6,5).(6, 5). Working modulo 60:60: 4n,  5n+14 \mid n,\; 5 \mid n + 1 gives n4,24,44;n \equiv 4, 24, 44; 5n,  4n+15 \mid n,\; 4 \mid n + 1 gives n15,35,55;n \equiv 15, 35, 55; 5n,  6n+15 \mid n,\; 6 \mid n + 1 gives n5,35;n \equiv 5, 35; and 6n,  5n+16 \mid n,\; 5 \mid n + 1 gives n24,54.n \equiv 24, 54. The union is the 88 residues {4,5,15,24,35,44,54,55}\{4, 5, 15, 24, 35, 44, 54, 55\} modulo 60.60.

Each residue occurs 1010 times among 1n600,1 \le n \le 600, so the count is 810=80.8 \cdot 10 = 80. (Note n=600n = 600 fails: 601601 is divisible by none of 4,5,6,4, 5, 6, so 601,602,603601, 602, 603 share 600600's triple.)

← Problem 7#7
Full Exam

Problem 8 in Other Years