This problem is polynomially reducible to $ \mbox{NP - hard}$ problem of finding a monochromatic clique in graph.

Yes, but so is every problem in $ \bf P$

can any body post solution of this problem

Sage! wrote: This problem is polynomially reducible to $ \mbox{NP - hard}$ problem of finding a monochromatic clique in graph. But that does not mean this problem is in NPC.

Let $c = gcd(a, b)$, so $a = ca_1$ and $b = cb_1$. Therefore, $ca_1b_1$ is divisible by $a_1 + b_1$. Furthermore, since $gcd(a_1, b_1) = 1$, we see that $a_1 + b_1$ is relatively prime to $a_1$ and $b_1$, so $(a_1 + b_1) | c$. Since $a + b \le 99 \Rightarrow a_1 + b_1 \le 9$. Clearly, we must have $a_1 + b_1 \ge 3$, so we can go through the cases to find possible pairs (a, b): (6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24); (12, 4); (24, 8); (36, 12); (48, 16) (20, 5), (40, 10), (15, 10), (30, 20), (45, 30) (30, 6) (42, 7), (35, 14), (28, 21) (40, 24) (45, 36) yielding 23 pairs and 24 numbers. Therefore, there are 26 numbers not listed above. Thus, $K > 26$. Now we need to find the smallest possible value of $K - 26$ such that any group of $K - 26$ we choose from the 24 will result in at least one ordered pair showing up. We see that this minimum value is 13, so we obtain the minimum value of $K$ being $\boxed{39}$.

From $a+b|ab$, we can rewrite $b$ as $ka$. We now have $(k+1)a|ab\implies(k+1)|b$. We can now generate pairs $(a,b)$ be taking $q$, a factor of $a$, and letting $b=a(q-1)$. We can make the following observations. Odds beyond $25$ do not generate any useable pairs. Similarly, $17$, $19$ and $23$ do not generate anything. Evens above $24$ only generate useable pairs of the form $(a,a)$, as do $2$, $3$, $14$, $20$ and $22$. $4$ generates only $(4,4)$ and $(4,12)$, so we can throw this in too. Finally, we also throw in $11$ and $13$. Out total is now $13+3+13+5+1+2=37$. Adding one for $1$, we get $38$. Whatever our next number is, we will have a pair that satisfy the conditions, so the answer is $\boxed{39}$.

fclvbfm934 wrote: Let $c = gcd(a, b)$, so $a = ca_1$ and $b = cb_1$. Therefore, $ca_1b_1$ is divisible by $a_1 + b_1$. Furthermore, since $gcd(a_1, b_1) = 1$, we see that $a_1 + b_1$ is relatively prime to $a_1$ and $b_1$, so $(a_1 + b_1) | c$. Since $a + b \le 99 \Rightarrow a_1 + b_1 \le 9$. Clearly, we must have $a_1 + b_1 \ge 3$, so we can go through the cases to find possible pairs (a, b): (6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24); (12, 4); (24, 8); (36, 12); (48, 16) (20, 5), (40, 10), (15, 10), (30, 20), (45, 30) (30, 6) (42, 7), (35, 14), (28, 21) (40, 24) (45, 36) yielding 23 pairs and 24 numbers. Therefore, there are 26 numbers not listed above. Thus, $K > 26$. Now we need to find the smallest possible value of $K - 26$ such that any group of $K - 26$ we choose from the 24 will result in at least one ordered pair showing up. We see that this minimum value is 13, so we obtain the minimum value of $K$ being $\boxed{39}$. How could a+b<=99 implies a+b<=9?

Given $c(a_{1}+b_{1})\le 99 = 9 \cdot 11$ We know $a_{1}+b_{1} \mid c \Rightarrow$ $a_{1}+b_{1} \leq c$ From $(1)$, we get $a_{1}+b_{1} \leq 9$, as $a_{1},b_{1} \in \mathbb{Z^{+}} \blacksquare $

Holy this one took me so much Notice $a+b | a^2$ and thus you may check that $(a,ka)$ is a solution for $7>k>1$ and counting the number of pairs you'd get 16 pairs. But some numbers are repeated and thus by pingeonhole and some more couting you get that in the worst case a 39 number subset solves the problem. Then to show that $(a,ka)$ are the only pairs is what took me a lot of time: fix $a$ and vary $b$. When $a$ is a power of a prime then $b | a$ obviously. Thus we are only left with the following numbers from 1 to 50: $28,44,45,50$ (excluding all the pairs $(a,ka)$ that worked as above shown, but case-check work gives that none of $28,44,45,50$ work, and we're done.