Waste less time on Facebook — follow Brilliant.
×

Recursion

Here is my first #TorqueGroup post! Please tell me anything you like/dislike about it, if anything is unclear, or anything else!

Recursion


Recursion is using smaller cases to construct larger cases.

Here are some signs that recursion might be a good method to attack a problem:

  1. The problem asks for the value of a large case, and you can determine small values or they are given.

  2. There is a clear connection between small cases and large cases.

Here are some steps helpful when applying recursion to a problem:

  1. Analyze small cases.

  2. Try to construct larger cases using smaller cases.

  3. Make a conjecture about a connection between a larger case and the case[s] smaller than it.

  4. Prove your conjecture.

  5. Determine the answer using the connection you found.

Let us begin with a simple example:


A collection of 8 cubes consists of one cube with edge-length \(k\) for each integer \(k\), \(1\le k\le 8\). A tower is to be built using all 8 cubes according to the rules:

  • Any cube may be the bottom cube in the tower.

  • The cube immediately on top of a cube with edge-length \(k\) must have edge-length at most \(k+2\).

Let \(T\) be the number of different towers than can be constructed. What is the remainder when \(T\) is divided by 1000? (AIME)


Your initial instinct may be to try casework based on which position a certain block is in, or maybe you thought that complementary counting was a good approach. However, recursion turns out to be a very fruitful approach to solve this problem. Looking back at our signs:

The problem asks for the value of a large case, and you can determine small values or they are given.

Yes, the problem asks about a tower with 8 cubes, and finding the number of towers of 1, 2 and even 3 is very simple, as the restriction doesn't matter.

There is a clear connection between small cases and large cases.

Yes, to get from 4 cubes to 5 cubes, simply add a cube, although the method of doing that may be slightly trickier.

Let \(T_n\) be the number of towers of \(n\) cubes. Let us apply our steps above:

Analyze small cases.

With 1 cube, there is clearly only 1 possible tower, so \(T_1=1\). With 2 cubes, there are \(2\) possible towers, and \(T_2=2\). With 3 cubes, there are \(6\) possible towers, and \(T_3=6\).

Try to construct larger cases using smaller cases.

If we have 3 cubes, and want to place the 4th, where can we put it? We can clearly put it on the bottom by the first rule in the problem. Following that thought, we can put it on top of the 2 or the 3, but not the 1. Then, we have 3 places we can put the 4th cube, and so \(T_4=T_3\cdot 3=6\cdot 3=18\).

If we have 4 cubes, and want to place the 5th, where can we put it? We can put it on the bottom, or we can put it on top of the 3 or the 4. Therefore, there are 3 places we can put the 5th cube, and \(T_5=T_4\cdot 3=18\cdot 3=54\).

Make a conjecture about a connection between a larger case and the case[s] smaller than it.

We can conjecture that \(T_k=3T_{k-1}\) for \(k\ge 3\). Luckily, this connection only depends on the previous term, so the work is easier.

Prove your conjecture.

If \(k\ge 3\), then the \(k^{th}\) cube can go on the bottom, or on top of the \((k-1)^{th}\) cube or the \((k-2)^{th}\) cube. Then, we conclude that \(T_k=3T_{k-1}\), as for each tower with \(k-1\) cubes, the \(k^{th}\) cube can go in 3 places.

Determine the answer using the connection you found.

Finally, \(T_2=2\), and \(T_8=3(T_7)=3^2(T_6)=\cdots=3^6(T_2)=1\boxed{458}\).

Well, that wasn't that bad, was it? I guarantee casework and other methods would have taken longer. Now that we have seen a more basic application of recursion, let us dive in deeper with another problem.


In how many ways can 7 teams place in a tournament if ties are allowed?


First, let us try to understand the problem, and I think a good way to go about that is by listing some possible orderings. Let the teams be numbered 1 through 7. We could have 1 be first, 2 be second, and so on till 7 which is last, or we could have 1 and 3 and 6 tie for first, and the other four teams tie for second, or we could... You know what, I'm starting to think that there might be a few too many possibilities to list. In fact, even without ties, there are \(7!=5040\) possibilities.

Now, let us try casework. If there are no ties, there are \(5040\) possibilities. lf there is one tie between two teams for first, we first pick the two teams that tie, and then order the remaining five teams. In fact, the number of possible placements, assuming teams are indistinguishable, is equal to the number of ordered partitions of \(7\), which you will soon see in problem number 1 below. I'll tell you this much: it is way too large to do by hand.

As this post is about recursion, I hope you are now thinking about how to apply recursion to this problem. Sign number 1 (asks for a large case, small cases are determinable) is satisfied. Number 2 (connect larger cases with smaller cases) is also satisfied, as all we do is add a team. Now, let us try to think about how a recursion would work...

If we have 6 teams, and want to place the 7th, where can be put it? If there are no ties in the 6 teams, this question is not so difficult. We can have 7 tie with any of the other 6 teams, or we can have it not tie, and be first, second, third, ..., or last. But what if there are ties? Say there is one tie. Then, we can have 7 tie with any of the 5 (do you see why 5 now?) other places, or it can not tie, being first, second, third, ..., or last. Continuing this train of thought, if we knew how many possibilities there were for 6 teams in 4 "groups," then we could place the 7th team tying with one of the 4 groups, or it could be alone in 5 places. This starts to sound like a recursion we can do!

