Porisma

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 (54) 4!/3!=20\binom54\,4!/3!=20 ways. Two runs 00 and one isolated zero occupy three gaps in (53) 3!/2!=30\binom53\,3!/2!=30 ways. The printed total is 1+20+30=511+20+30=51 nine-position binary strings.

How did this part go?

(a) Source method 2: classify all forbidden run patterns

There are 9!/(4!5!)=1269!/(4!5!)=126 unrestricted strings. Exclude the zero-run multiplicity patterns: [5] gives 5; [4,1] gives (52) 2!=20\binom52\,2!=20; [3,2] gives (52) 2!=20\binom52\,2!=20; and [3,1,1] gives (53) 3!/2!=30\binom53\,3!/2!=30. Thus 126−5−20−20−30=51126-5-20-20-30=51. These are disjoint maximal-run patterns, not overlapping choices of a substring 000.

How did this part go?

(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 4!/(2!1!1!)=124!/(2!1!1!)=12 ways. Therefore the answer under the literal integer interpretation is 4+12=164+12=16. The source’s 51 is correct only when these are nine-position strings with leading zeros allowed.

How did this part go?

(b)(i) Keep the two empty seats

The eight circular objects are six distinct people and two indistinguishable vacancies. Fix one person as reference: (8−1)!/2!=2520(8-1)!/2!=2520.

How did this part go?

(b)(ii) Numbered seats distinguish rotations

Assign that reference person to one of eight numbered seats: [(8−1)!/2!]×8=20160[(8-1)!/2!]\times8=20160.

How did this part go?

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.

Read the hint