Problem 20 - Entrance Test

Let N_k be the number of integers from 1 to 1000 that are divisible by k. N_k = floor(1000/k). 1. Number of integers divisible by 3: N_3 = floor(1000/3) = 333. 2. Number of integers divisible by 5: N_5 = floor(1000/5) = 200. 3. Number of integers divisible by 15 (which means divisible by both 3 and 5, since 15 is the least common multiple of 3 and 5): N_15 = floor(1000/15) = 66. We are looking for integers that are divisible by 3 or 5, but not by 15. This can be broken down using the Principle of Inclusion-Exclusion. First, find the number of integers divisible by 3 or 5 (N_3 U N_5): N_3 U N_5 = N_3 + N_5 - N_15 N_3 U N_5 = 333 + 200 - 66 N_3 U N_5 = 533 - 66 = 467. This set includes all numbers divisible by 3, all numbers divisible by 5, and counts numbers divisible by 15 only once. Now, we need to find the numbers in this set that are NOT divisible by 15. Since the set of numbers divisible by 15 (N_15) is a subset of (N_3 U N_5), we simply subtract N_15 from N_3 U N_5. Number of integers divisible by 3 or 5 but not by 15 = (N_3 U N_5) - N_15 = 467 - 66 = 401. Alternatively, consider numbers divisible by 3 only, and numbers divisible by 5 only: Numbers divisible by 3 but not 5: N_3 - N_15 = 333 - 66 = 267. Numbers divisible by 5 but not 3: N_5 - N_15 = 200 - 66 = 134. The sum of these two categories gives the desired count: 267 + 134 = 401.