1
$\begingroup$

At least how many numbers of the set $\{1,2,...30\}$ be deleted so that the difference of no pairs of the members of that set equals $10$?

I found 10 pairs having a difference of 10:
$1,11 - 2,12 - 3,13 - 4,14 .... 10,20 $. I think if we select one number from each pair,the condition would be met,but is 10 the minimal answer?

$\endgroup$
  • $\begingroup$ What about $(11,21) , (12,22) ... (20,30)$? $\endgroup$ – Dionel Jaime Dec 1 '17 at 20:05
  • $\begingroup$ "the condition would be met,but is 10 the minimal answer?" Welp. I think the obvious next step is to prove via pigeon hole that any 21 numbers from 1.... 30 must have a pair whose difference is 10. Work on that. $\endgroup$ – fleablood Dec 1 '17 at 20:05
3
$\begingroup$

Let $A\subseteq\{1,2,\ldots,29,30\}$ be such that $10\not\in(A-A)$.
Let $S_1=\{1,11,21\},S_2=\{2,12,22\},\ldots,S_{10}=\{10,20,30\}$.
If $|A|\geq 21$, by the pigeonhole principle there is some $k$ such that $S_k\subseteq A$, leading to a contradiction (if $S_k\subseteq A$, then $10\in(A-A)$). It follows that the maximum size of $A$ is $20$ as conjectured. In such a case $A=[1,10]\cup[21,30]$.

$\endgroup$
  • $\begingroup$ So you mean $10$ is the minimum number of members to be deleted? $\endgroup$ – Hamid Reza Ebrahimi Dec 1 '17 at 20:14
  • $\begingroup$ @HamidRezaEbrahimi: yes, of course. $\endgroup$ – Jack D'Aurizio Dec 1 '17 at 20:14
  • $\begingroup$ Thanks :) , +1. $\endgroup$ – Hamid Reza Ebrahimi Dec 1 '17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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