RMO combinatorics + recurrence

 

This is Tower of Hanoi/Brahma or Pyramid puzzle.
An = minimum number of ways to shift the entire stack to 3rd tower via 2.

Now, let's say we somehow transfer the entire stack except the last disk to 2.
There are A_(n-1) ways to do that.

Now, the last disk can be moved to 3rd tower in 1 move.
And then again A_(n-1) ways to move these disks to 3 via 1.
So A_n = 2*A_(n-1) + 1.

This is first order non-homogeneous linear recurrence.
So divide by 2^n on both sides.
And eventually you get An = 2^n - 1.

Let An = number of ways for A to get ball back after 'n' passes.
If A gets the ball back after 'n'th pass then some other player had it after (n-1)th pass.
Number of ways for A to have the ball after (n-1) passes = A_(n-1).

=> number of ways for A to NOT have the after (n-1) passes = Total ways - A_(n-1)
Total ways for ball to move during (n-1) passes = 4^(n-1).
Why?
Because each player can pass the ball in 4 ways during each pass.

=> A_n = 4^(n-1) - A_(n-1)
This is first order recurrence.
Solution:

So basically total ways to color in a way that no 2 consecutive sectors are same (except possibly the first and last) = r * (r-1)^(n-1)
Why?
Because first sector can be colored in 'r' ways and every other sector in (r-1) ways.
Now if 1st and 'n'th sector have same color, then there are A_{n-1} ways to do that since 1st and nth sectors are effective 1 sector due to their color being same.

And if 1st and 'n'th sectors are different then there are A_{n} ways to do that.
So
An+ A_(n-1) = r*(r-1)^(n-1)

A2 = r*(r-1)
Use that to solve and get:

So let's say (n-1) lines create A_(n-1) regions.
'n'th line intersects them at (n-1) points and creates 'n' segments 2 of which extend to infinity in either direction.
These 'n' segments introduce 'n' new regions.
Why?
Because each segment passes through a certain region and divides into 2.
So 'n' segments introduce 'n' new regions.

Now let's do the same problem with 'n' circles.

Each circle will intersect all other circles at 2 points.
Let us say (n-1) circles are already there which yield A_(n-1) regions.
Now the nth circle will intersect each of the (n-1) circles at 2 points.
So total 2(n-1) intersection points.
And since circle is a closed figure, unlike lines, these intersection points will introduce 
2(n-1) segments, which is same as number of intersection points.

Whereas in lines, number of segments introduced was 1 more than number of intersection points.

So A_n = A_{n-1} + 2(n-1)
And solving this we get:
An = n^2 - n + 2


Note: my first thought was that these are same as Venn diagrams and answer should be 2^n which is all possible combinations of all sets, but that's wrong.

Now, what if instead of circles we have parabolas?

Note that parabolas intersect each other at 4 points which introduce 5 new segments, i.e. one more than intersection points.

So A_n = A_{n-1} + 4{n-1} + 1

What about ellipses?
They will intersect each other at 4 points and create same number of segments as intersection points because they are closed.

So A_n = A_{n-1} + 4{n-1}