Hi! Let’s p_i is the i-th prime number. Consider two cases: 1. n is more or equal to p_6. Then let’s consider set {p_1p_2p_3, p_1p_4p_5, p_2p_4p_6, p_3p_5p_6}. It’s easy to see that gcd of any two numbers from this set is equal to p_i, but product of remaining two isn’t divisible by p_i. Therefore, if n is more than 12 (p_6=13), then there exist not “good” set. 2. n is less than p_6 Let’ s prove that then all sets are good. Suppose that {a,b,c,d} is the bad set. Then any two numbers of this set both are divisible by prime number, but remaining two aren’t divisible by this prime. Since there are C_4^2=6 pairs, product of a,b,c,d is divisible by six distinct primes. So, 12! is divisible by six distinct primes and it’s not true, because 12 is less than p_6 (?!). Hence, the greatest such n is 12.

pixi wrote: Hi! Let’s p_i is the i-th prime number. Consider two cases: 1. n is more or equal to p_6. Then let’s consider set {p_1p_2p_3, p_1p_4p_5, p_2p_4p_6, p_3p_5p_6}. It’s easy to see that gcd of any two numbers from this set is equal to p_i, but product of remaining two isn’t divisible by p_i. Therefore, if n is more than 12 (p_6=13), then there exist not “good” set. 2. n is less than p_6 Let’ s prove that then all sets are good. Suppose that {a,b,c,d} is the bad set. Then any two numbers of this set both are divisible by prime number, but remaining two aren’t divisible by this prime. Since there are C_4^2=6 pairs, product of a,b,c,d is divisible by six distinct primes. So, 12! is divisible by six distinct primes and it’s not true, because 12 is less than p_6 (?!). Hence, the greatest such n is 12. Your sets for part 1 work but that doesn't imply $n\le 12$, that implies $n\le max\{p_ip_jp_k\}-1$. @below No, that does not mean $n\le 12$. Check again your procedure. I know that $12$ is not the answer since I solved it and I saw the official solution and it is the same answer as me. I dare you to find a bad set containing $13$. There are no such sets.

In the part one I proved that if n satisfies, then there don’t exist six distinct primes less or equal to n. That is, n is less than 13.

