Ok, what. $0$ works other than that the answer is powers of $2$.

The answer is all integral powers of $2$ (and $0$ :/). For $|S|=1$, simply take $1$. Otherwise, consider two sets of primes $A$ and $B$ with $n$ primes each, all $2n$ of them being distinct. Label the primes $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots, b_n$. Then the set of all numbers of the form \[c_1\cdot c_2\cdot \cdots \cdot c_n\]where $c_i=a_i$ or $c_i=b_i$ satisfy the problem conditions (clearly $|S|=2^n$ since there are two choices for each $c_i$). It's easy to see this works (although quite annoying to explain :/) It remains to show these are the only possibilities. Consider only $|S|>1$ (since we already explicitly showed $|S|=1$ works). Claim: $1$ is not in $S$. Let $a\ne 1$ also be in $S$. If $1\in S$, then $\gcd(1,1)=\gcd(a,1)=1$ which contradicts the unique condition. Claim: For any element $a$ in $S$, $|S|=\tau(a)$ where $\tau(a)$ is the number of divisors of $a$. Clearly $|S|\geq \tau(a)$ since each divisor of $a$ must be paired with a distinct element of $S$. If $|S|>\tau(a)$, then by PHP there exists $t_1\ne t_2 \in S$ such that $\gcd(t_1,a)=\gcd(t_2,a)$, which contradicts the unique condition so we must have equality. Before introducing the final claim, an important observation is that each element of $S$ must be paired to a unique element that is relatively prime to it, so we can look at these $\frac{1}{2}|S|$ pairs ($|S|$ can't be odd since $1$ isn't in it but it's the only integer relatively prime to itself). Claim: If $a \in S$, then for all primes $p$ dividing $a$, $\nu_p(a)=1$. Note that exactly $\frac{\nu_p(a)}{\nu_p(a)+1}$ of the elements in $S$ are divisible by $p$. If $\nu_p(a)>1$, then this means more than half of the elements of $S$ are divisible by $p$. But by PHP, this creates a contradiction with the relatively prime pair observation, so we must have $\nu_p(a)=1$. Thus $|S|=\tau(a)=2^{\text{number of distinct primes dividing }a}$, as claimed.

