Lecture 7: Chinese Rings Puzzle
9200 views
|
2
ratings
Lesson Description:
Learn about the Chinese Rings Puzzle and how it relates to Discrete Math.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 3 - A problem set with some problems from this lecture
- Problem Set 3 Solutions - Solutions to the Problem Set
- Problem Set 4 - A problem set with some problems from this lecture
- Problem Set 4 Plus - A problem set with some problems from this lecture
- Problem Set 4 Solutions - Solutions to the Problem Set
- Exam 2 - An exam for the current material
Questions answered by this video:
- What is an algorithm for the Tower of Hanoi problem?
- How do you write a recursive program for solving the Towers of Hanoi problem?
- What is the seven rings problem and how do you solve it?
- What is the Chinese rings puzzle and how do you solve it?
- How can you remove all the rings in the seven rings problem using recursion?
- What are the two possible moves in the seven rings problem?
- What does the seven rings problem look like using six binary digits?
- How do you get the hardest ring off of the Chinese rings puzzle?
- What is the time complexity for the Chinese rings puzzle?
- How can you use induction to find the number of steps needed to solve the seven rings problem?
- Why does it take 42 moves to solve the Chinese rings puzzle with six rings?
- How can you set up a spinner with 0s and 1s so if the spinner lands on a boundary between two regions, it picks either the right or the left region is selected?
- What is a gray code?
-
Staff Review
This video starts off with an explanation of some ideas behind how to solve a variation of the Towers of Hanoi problem. Then, the meat of this lecture deals with the Chinese rings puzzle or seven rings problem. Theory behind this problem and analysis of the problem using binary place-holder digits. This discussion really explains clearly how to solve this puzzle. A really long and hairy time complexity computation is done in depth using a recurrence equation, some algebra, and induction. Some applications of the Chinese rings puzzle are the shown.