plagueis wrote: A four-element set $\{a, b, c, d\}$ of positive integers is called good if there are two of them such that their product is a mutiple of the greatest common divisor of the remaining two. For example, the set $\{2, 4, 6, 8\}$ is good since the greatest common divisor of $2$ and $6$ is $2$, and it divides $4\times 8=32$. Find the greatest possible value of $n$, such that any four-element set with elements less than or equal to $n$ is good. Proposed by Victor and Isaías de la Fuente Here is a solution with motivation, but with a lot of notation abuse. The main point of the problem is to construct such a set. The easiest way to do so is manipulating primes. $\underline{\textcolor{blue}{\text{Part 01: Constructing such a set and basic intuition}}}$ Suppose that we have a prime $P$ that doesn't divide other elements other than a particular element $n$, then we might as well delete it and it won't affect the problem. This way we want to force the gcd of any two numbers being a prime number. (We could formalize this later on by saying that unnecessary primes could be deleted in the process). The main point is here: We want to make sure that if a prime $P$ divides two elements $x_i, x_j$, then it won't divide any other element. This construction forces gcd of any two numbers won't divide the product of the other two numbers. Therefore, we have the following construction in mind: \[ \{ p_1 p_2 p_3, p_1 p_4 p_5, p_2 p_4 p_6, p_3 p_5 p_6 \} \]for distinct prime numbers $p_1, p_2, p_3, p_4, p_5, p_6$, which for obvious reasons to minimize the sum, we wanted them to be $2, 3, 5, 7, 11, 13$. Now, we then wanted to find \[ \min_{p_1, p_2, p_3, p_4, p_5, p_6 \in \{ 2, 3, 5, 7, 11, 13 \}} \max \{ p_1 p_2 p_3, p_1 p_4 p_5, p_2 p_4 p_6, p_3 p_5 p_6 \} \]Instinct tell us that $(13, 11)$ mustn't be grouped together (yep, multiply two largest prime numbers from the set is not a wise decision). and we want to pair up small primes with large primes if possible. This pretty much motivates the construction: \[ \{ 13 \cdot 7 \cdot 2, 11 \cdot 7 \cdot 3, 13 \cdot 5 \cdot 3, 11 \cdot 5 \cdot 2 \} \]which works just find for any $n \ge 231$. $\underline{\textcolor{blue}{\text{Part 02: Proving for any } n \le 230 \ \text{will work}}}$ We want to simplify the working set as much as possible. Once you start to play with numbers: you could see that if we could reduce or delete prime in certain conditions. Here, we'll try to formalize our thought. We'll try to reduce the criteria of good sets. First, we will prove that if the four numbers $\{ a,b, c , d \}$ satisfy $\gcd(i,j,k) > 1$ for any $i,j,k \in \{ a, b , c , d \}$. Then divide $i,j,k$ by $\gcd(i,j,k)$ and the set will work as well. To simplify notation, we'll write it as $\{ y_1 = kx_1, y_2 = kx_2, y_3 = kx_3, y_4 = x_4 \}$, where $k > 1$ is a prime. We'll show that $\{ x_1, x_2, x_3, x_4 \}$ is good as well. We know that for some $1 \le i < j \le 4$, we have \[ \gcd(y_i, y_j) \mid \frac{y_1 y_2 y_3 y_4}{y_i y_j} \]Suppose that $1 \le i < j \le 3$, then notice that $\frac{\gcd(y_i, y_j)}{k} \mid \frac{y_1 y_2 y_3 y_4}{y_i y_j k }$ which works as $\frac{y_1 y_2 y_3 y_4}{y_i y_j y_k} \in \mathbb{Z}$. Otherwise, then $j = 4$. If so, then $\gcd(y_i, y_4) \mid \frac{y_1 y_2 y_3}{y_i}$ But, if $k \mid y_4$, then doing the same procedure will work, otherwise no $k$ is used and could just be deleted. Thus, we assume that $\gcd(y_i, y_j, y_k) = 1$ for any good set $\{ y_1, y_2, y_3, y_4 \}$ and $1 \le i < j < k \le 4 \}$. First, denote all four numbers as product of primes. Suppose that there exists a number $x_i$, $1 \le i \le 4$ and a prime number $p$ such that $\nu_p (x_i) \ge 2$. By the previous argument, $p$ could only divide at most $2$ numbers. If $p$ only divides $x_i$ alone, we could just delete it as nothing would change (proof ommited). Thus, $p$ must divide exactly $2$ of these numbers. If $\nu_p(x_i) \ge 2$ and $\nu_p(x_j) \ge 1$ for the other number. Then, we prove that divide $x_i$ by $p^{\nu_p(x_i) - 1}$ and the set will work again. To prove this, assuming the set is good, if the two numbers that are considered the gcd both have $p$, then $\nu_p(x_i)$ could be "ignored" as long as it is $\ge 1$, since this $p$ won't divide the other two. Otherwise, then the $\gcd$ won't contain $p$, so we could safely "delete" $p$ as well. (Note: use $a \mid bp$, and $p \nmid a$ then $a \mid b$.) Hence, we could safely assume that $\nu_p(x_i) = 1$ for all $i$ such that $p \mid x_i$. Same argument could be used to deduce if gcd of any two numbers must be a prime number or $1$. Now, proving this would be much easier, as we are given these facts on good sets (remember, we could reduce any good sets to satisfy the given criteria): 1. No three numbers would have common divisor. 2. All the numbers are $\textcolor{red}{\text{squarefree}}$. 3. No isolated primes. Prime only divide a number. We'll prove that there exists two elements which are relatively prime. Suppose otherwise, By using these three facts, we could finish this by noting the following: let $p_{i,j}$ be the common primes of $x_i$ and $x_j$, which must exists for every $(i,j)$, and it is unique, and $\nu_p(x_i) = \nu_p(x_j) = 1$ as well. Now, we can then write \[ x_k = a_k \cdot \prod_{i \in \{ j, k \}} p_{jk} \]By condition $3$, $a_k = 1$ for all $k$. Thus, \[ x_1 = p_{12} p_{13} p_{14} \ x_2 = p_{12} p_{23} p_{24} \ x_3 = p_{13} p_{23} p_{34} \ x_4 = p_{14} p_{24} p_{34} \]we could rewrite this as in our first part of our arguments: $6$ distinct primes. But by simple bounding argument, one can show that \[ \min_{p_1, p_2, p_3, p_4, p_5, p_6 \in \{ 2, 3, 5, 7, 11, 13 \}} \max \{ p_1 p_2 p_3, p_1 p_4 p_5, p_2 p_4 p_6, p_3 p_5 p_6 \} \ge 231 \]so we are done since any set with $n \le 230$ could be reduced to a good set such that two of its elements are relatively prime.