2020 OIM Problems/Problem 4

Problem

Prove that there exists a set $C$ of 2020 positive and distinct integers that simultaneously fulfills the following properties:

When we calculate the greatest common factor of every two elements of $C$ , we obtain a list of numbers that are all different.

When you calculate the least common multiple of every two elements of $C$ , you get a list of numbers that are all different.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

Let the terms be $\{c_1,c_2,\ldots,c_n\}$ . We wish to make each $c_i$ a product of distinct primes (so no square factors) such that every $c_i$ shares exactly one prime factor with each other $c_i$ . To do this, distribute $1999$ distinct primes to $c_1$ 's factorization and one each to the remaining $c_i$ . For $c_2$ , distribute $1998$ distinct primes (distinct from the previous primes as well) to $c_2$ 's factorization and one each to the remaining $c_i$ (not including $c_1$ ). Continue this pattern; by construction, it is clear that every pair of terms will only share one prime, and this prime is distinct for all pairs (also by construction). Thus the first condition is satisfied.

For the second condition, assume for the sake of contradiction that for some two distinct pairs of elements of the set, their least common multiple is the same. This can fall into one of two cases:

If one element is shared between the two sets: let the shared element be $c_k$ and the other two $c_a$ and $c_b$ ; then $\text{lcm}(c_k,c_a)=\text{lcm}(c_k,c_b)$ . However, notice that $c_a$ and $c_b$ only share one prime by construction; since each $c_i$ is constructed to have $1999$ prime factors, then there are $1998$ unshared primes each between $c_a$ and $c_b$ . Additionally, only one prime is shared between $c_a$ and $c_k$ and between $c_k$ and $c_b$ , so there are many more unshared primes that are distinct to each least common multiple, which is a contradiction.

If no element is shared between the two sets: let the elements be $c_a,c_b$ and $c_m,c_n$ . Then we must have $\text{lcm}(c_a,c_b)=\text{lcm}(c_m,c_n)$ . However, pairwise there may only be $6$ shared primes in total while there are a total of $7996$ prime factors amongst the four elements. Clearly, this means that both sides will have distinct primes, which is also a contradiction.

In both cases above, the contradiction comes from the fact that if one side contains a prime that the other side is not divisible by, then the $\text{lcm}$ of the first side will also be divisible by the prime but the $\text{lcm}$ of the second side will not, which is not possible. Therefore, the second condition is satisfied, and we are done.

~ eevee9406

Page

Toolbox

Search

2020 OIM Problems/Problem 4

Problem

Solution

See also