How does all this recursion stuff apply to an actual contest question?
-
How does all this recursion stuff apply to an actual contest question? I can semi-understand the explanation you've provided
but I don't really follow the videos. Key takeaways maybe? -
Also the question was written out wrong it said 2 whites instead of 3
-
@The-Blade-Dancer That's a really good question; when can we actually use a recursive method like the one that Prof. Loh showed us? There's a bit of art to finding the best strategy for a math contest problem.
For example, a question might ask, "How many ways are there to cross \(12\) stepping stones over a stream if you can hop by one or two stones each time?"
Or, something like, "How many ways are there to build a tower \(100\) units tall out of \(1 \times 1 \times 1\)-unit cubes, \(2 \times 2 \times 2\)-unit cubes, and \(3 \times 3 \times 3\)-unit cubes, if there are unlimited numbers of each?"
Or perhaps you want to make a string of letters without two consecutive vowels in a row.
Taking a counting or casework approach to these questions would be a lot harder than trying to use recursion.
Another great thing about recursion is that the thinking approach of recursion has similarities to the inductive form of proof. For example, the formula for a sum of the first \(n\) squares: \( \frac{n(n+1)(2n+1)}{6}.\) Proving such ideas using induction can be very elegant and fast!
Thanks for your feedback about the videos. Would it help if there were more pauses in the video with more guiding mini-questions? This is definitely possible! Please let us know, and we'll do our best to improve.
-
maaaaaybe? Guiding mini questions definitely help, but I'd be kind of shook by the sheer amount of lesson parts that would bring.
-
@The-Blade-Dancer I've forked the rest of this topic and moved it to the Comments section
