Josh's Exam Cramming

After trying some early casework it becomes clear that this is not going to be particularly fruitful. However, a recurrence relationship seems possible. So let f(n) denote the number of possible sequences after n days. f(n) = Sequences with algebra in position n , sequences with combinatorics in position n and sequences with number theory in position n , $a_{A}$ , $a_{C}$ and $a_{N}$ respectively. $a_{A}$ = the number of sequences of length n-1 which have algebra or number theory on day n-1 , $a_{C}$ = the number of sequences of length n-1 which have Combinatorics or number theory on day n-1 , $a_{N}$ = the number of sequences of length n-1 which have algebra or combinatorics or number theory on day n-1 . Clearly $a_{N}$ = f(n-1) . Also $a_{A}$ + $a_{C}$ = f(n-1) .+ f(n-2) . Therefore f(n) = 2 f(n-1) + f(n-2) . f(0) = 1 and f(1) = 3. Quicky building up this relation we get f(10) = 8119. So the last 3 digits are 119

Let's call

$n$ the lenght of the combination.

$a_n$ the number of combination ending with Nuber Theory the nth day.

$b_n$ the number of combination ending with Algebra or Combinatorics the nth day.

The $n+1$ -th day, we have

$1$ combination ending with NT, every combination the previous day;

$2$ combination ending with Algebra or Combinatorics, every ending with NT the $n$ -th

$1$ combination ending with Algebra or Combinatorics, every combination that ends with either A or C., the $n$ -th day. So:

$\begin{cases} { a }_{ n+1 }={ a }_{ n }+{ b }_{ n } \\ { b }_{ n+1 }=2{ a }_{ n }+{ b }_{ n } \end{cases}$

Computing, ${ a }_{ 11 }=8119$ . The answer is $\boxed { 119 }$

First, We formulate a function that generates all sequences of length n:

>>> def strings(n):
...     if n==1:
...             return ['A','B','C']
...     else:
...             newlist=[]
...             for i in strings(n-1):
...                     newlist.append('A'+i)
...                     newlist.append('B'+i)
...                     newlist.append('C'+i)
...             return newlist
...

Then, we count the number of strings in which we have AB or BA:

>>> d=0
>>> for i in strings(10):
...     if not (i.count('AB') or i.count('BA')):
...             d += 1
...

Let's ask for d

>>> d
8119

The problem can be computed easily using recursion as below: (code written in Boo)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

mf={};
mg={};

def f(n as int, numtheo as bool) as int:
    if n<=1:
        return 1;

    if numtheo:
        if mf[n]==null:
            mf[n]=f(n-1, true)+2*f(n-1, false);
        return mf[n];

    if mg[n]==null:
        mg[n]=f(n-1, true)+f(n-1, false);
    return mg[n];

print f(11, true);

I got the recurrence relation for this problem, $a_{n}=5a_{n-2}+2a_{n-3} ,$ where the initial conditions are $a_{1}=3, a_{2}=7, a_{3}=17.$

After that, I almost became crazy with finding the general solution! In addition, I failed at the the first try, then I cheated with using Wolfram Alpha. :\

I couldn't figure out a fast way to do it, but I thought the long shot is the only way in my grasp, so, I made a sort of flowchart. This is not a long solution, but I decided to explain it elaborately.

So, I took A = Algebra, B = Number Theory, C = Combinatorics. Clearly, we can't have a sequence with either CA or AC in it. So let us arbitrarily begin said sequence with A. Notice that we can only follow by either A or C. So 2 ways are possible, till now.

A A C

Now, A again will yield two combinations, and C will yield three.

A A C A C A B C

And So on. To make my work simpler, I wrote down the number of ways each letter gives.

A will give 2 combinations, B and C, which give 2 or 3 respectively themselves. So on.

                                                                   A

                   2                                                                                                                3
  2                                      3                                                                      2                      2                  3

2 3 2 2 3 2 3 2 3 2 2 3

And so on. Note that each 2 gives rise to one 2 and one 3, and each 3 gives rise to two 2s and one 3.

I will re-write as:-

                                                                       A

                                II                                                                                      III

                              3 x II                                                                                 2 x III

                           7  x  II                                                                                  5 x III

Again, note that the sum of the co-efficients i.e. the number of 2's and 3's together, make up the number of 3's in the next step, as both 2 and 3 give rise to only one 3 in the next step.

On the other hand, as one 3 gives rise to two 2s, and one 2 gives rise to one 2, the number of 2s in the next step is equal to twice the (number of 3s + number of 2s)

If you continue my procces-ish flowchart.

          [1]                                                                  A

     [2]                     II                                                                                   III

     [3]                  3 x II                                                                             2 x III

     [4]                  7 x II                                                                             5  x III

     [5]                  17 x II                                                                           12 x III

    [6]                  41 x  II                                                                            29 x III

   [7]                   99 x II                                                                              70 x III

    [8]                 239 x II                                                                             169 x III

     [9]               577  x II                                                                               408 x III

     [10]             1393 x II                                                                             985 x III

Thus, if you start with A, there are $1393 + 985 = 2378$ C, there are $1393 + 985 = 2378$

For B, it's a bit different, work it out similarly, you get $3363$

Therefore, (2378 + 2378 + 3363 = 8119)\

Therefore \boxed{119} is the answer.

sighs It's actually a easy method, but my poor descriptive skills made me type an essay, nevertheless, it's easy to understand.

Edit:- Crap, my flowcharts messed up. Any genius out here can help me with it?

Thanks again :)

\­( ... \­)