I came across this interesting problem in the Olympiad Maths challenge practice problem, and it is really fascinating:
Some $n$ numbers are selected randomly from the integers $1$ to $420$. $2$ integers $a$ and $b$ are chosen from that set of $n$ numbers such that $a$ and $b$ are relatively prime. Find the minimum value of $n$ that ensures there exists $2$ such integers $a$ and $b$
If you don't know what relatively prime is it means that the two numbers don't share any factors greater than one (therefore the HCF of $a$ and $b$ is $1$)
My evaluation is that two numbers is relatively prime if at least $1$ of the number is prime, therefore not sharing any factors with the other number except $1$ (since primes have the factors only $1$ and itself).
This evaluation should work! UNLESS the second number is the prime number doubled, or tripled, or quadrupled, etc.
First of all, I have to deal with the fact that we're randomly picking from the set of $1$ to $420$, so I have to find the number of prime numbers between $1$ and $420$.
This post almost answers my prime question, but I tried $\pi(420) $ and I got about $69$ (Very nice coincidence by the way, $69420$). And the pool of answers is no near that (Multiple choice: $208, 211, 215, 220$) So I am now stuck in this hole precisely here.
Any help would be greatly appreciated!
Best Answer
This can be easily solved by using the pigeon hole principle.
Observe that if two numbers are consecutive, then they are relatively primes. Now one can pick every second number starting from $2$ till $420$ (all the even numbers). Now as every alternate number is picked already, the pigeonhole principle guarantees that picking any more numbers would result in a pair of consecutive numbers, which will be relatively prime.
$\therefore $ The minimum value of $n$ to guarantee that there will be $2$ relatively prime numbers in the chosen $n$ numbers is $211$.
Note: It is not necessary that one of the numbers is prime for the pair to be relatively prime. For example $(9,14)$ is such a pair of relatively prime numbers with none of them being prime. Any numbers of the form $a=p_1^{a_1}\cdot p_2^{a_2}\cdots p_n^{a_n}$ and $b=q_1^{b_1}\cdot q_2^{b_2}\cdots q_m^{b_m}$ are relatively prime $(p_i\neq q_i\space \forall\ i\in \mathbb N)$ with none of them being primes.