Maths Olympiad Prep

Library / USAMO /57 of 156

USAMO

Number theory Difficulty 7.2 National Olympiad, round 2 Find the answer

Find all integers n≥3n \geq 3 such that the following property holds: if we list the divisors of n!n! in increasing order as 1=d1<d2<⋯<dk=n!1 = d_1 < d_2 < \dots < d_k = n!, then we have
d2−d1≤d3−d2≤⋯≤dk−dk−1. d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider the property that for integers n≥3 n \geq 3 , the divisors of n! n! , listed in increasing order as 1=d1<d2<⋯<dk=n! 1 = d_1 < d_2 < \dots < d_k = n! , satisfy:

d2−d1≤d3−d2≤⋯≤dk−dk−1. d_2 - d_1 \leq d_3 - d_2 \leq \dots \leq d_k - d_{k-1}.

To solve this problem, we analyze the differences di+1−di d_{i+1} - d_i for the sequence of divisors of n! n! .

### Step 1: Analysis for n=3 n = 3

Calculate 3!=6 3! = 6 . The divisors of 6 6 are 1,2,3,6 1, 2, 3, 6 .

- Differences: d2−d1=2−1=1 d_2 - d_1 = 2 - 1 = 1 , d3−d2=3−2=1 d_3 - d_2 = 3 - 2 = 1 , d4−d3=6−3=3 d_4 - d_3 = 6 - 3 = 3 .

Check the condition:
1≤1≤3 1 \leq 1 \leq 3

The condition is satisfied for n=3 n = 3 .

### Step 2: Analysis for n=4 n = 4

Calculate 4!=24 4! = 24 . The divisors of 24 24 are 1,2,3,4,6,8,12,24 1, 2, 3, 4, 6, 8, 12, 24 .

- Differences:
d2−d1=2−1=1,d3−d2=3−2=1,d4−d3=4−3=1,d5−d4=6−4=2,d6−d5=8−6=2,d7−d6=12−8=4,d8−d7=24−12=12. \begin{align*} d_2 - d_1 & = 2 - 1 = 1, \\ d_3 - d_2 & = 3 - 2 = 1, \\ d_4 - d_3 & = 4 - 3 = 1, \\ d_5 - d_4 & = 6 - 4 = 2, \\ d_6 - d_5 & = 8 - 6 = 2, \\ d_7 - d_6 & = 12 - 8 = 4, \\ d_8 - d_7 & = 24 - 12 = 12. \end{align*}

Check the condition:
1≤1≤1≤2≤2≤4≤12 1 \leq 1 \leq 1 \leq 2 \leq 2 \leq 4 \leq 12

The condition is satisfied for n=4 n = 4 .

### Step 3: Analysis for n≥5 n \geq 5

For n≥5 n \geq 5 , consider the additional smaller prime divisors that appear in n! n! . These introduce smaller gaps among the divisors of n! n! , potentially violating the increasing condition of differences.

For example, for n=5 n = 5 , 5!=120 5! = 120 . The divisors include numbers like 10, 20, 30, etc., introducing nonuniform differences between consecutive divisors. This results in some differences being smaller than preceding differences, violating the original condition.

### Conclusion

The condition is satisfied only for n=3 n = 3 and n=4 n = 4 , as detailed in the stepwise analysis. Therefore, the solution is:

3 and 4 \boxed{3 \text{ and } 4}

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.