Beautiful problem. Let's look at what it says for a moment. A version of Ramsey's Theorem says this: if we color the $k$-element subsets of $\mathbb N$ with two colors (it works for a fintie number of colors, of course, but we're interested in this case here), then there is an infinite $k$-homogemous set, i.e. an infinite set all of whose $k$-element subsets bear the same color. This problem says that this sort of result is not necesarily true any more if we try to do this for all $k\ge 2$ at the same time: if we color all the subsets of $\mathbb N$ which have at least two elements with two colors, then there need not exist an infintie set which is $k$-homogenous for all $k$. Here, of course, the set of primes represents $\mathbb N$, and the product $p_{i_1}\cdot\ldots\cdot p_{i_k}$ represents the set $\{\i_1,\ldots,i_k\}$. If a product of distinct primes (we don't work with non-square-free numbers) belongs to the set we want to construct, we'll say the corresponding set is red, while if it does not we'll say the corresponding set is blue. That's why from now on we'll work in this setting, using subsets of $\mathbb N$ instead of square-free positive integers. We now prove that given $k\ge 2$ and some $x\in\mathbb N$, we can find a two-coloration of the $k$-element subsets of $\mathbb N$ such that $x$ belongs to no infinite $k$-homogenous set. This is almost obvious. We can simply color all the $k$-element sets which contain $x$ in red, and the rest of them in blue. We'll call this procedure $P(x,k)$. Now, in order to obtain what we want, we can apply the procedures $P(k,k)$ for all $k\ge 2$. In other words, in the two-coloring of the subsets of $\mathbb N$ which have at least $2$ elements that we obtain, $2$ cannot belong to any infinite $2$-homogenous set, $3$ cannot belong to any infinite $3$-homogenous set, and, in general, $n$ cannot belong to any infinite $n$-homogenous set. In other words, there are no infinite subsets of $\mathbb N$ which are $k$-homogenous for all $k\ge 2$.

Maybe another solution to this beautiful problem: The set $ A$ of the square-free positive integers is defined as follows: A product $ n$ of $ k$ distinct primes $ p_{1},\ldots,p_{k}$ is a member of $ A$ if and only if $ n\equiv 1\pmod{k+1}$, i.e. $ p_{1}\cdot\ldots\cdot p_{k}\in A\Leftrightarrow p_{1}\cdot\ldots\cdot p_{k}\equiv 1\pmod{k+1}$ for all $ k$ and all primes $ p_{i}$. Now, let $ S$ be an infinite set of primes and let $ p_{1}$ be the smallest and $ p_{2}$ be the second-smallest prime in $ S$. Let furthermore $ p$ be any prime with $ p>p_{2}$. Lets now consinder $ S$ modulo $ p$. By the pigeonhole principle, some remainder modulo $ p$ must appear infinitely many times in $ S$, i.e. there exists an integer $ a$, so that $ q\equiv a\pmod p$ for infinitely many $ q\in S$. Obviously, $ p\nmid a$. Take now $ p-1$ distinct primes $ q_{1},\ldots,q_{p-1}\in S$ and let $ m=q_{1}\cdot\ldots\cdot q_{p-1}$. Then $ m\in A$ because by Fermat's little theorem, $ m = q_{1}\cdot\ldots\cdot q_{p-1}\equiv a^{p-1}\equiv 1\pmod p$. On the other hand, we have $ p>p_{2}>p_{1}$ by definition, so $ p_{2}\not\equiv p_{1}\pmod p$. Hence, at least one of the numbers $ p_{1}\cdot a^{p-2}$ and $ p_{2}\cdot a^{p-2}$ is not congruent to $ 1$ modulo $ p$. Thus, at least one of the numbers $ n_{1}= p_{1}\cdot q_{1}\cdot \ldots \cdot q_{p-2}$ and $ n_{2}= p_{2}\cdot q_{1}\cdot \ldots \cdot q_{p-2}$ is not congruent to $ 1$ modulo $ p$ and hence ist not a member of $ A$. $ \Box$

Another solution: Interpretating A as a set of finite subsets of N, we say that $ \{n_{1},n_{2},\ldots,n_{k}\}\in A$, where $ n_{1}< n_{2}< \ldots n_{k}$, if and only if $ n_{2}\le n_{1}+k$. Given an infinite set of naturals, just take the first $ d$ elements, where d is the difference between the two least elements: this set belongs to A. Now take the first element, not the second, an then all the next d-1 elements: this set does not belong to A.

