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. How many seatings are possible?

Solution. The end chairs are the bottleneck, so fill them first, from the $3$ people who are neither Alice nor Bob: $3$ choices for the left end, then $2$ for the right end, $3\cdot 2 = 6$ ways. The three middle chairs take the three people left (Alice, Bob and one other) in any order, $3! = 6$ ways. At every step the number of choices is the same whatever happened before, so the total is $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.