Straigtforward application of infinite pigeonhole principle. Infinite pigeon =infinite multiples. Finite hole=finite subset. So,for any natural numbers $n$,there are infinitely many multiples of $n$ in $S$.

Olympus_mountaineer wrote: Straigtforward application of infinite pigeonhole principle. Infinite pigeon =infinite multiples. Finite hole=finite subset. So,for any natural numbers $n$,there are infinitely many multiples of $n$ in $S$. I thingk $S$ isn't depend on $n$.

WypHxr wrote: Olympus_mountaineer wrote: Straigtforward application of infinite pigeonhole principle. Infinite pigeon =infinite multiples. Finite hole=finite subset. So,for any natural numbers $n$,there are infinitely many multiples of $n$ in $S$. I thingk $S$ isn't depend on $n$. I think you're interpreting it wrong... look at it this way: Say there were finite number of multiples in all subsets of $\mathbb{N}$, and as there are finitely many subsets, hence there must only be finitely many multiples of $n$, which is obviously a contradiction. But did this actually come in an Olympiad?

Yes.It is appeared @ Olympiad.

Olympus_mountaineer wrote: The set of natural numbers $\mathbb{N}$ are partitioned into a finite number of subsets.Prove that there exists a subset of $S$ so that for any natural numbers $n$,there are infinitely many multiples of $n$ in $S$. There is a typo. There is no 'of'. The set of natural numbers $\mathbb{N}$ are partitioned into a finite number of subsets.Prove that there exists a subset $S$ so that for any natural numbers $n$,there are infinitely many multiples of $n$ in $S$.

Olympus_mountaineer wrote: The set of natural numbers $\mathbb{N}$ are partitioned into a finite number of subsets.Prove that there exists a subset of $S$ so that for any natural numbers $n$,there are infinitely many multiples of $n$ in $S$. We proceed by contradiction. Let the subsets be $\mathcal{S}_1, \mathcal{S}_2, \dots , \mathcal{S}_k$. For each $1\leq i\leq k$, let $m_i$ be a natural number such that there do not exist infinitely many multiples of $m_i$ in $\mathcal{S}_i$. Let$M=m_1\cdot m_2\cdots m_k$. Now consider all the infinite multiples of $M$. By infinite pigeonhole principle, then there are infinitely many multiples of $M$ belonging to some subset $S$. Let such subset be $\mathcal{S}_j$. Then $\mathcal{S}_j$ contains infinitely many multiples of $m_j$, so we've reached a contradiction.

Assume that, there are total $k$ sets $(A_1, A_2, \cdots, A_k)$. For the sake of contradiction we assume that, in all the sets there are finite multiples of $n$. For each set $A_i$, we consider a function $f(A_i) = mn$, where $m$ is the maximum. If there aren't any, it simply return $0$ (On other words, for that case $m_i = 0$). So, if we consider all the outputs, \[S = \lbrace m_1n, m_2n, m_3n, \cdots m_kn \rbrace\] Let $\max(S) = n \times m_j$. Consider, $n(m_j + 1)$. Obviously $n(m_j + 1)$ and $nm_j$ doesn't belong to the same set. Say, it belongs to the set $A_{r}$, and we got an output $nm_r$ from this set, and it is the maximum value divisible by $n$ from this set. Note that, \[m_jn \geq m_rn \text{ and } m_rn \geq (m_{j} + 1)n\]Hence, contradiction.