Introduction to Recursion

Introduction to Recursion: Level 4 Challenges


A toy model for a growing network is the recursive tree. The tree starts as a single node and at each step in the growth process, one new node is added which makes a single connection, at random, to an existing node.

Assume that the network has grown large enough so that its statistical properties are effectively constant. The fractions of nodes that have connections to exactly 7 other nodes is given by some fraction ab\dfrac ab, where aa and bb are positive coprime integers. What is the value of a+ba + b?

A human pyramid is built up by several layers. At the top, there is one person, and each subsequent layer has 1 additional person. Each person is supported by the 2 people that are beneath them.

Consider a 9 layer pyramid, which comprises 45 people. Assuming that all the cheerleaders weigh 128 pounds each, and that the weight is equally distributed amongst both supporters, what is the most weight supported by anyone in this pyramid?

How would you generalize this?

Image credit: Wikipedia Pere Lopez

How many ways can the numbers 1,2,3,4,5,6,71,2,3,4,5,6,7 be arranged in a row such that the numbers in the 2nd, 4th, and 6th positions are each larger than both of their neighbours?

The Tower of Hanoi is a traditional game where there are 3 pegs and nn discs arranged as seen in picture. All discs are to be moved from 1st1^{st} peg P1P_1 to 3rd3^{rd} peg P3P_3 such that only one disc is moved at once. But no disc should be kept on one smaller than it during the process. So the minimum number of moves required to transfer all discs to P3P_3 (say ana_n) is counted by an=2an1+1a_n=2a_{n-1}+1 and a1=1a_1=1 i.e. after solving becomes an=2n1.a_n=2^n-1.

If we have a Tower of Hanoi with 42 pegs, and we have an additional rule that no disc can be moved more than twice, what is the maximum number of discs such that all discs can be moved to pegs other than the first peg P1?P_1?

A single snowflake rests at the origin, (0,0)(0, 0), on an infinite cartesian plane. At time t=0t = 0, it divides and replicates itself, moving exactly 11 unit in each of the 88 major compass directions (N, NE, E, SE, S, SW, W, and NW), leaving (0,0)(0, 0) vacant.

At t=1t = 1, all snowflakes which occupy the exact same points are merged into one, and then the process repeats for every snowflake, resulting in the following pattern:

So, to iterate the first few steps:

  • There is 11 snowflake at time t=0t = 0
  • At time t=1t = 1, there are 88 snowflakes pre-merge.
  • No snowflakes coincide, so there are 88 snowflakes post-merge as well.
  • At time t=2t = 2, there are 6464 snowflakes pre-merge.
  • Post-merge, only 3333 snowflakes remain.

How many snowflakes are there at time t=1000t = 1000, post-merge?

Image Credit:

Problem Loading...

Note Loading...

Set Loading...