Not so likely after all

First, we claim that $N \ge 152$ . Consider the set that contains all multiples of $4$ and odd integers. There are $151$ elements, and no two numbers have gcd equal to $2$ , thus $N \ge 152$ .

On the other hand, $N \le 152$ because if $152$ numbers is chosen from the set $\{1, 2, 3, ..., 201\}$ , at least $152 - 101 = 51$ of them are even. Partition the set of even numbers $\le 200$ into $50$ pairs, $\{2, 4\}, \{6, 8\}, ... , \{198, 200\}$ . Note that the gcd of the numbers in any pair is $2$ . By pigeonhole principle, $2$ of the selected numbers will fall into the same pair. This completes our proof. Thus, $N = \boxed{152}$ .

First, note that a subset with $152$ elements must contain two numbers whose gcd is 2 because this subset necessarily contains two consecutive even integers. Thus, $gcd(2n, 2n + 2) = 2 gcd(n, n + 1) = 2$ .

Now, we only need to show that there exists a $151$ element subset which has no pair of elements whose gcd is 2. This can be done by creating a subset of all of the odd numbers and all of the numbers divisible by $4$ . There are $101$ odd numbers and $50$ numbers divisible by $4$ , thus we have just created a $151$ element subset which does not contain two numbers whose gcd is $2$ . So, we affirm $152$ as our answer. $\blacksquare$

To find the smallest case where N has this property we must consider the worst case, that is, the case where we have the maximum number of elements in the subset without any pair of the integers in the subset having a greatest common divisor of 2.

The subset must therefore contain all of the odd numbers between 1 and 201 inclusive, as no two odd numbers can have a gcd of 2. Then surely if we add two more numbers to the subset, those two numbers must both be even and therefore have a gcd of 2. Not quite, of course, because we could have two even numbers with a gcd of 4 (or 8, or 16, etc). Hence the subset must contain all of the elements in the original set that are divisible by 4. Then, if we add one more element to the subset, the condition will be met.

Hence the smallest value of N is 101 (there are 101 odd integers between 1 and 201 inclusive) + 50 (there are 50 integers divisible by 4) + 1 = 152

Since the question says that "for any subset" , we'll consider the worst case...

First let's find out what we need... At first we need at least two even numbers... If $\text{gcd}(a,b)=2$ , then at least one of $a$ and $b$ must have exactly one $2$ in it's prime factorization...

Note that in the set $\left\{1,2,3,...,201\right\}$ , there's exactly $\left \lfloor{\dfrac{201}{2}}\right \rfloor=100$ even numbers and so there's exactly $101$ odd numbers... Notice that some of the even numbers have more than one $2$ in it's prime factorization... Let's find out the number of evens which have only one $2$ in it's prime factorization... It's simply $100-\left\lfloor{\dfrac{201}{4}}\right\rfloor=50$ ...

Remember that we need to consider the worst case... Suppose the subset is $S$ ... Let's pick up all of the $101$ odd numbers in $S$ ... Now we have all of the $100$ even numbers in $S^{\mathsf{c}}$ ...

For the sake of the worst case, now we pick up all $50$ of the evens who have more than one $2$ in their prime factorizations... We now have $101+50=151$ elements in $S$ ... Now we need just one of the remaining evens in $S^\mathsf{c}$ who have just one $2$ in their prime factorizations...

In total, we have the smallest value of $N$ which is: $N=151+1=\fbox{152}$

We claim that $N=\boxed{152}$ . First, we will show that 152 satisfies the property. There are 101 odd numbers in the set, and so at least 51 of the 152 must be even. Then, all 51 numbers are elements of the set $\{2,4,6,\cdots,200\}$ and every pair of numbers must have a greatest common divisor of at least 2. If every pair of numbers has a greater common divisor, they must be all divisible by an additional prime, possibly 2. The even number larger than 2 that has the most multiples among the even numbers up to 200 is 4, which has 50 multiples. Therefore, the 51 numbers cannot all be divisible by a number larger than 2, and thus 152 satisfies the property.

