Concrete Math Reading Notes(01)

17 minute read

A Foundation for Computer Science

In this part, I’d like to write a serial reading notes about Concrete Math, and I will record my thought and understanding about this book.

And in this section, I read the chapter one of Concrete Math, and this chapter explores three recurrent problems, and gives some magic on how to solve those question.

THE TOWER OF HANOI

The tower of hanoi was invented by French mathematician Edouard Lucas in 1883, and we are given raise your hand a tower of eight disks, initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller

Thinking1

It is not easily obvious that this is a recurrent problem, if we didn’t meet before. The best way to tackle a question like this is to generalize it a bit, we are not easy to find the regularity of this problem, but we can immediately see how to transfer the tower that contains only one or two disk, and then three. Using look at small cases strategy, we see , and

But now let's change our perspective and try to think big, experiments with three disks, this gives us a clue for transferring n disks in general: We first transfer the n − 1 smallest to a different peg, then move the largest, and finally transfer the n−1 smallest back onto the largest. How we verify our answer? First we can analyze from the problem itself, because the largest disk must be move, so the n - 1 smallest disks must move to a single peg before this, which cost T_{n-1}$% moves. so we can confirm the formula is that:

And also, if we have enough time, we can compute that: ; ; ; , so it certainly looks right, at least for

Mathematical induction is a general way to prove that some statement about the integer n is true for all . Since . And the induction follows for n > 0 if we assume that holds when n is replaced by n − 1:

But usually it is not easy to find the formula, our analysis of the Tower of Hanoi led to the correct answer, but it required an inductive leap, we relied on a lucky guess about the answer, if we look at that recurrence, we can add 1 to both sides of equations:

We let :

And It doesn’t take genius to discover that the solution to this recurrence is just ; hence . Even a computer could discover this.

Magic

Usually it always not easy to find the recurrence formula of a recurrence problem, so we should use recurrence thinking, and also we could find some magic to simplify the recurrence, and then we can immediately find the answer we want, Think Small, then Think Big and also need think different

LINES IN THE PLANE

How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? Or, more academically: What is the maximum number Ln of regions defined by n lines in the plane

Thinking2

Again we start by looking at small cases, so for Line 0, 1, 2 we can get the answer here:

01 pic

So we get the formula is ? because every new line doubles the number of regions, but the author told us its wrong, if we reflect on this problem, analyze every new line, we find that each line can split split an old region in at most two pieces, A straight line can split a convex region into at most two new regions, which will also be convex.

02 pic Add the third line, and we can analyze more clearly.

The nth line increases the number of regions by k if and only if it splits k of the old regions, because each line can only spilt one region into two region; and it splits k old regions if and only if it hits the previous lines in k − 1 different places, because each k line can split one region into k+1 region; Therefore the new line can intersect the n−1 old lines in at most n−1 different points, and we must have

It’s easy to guess and compute the formula, but let’s thinking in recursive:

Because equal to , so , we got the “close forms” formula.

More?

Now, support we use bent lines which contains one “zig”:03 pic We see and , because each line is bent line, we realize that a bent line is like two straight lines except that regions merge when the “two” lines don’t extend past their intersection point.

04 picThinking if this “two” line beyond their intersection point, we got two more regions, actually we can find that, every time we beyond each intersection, we change one region into three, means we got two, so:

Magic2

Thinking small is important we got the answer quickly by doing some tricks? maybe sometimes we are true, but along with the complication of problems the answer always wrong, more thing we should do is to find the relationships between one case and two case, and then find the recurrent function, and this is why told those problem a recurrent problem.

THE JOSEPHUS PROBLEM

During the Jewish{Roman war, Josephus was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left.

We can express this story as a concrete math problem, we start with n people numbered 1 to n around a circle, and we eliminate every second remaining person until only one survives. For example we have 10 people here, so the elimination order is 2, 4, 6, 8, 10, 3, 7, 1, 9; and 5 remains. We determine the survivor’s number, .

Is when n is even? We can list a sample table:

And we can obviously find that the conjecture fails when n=4 and n=6.

Okay, we at least find that every J(n) seems to be odd, because every even number eliminated in the first loop… So we start with 2n people, because we can eliminate all not even number immediately.

05 picYes, when the first loop ends, there remains n people, the circle looks like the circle of n people? the are the next while in J(n) are , so there have an equation:

06 picAbout the odd case. With 2n+1 people, we wiped the number 1 person after 2n, so that we got the formula:

Combining these equations with J(1) = 1 gives us a recurrence that defined J in all cases:

Our recurrence makes it possible to build a table of small values very quickly. Perhaps we’ll be able to spot a pattern and guess the answer.

It seems we can group by powers of 2 (marked by vertical lines in the table); J(n) is always 1 at the beginning of a group and it increases by 2 within a group. So if we write n in the form n = 2m + l, where 2m is the largest power of 2 not exceeding n and where l is what’s left, the solution to our recurrence seems to be:

It is true if we verify.but! Consider there have power operation, so we think about the binary way! Suppose n’s binary expansion is:

;

Because so we can express as:

Amazing! We got the binary expansion:

.

We understand the J function pretty well; the next step is to generalize it.With different constants we might not have been lucky enough to guess the solution, because the solution might have been really weird. Let’s investigate this by introducing constants α, β and γ and trying to find a closed form for the more general recurrence.

And the …


我放弃一波。以后再填坑,看不太懂。。。

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.