What is the largest number of elements in a subset of $\{1,2,3, \ldots, N\}$ such that the sum of every pair of distinct elements in it is different?

$5$ is the largest cardinality. A set of $5$ elements is $\{1,2,3,5,8\}$ (as you already noted it contains Fibonacci numbers).

If we have a subset $S$ with $6$ elements such that the sum of every pair of distinct elements in $S$ is different then the number of such values is $\binom{6}{2}=15$. On the other hand, by summing two different numbers in $\{1,2,3,\dots,9\}$ we obtain $15$ different numbers: $3,4,5,\dots,17$. Since we have $15$ distinct values among $15$, we must have them all. Therefore we have $3$, which can be obtained only as $1+2$, and $17$, which can be obtained only as $8+9$. Hence $1,2,8,9\in S$ and we have a contradiction because $1+9=2+8=10$.

Tags:

Combinatorics

Related

How to evaluate $ \int_0^1 \frac{\ln(x+\sqrt{1-x^2})}{\sqrt{1+x^2}} \, \mathrm{d}x $ Find the sum of series without differentiation If $\lim_{x\to 0}\left(f(x)+\frac{1}{f(x)}\right)=2,$ show that $\lim_{x\to 0}f(x)=1$. Prove that $1 \leq A \leq \frac{5}{4}$ and $0 \leq B < \frac{81}{16}$ Invariant subspaces to the permuting action of the alternating group. Is every natural number the truncation of a prime? Finding remainder of $123^{456}$ divided by 88 using Chinese Remainder Theorem How large is the area that the bug can access? Counting summation of binomial coefficients Solving $\cos(2x)\cos\left(x - \frac{\pi}{6}\right) = \sin(2x)\sin\left(\frac{\pi}{6} - x\right)$ for $x\in(0,\pi/2)$ When does every compact $A$ in a topology satisfy $A⊆B⊆C$ for some open $B$ and compact $C$? Let $f$ be a real function and $a<b<c<d$. If $f$ is convex on $[a,c]$ and $[b,d]$, then can we say $f$ is convex on $[a,d]$?

Recent Posts