We claim the only possibilities for size of $S$ are $\boxed{2^k, k \ge 0}$. For $k = 0$, $S = \{1\}$ works. Now a construction for $k \ge 1$. Select $2k$ distinct primes $p_1,p_2,...,p_k$, and $q_1,q_2,...,q_k$. Consider a bit-string $B$ with $k$ digits. Let $n(B) = \prod_{i=1}^k f_B(i)$, where $f_B(i) = p_i$ if $B[i] = 0$, $f_B(i) = q_i$ if $B[i] = 1$. We claim that taking $S$ to be $n(B)$ where $B$ is one of the $2^k$ possible bit strings is a valid $S$. To prove this, consider a divisor $d$ such that $d | n(B)$ where $B$ is some bit string. Consider a bit string $B'$ such that $B'[i]=0$ if $f_B(i) | d$, $1$ otherwise. It follows that is that $\gcd(n(B),n(B \oplus B')) = d$ (where $\oplus$ denotes XOR). Now we show that if $|S| = K$ where $K$ has a prime factor $\ge 3$, then it is impossible to have a valid set $S$. Consider an arbitrary integer $n \in S$. Let $\tau(n)$ denote the $\#$ of positive integer divisors of $n$. We know that for every divisor $d | n$ we have some $n' \in S$ such that $\gcd(n,n') = d$, and furthermore $n'$ is unique. Follows that $|S| = K = \tau(n)$. And since $n \in S$ was arbitrarily picked, we know that for any $n \in S$, we must have $\tau(n) = K$. Now consider $m \in S$ such that $\gcd(m,n) = 1$. Let $n = p_1^{e_1}p_2^{e_2}\cdots p_j^{e_j}$ be prime factorization of $n$. We know that $K = \tau(n) = \prod_{i=1}^j (e_i+1)$, and since $K$ has a prime factor at least $3$, WLOG let $e_1 \ge 2$. Consider the $x \in S$ such that $\gcd(n,x) = \frac{n}{p_1}$. Clearly $x \neq n, x \neq m$, and thus $\gcd(m,x)$ is some $d | m$ such that $1 < d < m$. Since $\gcd(m,n) = 1$, then $\gcd(n,d) = 1$. And thus $\left(\frac{n}{p_1}\right)d | x$, $\gcd\left(\frac{n}{p_1},d\right) = 1$. It follows that $\tau(x) \ge \tau\left(\frac{n}{p_1}\right)\tau\left(d\right) \ge \tau(n)\frac{e_1}{e_1+1}(2) > K$ since $e_1 \ge 2$, so $\tau(x) \neq K$, which is bad since $x \in S$.

Would we lose points if we did not include 0? The problem statement says "For each $s \in S,$ blah blah blah" which implies there exists $s \in S.$ It would be different if the problem had said "If $s \in S,$ blah blah blah."

@above hopefully not...

We claim that the size of $S$ must be a power of $2$. Lemma. If $n \in S$, then $|S| = \tau(n)$. Proof. Note that the gcd of $n$ and any element of $S$ must obviously be a divisor of $n$. So we have two cases: If $|S| < \tau(n)$, then there wouldn't be enough elements to satisfy the condition. If $|S| > \tau(n)$, then there must exist $2$ elements of $S$ that have the same gcd with $n$, which is prohibited. Thus, $|S|=\tau(n)$, as claimed. $\blacksquare$ Let $n=|S|$. We will show that $n$ must be a power of $2$. Suppose, for the sake of contradiction, that $n$ has prime divisors other than $2$. Then all elements of $S$ must be of the form $p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ ($p_i$ are distinct primes) where at least one of the $\alpha_i$ exceeds $1$. By the Lemma, we also have \[ n = (\alpha_1+1)\cdots(\alpha_k+1). \]Now, let $s \in S$ be such that $s = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, where, without loss of generality, $\alpha_1 > 1$. By the condition, there exists a unique $t$ such that $\gcd(s, t) = p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$. In particular, \[ p_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \mid t. \]Moreover, we also know that there is an element of $S$ coprime to $s$. Let $u=q_1^{\beta_1}\cdots q_j^{\beta_j}$ be this element. Since $s$ is the unique element of $S$ coprime to $u$, all other elements of $S$ must share at least one prime divisor with $u$. In particular, $t$ must share a prime divisor $q \in \{q_1, \ldots, q_j\}$ with $u$. Since $q \notin \{p_1, \ldots, p_j\}$, we have \[ qp_1^{\alpha_1-1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \mid t. \]However, notice now that the number of divisors of $t$ exceeds $n$; indeed, \begin{align*} 2\alpha_1(\alpha_2+1)\cdots(\alpha_k+1) &> (\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1) \\ \iff 2\alpha_1 &> \alpha_1+1 \\ \iff \alpha_1 &> 1, \end{align*}which contradicts the Lemma. We now present a construction to show that if $|S|=2^k$, then there is a valid $S$. Let $\{p_1,\cdots,p_k, q_1,\cdots,q_k\}$ be a set of $2k$ distinct primes, and denote $[k]=\{1,\cdots,k\}$. Consider \[ S = \left\{\Bigg(\prod_{i \in E}p_i\Bigg)\Bigg(\prod_{j \in [k]\setminus E}q_j\Bigg) : E \subseteq [k]\right\}. \]To help clarify the above definition of $S$, here is the construction written out explicitly for $k=3$: \[ \begin{tabular}{ccc|ccc||c} $p_1$ & $p_2$ & $p_3$ & $q_1$ & $q_2$ & $q_3$ & Element \\ \hline 1 & 1 & 1 & 0 & 0 & 0 & $p_1p_2p_3$ \\ 1 & 1 & 0 & 0 & 0 & 1 & $p_1p_2q_3$ \\ 1 & 0 & 1 & 0 & 1 & 0 & $p_1p_3q_2$ \\ 0 & 1 & 1 & 1 & 0 & 0 & $p_2p_3q_1$ \\ 1 & 0 & 0 & 0 & 1 & 1 & $p_1q_2q_3$ \\ 0 & 1 & 0 & 1 & 0 & 1 & $p_2q_1q_3$ \\ 0 & 0 & 1 & 1 & 1 & 0 & $p_3q_1q_2$ \\ 0 & 0 & 0 & 1 & 1 & 1 & $q_1q_2q_3$ \\ \end{tabular}

We claim that the possible values of $|S|$ is all numbers of the form $2^x$ where $x$ is a non-negative integer. First, we will prove that all numbers of this form work by induction: Base Case: $|S| = 1$ The set $S = \{1\}$ obviously works. Inductive Step: Suppose $G$ is the set with $2^{n-1}$ elements satisfying the conditions. Then, we will construct a set $H$ of size $2^n$ that works as well: Let $p$ and $q$ be two distinct primes that do not divide any of the elements in $G$. Note that these exist because $G$ is finite and there are an infinite number of primes. Now, for each element $s \in G$, add $sp$ and $sq$ to $H$. We will now prove that $H$ satisfies the conditions. Take any element from $H$, without loss of generality let it be of the form $sp$. Now, if $d$ is a divisor of $s$, then all divisors of $sp$ are of the form $d$ or $dp$. By inductive hypothesis, there exists a unique $t \in G$ such that $\gcd(s,t) = d$ (which means $tp$ and $tq$ are in $H$). Now, if a divisor of $sp$ is of the form $d$ (where $d \mid s$), then $tq$ is the unique element in $H$ satisfying $\gcd(sp,tq) = d$ (since $p$ and $q$ are distinct primes). On the other hand, if a divisor of $sp$ is of the form $dp$, then $tp$ is the unique element in $H$ satisfying $\gcd(sp,tp) = dp$. Therefore, $H$ also satisfies the conditions of the problem and $|H| = 2|G| = 2^n$ so we are done. Now, we will prove that $|S|$ cannot take on any other values. Lemma: For any $s \in S$, the number of divisors of $s$ equals $S$. Proof: Note that for any element $t \in S$, $\gcd(t,s)$ is a divisor of $s$. However, the condition on $S$ states that the mapping from divisors of $s$ to $t$ is an injective function, and we have just shown that it is surjective, which means that it is a bijection. Therefore, the number of divisors of $s$ equals $|S|$. Now, suppose for contradiction that $|S| \neq 2^x$. Then, take any element $k \in S$. Let $k=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$. The lemma states that: $$(e_1+1)(e_2+1)...(e_k+1) = |S| \neq 2^x$$Therefore, some $e_i > 1$. Without loss of generality, let it be $e_1$. Then, take the element $t \in S$, such that $$\gcd(k,t) = \frac{k}{p_1} = p_1^{e_1-1}p_2^{e_2}\dots p_k^{e_k}$$Now, let $a \in S$ be such that $$\gcd(k,a) = p_1^{e_1}$$and $b \in S$ be such that $$\gcd(k,b) = p_1^{e_1-1}$$Now, note that if $q$ is a prime $\neq p_i$, then $q$ does not divide $t$, otherwise the number of factors of $t$ is at least $$e_1(e_2+1)(e_3+1)...(e_k+1)\cdot 2 > (e_1+1)(e_2+1)...(e_k+1) = |S|$$which is a contradiction. Also, note that for any $p_i$ with $i \neq 2$, $p_i \nmid a$ and $p_i \nmid b$. Therefore, $$\gcd(t,a) = p_1^{e_1-1}$$$$\gcd(t,b) = p_1^{e_1-1}$$This contradicts the uniqueness guaranteed by the problem statement, so we are done.

Does anyone know what would happen if I did this, but without the proof of correctness part? Also if we didn't do the empty set

Yay I included zero as an acceptable size I did this by showing (a) if there is a non-power of 2 and nonzero amount of elemente there must be something with p^2 or higher, then (b) if there is an element S1 with p^2*(something) (where something has no power of p), then there is another element S2 where gcf(S1, S2)= (something)*p and there is a third where gcf(S2, S3)=(something). However, gcf(S1, S3) must equal (something) as well, which contradicts the original statement, thus there cannot be an element with p^2 for any prime, this 0 and 2^k are the only acceptable sizes

Is it just me, or was this abnormally tough for a p4?

Let's go I included zero. The answer is all powers of $2$. You can inductively construct something. Then you can show that the divisor count of everything in $S$ must be the same if it satisfies the conditions, and then that the exponents of the primes must be 1 which gives the other solution set. I don't think this problem was super hard for a JMO 5, and in fact JMO 4 took longer. Definitely wasn't easy though. Who knows, maybe 28 will make MOP.

How many points would I get if I got the answer of the powers of 2 part answer(but not the 0 part)? Didn't have time to finish the sol tho

Very vague sketch:

You can use this as a hint for the problem , but mostly I'm too lazy to writeup.

spartacle wrote: Is it just me, or was this abnormally tough for a p4? this was 5 though???? If you didn't include 0 then 6 is a probable score

I refuse to believe not including 0 is an actual dock.

Rip I forgot 0. To get $2^n$, take distinct primes $p_1, q_1, \ldots p_n, q_n$, and consider all numbers you get by choosing one of each $(p_i, q_i)$ and multiplying it all up. This works. To show we must have $2^n$, we claim that for all primes $p$ and $x \in S$, $v_p(x) \leq 1$. We prove this by contradiction: say $v_p(x) > 1$. Then $p$ divides $\frac{x}{p}$, so consider $y$ such that $\gcd(x,y) = \frac{x}{p}$, and $z$ such that $y$ and $z$ are relatively prime. Then all prime factors of $x$ are prime factors of $y$, so $x$ and $z$ are also relatively prime, a contradiction. This now finishes because the size of $S$ is just the number of divisors of any of its elements, which must be $2^n$ given $v_p(x) \leq 1$.

I really don't think not including zero will be -1 either. Answer is powers of $2^k$ with construction by selecting a prime from each of $k$ pairs $(p_i,q_i)$. We show numbers in $S$ must be squarefree. First note that if the numbers are $a_1, \dots a_{|S|}$ then $\text{gcd}(a_1,a_i), \dots , \text{gcd}(a_{|S|},a_i)$ are exactly the divisors of $a_i$, hence every $a_i$ has exactly $|S|$ divisors. Look at some $s \in S$ with prime factorization $p_1^{e_1-1} \cdots p_k^{e_k-1}$ so $|S|=e_1 \cdots e_k$ and assume for contradiction WLOG $e_1>2$. Then look at $t \in S$ with $\text{gcd}(s,t)=p_1$ so $t=p_1 N$ with $\text{gcd}(N,s)=1$ and $N$ has $|S|/2$ divisors. Now count the number of elements of S which are divisible by $p_1$ (which is the number of $d \mid s$ with $p_1 \mid d$, i.e. $(e_1-1)(e_2 \cdots e_k)$) and count the number of elements of $S$ which aren't divisible by $p_1$ (which is the number of divisors of $N$, i.e. $|S|/2 = (e_1 \cdots e_k)/2$ ) but when you add these numbers together you get something greater than $|S|=e_1 \cdots e_k$, contradiction.

No like I just got the answer (and wrote some progress down), I think the answer would be worth something right? I agree with the not including 0 part like idt that's worth a dock(should have made it clearer that empty sets were allowed I think)

Here's a different finish for why all elements of $S$ must be squarefree: For any $s\in S$, we need each element of $S$ to correspond to exactly one divisor of $s$ (namely the value of $t$ for that divisor), so $|S|$ is equal to the number of divisors of every $s\in S$. Suppose that one non-squarefree element of $S$ is $s = p_1^{e_1} \cdots p_k^{e_k}$. If there is some $e_i$ which is not one less than a power of $2$, say $e_1$, then "ask" for a $t$ corresponding to the divisor $p_1^{\text{largest \(2^\ell-1\) under \(e_i\)}}p_2^{e_2}\cdots p_k^{e_k}$. But this yields a contradiction, since \[\nu_2(d(t))\geq \nu_2(2^\ell) + \nu_2(d(s))-\nu_2(e_1+1))>\nu_2(d(s))\](where $d$ is the divisor-counting function), while $d$ is multiplicative and $d(t)=d(s)$. So all of the $e_i$ are one less than a power of $2$. If one of them is at least $3$, say $e_1$, then ask for a $t$ corresponding to $p_1^{2}$. In this case, $3\mid d(t)$ but $3\nmid d(s)$, which is a product of powers of $2$. The end.

The answer is perfect powers of $2$ (okay, well $0$ works too, I guess). $|S| = 1$ is attained by $S = \{ 1\}$. If $n \geq 1$, consider the $2^n$ terms of the expansion of \[(p_1+q_1)(p_2+q_2) \dots (p_n + q_n),\]where $p_1, q_1, p_2, q_2, \dots, p_n, q_n$ are distinct primes. We claim that the set of these $2^n$ values satisfies the conditions set on $S$. Consider one of its terms, $p_1 \cdot p_2 \cdots p_{n-1} \cdot p_n$. Each term in the expansion above contains some subset of the prime factors $\{ p_1, p_2, \dots, p_n \}$; the greatest common divisor between such a term and $p_1 p_2 \dots p_n$ will just be the product of the primes in that subset, so the set $S$ described here satisfies the conditions of the problem. We will now show that these are the \textit{only} possible values of $|S|$. Firstly, we claim that there must be a one-to-one correspondence between divisors of an element in $S$ and elements in $S$. In other words, every element in $S$ has $|S|$ divisors. Let $x$ be an element in $S$. For each element in $S$, its greatest common divisor with $x$ is, by definition, \textit{some} divisor of $x$. On the other hand, we are given in the problem that each divisor of $x$ must correspond to exactly one element in $S$. This proves the one-to-one correspondence. We now claim that every element in $S$ is squarefree; that is, the exponent of each prime in the prime factorization of an element in $S$ is exactly $1$. Firstly, if $|S| = 1$, by inspection, $S=\{ 1 \}$; $1$ is squarefree. Now, we assume that $|S| \geq 2$. Write an element $x \in S$ in the form \[x = p_1^{e_1} \cdot p_2^{e_2} \cdot \dots \cdot p_k^{e_k}.\]So, $|S| = (\text{number of divisors of } x) = (e_1+1)(e_2+1) \dots (e_k+1)$. There must exist another element $y \in S$ of the form \[y = p_1^{e_1-1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot \dots \cdot p_{k}^{e_k} \cdot p_{k+1}^{e_{k+1}} \cdot \dots \cdot p_{k+i}^{e_{k+i}},\]as the unique element in $S$ satisfying $\gcd \left( x, y \right) = \frac{x}{p_1}$. We established before that each element in $S$ has the same number of divisors. Therefore, we have that \begin{align*}(e_1+1)(e_2+1) \dots (e_k+1) &= (e_1)(e_2+1)(e_3 + 1) \dots (e_k + 1)(e_{k+1} + 1) \dots (e_{k+i} + 1) \\ \implies \frac{e_1 + 1}{e_1} &= (e_{k+1} + 1) \dots (e_{k+i} + 1) \\ \implies \frac{e_1+1}{e_1} & \in \mathbb N \\ \implies e_1 &= 1. \end{align*}The same reasoning can be applied on $e_2,e_3, \dots, e_k$, to show that $x$ must be squarefree. This implies that the number of divisors of $x$ is a power of two, so $|S|$ must be a power of two.

Why easier than p4 :skull: The answer is $0$, $1$, and $2^n$ for $n\ge 1$. For the former two, constructions are $S = \emptyset$ and $S = \{1\}$ respectively. For the third one, take as a construction \[ S = \left\{\prod_{i =1}^n\left(\begin{cases}p_i & i\in S\\ q_i & i\not\in S\end{cases}\right)\Big| T\in\mathcal{P}([n])\right\},\]where $p_1, p_2, \dots, p_n, q_1, q_2, \dots, q_n$ are pairwise distinct primes. We will now show that no other sizes are possible. Let $|S| = k\ge 3$ and let $S = \{x_1, x_2, \dots, x_k\}$. First, observe that, for any fixed $x_i$, there is a unique $x_j$ corresponding to each divisor $d$ of $x_i$ (that is, there is a unique $x_j$ such that $\gcd(x_i,x_j) =d$), so $k = d(x_i)$. As a consequence, we have $1\not\in S$, as otherwise, we would have that $k = d(1) = 1 < 3$. Hence, each of the $x_i$'s has a prime factorization. Now, we have the following claim. Claim: Each $x_i$ is squarefree. That is, for all $p|x_i$, we have $\nu_p(x_i) = 1$. Proof: Let $p$ be an arbitrary prime in the prime factorization of $x_i$, and let $x_i = p^n\cdot x_i'$ where $\gcd(p, x_i') = 1$. Then, for some $y$ coprime with $x_i$, the number $p^{n-1}x_i'y$ must be in $S$. Then, we have \[ k = d(p^nx_i') = d(p^{n-1}x_i'y)\implies (n+1)d(x_i') = nd(x_i')d(y)\implies d(y) = \frac{n+1}{n}.\]Since $d(y)$ is an integer, so is $\tfrac{n+1}{n}$, which forces $n = 1$ $\square$ It immediately follows that each element of $S$ is of the form $p_1p_2\cdots p_m$, so $k = d(p_1p_2\cdots p_m) = 2^m$, which is a power of $2$, as desired.

Please don't tell me that someone got their score docked due to just missing $0$ (which yeah, I totally did ). I claim that all $2^k$ work for any non-negative $k$. Firstly, for each number in the set, note that we have the number of elements equal to the number of divisiors of that number from which it follows that all the numbers have the same number of divisors. Now, let one of the numbers from the set have the prime factorization $s=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$ where the powers are in an non-increasing order. We thus have that $d(s)=(e_1+1)(e_2+1)\cdots(e_k+1)$ for all $s\in S$. I claim that $e_k \le 1$. FTSOC assume $e_k \ge 2$. Now consider the case for the divisor $d=p_1^{e_1}\cdot p_2^{e_2}\cdots p_{k-1}^{e_{k-1}}\cdot p_k^{e_k-1}$. Now if the element $t$ corresponding for our $d$ has a new prime in its prime factorization other than our $p_i$ in its prime factorization, then the $d(t)\ge (e_1+1)(e_2+1)\cdots (e_{k-1}+1)(e_k)\cdot 2$. This gives $e_k \le 1$ which is a contradiction. Otherwise, $t$ must have the power of some prime at least one more than that in $s$ other than $e_k$. So we must have $d(s)\ge (e_1+1)(e_2+1)\cdots(e_{i-1}+1) (e_i +2)(e_{i+1}+1)\cdots (e_{k-1}+1)(e_k)$ which then gives for some $i$ that $e_k < e_i$ which is again a contradiction. Thus we must have $e_k\le 1$. This gives that the number of divisors is a power of two and thus the number of elements. Now for the construction, I'll just leave a sketch. For some $k$, pick two numbers $a=p_1\cdot p_2\cdots p_k$ and $b=q_1\cdot q_2\cdots q_k$ where the $p_i$ and $q_j$ are all distinct. Now write down all the divisors of $a$ with $x$ primes, and pair them up with the $k-x$ primes of $b$. This works as $\binom{k}{x}=\binom{k}{k-x}$. Moreover, for each number, there must be at least $d(s)$ number of dictinct pairwise gcd's and this combined with the fact that there are exactly $d(s)$ elements guarantees the uniqueness and we are done.

does this work? The answer is all powers of $2$ (and $0$ :unamused:). For the construction, take $(p_1 \text{ or } q_1) \cdot (p_2 \text{ or } q_2) \cdots (p_{k} \text{ or } q_{k}).$ For the proof that it can only be a power of $2,$ note that $\tau(s) = |S|$ for each $s \in S.$ Assume FTSOC there exists $\nu_{p_1} (x) > 1.$ Let $x = p_1^{e_1} p_2^{e_2} \cdots p_{k}^{e_{k}},$ with $e_1 \ge 2.$ Then, there must exist $y$ such that $\gcd(x,y) = \frac{x}{p_1}.$ Write $y = K \cdot p_1^{e_1-1} p_2^{e_2} \cdots p_{k}^{e_{k}}.$ Because $\tau(x) = \tau(y)$ and $\frac{e_1+1}{e_1} < 2,$ we know that $y$ cannot have any prime factors not in $x.$ Therefore, we can write $y = p_1^{e_1-1} p_2^{f_2} \cdots p_{k}^{f_{k}},$ where $f_{i} \ge e_{i}$ for all $2 \le i \le k.$ However, there also exists $z$ such that $\gcd(x,z) = p_1^{e_1-1}.$ Write $z = p_1^{e_1-1} q_2^{g_2} \cdots q_{\ell}^{g_{\ell}},$ where none of the $q_{i}$'s are factors of $x.$ However, from here we see that $x$ and $y$ satisfy $\gcd(x,z) = \gcd(y,z) = p_1^{e_1-1},$ contradiction. Since all of the elements of $S$ must be square-free, the number of divisors of each of them (and therefore $|S|$) must be a power of $2.$

wait what the heck this one almost got me The answer is all powers of $2$. If you did not have breakfast the day of the contest, $0$ is included. Otherwise, it may or may not be included. Construction: Consider the integers given by the products of the primes in tuples in $\{p_1, q_1\} \times \dots \times \{p_k, q_k\}$ for distinct primes $p_i$ and $q_i$. This clearly works and results in $|S|=2^k$. $0$ case is a piece of cake if and only if you had breakfast. Bound: WLOG $S$ is nonempty. We prove the following claims. Claim: All elements of $S$ are squarefree. Proof. Consider the complete graph on the elements of $S$. Let $p$ be any prime. Relabel each element $n$ with $\nu_p(n)$. Then it is easy to see that given a fixed vertex $s \ge 1$, all neighbors of $s$ are less than $s$. For fixed $s>1$, consider the number $1$ connected to $s$ (which must exist for obvious reasons). Note that we must have $1 > s$ consequently, which is impossible. Thus each label must be at most $1$, implying the conclusion. Next we have the following intuitive bound. Claim: For each $s \in S$, $|S|=\tau(s)$. Proof. Fix $s \in S$. If $|S|<\tau(s)$, then there are too few elements for the problem condition to be satisfied, and if $|S|>\tau(s)$, then a divisor of $s$ is repeated among the $\gcd$s (by Pigeonhole). Thus $|S| = \tau(s)$. Since $\tau(s)$ is a power of $2$ for each $s \in S$, $|S|$ is a power of $2$, as desired.

For construction, you can take a t-dimension hyper cube, put a prime in each of the 2t "faces"(t-1 dimension object). And let the each vertex be the product of primes from its connected "faces".

Fire problem, a bit tricky for a 1/4 The answer is $|S|$ is $2^n$ or $0$. Claim. for $n\in S$, $|S| =\tau(n)$. Clearly for $n$, a distinct number $x$ is in $S$ for each divisor of $n$. Any other number must have a repeating gcd, contradicting uniqueness. Claim. $\nu_p(n) \leq 1$ for $n\in S$. Say FTSOC $p^k X \in S$ for $k\geq 2$ and integer $\gcd(p, X) = 1$. Then, for the gcd $p^{k-1}X$, we must have $p^{k-1}X\cdot Y \in S$ for $\gcd(pX, Y) = 1$. Now, for $p^{k-1}X\cdot Y$ to have a number in $S$ with gcd $p^{k-2}$, we must have some $p^{k-2}Z \in S$ (With Z relatively prime to everything else). However, now $$\gcd(p^{k-2}Z, p^k X) = \gcd(p^{k-2}Z, p^{k-1}X\cdot Y)$$a contradiction. Hence all elements in $S$ must contain $n$ primes for some $n$ (Otherwise $\tau(x\in S)$ would be nonconstant). This gives $2^n$ distinct numbers, which can be given by the construction of making sets of $n$ primes from sets $|A| = |B| = n$ where we either any number $x\in S$ is either divisibly by the $i$th prime in $A$ or the $i$th prime in $B$ not both.

The answer is $2^n$ for $n \geq 0$ or $0$. Construction: for $0$ and $1$, take the null set and $\{ 1 \}$, respectively. For $2^n$ and $n \geq 1$, consider distinct primes $p_1, p_2, \dots, p_{2k}$; then letting $S$ be $\{ (p_1 \text{ or } p_2) \cdot (p_3 \text{ or } p_4) \cdots (p_{2k-1} \text{ or } p_{2k})) \}$ over all possibilities suffices. Notice that by the set condition, if we consider any element $x$, then $|S|$ is the number of divisors of $x$. Claim: $v_p(x) \leq 1$ for any $p, x$. FTSoC assume $v_p(x) =e \geq 2$. Then, looking at $x$, we see that $\frac{e}{e+1}$ of the elements in $|S|$ must be divisible by $p$. Now, consider the unique element $t$ such that $\gcd(x, t) = p$; looking at $t$, we see that $\frac{1}{2}$ of the elements in $|S|$ must be divisible by $p$. However, this means $e \leq 1$, contradiction. Thus, as each element must have the same number of divisors, and is of the form $p_1p_2 \cdots p_k$ for some $k$, we have that $|S| = 2^k$ for some $k \geq 0$.

Huh why $0$ work

Are people actually getting deducted for forgetting about 0?

How many points would you recieve for this problem if you just got the correct answer+correct construction? I would think 1-2 pts. but please correct me if I am wrong.

The answer is $|S| = 0, 2^n$ for nonnegative $n$, the $|S| = 0$ clearly works. First we will show that $\nu_p(s) \leq 1$ for any prime $p$ and $s \in S$ which implies the claim as all elements in $S$ have the same amount of divisors. FTSOC $\nu_p(s) > 1$ for some element $s$. Then there exists an element $t \in S$ not equal to $\frac{s}{p}$ so that $\gcd(t, \frac{s}{p}) = \frac{s}{p}$, which implies that $t$ shares the same prime divisors as $s$. However this implies that there must a unique element $u$ so that $\gcd(u, t) = 1$ and $\gcd(u, s) = 1$ which is a contradiction as $1$ is a divisor of $u$. Our construction for $|S| = 2^n$ is letting each element be $p_iq_jr_k\dots$ where we have two groups of distinct primes $p_1q_1r_1\dots$ and $p_2q_2r_2$. Clearly there are $2^n$ possible elements in $S$ and the construction works so we are done.

Frestho wrote: "For each" doesn't imply there is an element. For each just means (in this context) that a property applies to every element of the set; if there are no elements, there are no conditions to be met, meaning the statement is automatically true. You could say "for each element $s \in \emptyset$, we have $s=69$" which is vacuously true. https://math.stackexchange.com/questions/426051/hows-it-possible-for-each-element-of-the-empty-set-to-be-even By this logic I am friends with Michael Jackson (I have no friends) We claim the answer is all $|S| = 2^n$ where $n$ is a nonnegative integer. When $n = 0$ then $S = \{ 1 \}$ works, otherwise consider two disjoint sets of primes $\{p_1, p_2, \dots, p_n \}$ and $\{q_1, q_2, \dots, q_n \}$, then for every $1 \le k \le n$ simply let either $p_k$ or $q_k$ be a prime factor of the element, it is easy to see there are $2^n$ possibilities. Now we prove necessity. Let $\tau$ be the number of divisors function, we claim that for all $s \in S$ we have $\tau(s) = |S|$. Clearly by the unique condition we have an injective mapping implying $|S| \ge \tau(s)$. Now if $|S| > \tau(S)$ by Pigeonhole Principle there exists two elements $da, db \in S$ where $d \mid s$ and $a$, $b$ are both relatively prime to $s$. But this contradicts the uniqueness condition, so $|S| = \tau(S)$. Next we claim that for every prime $p$, there exists an element $s \in S$ that satisfies $\nu_p(s) \le 1$. Assume otherwise, then all $\nu_p(s) \ge 2$. This quickly yields a contradiction as for any $s$, we can choose a divisor $d \mid s$ where $\nu_p(d) = 1$, and $\nu_p(\gcd(s, t)) = 1 \ge 2$ is absurd. Now consider the element $x \in S$ satisfying $\nu_p(x) = 1$, then exactly $\frac{1}{2}$ elements of $S$ are multiples of $p$. But for any other element $s \in S$ we must also have $\frac{\nu_p(s)}{\nu_p(s) + 1}$ multiples of $p$ in $S$, so $\nu_p(s) = 1$ for all $s \in S$. Taking the above claim over all primes $p$ it is clear that $|S|$ can only be powers of two. We are done.

I have a very weird proof of the bound...someone please check this works We first check the cardinality must be a power of $2$. We show that for an element of $S$, all its prime factors have multiplicity $1$. Assume for the sake of contradiction for some $k \ge 2$ that $p^kq \in S$, with $\gcd(p,q)=1$. From the problem condition, there exists some $pq' \in S$ with $\gcd(q,q')=1$ and $\gcd(p,q')=1$. There also exists some $q'r \in S$ with $\gcd(r,q')=1$, $\gcd(r,q)=1$, and $\gcd(r,p)=1$. Now consider the element $n \in S$ such that $\gcd(n,q'r)=r$. If $n$ is a multiple of $p$, then $\gcd(n,pq')=p$. But also $\gcd(pq',p^kq)=p$, a contradiction. If $n$ is not a multiple of $p$, then $\gcd(n,pq')=1$ and $\gcd(n,p^kq)=1$ (note $n$ cannot be a multiple of $q$. Indeed, otherwise $\gcd(n,pq')=1$ and $\gcd(n,p^kq'')=1$ for some $p^kq'' \in S$ with $\gcd(q,q'')=1$), a contradiction. Thus all prime factors of any element in $S$ have multiplicity $1$, from which it readily follows $|S|=2^k$.