Carpeting and Traffic light - Conclusion

Don't you feel the approach that I used in the previous post, traffic light setting, is a little bit overwhelming? I don't blame you if you do. But it does demonstrate some thing important, it's show what we can do with the problem.

First, with this approach, I always get an answer which may be "no, I can not do it in 3 turn per cycle" or "yes, I can". Not only that, I get a specific light setup, a pretty good one. Even with more complicate situations, say bigger intersections, I still definitely get an answer.

I also know that there is no way to let every one pass through safely only 2 turns per cycle, no matter how much I try. It is definitely good to know your limit, isn't it?

Moreover, if I have a problem that have hundreds of directions. Once I turn the problem to a graph, I probably going to look up a solution of graph coloring, which suit my case, or use one if it's already out there. Either way, I have a pretty good idea how to solve my problem.

You probably realize by now that I am using mathematical abstraction, a graph, to help us to understand, learn more about limitations and provide a solution to the problem.

This concept is important in computer science, because when you try to solve problem with computers, you actually turn a real problem into an abstract problem in computers. Mathematics give you a good guide line now to implement these abstractions. This what you are going to learn when you go to collage for computer degree, learning to solve problem using mathematics, and learn how to implement it in computers

Carpeting and Traffic light, what do they have in common? - Part 2

In the previous post, I define a carpeting problem. It quite a simple problem that can be described, including a solution in couple paragraphs. The traffic light problem is quite more complex.

Traffic light setting: I want to setup a traffic light on a intersection (figure 1), which A, B, and C are two-way streets, while D is a one way street, and have to make sure that every one can get thought the intersection safely.

figure 1

If I setup the light as follow:

1. let A go to B and C, and block every one else
2. let B go to A and C, and block every one else
3. let C go to A and B, and block every one else
4. let D go to A, B and C and block every one else.

There will be 4 turns signal for each cycle. I  ensure that every one get their turn, and pass through the intersection safely. 

You may notice that while we let A go to B and C, in the same time C can safely go to A. This raise the question, can we do 3 turns signal in each cycle, and still let every one get through safely?

Carpeting and Traffic light, what do they have in common?

Nothing ... you may say so. And I completely agree with you. However, what I am talking about is two problems, Carpeting a house and Traffic light setting. They may have some thing in common that might surprise you. I have to be more specific, haven't I?

Carpeting a house: I want to fully carpeting this house with one condition. I want every room that connect to each other have different color. For the room that is not directly connect, may share the same color.

figure 1

For this particular house, kitchen (K) and living room (L) are connected, they have to have different color. Assuming the small area in front of rest room (R) is belongs to kitchen. All bedroom (MB, B1 and B2) can have the same color. In this case, 3 colors is enough. But can I do this with two color?

Remember the small area in front of restroom is belongs to Kitchen, so B1 and B2 are not directly connected, so living room.

figure 2

Let draw this floor plan differently (figure 2):  All the room are connected directly to kitchen, except the master bedroom (MB). We have to choose two different colors for kitchen and living room, say C1 for kitchen and C2 for living room. Then we can use C1 for master bedroom and C2 for bedroom 1 and 2. Using two colors is possible then.

Permutation and Mathematical Induction

Last post, I show how basic mathematical induction works. Now, I am going to use it to prove that an algorithm is work correct. In this case, we are going to prove a permutation algorithm, which take an array of unique numbers L, and return an an array of all permutations of L. Let call it perms(L). For example:

1. If L = [ ], then perms(L) would be [ [ ] ].
2. If L = [1, 2, 3], the result of perms(L) will be an array [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Note: the arrary could be any order.

The algorithm that I am going to prove is shown here:

 1: def perms(L)
 2:   return [[]] if L.size == 0
 3:   result = []
 4:   L.each do |elm|
 5:     L1 = L - [elm]
 6:     perms(L1).each |p|
 7:       p1 = [elm] + p
 8:       result << p1
 9:     end
10:   end
11:   return result
12: end

The exact statement that I want to prove to you is: for any given array L of size n, the perms(L) is an array of all size-n permutation of L.

First, basis step: Let L = [ ]. The L.size will be 0. Then the perms(L) will return immediately with value [ [ ] ], which is the array of all size-0 permutation of L.

Inductive step: Let assume statement is true for any array with size n. We have to show that for any array L of size n+1, perms(L) will return an array of all size-(n+1) permutation of L.

Chinese Abacus and Mathematical Induction

When I was a kid, I used to practice Chinese Abacus every day. Me and my brother turn this boring practice into a competition, and the winner is the person who can do 1 + 2 + ... + 100 faster! Of course, it's has to be correct. At that time, we were told that the correct value is 5050, and we did not question about it.

Now, I kinda wonder, if I am going to proof to some one that 1 + 2 + ... + 100 = 5050, how can I do that?  Here one way to do it.

First line up two line of sum this way, one from 1 to 100, another from 100 to 1.

  1 +   2 +   3 + ... + 100
100 +  99 +  98 + ... +   1
---------------------------------------
101 + 101 + 101 + ... + 101 = 101 * 100

Then, sum each column. As you can see, sum value in each column is equal 101. Since we know that there is going to be 100 column. So the sum of the last line, which is sum of those two line, is 101 * 100. Because we start with 2 lines,  the sum of  \(1 + 2 + 3 + ... + 100\) = \(101 \cdot 100 / 2 = 5050 \).

This way, we can also show that, for any given interger \(n \ge 1\)
$$ \displaystyle\sum_{i=1}^{n} i = 1 + 2 +  ... + n = \frac{n\dot(n+1)}{2}$$
Nice!, It's probably require a genius to come up with the proof like this, don't you think?

Another way, we can use mathematical induction to proof this statement too. It's more systematic, and can be generalize to prove more complex statements. The proof by mathematical induction has two parts, basis step and induction step. Basically, we have to show the basis is true, then show if any given number is true, then the next one also true.