<p>Number of ways of selecting three integers from \(\{1, 2, 3, \ldots, n\}\) if their sum is divisible by 3 is</p>
<p>\(3\binom{n/3}{3} + (n/3)^3\) if \(n = 3k,\ k \in N\)</p>
<p>\(2\binom{(n-1)/3}{C_3} + \binom{(n+2)/3}{C_3} + \left(\dfrac{(n-1)/3}{1}\right)^2\left(\dfrac{(n+2)/3}{1}\right)\) if \(n = 3k+1,\ k \in N\)</p>
<p>\(2\binom{(n-1)/3}{C_3} + \binom{(n-2)/3}{C_3} + \left((n-1)/3\right)^2\left((n-2)/3\right)\) if \(n = 3k+2,\ k \in N\)</p>
<p>independent of <i>n</i></p>
Step-by-Step Solution
Key Concept: Partition {1,2,...,n} into three residue classes modulo 3, then count selections where the sum of residues ≡ 0 (mod 3). This occurs when either all three are from the same class, or one from each class.
<p><strong>Step 1: Partition into residue classes.</strong><br>Partition {1,2,...,n} by residue mod 3:<br>• Class A (≡0 mod 3): {3,6,9,...}, size = ⌊n/3⌋<br>• Class B (≡1 mod 3): {1,4,7,...}, size = ⌈n/3⌉ or ⌊n/3⌋+1<br>• Class C (≡2 mod 3): {2,5,8,...}, size = ⌈n/3⌉ or ⌊n/3⌋<br><br>Let a = ⌊n/3⌋, b = ⌈(n+2)/3⌉, c = ⌈(n+1)/3⌉ denote the sizes.</p><p><strong>Step 2: Sum divisible by 3.</strong><br>Sum of three residues ≡ 0 (mod 3) when:<br>• All three from class A: C(a,3)<br>• All three from class B: C(b,3)<br>• All three from class C: C(c,3)<br>• One from each class: a·b·c</p><p><strong>Step 3: Apply to cases based on n mod 3.</strong><br><br><u>Case n ≡ 0 (mod 3):</u> a=b=c=n/3<br>Answer = 3·C(n/3,3) + (n/3)³<br><br><u>Case n ≡ 1 (mod 3):</u> a=(n-1)/3, b=c=(n+2)/3<br>Answer = C((n-1)/3,3) + 2·C((n+2)/3,3) + [(n-1)/3]·[(n+2)/3]²<br><br><u>Case n ≡ 2 (mod 3):</u> a=b=(n-2)/3, c=(n+1)/3<br>Answer = 2·C((n-2)/3,3) + C((n+1)/3,3) + [(n-2)/3]²·[(n+1)/3]<br><br>∴ Answer: ABC (all three cases evaluated separately or unified formula)</p>
Correct Answer: ABC