It remains to be shown that 151 doesn't satisfy the property. Let $A=\{1,3,5,\cdots,201\}$ and $B=\{4,8,12,\cdots,200\}$ We claim that the subset $A\cup B$ ,with 151 elements, has no pair of elements with greatest common divisor 2. Both must be even, and thus in set $B$ . However, all elements of $B$ are multiples of 4, so each pair within the set $A\cup B$ has greatest common divisor 1 or at least 4.

Therefore, the answer is $N=\boxed{152}$ .

Motivation: I tried to make a set with as many elements as possible without a pair with greatest common divisor of 2. I first took all the odd numbers, and then tried to find as many even numbers as possible that shared an additional divisor.

First take all the odd numbers $1,3, \ldots, 201$ (total $101$ numbers) in a set and $gcd$ of the set is not $2$ . Now add all multiple of $4$ ( $4,8, \ldots, 200$ , i.e., total $50$ numbers) in the set to make the cardinality of the set $151$ and still in this set no two numbers whose $gcd$ is $2$ . Now, add any one digit from the remaining numbers ( $2,6, \ldots, 198$ ) in the set we can find two numbers whose greatest common divisor is exactly $2$ . So the answer is $\boxed{152}$ .

Motivation: Our motivation is to find the set with maximum cardinality and still we can't find any two numbers whose $gcd$ is exactly $2$ . So first take all odd numbers from the original set. Now we have to take two even numbers to get the $gcd$ is exactly $2$ . At this stage, if we take all digits multiple of $4$ , we still unable to find any two numbers such that $gcd$ is exactly $2$ . At this stage the constructed set is of maximum cardinality and $gcd$ is not $2$ . Now add any integer from $2,6, \ldots$ to get two numbers whose greatest common divisor is exactly $2$ .

Generalize: For any odd integer $n$ , which is the maximum number of the set, $N={\frac{n+1}{2}}+\lfloor{\frac{n}{4}}\rfloor+1$ .

For any even integer $n$ , which is the maximum number of the set, $N={\frac{n}{2}}+\lfloor{\frac{n}{4}}\rfloor+1$ .

101 odd numbers + 50 multiples of 4 + 1 even number = 152 numbers

Let U={1,2,3,...,2013}. Let P(n) be the property that any subset of U with n elements must contain two numbers whose greatest common divisor (GCD) is 2. We wish to find the smallest n for which P(n) is true.

Let S be the subset of numbers which are divisible by 2 but not by 4. Then S= {2,6,10,...,198}. Also, |S|=50.

U\S is a subset of U with 151 elements that doesn't have two numbers with GCD exactly 2. For each n<=151, we can find a subset of U\S that doesn't satisfy the desired property. Therefore P(n) is false for all n<=151. Therefore, N >=152.

Let T={4,8,12,...,200}.

Any subset A of U with 152 elements will have at least one element s from S and at least one element t from T. GCD(s,t) = 2.

Generalization

For U = {1,2,3,...,K} with K>=4 (?), N=[(3K+5)/4], where [.] is the greatest integer function.

We have to find the two numbers whose GCD is exactly 2, so (4, 2) is an example.

To find this, first we eliminate all of the odd numbers because odd numbers do not have 2 as a factor.

There are ((201-1)/2)+1=101 odd numbers in this subset.

Then, we eliminate all the multiples of 4 because (multiple of 4, multiple of 4)'s GCD is 4, not 2.

There are 50 multiples of 4.

Now we will need a multiple of 2, but not of 4 to complete the subset.

It can be any multiple of 2, but not a multiple of 4. (2, 6, 10, etc.)

So the answer is 101+51+1=152.

Take out all the odd numbers there are 202/2=101 of them

Take out all the multiples of 4 there are 200/4=50 of them

Then you just need 1 number divisible by 2 yet not divisible by so that when you can just choose this particular number and one of the multiples of 4 and this pair will have GCD of 2

SO grand total of $101+50+1= \boxed{152}$

