1

This question originates from one of my tasks:

Choose $n+1$ whole numbers $a_1 \le a_2 \le ... \le a_{n+1}$ between $1$ and $2n$ inclusive.

Prove that among those $n+1$ number there exist 2 indexes $i$ and $j$ such that $a_i |a_j$, or $a_j$ is divisible by $a_i$

From my tests:

  • $n=1$ $\rightarrow$ choose 1 and 2
  • $n=2$ $\rightarrow$ choose 2, 3 (2 primes) and 4
  • $n=3$ $\rightarrow$ choose 2, 3, 5 (3 primes) and 4 or 6
  • $n=4$ $\rightarrow$ choose 2, 3, 5, 7 (4 primes) and any even numbers
  • $n=5$ $\rightarrow$ choose the upper 4 primes and 2 even numbers
  • $n=6$ $\rightarrow$ choose 2, 3, 5, 7, 11 (5 primes) and 2 even numbers

And with what I can notice up to $n = 10$, there will be always at most $n$ primes between $1$ and $2n$. Is this theory provable?

idkwhatismyname
  • 41
  • 5
    half are even. half are odd – sku May 21 '22 at 15:35
  • 1
    If important, it would have been noted in the elementary texts. Sku's remark above prove that the question is not important. Bertrand's postulate is a kind of "similar" question. – Piquito May 21 '22 at 15:53
  • For any positive odd number $n$, at most one of $n$ and $n+1$ might be prime (and if there is a prime, it must be $2$ if $n=1$ and $n$ otherwise). – Geoffrey Trang May 21 '22 at 16:09
  • I want to note that what you're doing for your proof isn't what the proof wants, I'm pretty certain. The idea is that the $n+1$ numbers between $1$ and $2n$ are supposed to be chosen randomly. That is, any choice of $n+1$ integers have at least one divisible by another. You don't get to choose. :) – Eric Snyder May 22 '22 at 05:44

0 Answers0