Produce a set A such that r(n)>0 for all n in [1,N], but with |A|<= sqrt(4N+1). Note that r(n)=∣∣{(a,a′):a,a′ in A,n=a+a′}∣∣

Cindy Noble 2022-09-04 Answered
Produce a set $A$ such that $r\left(n\right)>0$ for all $n\in \left[1,N\right]$, but with $|A|\le \sqrt{4N+1}$.
Note that
$r\left(n\right)=|\left\{\left(a,{a}^{\prime }\right):a,{a}^{\prime }\in A,n=a+{a}^{\prime }\right\}|$
$A=\left\{0,1,2\right\}$ would work with the interval being $\left[1,4\right]$. Then $3\le \sqrt{17}$.
A second part of the question shows that one can prove that $|A|\le \sqrt{N}$ if it satisfies the above conditions. But $3>\sqrt{4}=2$. Does this mean that my set $A$ is wrong?
You can still ask an expert for help

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it

Answers (1)

Peutiedw
Answered 2022-09-05 Author has 9 answers
It should be $|A|\ge \sqrt{N}$, since you need at least that many numbers in $A$ to form enough pairs to produce all the $N$ numbers.
Did you like this example?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it