Counting Strategies: Casework, Complementary & Overcounting

How many ordered pairs $(a,b)$ with $a,b\in\{1,\dots,6\}$ have $a+b$ a multiple of $3$?

Case $a+b=3$: $(1,2),(2,1)$ — $2$ ways. Case $a+b=6$: $(1,5),(2,4),(3,3),(4,2),(5,1)$ — $5$ ways. Case $a+b=9$: $(3,6),(4,5),(5,4),(6,3)$ — $4$ ways. Case $a+b=12$: $(6,6)$ — $1$ way. These cases are disjoint and cover all multiples of $3$ between $2$ and $12$, so the total is $2+5+4+1=\boxed{12}$.

How many three-digit numbers have digits summing to $5$? Write the number as $\overline{abc}$ with $a\ge 1$. Case on the hundreds digit $a$: for each $a\in\{1,2,3,4,5\}$ the tens and units must sum to $5-a$, giving $(5-a)+1=6-a$ ordered choices. Summing, $5+4+3+2+1=\boxed{15}$ numbers.

How many three-digit numbers ($100$ to $999$) have at least one repeated digit? Total three-digit numbers: $900$. The complement is “all digits distinct”: the hundreds digit has $9$ choices ($1$--$9$), the tens digit $9$ choices (any but the hundreds), the units $8$ choices, giving $9\cdot 9\cdot 8=648$. Therefore the answer is $900-648=\boxed{252}$.

Five people sit in a row of five chairs, but Alice and Bob refuse to sit in the two end chairs. Build the seating: first place the three “unrestricted” people (call them the others). Actually, seat the restricted pair first, since they are the bottleneck. The two end chairs must be filled by $3$ non-restricted people: choose an ordered pair for the two ends in $3\cdot 2=6$ ways. The remaining $3$ chairs take the remaining $3$ people in $3!=6$ ways. Total $6\cdot 6=\boxed{36}$.

How many length-$4$ strings over $\{A,B\}$ have no two adjacent $A$'s? Build left to right and case on the number of $A$'s. Equivalently, place the $A$'s in gaps around the $B$'s: with $k$ $B$'s there are $k+1$ gaps and we choose positions for the $A$'s. For $0,1,2$ A's we get $\binom{5}{0}+\binom{4}{1}+\binom{3}{2}=1+4+3=\boxed{8}$.

How many distinct necklaces use $5$ different colored beads if rotations and reflections are considered the same? Line them up: $5!=120$ arrangements. Each necklace can be rotated $5$ ways and flipped $2$ ways, so it is counted $5\cdot 2=10$ times. Answer: $120/10=\boxed{12}$.

A club counts committees of $2$ from $6$ people by “pick a first member ($6$ ways), pick a second ($5$ ways)” getting $30$. But $\{X,Y\}$ and $\{Y,X\}$ are the same committee, counted $d=2$ times. The true count is $30/2=15=\binom{6}{2}$, showing $\binom{n}{k}=\dfrac{n!/(n-k)!}{k!}$ is exactly correcting for the $k!$ orderings.

How many solutions in nonnegative integers does $x_1+x_2+x_3=7$ have? Represent a solution as $7$ stars split by $2$ bars, e.g. $\star\star|\star\star\star|\star\star$. Each arrangement of $7$ stars and $2$ bars gives exactly one solution, so the count is $\binom{7+2}{2}=\binom{9}{2}=\boxed{36}$.

How many shortest grid paths go from $(0,0)$ to $(4,3)$ moving only right/up? Each path is a sequence of $4$ R's and $3$ U's — a bijection with strings, so $\binom{7}{3}=\boxed{35}$.

Roll a fair die $4$ times. Probability of at least one six? “No six” on all four rolls has probability $\left(\tfrac{5}{6}\right)^4=\tfrac{625}{1296}$. So $P(\text{at least one six})=1-\tfrac{625}{1296}=\boxed{\tfrac{671}{1296}}$.

