Swati made a list of N different positive integers, each strictly less than 1000. Swati told her friend Roma what the value of N was, and based on this value, Roma knew that there were some two integers in Swati's list that had a product divisible by 15. What is the smallest value that N could have been
A list of N different positive integers. There are some two integers that had a product divisible by 15. What is the smallest value of N
-2
$\begingroup$
combinatorics
-
1-1. Brain [still not engaged](http://math.stackexchange.com/q/241273) + outrageous comment = "winning" combination. – 2012-11-21
1 Answers
3
Among, $1$ to $999,$ there are $[\frac{999}5]=199$ multiples of 5.
So, there are $999-199=800$ positive integers $<1000$ which are not multiple of $5.$
So, if we take $N\ge800+1=801,$ the set will contain at least one multiple of $5.$
Similarly, for $N\ge999-\frac{999}3+1=667,$ the set will contain at least one multiple of $3$
So, if we take $N=max(801,667)=801,$ we shall definitely find at least one multiple of $5$ and of $3$.
-
0@chndn, welcome. But don't forget to avoid phrases like "I want answer in 10 mins (if u can)". – 2012-11-22