I recently came across an interesting problem in this document from the Berkeley Math Circle (year 2000). Namely, Problem 4 in page 2 asks:
Problem. A set $S$ of positive integers is called a finite basis if there exists some $n$ such that every sufficiently large positive integer can be written as a sum of at most $n$ elements of $S$. If the set of positive integers is divided into finitely many subsets, must one of them necessarily be a finite basis?
I do not have good intuition as to whether the answer is "Yes" or "No". If the answer were "No", it would seem very hard to come up with a counterexample (because showing that a particular infinite subset is not a finite basis seems daunting). On the other hand, if the answer were "Yes", it would require a proof that would work no matter how $\mathbb{N}$ were partitioned into finitely many subsets. Either case seems murky, and it is unclear to me how to proceed. If I were to bet, I would think the answer is "Yes".
I would appreciate any insight on this problem. Thank you!
The answer is no. Suppose that for every integer $N$, there exists an integer $k > N$ with no elements in $A$ between $k$ and $k^2$, and we'll prove this shows $A$ isn't a finite basis. To see this, suppose $nA = \mathbb{N}$. Find a $k > n$ according to the assumption, and look at $k^2$. Since all summands in the representation must be $\leq k^2$, but there are no elements in $A$ between $k$ and $k^2$, all of them must be less than $k$, so the maximum value is $n k < k^2$.
Now we will partition $\mathbb{N}$ to two sets, each having this property. We will start with both sets empty, and alternatively create a gap in each:
$$A = \{2,3,4,5^2+1,..,(5^2+1)^2, ((5^2+1)^2+1)^2+1, ...\}$$ $$B = \{1,5,6,...,5^2,(5^2+1)^2+1,...,((5^2+1)^2+1)^2, ...\}$$
It's easy to see both sets have the desired property, so neither is a finite basis.