Hesam chose $10$ distinct positive integers and he gave all pairwise $\gcd$'s and pairwise ${\text lcm}$'s (a total of $90$ numbers) to Masoud. Can Masoud always find the first $10$ numbers, just by knowing these $90$ numbers? Proposed by Morteza Saghafian
Problem
Source: Iranian TST 2019, third exam day 1, problem 2
Tags: Combinatorial Number Theory, number theory, combinatorics
26.04.2019 11:18
Nope, consider the two set of 10 numbers $$A=\left\{ \frac{p_iP}{p_{i-1}} \mid i \in \{ 1,2,\dotsc ,10\} \right\} \text{ and } B=\left\{ \frac{p_{i-1}P}{p_i} \mid i\in \{ 1,2,\dotsc ,10\}\right\} ,$$where $p_1,p_2,\dotsc ,p_{10}$ are pairwise distinct prime numbers, indices taken modulo $10$ and $P$ denotes the product of those primes. The total 90 numbers from both sets are $$p_ip_jP\text{ and }\frac{P}{p_ip_j}\text{ for all }i\neq j\in \{ 1,2,\dotsc ,10\}.$$Hence, we can never distinguish these two choices of 10 numbers from the 90 numbers given alone.
31.03.2020 10:32
We cannot distinguish $A=\left\{ 2^{1}\times3, 2^{2}, 2^{3}, ..., 2^{10} \right\}$ and $B=\left\{2^{1}, 2^{2} \times 3, 2^{3}, ..., 2^{10} \right\}$, too. Also, you can change $2$ to a prime number $p$ and $3$ to a different prime number $q$.
22.05.2022 09:05
Another construction is to consider the sets $$ A = \{p,q,q^8,q^7,\ldots,q^2\} ~~,~~ B = \{pq,1,q^8,q^7,\ldots,q^2\} $$where $p,q$ are any two distinct primes. Observe that $$ \{\gcd(p,q),\text{lcm}(1)\} = \{1,pq\} = \{\gcd(pq,1),\text{lcm}(pq,1)\} $$Also, for any $q^i$ we have \begin{align*} \{\gcd(p,q^i),\gcd(q,q^i)\} = &\{1,q\} = \{\gcd(pq,q^i),\gcd(1,q^i)\} \\ \{\text{lcm}(p,q^i),\text{lcm}(q,q^i)\} = &\{pq^i,q^i\} = \{\text{lcm}(pq,q^i),\text{lcm}(1,q^i)\} \end{align*}Hence the set of $\gcd$ and $\text{lcm}$ for both sets $A,B$ is same. $\blacksquare$
20.10.2024 14:41
Difficult question to make a real solution, but easy to consider the answer. Cute question for combinatorial number theory ^^