Library / /226 of 397

, 2023

Number theory Difficulty 6.0 National Olympiad Prove it Taiwan

Let $Q$ be a set of prime numbers, not necessarily finite. For a positive integer $n$ consider its prime factorisation; define $p(n)$ to be the sum of all the exponents and $q(n)$ to be the sum of all the exponents corresponding only to primes in $Q$ . A positive integer $n$ is called special if $p(n) + p(n + 1)$ and $q(n) + q(n + 1)$ are both even integers. Prove that there is a constant $c > 0$ independent of the set $Q$ such that for any positive integer $N > 100$ , the number of special integers in $[1, N]$ is at least $cN$ .
(For example, if $Q = \{3, 7\}$ , then $p(42) = 3$ , $q(42) = 2$ , $p(315) = 4$ , $q(315) = 3$ )

Solution

Fact 1: For any 5 integers, there are at least 2 of them that have same parity for both $p$ and $q$ by the pigeonhole principle.

Fact 2: $p(m) + p(n) \equiv p(m/d) + q(m/d) \pmod{2}$ if $d \mid \gcd(m, n)$ .

Consider the set
$A_k = \{72k, 72k + 6, 72k + 8, 72k + 9, 72k + 12\}$
By Fact 1, for some $n_1, n_2 \in A_k$ , $p(n_1) \equiv p(n_2) \pmod{2}$ and $q(n_1) \equiv q(n_2) \pmod{2}$ .

Observe that the set is constructed in a way so that $d = n_1 - n_2 \mid \gcd(n_1, n_2)$ , so by Fact 2, $n_1$ is special. That is, at least one number in $S_k = \{\frac{n_i}{n_j-n_i} \mid j > i\}$ .

Clearly, $\bigcup_{k \le (N-12)/72} S_k \subseteq [1, N]$ and every number can only belong to at most 10 different $S_k$ , thus $[1, N]$ contains at least $\lfloor \frac{N-12}{720} \rfloor$ special numbers. Plus the fact that $S_1 \subset [1, 100]$ , so there is at least one special number in $[1, 100]$ , we know such constant $c > 0$ exists.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.