101 ta odd no..50ta multiples of 4..total 151 elements no two of which have gcd 2. Ete 2 add kor..152 element subset

In {1,2,3....,201} number of odd integers is 101 , multiples of 4 is 50 and remaining odd multiples of 2 is 50. In order to get a set with GCD exactly 2, also considering worst case situation, the set should contain all the odd integers and all the even multiples of 2 (multiples of 4) (such that now the GCD is 4) and atleast one odd multiple of 2 to get an exact GCD 2. Therefore the answer is 101 + 50 + 1 = 152.

Look at the subset containing all the odd numbers in S = {1,2,3,....,201} as well as all the multiples of 4. This subset will contain 101 odd numbers and 50 multiples of 4 for a total of 151 elements, no two of which have a gcd of 2. Any remaining element a of S that we then add to this 151-element subset will be such that gcd(a,4) = 2. So this means that P = 152.

Note that in order for the gcd of two numbers to be 2, they must be of the form $2\cdot m_1$ and $2^a\cdot m_2$ , where $m_1,m_2$ are odd and $a\ge 1$ . So the pairs we are looking for (that have gcd=2) are of the form $(2m_1,2^am_2)$ . (*)

The number of numbers in the set that are of the first form is 50, because $m_1$ can take the values $1,3,...,99$ .

This means that 201-50-151 numbers cannot be the first pair in (*). This means that if N=151, one of the subsets can have no such numbers of the form $2m_1$ ( $m_1$ odd) and so does not satisfy the property.

Now the next number up, 152, does indeed satisfy the property. This is because by the pigeonhole principle, at least one of the numbers in any subset will be of the form $2m_1$ ( $m_1$ odd), and similarly by the pigeonhole principle, at least one of the remaining numbers in the subset will be of the form $2^am_2$ . So the answer is $\boxed{152}$ .

Let's look at this problem from a different point of view:

We want to find the LARGEST N for which there exists a subset of length N that haven't any pair whose gcd is 2.

We can start by adding all prime numbers in the set, we are sure that any pair's gcd is 1. Let's extend it a little bit, we actually can add all the odd numbers between 1 and 201. Now we have 101 numbers in our set and the remaining numbers are even numbers. After a little more thinking, we find out that we can add all numbers that are multiples of 4 as any pair of them will have a gcd == 4.

Lemma : if X divides Y and X divides Z then X divides Y - Z

Now we have 151 element in our set and we are left with multiples of 2 that aren't multiples of 4 at the same time, a total of 50 numbers. Now it's clear that if we add any element to the set there will be some pairs whose gcd is 2, so the answer is $\boxed{152}$

Since we must guarantee having two numbers whose greatest common divisor is 2, it's a good idea to think of the "worst-case scenario" that we can have while constructing the subset.

First, I realized that any even number has 2 as a divisor, so then I thought about what would happen if we unluckily picked all odd numbers in the original set. This list of odd numbers is $1, 3, 5, 7, ..., 199, 201$ , and there are $\dfrac{201+1}{2} = 101$ numbers in this list (add 1 to each term and divide by 2). So, we know that $N$ is at least $101$ .

Then, I thought, isn't it just $101+2 = 103$ ? After selecting all odd numbers left, we have to pick two even numbers, so we add $2$ to get $103$ . But, this misses the fact that the greatest common divisor is EXACTLY $2$ . Again, we could be unlucky and choose two numbers whose greatest common divisor is even, but not $2$ . How would this happen? Well, if we unluckily pick all the multiples of $4$ , then the greatest common divisor would be $4$ . The multiples of $4$ in the range are $4, 8, 12, ..., 196, 200$ . There are $\dfrac{200}{4} = 50$ terms in this list. So, our $N$ raises to $101+50 = 151$ .

Now, no matter what element we pick next, it will be even but not have a factor of $4$ in it, so we add $1$ to $N$ , to get the answer, $\boxed{152}$

Motivation: As I said before, the worst-case scenario allows us to figure out when the result will be guaranteed. Also, the fact that the GCD is exactly 2 suggests that there is a good way to solve the problem using parity.