Prize Strings

A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.
During an n-day period a trinary string is formed for each child consisting of L’s (late), O’s (on time), and A’s (absent).
Although there are eighty-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:
OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO
How many “prize” strings exist over a 30-day period?

This question can be solved by defining a function that grows according to its own previous terms. The function is defined by the attendance history of previous days:

– If the student arrived on time (or late) today, we count the number of successes from the previous day.
– If the student was absent today, we count the success from two and three days ago.

More formally, we define three sequences, $P_n$, $A_n$ and $L_n$ representing the number of prize-achieving strings ending in on-time, absence, and late, respectively.

The given starting conditions are $P_1=2$, $A_1=1$ and $L_1=1$ for the first day.

For the second day, these sequences develop based on those starting conditions:
$P_2 = P_1 + L_1 + A_1 = 4$,
$A_2 = P_1 = 2$ and
$L_2 = P_1 = 2$.

The general recurrence relation for ‘n’ days would then be:
$P_n = P_{n-1} + A_{n-1} + L_{n-1}$,
$A_n = P_{n-1} + P_{n-2}$, and
$L_n = P_{n-1}$.

We can calculate these sequences up to n = 30 using a suitable programming language.

After calculating, we get $P_{30} + A_{30} + L_{30}$ totals to 1918080160, which is the number of “prize” strings in a 30-day period.

To solve such problem, it is advisable to use dynamic programming to store previously calculated values. With programming, we can calculate the values in loops rather than filling in the sequences term-by-term manually.

More Answers: