Maths Olympiad Prep

Library / /40 of 144

Number theory Difficulty 7.9 National olympiad, round 2 Find the answer

For every positive integer nn with prime factorization n=i=1kpiαin = \prod_{i = 1}^{k} p_i^{\alpha_i}, define
(n)=i:  pi>10100αi.\mho(n) = \sum_{i: \; p_i > 10^{100}} \alpha_i.
That is, (n)\mho(n) is the number of prime factors of nn greater than 1010010^{100}, counted with multiplicity.

Find all strictly increasing functions f:ZZf: \mathbb{Z} \to \mathbb{Z} such that
(f(a)f(b))(ab)for all integers a and b with a>b.\mho(f(a) - f(b)) \le \mho(a - b) \quad \text{for all integers } a \text{ and } b \text{ with } a > b.

[i]

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

Solution

To solve this problem, we need to find all strictly increasing functions f:ZZ f: \mathbb{Z} \to \mathbb{Z} such that the condition given by:

(f(a)f(b))(ab) \mho(f(a) - f(b)) \le \mho(a - b)

holds for all integers a a and b b with a>b a > b .

### Step-by-step Solution:

1. Understand the Strictly Increasing Condition:
- Since f f is strictly increasing, for a>b a > b , we have f(a)>f(b) f(a) > f(b) .

2. **Analyzing \mho Function**:
- The function (n)\mho(n) computes the sum of the exponents of prime factors of n n that are greater than 10100 10^{100} .
- For the inequality (f(a)f(b))(ab)\mho(f(a) - f(b)) \leq \mho(a - b), f(a)f(b)f(a) - f(b) must have "less complex" prime factors (in the sense of being smaller or having smaller exponent multiplicities) compared to aba - b.

3. Considering a Linear Function:
- A natural guess for a strictly increasing function from Z\mathbb{Z} to Z\mathbb{Z} is a linear function of the form f(x)=Rx+c f(x) = Rx + c , where R R and c c are integers.
- For linear functions, f(a)f(b)=R(ab) f(a) - f(b) = R(a-b) .

4. **Evaluate \mho with Linear ff**:
- Substitute into the inequality: (R(ab))(ab)\mho(R(a-b)) \leq \mho(a-b).
- Given that (R(ab))\mho(R(a-b)) only considers primes greater than 1010010^{100}, and if RR does not introduce any prime factor greater than 1010010^{100}, then the inequality holds trivially.

5. Conclusion:
- Hence, any linear function f(x)=Rx+c f(x) = Rx + c with integer R R that ensures R R has no prime factors greater than 1010010^{100} satisfies the condition.
- The general form of the solution is:
f(x)=Rx+c f(x) = Rx + c
where R R and c c are integers, and the prime factors of R R are all less than or equal to 1010010^{100}.

Therefore, the strictly increasing functions satisfying the condition are expressed by:

f(x)=Rx+c \boxed{f(x) = Rx + c}
where RR is a positive integer whose prime factors do not exceed 1010010^{100}, and cc is any integer.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.