Swati's Secret Number

We know that there are 999 integers less than 1000, so this is the number of possible candidates for Swati's list. Now, we realize that in order for a number to be divisible by 15, it need to be divisible by both 3 and 5. There are 333 numbers less than 1000 that are divisible by 3. Similarly, there are 199 numbers less than 1000 that are divisible by 5. This means that there are 66 numbers that are divisible by both 3 and 5.

333 + 199 - 66 = 466 numbers less than 1000 that are divisible by 3 or 5. Subtracting this from 999, we get that there are 533 numbers less than 1000 that are divisible by neither 3 nor 5.

Now, imagine the following scenario. Swati's list contains all 533 of these numbers, and the numbers that are ONLY divisible by 3 (333 - 66 = 267). This means that ANY other number that is added to the list will have to be divisible by 5, and hence will satisfy the given condition, (being divisible by 15).

This makes for a total of 533 + 267 + 1 = 801 numbers in Swati's list. This is the minimum value for N so that Roma would be able to deduce the proposed statement (Two integers in Swati's list whose product was divisible by 15).

For there to be two numbers that multiply together to make a multiple of 15, there must be at least one multiple of three and at least one multiple of 5. Therefore for there to be no two numbers that fulfill this there must either be no multiples of 5 or no multiples of three. If there are no multiple of five then there are 1000/5 numbers that must be left out, leaving 800 non-multiples of five. Conversely, if there are at least 801 numbers, then one of them must be a multiple of 5. Since 1000/5 > 1000/3, out of the other 800 numbers, we know that one of those numbers must also be a multiple of 3. Hence, we have a pair of numbers whose product is a multiple of 15.

[Slight edits for clarity - Calvin]

If in N numbers, there is no number divisible by 5 , so there will be , no two numbers whose product will be divisible by 15. i.e. 1,2,3,4,6,7,8,9,11,12,13,14,16 ..... There are 199 nos. divisible by 5 in 1 to 999 Thus Swati can pick 800 numbers in which product of any two numbers can not be divided by 15. Now she has to add at-least one number which have no alternative but divisible by 5. & 3 is already available amongst first 800. Therefore Swati will have minimum 801 integers.

Note $15= 3\times 5$ . There are 333 multiples of 3, 199 multiples of 5, and 467 numbers that are neither multiples of 3 or 5 (C), from 1-999. Clearly, as long as a number from each of A and B can be guaranteed, we have the required condition of 2 numbers with a product divisible by 15. Clearly the smallest N that can guarantee this is 467+333+1=801.

To be divisible by $15$ , a number has to be divisible by $3$ and $5$ .

$1000$ is the $200$ th multiple of $5$

So, till $999$ , there are $199$ numbers divisible by $5$ and $800$ that are not divisible by it. This means that we can choose $800$ numbers and still not have the product of any two of these divisible by $5$ .

But as soon as we select the $801$ st number, we are sure to get at least one number divisible by $5$ . (I think this is called the pigeonhole principle).

Similarly for $3$ , if we select $667$ numbers, at least one of them is divisible by $3$ . But we know that we need at least $801$ numbers from our consideration of $5$ , and many out of these $801$ will be divisible by 3 , so $801$ is the answer

Suppose Roma Choice $999-\floor{\frac{999}{5}}=800$ number not divisible by $5$ .

if Roma Choice one again number, he get $N=\fbox{801}$

We need to exclude all numbers $< {1000}$ that are not divisible by $3$ , $5$ or both. To skip repeating numbers in our counting, lets first work with those numbers divisible by $3$ and $5$ . $\frac {1000} {15} = 66.67$ , so there are $66$ of those numbers. Now, those divisible only by $3$ are $\frac {1000} {3} - 66 = 267$ numbers. Now with five: $\frac {1000} {5} - 66 - 1 = 133$ . Why $-1$ ? Remember we're working with numbers $< 1000$ .

Now, in the worst of the cases, the list contains the $533$ other numbers not divisible neither by $3$ nor $5$ . Then, suppose the list contains the $267$ values divisible by $3$ . After this, the list is forced to have a number divisible by $5$ or by both $3$ and $5$ . So in this moment we'll have $2$ numbers with product divisible by $15$ . Finally, our answer is $533 + 267 + 1 = 801$ .

Important: Including $1000$ gives the same value, but is still wrong including the $1000$ .

As 1000/5=200, so we have 199 numbers less than 1000 which could be divisible by 5 and only 800 numbers couldn't so to be sure that the group I have have at least one number be divisible by 5, the group must be at least 801 numbers

Also as 1000/3=333.33, so we have 333 numbers less than 1000 which could be divisible by 3 and only 666 numbers couldn't so to be sure that the group I have have at least one number be divisible by 3, the group must be at least 667 numbers

so to be sure that the group I have have two numbers which one is divisible by 3 and the other is divisible by 5, it must be at least 801 numbers.

Between 1 and 999(endpoints included) there are 666 numbers which are not divisible by 3...Hence if we choose 667(or more) numbers at least one will be divisible by 3 .Similarly there are 800 numbers not divisible by 5 so choosing 801 numbers will compulsorily have 1 divisible by 5 so choosing 801 will ensure the existence of a multiple of 5 and a multiple of 3 the product of which will be divisible by 15!!!

Among the 999 numbers,800 numbers are not divisible by 5 so if we choose 801 then at least one will be divisible by 5.....Similarly 666(\m/The number of the beast\m/) numbers are not divisible by 3 which are included in the 801 numbers...So the minimum value of n is 801

Use Pigeon hole Principle..

We at first note that Swati's set consists of numbers strictly less than 1000.Let M be a function that gives us the number of multiples that are less than 1000.Therefore,

M(5)=199

M(3)=333

M(15)=66

NOTE: M(x)=ceiling of $999/x$

Therefore,number of positive integers not divisible by any of the numbers 3,5,15 is

$999-[M(3)+M(5)-M(15)]=999-466=533$

We also note that M(3)>M(5) i.e. 333>199.Also,the number of positive integers below 1000 divisible only by 3 or 5 are respectively $p=M(3)-M(15)$ and $q=M(5)-M(15)$ .Therefore,

Minimum of N=(Number of positive integers not divisible by both 5 and 3)+(the larger value between p and q)+1=533+267+1=801

Therefore,the smallest value of N could have been 801.