1. Problem: Find how many integers $\leq 1000$ are not multiples of 4, 5, or 6. Step 1: Use Inclusion-Exclusion Principle. Step 2: Count multiples: - Multiples of 4: $\left\lfloor \frac{1000}{4} \right\rfloor = 250$ - Multiples of 5: $\left\lfloor \frac{1000}{5} \right\rfloor = 200$ - Multiples of 6: $\left\lfloor \frac{1000}{6} \right\rfloor = 166$ Step 3: Count multiples of pairwise intersections: - Multiples of $\mathrm{lcm}(4,5)=20$: $\left\lfloor \frac{1000}{20} \right\rfloor = 50$ - Multiples of $\mathrm{lcm}(4,6)=12$: $\left\lfloor \frac{1000}{12} \right\rfloor = 83$ - Multiples of $\mathrm{lcm}(5,6)=30$: $\left\lfloor \frac{1000}{30} \right\rfloor = 33$ Step 4: Count multiples of triple intersection: - Multiples of $\mathrm{lcm}(4,5,6)=60$: $\left\lfloor \frac{1000}{60} \right\rfloor = 16$ Step 5: Apply Inclusion-Exclusion: $$ \text{Multiples of 4 or 5 or 6} = 250 + 200 + 166 - 50 - 83 - 33 + 16 = 466 $$ Step 6: Total integers $\leq 1000$ are 1000, so those not multiples of 4,5,6: $$ 1000 - 466 = 534 $$ --- 2. Problem: Find number of permutations of $\{1,2,3,4,5,6\}$ where 1 and 6 are not at the ends. Step 1: Total permutations of 6 elements: $6! = 720$ Step 2: Count permutations with 1 or 6 at ends. Step 3: Number with 1 at an end: 2 ends $\times$ permutations of remaining 5 elements $= 2 \times 5! = 240$ Step 4: Number with 6 at an end: similarly 240 Step 5: Number with both 1 and 6 at ends: - 1 at left and 6 at right: $4! = 24$ - 6 at left and 1 at right: $4! = 24$ - Total: 48 Step 6: By Inclusion-Exclusion, number with 1 or 6 at ends: $$ 240 + 240 - 48 = 432 $$ Step 7: Number with neither 1 nor 6 at ends: $$ 720 - 432 = 288 $$ --- 3. Problem: Prove that among any 5 points inside an equilateral triangle of side 2 cm, there exist two points at distance $\leq 1$ cm. Step 1: Divide the triangle into 4 smaller equilateral triangles by connecting midpoints of sides. Step 2: Each smaller triangle has side length 1 cm. Step 3: By pigeonhole principle, placing 5 points into 4 smaller triangles means at least one triangle contains 2 points. Step 4: Maximum distance between any two points in a small triangle is its side length 1 cm. Step 5: Hence, there exist two points with distance $\leq 1$ cm. --- 4. Problem: Given set $A$ of 20 integers, prove there exists subset $B \subseteq A$ with $|B|=4$ such that for every $x,y \in B$, $x - y$ is divisible by 6. Step 1: Consider residues modulo 6 of elements in $A$. Step 2: There are 6 residue classes mod 6. Step 3: By pigeonhole principle, at least one residue class contains at least $\left\lceil \frac{20}{6} \right\rceil = 4$ elements. Step 4: These 4 elements form subset $B$ where differences are multiples of 6. --- 5. Problem: From 21 integers chosen from $\{1,6,11,\ldots,196\}$, prove there exist two whose sum is 197. Step 1: The set is an arithmetic progression with first term 1, common difference 5, last term 196. Step 2: Number of terms: $\frac{196 - 1}{5} + 1 = 40$. Step 3: Pairs summing to 197 are $(1,196), (6,191), (11,186), \ldots$ each pair sums to 197. Step 4: There are 20 such pairs. Step 5: Selecting 21 numbers from these 40 means by pigeonhole principle, at least one pair is chosen. Step 6: Hence, there exist two numbers whose sum is 197. Final answers: 1. 534 2. 288 3. Proven by pigeonhole and subdivision 4. Proven by pigeonhole on residues mod 6 5. Proven by pigeonhole on complementary pairs