Problem Set 1: Counting
Admissions-test preparation — arrangements, identities, inclusion–exclusion
Attempt each question before opening the solution. Solutions collapse in the web version and are printed in full in the PDF, so the same file serves as both handout and mark scheme.
Question 1
How many four-digit positive integers have digits that are strictly increasing from left to right?
A strictly increasing string of digits is determined entirely by which digits appear — there is exactly one way to order any chosen set. The digit \(0\) can never appear, since it would have to come first and no four-digit number begins with \(0\). So we are choosing \(4\) digits from \(\set{1,2,\dots,9}\): \[ \binom{9}{4} \;=\; 126 . \] The lesson worth extracting: “strictly increasing” converts an arrangement problem into a selection problem.
Question 2
Eight people sit at a round table. Seatings are considered the same if one is a rotation of the other. In how many seatings are two particular people, \(A\) and \(B\), not adjacent?
Fixing rotations, the total number of seatings of \(8\) people is \((8-1)! = 5040\).
Count the seatings we do not want. Glue \(A\) and \(B\) into a single block: we now seat \(7\) objects round the table, in \((7-1)! = 720\) ways, and \(A,B\) can be ordered within the block in \(2\) ways — giving \(1440\) adjacent seatings. Hence \[ 5040 - 1440 \;=\; 3600 . \]
Question 3
Prove that for every integer \(n\geq 1\), \[ \sum_{k=0}^{n} k\binom{n}{k} \;=\; n\,2^{\,n-1}. \tag{1}\]
Count in two ways the set of pairs \((S,x)\) where \(S\subseteq\set{1,\dots,n}\) and \(x\in S\) — a committee together with its designated chair.
Choosing the committee first. A committee of size \(k\) can be chosen in \(\binom{n}{k}\) ways, and its chair in \(k\) ways. Summing over \(k\) gives the left-hand side.
Choosing the chair first. There are \(n\) choices of chair, and the remaining \(n-1\) people may be included or not, independently: \(2^{\,n-1}\) ways. That is the right-hand side.
Both count the same finite set, so they are equal. \(\blacksquare\)
A calculus proof also works — differentiate \((1+x)^n=\sum\binom{n}{k}x^k\) and set \(x=1\) — but the double count explains why the identity holds.
Question 4
How many integers \(n\) with \(1\leq n\leq 1000\) are divisible by none of \(2\), \(3\) and \(5\)?
Let \(A_d\) be the set of multiples of \(d\) in range, so \(\abs{A_d}=\lfloor 1000/d\rfloor\). By inclusion–exclusion, \[ \begin{aligned} \abs{A_2\cup A_3\cup A_5} &= \left(500+333+200\right) - \left(166+100+66\right) + 33 \\ &= 1033 - 332 + 33 \;=\; 734 , \end{aligned} \] using \(\abs{A_6}=166\), \(\abs{A_{10}}=100\), \(\abs{A_{15}}=66\) and \(\abs{A_{30}}=33\). The answer is \(1000-734 = 266\).
As a sanity check, the “expected” proportion is \(\tfrac12\cdot\tfrac23\cdot\tfrac45=\tfrac{4}{15}\), giving \(266\tfrac23\) — close to \(266\), as it must be, with the discrepancy coming from \(1000\) not being a multiple of \(30\).
Question 5
Consider the statement \[ \forall x\in\R:\quad x^{2}>4 \implies x>2 . \]
- Write down the negation of this statement, without using the word “not”.
- Decide whether the statement is true, justifying your answer.
(a) The negation of \(\forall x\,(P(x)\Rightarrow Q(x))\) is \(\exists x\,(P(x)\wedge\neg Q(x))\): \[ \exists x\in\R:\quad x^{2}>4 \ \text{ and } \ x\leq 2 . \]
(b) The statement is false. Take \(x=-3\): then \(x^{2}=9>4\), but \(x=-3\leq 2\). One counterexample suffices.
The correct implication is \(x^2>4 \iff \abs{x}>2\). Squaring discards sign information, and a great many admissions-test questions live in exactly that gap.
Q1 and Q2 test whether a student can recognise which of selection and arrangement a problem calls for. Q3 rewards a bijective argument over manipulation. Q5 is the one that separates candidates: the common wrong answer to (a) inserts the negation in the wrong place, producing \(\forall x\,(x^2>4 \Rightarrow x\leq 2)\).