And another one (but I'm not really sure if it is correct...): We will construct two disjoint sets $ A, B$ consisting of only squarefree numbers such that for every infinite set of primes $ S$ there exist $ m \in A$ and $ n \in B$ such that $ m$ and $ n$ are product of the same number ($ \geq 2$) of elements of $ S$. We define: $ p_{1}p_{2}...p_{n}\in A$ iff $ n$ has exactly two prime divisors from $ p_{1}, p_{2}, ..., p_{n}$ and $ p_{1}p_{2}...p_{n}\in B$ iff $ n$ has exactly one prime divisor from the same set (we don't care about the other numbers). Now let $ S=\{q_{1}, q_{2}, ...\}$. Consider the number $ m=q_{1}q_{2}q_{i_{1}}q_{i_{2}}...q_{i_{s}}$, $ n=q_{1}q_{i_{1}}...q_{i_{s}}q_{i_{s+1}}$, where $ s=q_{1}q_{2}-2$ and $ q_{i}$ are different elements of $ S$. From the definition we immidiately get that $ m \in A$ and $ n \in B$. I think that there can be very many significantly distinct solutions to this problem.

I think I have another construction: If $ p_{i}$ is the $ i$-th prime, and if $ n = p_{t_{1}}*p_{t_{2}}*...*p_{t_{m}}$, for some primes $ p_{t_{i}}$, assign to the number $ n$ the set $ (t_{1}, t_{2} ... t_{m})$ (clearly any squarefree number $ n$ can be written uniquely in such a form). Define the set $ A$ as follows: a number $ n$ is in $ A$ iff the assigned set $ (t_{1}, t_{2}, ... t_{m})$ is such that $ m | t_{1} + t_{2} + ... + t_{m}$. Now suppose to the contrary this set does not satisfy the condition: then say an infinite set $ S$ of primes, $ {s_{1}, s_{2} ... }$ (where $ s_{i}$ refers to the prime $ p_{s_{i}}$, is such, so that for any $ k$, either [1] all $ k$-element subsets of $ S$ are in $ A$ OR [2] all $ k$ element subsets of $ S$ are not in $ A$. If [2] occurs, then for any $ k$-element subset of $ S$, the sum of the elements in this $ k$-element subset is not divisible by $ k$. But this cannot happen, since using well-known Erdos result, in any $ 2k - 1$ numbers, some $ k$ have sum divisible by $ k$, and $ S$ is an infinite set. Since [2] never occurs, that means [1] must occur for every $ k$. This means for any fixed $ k$, any $ k$-element subset $ S$ has sum divisible by $ k$. Choose one such set, $ (t_{1}, t_{2} ... t_{k})$. Now replace $ t_{1}$ by another element from $ S$ - since the subset still has sum $ 0$ mod $ k$, this means that all elements apart from $ (t_{2} .. t_{k})$ are the same as $ t_{1}$ in $ Z_{k}$. Doing the same thing, but with $ t_{i}$ for other values of $ i$ (ie, replacing $ t_{i}$ by some other element in infinite subset $ S$) we find that elements of $ S$ have the same value in $ Z_{k}$. Now pick any two elements $ s_{1}, s_{2}$ from $ S$. This means $ s_{2} - s_{1}$ is divisible by $ k$, for any $ k$. But this is clearly a contradiction, since we can choose $ k$ to be arbitrarily large.

Let $p_1 < p_2 < \cdots$ be the ordered sequence of positive prime numbers. Now let $A$ be the set of all positive integers which are the product of $k$ distinct prime numbers one of which is $p_k$ for each $k \ge 2$. Consider an arbitrary set $S$ of primes and let $p_i$ be the minimal prime number in $S$. Now consider a sequence of $i$ distinct prime numbers $a_1, a_2, \dots, a_i$ such that $a_j \in S$ and $a_j > p_i$ for each $1 \le j \le i$. By the definition of $A$, it follows that $p_i \cdot a_1 \cdot a_2 \cdots a_{i-1} \in A$ and $a_1 \cdot a_2 \cdots a_i \not \in A$ and $A$ satisfies the conditions required by the problem.

I don't understand the problem. Is k fixed or does it vary depending on what S is?

@viperstrike $k$ varies depending on $S$. Sorry to resurrect; I was wondering about the validity of a possible construction. Denote the set of all primes as $\{p_1,p_2,p_3,\ldots\}$. For integral $i \ge 2$, let $B_i = \{ \prod_{j_k \in D} p_{j_k} \mid |D| = i \text{ and } j_k \equiv j_{m} \pmod {2^{i-2}} \text{ for } 1 \le k < m \le i\}$. Similarly, let $C_i = \{\prod_{j_k \in E} p_{j_k} \mid |E| = i \text { and } \exists k,m \text{ such that } 1 \le k < m \le i \text{ and } j_k \not \equiv j_m \pmod {2^{i-1}} \}$. Let $A_i = B_i \cap C_i$. Take $A = \bigcup_{i \ge 2} A_i$. The thought behind this was that if there exists at least one even-indexed prime and one odd-indexed prime in $S$, then since there are an infinite number of at least one of these classes represented in $S$, WLOG even-indexed primes, we can take a product of an even-indexed prime with an odd-indexed prime, which is in $A$, and an even-indexed prime with an even-indexed prime, which is not in $A$. This would correspond to the addition of the set $A_1$ to $A$. Motivation for larger $i$ works similarly. Notice also that the only set contributing $i$-factor products to $A$ is $A_i$. For arbitrary $S$, let the two smallest elements be $p_a < p_b$ and let $n$ be the smallest natural number such that $b < 2^n$. Then $a$ and $b$ are different $\pmod {2^n}$. We then proceed through the following $n$-step iteration: Step $1$: If not all indices in $S$ are odd and not all indices are even, then there exists at least one even-indexed $p_{2c}$ and one odd-indexed $p_{2d-1}$, the product of which is in $A_1$ and therefore in $A$. WLOG there are infinitely many odd-indexed primes in $S$. Then there exist $p_{2d-1}$ and $p_{2e-1}$ such that $p_{2d-1}p_{2e-1} \not \in A$. Done. Step $2$: Assume the assumption of step 1 is not true. If not all indices in $S$ are $a \pmod 4$ and not all indices in $S$ are $a+2 \pmod 4$, then there exists at least one index which is $a \pmod 4$ and one which is $a+2 \pmod 4$, and one of these classes contributes an infinite number of indices to $S$. Assume the first. Then we can take $a \equiv c \equiv d-2 \pmod 4$ so that the product $p_a p_c p_d$ is in $A_2$ and therefore in $A$. Take $a \equiv c \equiv e \pmod 4$, so that $p_a p_d p_e \not \in A$. Done. Step $3$: Assume the assumptions of steps $1$ and $2$ are not true. Proceed similarly to step 2, but work $\pmod 8$. $\vdots$ Step $n$: Assume the assumptions of all previous steps are not true. Then all indices are the same $\pmod {2^{n-1}}$. Since $a,b < 2^n$, it automatically follows that there exist two indices which are not the same $\pmod {2^n}$, namely $a$ and $b$. There must exist an infinite number of indices in $S$ corresponding to $a \pmod {2^{n}}$ or to $a+2^{n-1} \pmod{2^{n}}$. WLOG assume the former. Let $b < i_1 < i_2 < \cdots < i_{n-1} < i_n$ be such that $a \equiv i_1 \equiv i_2 \equiv \cdots \equiv i_{n-1} \equiv i_n \pmod {2^{n}}$. Then $p_{a}p_{b}p_{i_1} \cdots p_{i_{n-1}} \in A_{n}$ and therefore is in $A$ but $p_{a}p_{i_1}p_{i_2}\cdots p_{i_{n-1}} p_{i_n} \not \in A$. Done; this iteration handled the final case.

I had the same idea as Mc Teague but the resulting solution worded in a quite different way. let $\{p_i\}$ the set of all prime numbers, where $p_i < p_{i+1}$. Let $A_k = \{p_{i_1} p_{i_2}.....p_{i_{k}}, k >=2 $where all $i_j$ are not all congruent to the same value $mod (k)\}$ At last, let $A =\cup_{k>=2} A_k$. By contradiction : We suppose that for any $m \in A_k$ for any $k >=2$, there exists at least one prime divisor not in S. Therefore, all prime divisor in S have an indice congruent to the same value $mod(k)$. From here, it's easy to get a contradiction : take $p_i$ and $p_j$ two prime divisors of S and let k big enough, you'll have $k>i$ and $k>j$ and $i \equiv j [k]$, therefore $i=j$ : S has only one element, absurd. So there must exist $k$ and $m \in A$ where $m$ is a product of $k$ disctinct elements of S. let $k$ such a number. As $S$ as infinitely many primes, we can find infinitely many primes for which all indices are congruent to the same value $mod (k)$. Take $n$ the product of $k$ such numbers of S. $n \notin A$ but n is a product of k disctinct element of S : done.

It boils down to prove that there exists a countable collection $\mathcal{F}$ of subsets of $\mathbb{N}$ with the following property. For every infinite subset $D$ of $\mathbb{N}$ there exists $k\ge 2,$ such that $D$ contains a $k$-element subset of $D$ which is a member of $\mathcal{F}$ as well as a $k$-element subset of $D$ which is not a member of $\mathcal{F}.$ Proof. Arrange all 2-element subsets of $\mathbb{N}$ as $A_1,A_2,\dots.$ Map to each $A_i$ a family $\mathcal{F}_i$ of $i+1$-element subsets of $\mathbb{N}$ as follows $$\mathcal{F}_i := \{A_i\cup X : X\subset \mathbb{N}\setminus A_i\,,\, |X|=i-1 \}$$So, each set in $\mathcal{F}_i$ contains exactly $i+1$ elements. Let $\mathcal{F}:=\bigcup_{i=1}^{\infty} \mathcal{F}_i.$ This is the wanted collection of subsets. Indeed, let $D$ be an infinite set of numbers. Take any $x,y\in D.$ Let $A_n=\{x,y\}.$ Take any $A,B\subset D\setminus\{x,y\}$ such that $|A|=n-1, |B|=n.$ Now $A_n\cup A \in \mathcal{F}_n$ and $\{x\}\cup B\notin \mathcal{F}_n,$ which means $A_n\cup A\in \mathcal{F}$ and $\{x\}\cup B\notin \mathcal{F},$ since the only subsets in $\mathcal{F}$ with $n+1$ elements are those in $\mathcal{F}_n$ Comment. It was ISL 1994, N3, but it's a pure combinatorial one, just dressed as NT. I saw it given at Germany 2010 - Problem 3. Something about motivation. One may try first to find a collection of, say, 2-element sets, because it is the simplest way. It means you have to connect some of numbers in $\mathbb{N}$ with edges, that is, the edges will be the required sets. The imposed requirement just says that there should be no infinite set of vertices that form a clique or an anti-clique. Unfortunately, the infinite version of Ramsey's theorem shows, that it's impossible. The same happens if we try to choose subsets with same size $k>2,$ because of a version of Ramsey's theorem for $k$-uniform hypergraphs. This means that we are doomed by trying to create a collection of same size sets. We should vary $k$ by choosing bigger and bigger sets.

Here are a few constructions: 1) Lets denote the primes $p_1 < p_2 < \cdots $ in the increasing order of all prime numbers. Define $A$ as the set of numbers of the form $p_{i_1}, p_{i_2}, \cdots, p_{i_k}$ where $i_1 < i_2 < \cdots < i_k$ and $k=p_{i_1}$. Note that, in set S, let it have primes $q_1 < q_2 < \cdots$. Take $m=q_1 q_2 \cdots q_{q_1}$ and $n=q_2 q_3 \cdots q_{q_1+1}$ with $m \in A, n \notin A$. 2) Let $A_i$ denote the set of product of $i+1$ distinct primes, apart from including $p_i$ into the product. Define $A = A_1 \cup A_2 \cup A_3 \cup \cdots$. In set $S$, let it have primes $q_1 < q_2 < \cdots$. We let: $p_{i_1} = q_1$. If $i_1 > 1$ (that is $p_{i_1}$ is odd prime), then we have the values of $m, n$ to be: $m = q_2 q_3 \cdots q_{i_1+2}, n = q_1 q_2 \cdots q_{i_1+1}$. Then $m \in A, n \notin A$.