2
$\begingroup$

Prove that if $100$ integers are chosen from $1,2, \ldots, 200$, and one of the integers chosen is less than $15$, then there are two chosen numbers such that one of them is divisible by the other.


It is a classic exercise in combinatorics. For the answer, please refer to Choose 100 numbers from 1~200 (one less than 16) - prove one is divisible by another!. I want to move forward and ask something more. First, let me rephrase the question:

$100$ integers are chosen from $1,2, \ldots, 200$. Let $n$ be the smallest number of these chosen numbers. Prove that if $n=1,2,\ldots, 15$, then two chosen numbers can be found such that one of them is divisible by the other.


Now my question is:

Find all possible $n$.

This question comes to my mind when I first encounter this exercise. I was curious that why we should have the condition 'less than 16'. What if I change it to 'less than 17'? Does it mean that if $n=16$, it would be possible for me to find a counterexample? Of course, $n$ cannot be too large, as if $n=101$, then the chosen numbers would be $101, 102, \ldots, 200$ and none of them is a multiple of the others. So, I get the sense that some values of $n$ work, while some don't. So I post here to gather your opinions.

By the way, I cannot prove or disprove the statement when $n=16$. I think the idea to prove or disprove this case would help understand more about my ultimate questions.

$100$ integers are chosen from $1,2, \ldots, 200$. Let $n$ be the smallest number of these chosen numbers.

Prove or disprove: If $n=16$, then two chosen numbers can be found such that one of them is divisible by the other.

My attempt to construct a counterexample:

  • I noticed that no two numbers in the set $\{101, 102, \ldots, 200\}$ divides each other. So, I started with this set and added in $16$.
  • Then I had to remove $112, 128, 144, 160, 176, 192$.
  • I needed to add in some new numbers, but I then would need to, again, remove many more existing numbers. So I think it is getting nowhere....
  • Think in another direction: Start with an empty set. Add in the smallest number $16$. Then all the multiple of $16$ cannot be in the set.
  • Add in another number, say $17, 18, \ldots, 31$. Wait... Then I cannot add in anymore numbers...

I welcome any comments and suggestions.

$\endgroup$
  • $\begingroup$ If you read the accepted answer, you know that you need to be careful with what pigeon holes you choose, you can't just start off with all the numbers above $100$. That being said, it's entirely possible that the $16$ was not a real limit to the problem, but rather the limit as to where a pigeon hole proof stops being practical. $\endgroup$ – Arthur Sep 23 '15 at 13:48
0
$\begingroup$

There is a counterexample for the case where the condition is a number chosen is less than or equal to $16$. It is built on the ideas found in the question link and another similar question:

Prove that at most $100$ numbers can be selected

Form descending 2-sequences (these are the pigeonholes) starting with each term in $T=\{101,102,\ldots,199,200\}$, where each sequence is finite and ends on an odd term and the term in any sequence is the previous term divided by $2$. Denote each sequence by its starting term (note that $n=100$), e.g. $$\begin{array}{rll} S_{2n}&=(2n,n,\ldots)&=(200,100,50,25) \\ S_{2n-1}&=(2n-1) &=(199)\\ &\quad\vdots \\ S_{n+2}&=\{n+2,\ldots\}&=(102,51) \\ S_{n+1}&=\{n+1,\ldots\}&=(101) \end{array}$$

Every number in $\{1,2,\ldots,2n\}$ appears in exactly one of the $S_{k}$ because:

  1. Surjective. Every number inclusively between $1$ and $n$ has a multiple of a power of two inclusively between $n+1$ and $2n$. If not, $2 \ge \frac{2n+1}{n}$, which is absurd.
  2. Injective. No number can appear in more than one sequence. If this was untrue we could find two distinct terms in $\{n+1,n+2,\ldots,2n\}$, one of which is a multiple (of a power of two) of the other.

It is clear that every pair of terms in a given $S_{k}$ has the smaller term dividing the larger one, so we can choose at most one term from each $S_{k}$.
To construct a counterexample, we need to choose exactly one from each, and ensure that $16$ is included.

Sketch of the counteraxample P

When $n$ is odd, $S_n={n}$ has only one element, so this must be chosen. Hence, we need that $P$ contains every odd integer between $100$ and $200$, i.e. $$P_1=\{101,103,105,\ldots,199\}$$

This eliminates all submultiples so for the elements that cannot be chosen: $$Q_1=\{1,3,5,\ldots,65\}$$

For each odd number $n$ in $\{67,69,\ldots,99\}$ the relevant sequence is $S_n=(2n,n)$. It is less restrictive to choose $n$ than $2n$, since all further multiples of $n$ exceed $200$, and the submultiples of $n$ are a subset of those of 2n$. So choose

$$P_2=\{67,69,71,\ldots,99\}$$

This choice eliminates all numbers that are twice these:

$$Q_2=\{134,138,142,\ldots,198\}$$

Then for every large enough $n$ that is a multiple of $3$ in $P_1$ (and $4n>200$), the number $2n$ needs to be chosen (since $n,4n$ and higher multiples are excluded). So then

$$P_3=\{102,106,110,\ldots,130\}$$

The eliminated submultiples are:

$$Q_3=\{2,6,10,14,18,22,26,34,38,42\}$$

Now consider all even numbers at least $100$ that are not in $Q_2$ or $P_3$, a typical case is $196$ for which $S_{196}=(196,98,49)$ i.e. with an odd third number that is in $Q_1$. By an argument similar to that used before, it is preferable to choose the smaller of the two even numbers. This gives

$$P_4=\{50,54,58,62,66,68,70,74,76,78,82,84,86,90,94,98\}$$

which excludes the further multiples

$$Q_4=\{100,108,116,124,132,136,140,148,152,156,164,168,172,180,188,196,200\}$$

and additionally

$$Q_5=\{4,28,30\}$$

We are left with the disjoint 2-sequences (where entries that cannot be selected are removed), where one number must be chosen from each to make up the full quota of $100$:

$$\begin{array}{cllll} S_{128}'&=(128,64,32,16,8) & & S_{192}'&=(192,96,48,24,12) \\ S_{160}'&=(160,80,40,20) & & S_{144}'&=(144,72,36) \\ S_{184}'&=(184,92,46) & & S_{176}'&=(176,88,44) \\ S_{120}'&=(120,60) & & S_{112}'&=(112,56) \\ S_{104}'&=(104,52) \\ \end{array}$$

In addition, the numbers $8,12,20$ cannot be selected without preventing any selection from another 2-sequence. Hence

$$\begin{array}{clcllcll} S_{128}''&=(128,64,32,16) & & S_{192}''&=(192,96,48,24) & & S_{160}''&=(160,80,40) \end{array}$$

So it turns out that the following set is selectable as there are no pairwise multiples:

$$P_5=\{16,24,36,40,44,46,52,56,60\}$$

Resulting counterexample

Putting everything together a possible counterexample is:

$\begin{array}{ll} P&=P_1\cup P_2\cup P_3\cup P_4\cup P_5 \\ &=\{67,69,71,\ldots,199,\color{blue}{16},24,36,40,44,46,\\ &\quad 50,52,\ldots,62,66,68,70,74,76,78,82,84,86,90,94,98, \\ &\quad 102,106,110,\ldots,130 \} \end{array}$

$P$ contains $67$ odd numbers and $33$ even numbers, with the odd numbers being on average larger than the even numbers. This should not be major surprise.

$\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.