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 kk for each integer kk, 1k81\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 kk must have edge-length at most k+2k+2.

Let TT be the number of different towers than can be constructed. What is the remainder when TT 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 TnT_n be the number of towers of nn cubes. Let us apply our steps above:

Analyze small cases.

With 1 cube, there is clearly only 1 possible tower, so T1=1T_1=1. With 2 cubes, there are 22 possible towers, and T2=2T_2=2. With 3 cubes, there are 66 possible towers, and T3=6T_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 T4=T33=63=18T_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 T5=T43=183=54T_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 Tk=3Tk1T_k=3T_{k-1} for k3k\ge 3. Luckily, this connection only depends on the previous term, so the work is easier.

Prove your conjecture.

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

Determine the answer using the connection you found.

Finally, T2=2T_2=2, and T8=3(T7)=32(T6)==36(T2)=1458T_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!=50407!=5040 possibilities.

Now, let us try casework. If there are no ties, there are 50405040 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 77, 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 nn teams in kk groups in xx different ways. We can have n+1n+1 teams in kk groups by adding a team to any of the kk existing groups, giving kxkx ways, and we can have n+1n+1 teams in k+1k+1 groups by adding a team alone in k+1k+1 different locations, giving (k+1)x(k+1)x ways.

Now, let us start a recursion. Let f(n,k)f(n,k) be the number of ways nn teams can place into kk spots, and define f(n,0)=0f(n,0)=0 and f(n,k)=0f(n,k)=0 if k>nk>n. By our earlier logic, f(n+1,k)=(k)f(n,k1)+(k)f(n,k)=k(f(n,k1)+f(n,k))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)=1f(1,1)=1. Let us make a table, where nn goes down the side and kk is on the top: 12345671f(1,1)0000002f(2,1)f(2,2)000003f(3,1)f(3,2)f(3,3)00004f(4,1)f(4,2)f(4,3)f(4,4)0005f(5,1)f(5,2)f(5,3)f(5,4)f(5,5)006f(6,1)f(6,2)f(6,3)f(6,4)f(6,5)f(6,6)07f(7,1)f(7,2)f(7,3)f(7,4)f(7,5)f(7,6)f(7,7)\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!): 1234567110000002120000031660000411436240005130150240120006162540156018007200711261806840016800151205040\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=472931+126+1806+8400+16800+15120+5040=\boxed{47293}.


Problems:

  1. Find the number of ordered partitions of 1010 where an ordered partition of nn is a tuple of positive integers (a1,a2,,ak)(a_1,a_2,\cdots,a_k) such that a1+a2++ak=na_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 Tk=3Tk1T_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
5 years, 8 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Great Post!

Yan Yau Cheng - 5 years, 8 months ago

Log in to reply

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 - 5 years, 8 months ago

Log in to reply

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 - 5 years, 8 months 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 - 5 years, 8 months 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 - 5 years, 8 months ago

Log in to reply

Fantastic! A bit on the lengthy side, but very informative nonetheless. Many will benefit.

Bob Krueger - 5 years, 8 months ago

Log in to reply

Great first post to start your "business" up!

Looking forward to more of your posts.

Daniel Liu - 5 years, 8 months ago

Log in to reply

Great post!

Eddie The Head - 5 years, 8 months ago

Log in to reply

very interesting post

Chaimae Khalidi - 5 years, 8 months ago

Log in to reply

hi daniel! can you tell me how i can increase my mathematical thinking ability? any comment is much appreciated!

Brilliant Member - 5 years, 8 months ago

Log in to reply

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 - 5 years, 8 months ago

Log in to reply

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 - 5 years, 8 months ago

Log in to reply

@Daniel Chiu and what if you don't get those above your comfort zone problems?

Brilliant Member - 5 years, 8 months ago

Log in to reply

@Brilliant Member 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 - 5 years, 8 months ago

Log in to reply

@Daniel Chiu thank you!

Brilliant Member - 5 years, 8 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...