Color the $3$ beads of a triangular bracelet with $2$ colors, rotations only ($G$ has $3$ elements: rotate by $0,1,2$). Identity fixes all $2^3=8$ colorings; each nontrivial rotation fixes only the $2$ monochromatic colorings. By Burnside, $\tfrac{1}{3}(8+2+2)=\tfrac{12}{3}=\boxed{4}$ distinct bracelets.

Count the distinct bracelets of $6$ beads, each black or white, where rotations and reflections are considered the same. The symmetry group is the dihedral group $D_6$ with $|G|=12$. Take a cycle census, using $\bigl|\mathrm{Fix}(g)\bigr|=2^{\mathrm{cyc}(g)}$.

Rotations by $k$ positions have $\gcd(k,6)$ cycles:

Reflections (six of them, since $n$ is even): $3$ axes pass through two opposite beads ($2$ fixed beads $+2$ swaps $=4$ cycles $\Rightarrow 2^4=16$ each), and $3$ axes pass through opposite edges ($3$ swaps $=3$ cycles $\Rightarrow 2^3=8$ each). Reflection sum $=3(16)+3(8)=48+24=72$. Therefore

(Rotations alone would give $84/6=14$ necklaces; folding in reflections identifies one mirror pair, leaving $13$.)

How many distinct ways can the $6$ faces of a cube be painted using $3$ available colors, where two paintings are the same if a rotation of the cube carries one to the other? The rotation group has $|G|=24$. Census of how each rotation type permutes the $6$ faces:

Averaging over the group,

The same recipe with $c$ colors gives $\tfrac{1}{24}(c^6+3c^4+12c^3+8c^2)$ colorings.

Naively “$2^6$ colorings, divide by $12$ symmetries” gives $64/12=5.33\dots$ — not even an integer, a red flag. The action is not free: the all-black bracelet is fixed by all $12$ symmetries (stabilizer size $12$, orbit size $1$), and a bracelet like BWBWBW is fixed by several rotations and reflections. These small orbits are exactly what Burnside's averaging accounts for, producing the correct $13$ from the previous section. Plain division is only correct for the asymmetric colorings, whose orbits genuinely have full size $12$.

Seat $7$ distinct people around a round table; rotations are equivalent (no reflections). No nontrivial rotation can fix an arrangement of $7$ distinct people, so the action of the $7$ rotations is free and every orbit has size $7$. Plain division is valid: $\frac{7!}{7}=6!=\boxed{720}$. The distinctness of the objects is what guarantees freeness.

How many integers in $\{1,2,\dots,1000\}$ are divisible by none of $2,3,5$? Let $A_p$ be the multiples of $p$. Then $|A_2|=500,\ |A_3|=333,\ |A_5|=200$; pairwise $|A_6|=166,\ |A_{10}|=100,\ |A_{15}|=66$; and $|A_{30}|=33$. The count divisible by at least one is

so the answer is the complement $1000-734=\boxed{266}$.

How many functions from a $5$-element set onto a $3$-element set $\{1,2,3\}$ are there? Let $A_i$ be the functions that miss value $i$. A surjection avoids every $A_i$, so

Direct casework on the “shape” of the preimages ($3{+}1{+}1$ vs. $2{+}2{+}1$) also works but is error-prone; the complementary/IE form is mechanical.

In how many ordered ways do three dice ($1$--$6$) sum to $10$? The generating function is $\bigl(x+x^2+\cdots+x^6\bigr)^3$, and we want the coefficient of $x^{10}$. Shift each die by $1$ (let $a'=a-1$, etc.), so we need $a'+b'+c'=7$ with $0\le a',b',c'\le 5$. Unbounded stars and bars gives $\binom{9}{2}=36$; subtract the solutions where some variable exceeds $5$ (i.e. is $\ge 6$). Forcing one variable up by $6$ leaves a sum of $1$ among three nonnegative variables, $\binom{3}{2}=3$ ways, and there are $3$ choices of which variable overflowed (no two can overflow since $2\cdot 6>7$). Thus

Compare the raw casework: summing $\#\{a+b=10-c\}$ over $c=1,\dots,6$ forces you to track the $1$--$6$ bounds on $a,b$ case by case; the GF/IE route handles every bound in one subtraction.