0
$\begingroup$

Prove that among $70$ distinct positive integers that are $≤ 200$, there must be two whose difference is one of $4, 5,$ or $9$.

So from this there are $582$ possible pairs whose difference is $4,5,$ or $9$.

(i.e. $\{5,1\},\{6,2\},...,\{200,196\};\{6,1\},\{7,2\},...,\{200,195\};\{10,1\},\{11,2\},...{200,191}$).

Thus, since there are more possible pairs with qualifying differences than there are numbers to choose...

Suggestions?

$\endgroup$
  • 1
    $\begingroup$ Try to break the numbers into trios, with the numbers in each trio differ by 4,5 and 9, for example $\{1,5,10\}$. Then you can't have more than one from each trio. $\endgroup$ – Empy2 Dec 1 '15 at 5:40
3
$\begingroup$

First prove that if 5 numbers are choosen from a range of 13 consecutive integers then at least two have a difference of 4, 5 or 9. Once this is done there are at most 16 such ranges from 1 to 200 so at most 64 numbers can be placed before a pair of them have distance of 4, 5 or 9.

Now consider the pairs of triples:

A: (1,5,10) and (1,6,10)

B: (2,6,11) and (2,7,11)

C: (3,7,12) and (3,8,12)

D: (4,8,13) and (4,9,13)

Assume 5 numbers are placed in the interval 1 to 13, then either they are 5,6,7,8 and 9 or one of the numbers 5 to 9, say m, is not used.

I the first case 9-5=4. Otherwise select one triplet from each pair A .. D of triplets not containing m. Now each of the five placed numbers is in one of the four selected triplets so there is a pair with distance 4, 5 or 9.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

We will show that if $A$ is any subset of $\{ 1, 2, 3, \ldots, 200\}$ such that no two integers in $A$ differ by 4, 5 or 9, then $|A| \leq 64$.

Let for any integer $k$, $A+k$ represent the set $\{a+k: a \in A\}$. Note that $A \cap A+4 = A \cap A = A \cap A+9 = A+4 \cap A+ 9 = A+5 \cap A+9 = \phi$. Thus \begin{align*} |A \cup A+4 \cup A+5 \cup A+9| &= 4|A| - |A+4 \cap A+5| \end{align*} Note that $A$ can not contain more than 4 consecutive numbers. Also, if it contains $i, i+1, i+2, i+3$, then $i+4, i+5, i+6, i+7, i+8, i+9, i+10, i+11, i+12$ can not belong to $A$. Thus in any set of 13 consecutive numbers, it can not contain more than 4 consecutive numbers. Note that $A+4 \cap A+5$ is maximum when it contains as many consecutive numbers as possible. Thus the maximum of $|A+4 \cap A+5|$ happens, we have $|A+4 \cap A+5|$ is at most $3 \times \lfloor \frac{200}{13}\rfloor + 4 = 49$. Hence $$4|A| - 49 \leq 4|A| - |A+4 \cap A+5| = |A \cup A+4 \cup A+5 \cup A+9| \leq 209$$ and $|A| \leq 64$.

A set with 64 elements is $$\{13k + 1, 13k+2, 13k+3, 13k+4: k = 0, 1, 2, \ldots, 15 \}$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

A simpler solution for the problem as stated:

Let the numbers be

$$a_1, a_2,\ldots, a_{70}$$ and consider $$a_1, a_2,\ldots, a_{70}, a_1+4, a_2+4, \ldots, a_{70}+4, a_1+9, a_2+9, \ldots, a_{70}+9$$ There are 210 numbers and all are $\leq 209$. Thus some two must be equal. If $a_i = a_j+4$ or $a_i = a_j+9$, we are done. If $a_i+4 = a_j+9$, then $a_i = a_j+5$ and again we are done.

| cite | improve this answer | |
$\endgroup$

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.