Principles of Mathematics in Operations Research

Solutions 207

1.2 Observation: Every time we break a piece, the total number of pieces

is increased by one. When there is no pieces to break, each piece is a small

square. At the beginning when we had the whole chocolate with n squares

after 6=0 breaks, we had p—1 piece. After one break (6=1), we got p—2 pieces.

Therefore, p is always greater by one than b, i.e. p = b + 1. In the end,

p = b+ 1 = n.

The above argument constitutes a direct proof. Let us use induction to prove

that the above observation b = n — 1 is correct.

1. n = 2 => b — 1, i.e. if there are only two squares, we clearly need one
   break.


2. Assume that for 2 < k < n — 1 squares it takes only k — 1 breaks. In order
   to break the chocolate bar with n squares, we first split into two with k\
   and &2 squares {k\ + k 2 = n). By the induction hypothesis, it will take
   ki — 1 breaks to split the first bar and k^ — 1 to split the second. Thus,
   the total is

b = 1 + (fci - 1) + (k 2 - 1) = h + k 2 - 1 = n - 1.

1.3

Full Forward Method:

n\ n\ n\ in ).! 77.!

{n — r)\r\ r\(n — r)\ \n — r

Combinatorial Method:
(") denotes the number of different ways of selecting r objects out of n ob-
jects in an urn. If we look at the same phenomenon from the viewpoint of the
objects left in the urn, the number of different ways of selecting n — r objects
out of n is ( " ) • These two must be equal since we derive them from two
viewpoints of the same phenomenon.

CO C) = C7

1

) + »

Full Backward Method:

n-l\ (n-l\ _ (n-1)! (n - 1)

r J \r — lj (n — 1 — r)\r{r — 1)! (n — r)(n — r — 1)! (r — 1)!

(n — 1)! [n — r + r] fn^

(n — r)\r\ \r/

Combinatorial Method:

(") denotes the number of different ways of selecting r balls out of n objects in