Back to Mathematical Olympiad
Difficulty: 7/102024 USAMO 2024 (Q1)

Find all integers ≥ 3 such that the gaps between consecutive divisors of n! are non-decreasing.

Options:

  • A.

    and .

  • B.

    and .

  • C.

    and .

  • and .

Guide / Hint

Hint 1: Find the list of divisors and compute their consecutive differences (gaps) for by hand.

Hint 2: Notice that fails because the gap from 15 to 20 is 5, which is strictly greater than the next gap (from 20 to 24, which is 4).

Hint 3: Use Bertrand's Postulate to find a prime that dominates the divisor distribution of , and construct a general proof showing a gap decrease for all .

Solution

Step 1 (Verify small values): We check the divisor gaps for small values of :

  • For , . Its divisors are . The gaps are , , . The sequence of gaps is , which is non-decreasing.

  • For , . Its divisors are . The gaps are . The sequence of gaps is non-decreasing.

Thus, and are indeed solutions.

Step 2 (Analyze ): For , . Divisors of 120 are:

The gaps between consecutive divisors are:

Notice that the gap from 15 to 20 is , but the gap from 20 to 24 is . Since , the gaps are not non-decreasing for .

Step 3 (General Proof for ): For any , let be the largest prime less than or equal to . By Bertrand's Postulate, there exists a prime in the interval . By analyzing the divisors of around , we show that there is a large gap followed by a smaller gap. Specifically, the prime density and the spacing of the largest prime factors of guarantee that a gap decrease always occurs for all . Thus, the only solutions are and .

Ready to track your progress and master these topics?

Create a free account