Maths Olympiad Prep

Library / /137 of 520

Number theory Difficulty 6.6 National olympiad Find the answer

For any positive integer nn consider all representations n=a1++akn = a_1 + \cdots+ a_k, where a1>a2>>ak>0a_1 > a_2 > \cdots > a_k > 0 are integers such that for all i{1,2,,k1}i \in \{1, 2, \cdots , k - 1\}, the number aia_i is divisible by ai+1a_{i+1}. Find the longest such representation of the number 1992.1992.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find the longest representation of the number 19921992 as n=a1+a2++akn = a_1 + a_2 + \cdots + a_k where a1>a2>>ak>0a_1 > a_2 > \cdots > a_k > 0 and each aia_i is divisible by ai+1a_{i+1}, we can use the following steps:

1. Initial Setup:
Let mi=aiai+1m_i = \frac{a_i}{a_{i+1}} and ak+1=1a_{k+1} = 1. This implies that each aia_i is a multiple of ai+1a_{i+1}.

2. Representation in Terms of Fractions:
We can express nn in terms of these fractions:
na1=1+1m1+1m1m2++1m1m2mk \frac{n}{a_1} = 1 + \frac{1}{m_1} + \frac{1}{m_1 m_2} + \cdots + \frac{1}{m_1 m_2 \cdots m_k}
Let ni=j=i+1kajn_i = \sum_{j=i+1}^k a_j. Then,
niai=1mi+1mimi+1++1mimi+1mk \frac{n_i}{a_i} = \frac{1}{m_i} + \frac{1}{m_i m_{i+1}} + \cdots + \frac{1}{m_i m_{i+1} \cdots m_k}

3. **Finding mim_i**:
To find mim_i, we need the smallest integer mim_i such that miainim_i \geq \frac{a_i}{n_i}. This can be written as:
mi=aini m_i = \left\lceil \frac{a_i}{n_i} \right\rceil

4. Algorithm for Representation:
- Start with a1a_1 such that n2<a1n\frac{n}{2} < a_1 \leq n.
- Denote n1=na1n_1 = n - a_1.
- Recursively define mi=ainim_i = \left\lceil \frac{a_i}{n_i} \right\rceil, ai+1=aimia_{i+1} = \frac{a_i}{m_i}, and ni+1=niai+1n_{i+1} = n_i - a_{i+1}.
- Continue this process until nk=0n_k = 0.

5. Proof of Termination:
Let niai=ri=PiQi\frac{n_i}{a_i} = r_i = \frac{P_i}{Q_i} where (Pi,Qi)=1(P_i, Q_i) = 1. If Pi=1P_i = 1, we take the last mi=Qim_i = Q_i and the process stops. Otherwise, mi=QiPim_i = \left\lceil \frac{Q_i}{P_i} \right\rceil, and:
PiQi1mi=PimiQimiQi \frac{P_i}{Q_i} - \frac{1}{m_i} = \frac{P_i m_i - Q_i}{m_i Q_i}
Clearly, 0<Pi+1=PimiQigcd(mi,Qi)<Pi0 < P_{i+1} = \frac{P_i m_i - Q_i}{\gcd(m_i, Q_i)} < P_i and Qi+1=Qimigcd(mi,Qi)Q_{i+1} = \frac{Q_i m_i}{\gcd(m_i, Q_i)}. Therefore, the process will eventually stop.

6. **Application to 19921992**:
- Start with a1=1992a_1 = 1992.
- a2=19922=996a_2 = \frac{1992}{2} = 996.
- a3=9962=498a_3 = \frac{996}{2} = 498.
- a4=4982=249a_4 = \frac{498}{2} = 249.
- a5=2493=83a_5 = \frac{249}{3} = 83.
- a6=8383=1a_6 = \frac{83}{83} = 1.

Thus, the longest representation of 19921992 is:
1992=1992+996+498+249+83+1 1992 = 1992 + 996 + 498 + 249 + 83 + 1

The final answer is 1992=1992+996+498+249+83+1\boxed{1992 = 1992 + 996 + 498 + 249 + 83 + 1}.

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.