Discrete Maths, Lecture-7

These are my notes from 7th lecture of discrete mathematics course taught at Arsdigita university by Shai Simonson. Other posts relating to this are here.

In this lecture, we solve the chinese ring puzzle. This lecture is not just about presenting a solution to the mentioned problem but the thing one learns here is how you can approach such problems. Here is what we do in this lecture...

1. Model the problem in mathematical terms.


2. Come up with the solution algorithm by thinking recursively(that is, by thinking like, can we solve for n rings if we had solution for n-1 rings)


3. Creating recurrence relation for the complexity from the algorithm


4. Notice that we can not solve it with *repeated substitution technique*(though there are other techniques, but only this technique has been covered till now), so we try to make a guess by looking at T(1), T(2), T(3).....


5. We form a conjecture based on the pattern and then prove the conjecture with induction


6. Then we reduce the original complex recurrence relation into a very simple recurrence relation that is solvable easily with repeated substitution techniue.


7. We make other important observations like the pattern in the binary representation of T(1), T(2)... that immediately fits a pattern in the first look, so the moral is that one can try looking at alternate representations of the same thing to get different interesting perpectives... explore!


8. Then we make a note that the sequence generated by chinese ring configurations is also a gray code sequence that is the next configuration in the sequence differs from previous only by one bit.

Here are my notes...