Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A friend of mine taught me this question. I found that it is related with 'Postage stamp problem' (though it does not seem to be same).

Let $m,a_1\lt a_2\lt \cdots\lt a_n$ be natural numbers. Now let us consider the following condition :

Condition : For each $k\in\mathbb N$ which satisfies $1\le k\le m$, $k$ can be represented as $a_i, 2a_i$ or $a_i+a_j\ (i\not=j)$.

Letting $\min_m(n)$ be the min of $n$, then here are my questions.

Question 1 : What is $\min_{m=100}(n)$ under the condition?

Question 2 : What is $\min_{m}(n)$ under the condition?

Example : For $m=100$, $(1,2,\cdots, 8,9,10, 20, \cdots,80,90)$ is an obvious example with $n=18$.

Motivation : For $m=100$, it was almost by chance that I discovered the following example with $n=16$ :

$$(1,3,4,7,8,9,16,17,21,24,35,46,57,68,79,90)$$ I expect that $\min_{m=100}(n)$ would be $16$, but I can't prove it.

For smaller $m$, we can get $\min_{m}(n)$ such as $$\min_{m=1}(n)=\min_{m=2}(n)=1,\min_{m=3}(n)=\min_{m=4}(n)=2,$$$$\min_{m=5}(n)=\min_{m=6}(n)=\min_{m=7}(n)=\min_{m=8}(n)=3,\min_{m=9}(n)=4.$$

Since we know that $(1,2,\cdots,k)$ is an example for $m=2k$, we get $\min_{m=2k}(n)\le k$ for any $k\in\mathbb N$. However, I don't have any good idea. Can anyone help?

Update : For $m=100$, I found an interesting example with $n=16$ : $$(1,2,3,7,11,15,19,23,27,28,29,30,61,64,67,70)$$ Using arithmetic progressions might be a key.

share|improve this question
1  
One can get 14 as a lower bound for $\min_{100}(n)$ by checking that 13 maximally yields 92 numbers. –  Uwe Stroinski Nov 10 '13 at 17:38
add comment

1 Answer

To my understanding, you are asking about the smallest size of a subset $A\subset[0,m]$ such that $[0,m]\subset 2A$ (where $2A:=\{a'+a''\colon a',a''\in A\}$ is the doubling of $A$). This is OEIS sequence A066063. There is no hope to give an explicit formula, but clearly, you need $\binom{|A|}2+|A|\ge m+1$, implying $|A|\ge(1+o(1)\sqrt{2m}$. On the other hand, one can get away with $|A|=(2+o(1))\sqrt m$: to see this, assume for simplicity that $m$ is a square, say $m=l^2$, and take $A=\{0,1,\ldots,l-1\}\cup\{l, 2l,\ldots,l^2\}$.

This problem has been studied and better bounds are known, but I do not have references handy.

share|improve this answer
3  
To add to Seva's answer: see this paper by Gunturk and Nathanson which discusses some history on the problem and gives new bounds arxiv.org/pdf/math/0503241.pdf . Interestingly the constant is neither $\sqrt{2}$ nor $2$. –  Lucia Nov 10 '13 at 18:10
    
@Seva&Lucia: Many thanks! I'm happy to read the paper. –  mathlove Nov 11 '13 at 4:42
    
I believe the question is asking for the smallest size of a set $A\subset [0,m]$ such that $[0,m]\subset 2A\cup A$, not $[0,m]\subset 2A$. –  Steven Landsburg Nov 15 '13 at 17:48
    
@Steven Landsburg: this is completely equivalent, as $[0,m]\subset 2A$ enforces $0\in A$, whence $2A\cup A=2A$. –  Seva Nov 15 '13 at 18:08
    
@Seva: Right. But I mistyped. I meant to say that the OP seems to have been asking for the smallest size of a set $A\subset[1,m]$ such that $[1,m]\subset 2A\cup A$. –  Steven Landsburg Nov 15 '13 at 19:45
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.