Worked solution
Distinguish nine-digit integers from nine-position binary strings
(a) How many different nine-digit numbers can be formed from five 0 s and four 1 s such that no three 0 s are together? marks
(b) Six people sit at a round table with eight identical chairs. Find the number of seating arrangements if
(i) there are no restrictions, marks
(ii) the seats are numbered. mark
[2011/TPJC/II/6]
CJC · Review problems · Question 5
Answer
(a) 16 ordinary nine-digit integers; the printed 51 counts strings allowing leading 0. (b)(i) 2520; (ii) 20160.
(a) Source method 1: retain its binary-string interpretation
The printed answer 51 allows leading zeros. Place the four identical 1 s, creating five gaps for zero runs. No run may exceed length 2. Five isolated zero runs fill all five gaps in 1 way. One run 00 and three isolated zeros occupy four gaps in ways. Two runs 00 and one isolated zero occupy three gaps in ways. The printed total is nine-position binary strings.
(a) Source method 2: classify all forbidden run patterns
There are unrestricted strings. Exclude the zero-run multiplicity patterns: [5] gives 5; [4,1] gives ; [3,2] gives ; and [3,1,1] gives . Thus . These are disjoint maximal-run patterns, not overlapping choices of a substring 000.
(a) Qualify the printed “nine-digit numbers” wording
An ordinary nine-digit integer cannot start with 0. It must begin with 1, so only the four gaps after/between the four 1 s can contain zero runs. To place five zeros with each run at most 2, either the run sizes are a permutation of (2,1,1,1), giving 4 ways, or of (2,2,1,0), giving ways. Therefore the answer under the literal integer interpretation is . The source’s 51 is correct only when these are nine-position strings with leading zeros allowed.
(b)(i) Keep the two empty seats
The eight circular objects are six distinct people and two indistinguishable vacancies. Fix one person as reference: .
(b)(ii) Numbered seats distinguish rotations
Assign that reference person to one of eight numbered seats: .
Common mistakes
The source’s two methods agree on 51 but both include leading-zero strings. Agreement between methods does not resolve the prompt’s integer/string ambiguity.
Solution notes
Both printed methods, every run-pattern count, source 51 and both seating counts retained. The source says nine-digit numbers without a leading-zero allowance; its 51 is qualified as a string count and the literal integer answer 16 is derived. Original native transcription preserved.