The set of positive integers is partitioned into finitely many subsets. Show that some subset $S$ has the following property: for every positive integer $n$, $S$ contains infinitely many multiples of $n$.
Problem
Source:
Tags: induction
25.05.2007 03:25
Consider the set $F = \{1!, 2!, 3!, ... \}$. One of the subsets $S$ must contain infinitely many members of $F$, and for every $n$ all large elements of $F$ are multiples of $n$, giving the result.
26.04.2009 10:50
induction on the number of sets also kills it
15.09.2011 09:21
Assume $A_1, A_2, .., A_k$ are sets of positive integers that partition $\mathbb{N}$ and assume $A_i$ contains only finitely many multiples of $a_i$. Then $\mathbb{N} = \bigcup_{i=1}^k A_i$ contains only finitely many multiples of $\prod_{i=1}^k a_i$; contradiction
31.03.2016 18:30
Maybe harder than it needs to be, but lets try induction on the number of sets. If a set contains infinitely many multiples of $n$ for every $n$, call it good. $k=1$: obvious. Assume true for $k-1$. Now consider $k$ sets $A_1,..,A_k$. Define $B$ as the union of $A_{k-1}$ and$ A_k$. Then among $A_1,...,A_{k-2}, B$ there is one good set. If this set is not $B$, we are done. Suppose the set is $B$. If $A_{k-1}$ is good, done. Else there is a number $m$ such that $A_{k-1}$ does not contain infinitely multiples of m. Then for a sufficiently large $t$, $A_k$ contains $mt,m(t+1),m(t+2),...$. In this sequence we can find a multiple of $n$ for any $n$, so $A_k$ is good, done.