Cut the Rope (Stars and Sticks)
Intermediate
Video tutorial
Lecture Notes
The cut-the-rope technique is also referred as the stars and sticks method. It is arguably one of the most important and popular counting techniques. A generalization of this method is to count the integer solutions to the following equation $$x_1 + x_2 + \cdots + x_k =n$$
There are three possible cases:
- Positive integer solutions, i.e. $x_1$, $x_2$, $\cdots$, $x_k$ are all positive integers
- Non-negative integer solutions, i.e. $x_1$, $x_2$, $\cdots$, $x_k$ are all non-negative integers
- Mixed set of restrictions. For example, some of $x_i$ are positive, and the rest are non-negative.
These three types look similar but are different and require different solving techniques. The cut-the-rope technique is to solve the first type of problem (i.e. positive integer solution). Below is the model to count the positive integer solution to the equation $x_1 + x_2+x_3=8$:
