Largest set $B$ such that $|A\cap (B-B)|=p$ In a preprint I was reading the following was claimed without proof:

Let $A$ be a subset of $[n]:=\{1,2,\dots n\}$ where $|A|<\frac{n}{k}$ for some integer $k$. Then there exists a set $B\subset [n]$ such that $|B|=k$ and there exists no $b_1,b_2\in B$ such that $b_1-b_2 \in A$. (subtraction is not done mod $n$)

I am struggling to see how this is true. How would one prove this? If it is false, I would be interested in a proof of a weaker claim, such as "if $|A|<n/k^2$ then there exists a set $B$ with $k$ elements such that there exists no $b_1,b_2\in B$ such that $b_1-b_2 \in A$." (a probabilistic argument almost works for this weaker claim, but I couldn't figure out how to make the difference set of $B$  uniform enough)
 A: Edit. From the comments below, there was a typo which has been fixed.  Note that this answer only works if $k^2-k+1\leq n$.  I will see if this can be improved, although from the remark below that there are cases with $k^2-k+1>n$ such that there is a counterexample.
Write $[n]:=\{1,2,3,\ldots,n\}$.  Note that $|A|\leq \dfrac{n-1}{k}$. Presumably, $$B-B:=\{b-b'\,|\,b\text{ and }b'\text{ are in }B\}\,.$$
We shall determine elements $b_1<b_2<b_3<\ldots<b_k$ of $B\subseteq [n]$ inductively.  First, set $b_1:=1$.  Suppose that $l$ is a positive integer such that $l\leq k$ and $b_1,b_2,\ldots,b_{l-1}$ have been defined.
Consider $$T_{l-1}:=\{b_1,b_2,\ldots,b_{l-1}\}\cup\displaystyle\bigcup\limits_{r=1}^{l-1}\,\big(b_r+A\big)\,,$$ where $x+A:=\{x+a\,|\,a\in A\}$ for any $x\in \mathbb{Z}$.  We note that $$\begin{align}|T_{l-1}|&\leq \big|\{b_1,b_2,\ldots,b_{l-1}\}\big|+\sum_{r=1}^{l-1}\,\big|b_r+A\big|=(l-1)+\sum_{r=1}^{l-1}\,|A|
\\&=(l-1)+(l-1)\,|A|\leq (l-1)+(l-1)\,\frac{n-1}{k}\\&=(l-1)\,\frac{n-1+k}{k}\leq n-1\,,\end{align}\tag{*}$$
because $$(n-1)(k-l+1)\geq n-1\geq k^2-k=(k-1)k\geq (l-1)k\,.$$
Hence, $[n]\setminus T_{l-1}$ is nonempty.  Let $b_l$ be the least element of $T_{l-1}$.  Because $T_1\subseteq T_2\subseteq \ldots \subset T_{l-1}$, we conclude that $$b_1<b_2<\ldots<b_{l-1}<b_l\,.$$
By induction, the set $B:=\{b_1,b_2,\ldots,b_k\}$ has the property that $|B|=k$ and $A\cap (B-B)=\emptyset$.  The proof is now complete.
Example.  Let $n:=7$, $k:=3$, and $A:=\{1,4\}$.  Then, the procedure above produces

*

*$b_1=1$ with $T_1=\{1,2,5\}$;

*$b_2=3$ with $T_2=\{1,2,3,4,5,9\}$;

*$b_3=6$ with $T_3=\{1,2,3,4,5,6,7,9,10\}$.

Hence, $B=\{1,3,6\}$ satisfies the requirement.  Note that
$$B-B=\{-5,-3,-2,0,2,3,5\}$$
is disjoint from $A=\{1,4\}$.
Remark.  Let $k\geq 3$ be an integer.  Suppose that $n=(k-1)^2$.  Then $k^2-k+1>n$.  Note that $\left\lfloor\dfrac{n-1}{k}\right\rfloor=k-2$, so we take $A:=[k-2]$.  We shall prove that the set $B$ does not exist.  Partition $[n]$ into $$X_i:=\big\{(i-1)(k-1)+1,(i-1)(k-1)+2,\ldots,i(k-1)\big\}$$ for $i=1,2,\ldots,k-1$.  Observe that, if $B$ exists, then $B$ much contain at most one element from each of the sets $X_i$ for $i=1,2,\ldots,k-1$.  This means $|B|\leq k-1$, which leads to a contradiction.
P.S.  If $|A|\leq \dfrac{n}{k^2}$, then we only need $k\leq n$ (the condition $k^2-k+1\leq n$ is unnecessary).  The inequality (*) can be improved and become
$$|T_{l-1}|\leq (l-1)+(l-1)\frac{n}{k^2}\,.$$
Since $$\begin{align}n\left(k^2-l+1\right)&\geq n(k^2-k+1)\geq k(k^2-k+1)\\&> k(k^2-k)=k^2(k-1)\geq k^2(l-1)\,,\end{align}$$
we conclude that $|T_{l-1}|<n$.  By a similar argument, the set $B$ exists.
