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
Small Hint:

The integers sharing a given triple of floor values form a block of consecutive integers, so nn is determined exactly when its block has size 11

Big Hint:

The block has size 11 exactly when each of nn and n+1n + 1 is divisible by at least one of 4,5,6.4, 5, 6. Count such nn in one period of 60.60.

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: 44 dividing nn and 55 dividing n+1n + 1 gives n4,24,44;n \equiv 4, 24, 44; 55 dividing nn and 44 dividing n+1n + 1 gives n15,35,55;n \equiv 15, 35, 55; 55 dividing nn and 66 dividing n+1n + 1 gives n5,35;n \equiv 5, 35; and 66 dividing nn and 55 dividing n+1n + 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