Lecture 7: Chinese Rings Puzzle
In this lesson on the Chinese Rings Puzzle, the instructor explains how the puzzle relates to discrete math and the power of recursion. The puzzle involves a series of rings on a piece of steel, and the goal is to remove all the rings from the steel. The instructor goes through different configurations of the puzzle and explains the two moves that can be made to change the configuration, ultimately leading to a solution. The importance of experimenting and exploring to understand recursion is emphasized throughout the lesson.
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/
- 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
- 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.