To generalize, say we have \(n\) teams in \(k\) groups in \(x\) different ways. We can have \(n+1\) teams in \(k\) groups by adding a team to any of the \(k\) existing groups, giving \(kx\) ways, and we can have \(n+1\) teams in \(k+1\) groups by adding a team alone in \(k+1\) different locations, giving \((k+1)x\) ways.

Now, let us start a recursion. Let \(f(n,k)\) be the number of ways \(n\) teams can place into \(k\) spots, and define \(f(n,0)=0\) and \(f(n,k)=0\) if \(k>n\). By our earlier logic, \[f(n+1,k)=(k)f(n,k-1)+(k)f(n,k)=k(f(n,k-1)+f(n,k))\] For the base case, we can see that \(f(1,1)=1\). Let us make a table, where \(n\) goes down the side and \(k\) is on the top: \[\begin{array}{| l | l | l | l | l | l | l | l |} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & f(1,1) & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & f(2,1) & f(2,2) & 0 & 0 & 0 & 0 & 0 \\ \hline 3 & f(3,1) & f(3,2) & f(3,3) & 0 & 0 & 0 & 0 \\ \hline 4 & f(4,1) & f(4,2) & f(4,3) & f(4,4) & 0 & 0 & 0 \\ \hline 5 & f(5,1) & f(5,2) & f(5,3) & f(5,4) & f(5,5) & 0 & 0 \\ \hline 6 & f(6,1) & f(6,2) & f(6,3) & f(6,4) & f(6,5) & f(6,6) & 0 \\ \hline 7 & f(7,1) & f(7,2) & f(7,3) & f(7,4) & f(7,5) & f(7,6) & f(7,7) \\ \hline \end{array}\]

To finish, we simply fill in values (don't mess up here!): \[\begin{array}{| l | l | l | l | l | l | l | l |} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 \\ \hline 3 & 1 & 6 & 6 & 0 & 0 & 0 & 0 \\ \hline 4 & 1 & 14 & 36 & 24 & 0 & 0 & 0 \\ \hline 5 & 1 & 30 & 150 & 240 & 120 & 0 & 0 \\ \hline 6 & 1 & 62 & 540 & 1560 & 1800 & 720 & 0 \\ \hline 7 & 1 & 126 & 1806 & 8400 & 16800 & 15120 & 5040 \\ \hline \end{array}\] and the answer is \(1+126+1806+8400+16800+15120+5040=\boxed{47293}\).


Problems:

  1. Find the number of ordered partitions of \(10\) where an ordered partition of \(n\) is a tuple of positive integers \((a_1,a_2,\cdots,a_k)\) such that \(a_1+a_2+\cdots+a_k=n\).

  2. A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible? (AIME)

  3. In how many ways can 7 teams place in a tournament if ties are allowed? Try this problem with a single recursion that doesn't depend on groups. Hint: use more than one previous value in the recursion.

  4. See here.


Next week, I will write a post about recursion in computer science.

In two weeks, we will learn how to solve expressions such as \(T_k=3T_{k-1}\), which are called recurrence relations.


If you want more problems to work on, you can look up #RecurrenceRelations.

Note by Daniel Chiu
3 years ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Great Post! Yan Yau Cheng · 3 years ago

Log in to reply

@Yan Yau Cheng Yup! Nice post! I have learnt sth new today but will have to digest the second part further... (it's quite content-filled!) :) Happy Melodies · 3 years ago

Log in to reply

@Happy Melodies Yes, the second part is a very powerful technique that allows you to solve many problems that suggest horrible casework, and brilliant has a lot of those. Basically, you split each case into several parts which don't overlap, but cover all cases, and then find a recurrence for each one that depends on the previous ones. The connections can be slightly unintuitive.

One thing that would help is if I actually knew the name of the technique. Does anyone know the name? I feel like I've heard recursion states before but I can't find that when I look it up. Daniel Chiu · 3 years ago

Log in to reply

@Daniel Chiu I nice second topic you can do is Inequalities. I feel that I need practice with inequalities but I can't find a comprehensive guide on them. Daniel Liu · 3 years ago

Log in to reply

@Daniel Liu Well, I am really bad at inequalities, so I don't think I can do that. Anqi Li and Zi Song have been writing about inequalities. Daniel Chiu · 3 years ago

Log in to reply

Great post! Eddie The Head · 3 years ago

Log in to reply

Great first post to start your "business" up!

Looking forward to more of your posts. Daniel Liu · 3 years ago

Log in to reply

Fantastic! A bit on the lengthy side, but very informative nonetheless. Many will benefit. Bob Krueger · 3 years ago

Log in to reply

very interesting post Chaimae Khalidi · 3 years ago

Log in to reply

hi daniel! can you tell me how i can increase my mathematical thinking ability? any comment is much appreciated! Anup Navin · 3 years ago

Log in to reply

@Anup Navin I find that practicing math competition problems, for example the AMC 8, the AMC 10, the AMC 12, and other competitions help a lot. Daniel Liu · 3 years ago

Log in to reply

@Daniel Liu Seconded. Also, I think that trying problems one step above your "comfort zone" or problems you have little difficulty with is a good way to improve. Daniel Chiu · 3 years ago

Log in to reply

@Daniel Chiu and what if you don't get those above your comfort zone problems? Anup Navin · 3 years ago

Log in to reply

@Anup Navin Try as hard as you can. Ask questions or whatever your preferred method of getting help is. If you can't, then go down one level until you are ready. Daniel Chiu · 3 years ago

Log in to reply

@Daniel Chiu thank you! Anup Navin · 3 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...