Lesson 2

Advanced Problems.

1. (20 points) A space probe has discovered that organic matter on Mars contains DNA composed of five symbols: \((a, b, c, d, e)\). There are four forbidden pairs of symbols—\(ce\), \(cd\), \(ed\), and \(ee\)—which never occur in Martian DNA. However, any sequence that does not contain these pairs is admissible. The order of letters in a sequence is significant; thus, for example, the sequence \(bbdca\) is valid, while \(bbcda\) is not. Determine the recurrence relations satisfied by the number of such valid DNA sequences. Construct the solutions to these recurrence relations.
2. (20 points) How many ways are there to tile a \(3 \times 10\) rectangular board using \(1 \times 2\) dominoes?
3. (20 points) A gardener, after grafting a cutting of a rare plant, lets it grow for two years and then takes 6 cuttings from it annually. Each new cutting is treated in the same way.

   How many plants and cuttings will there be in the \(n\)-th year of growth of the original plant?

4. (20 points) An archaeologist has found \(k\) gold coins. From ancient texts, he discovered that one of them is counterfeit, and it weighs less than the genuine coins. The archaeologist has access to paid scales. If the left pan is heavier, he must pay 2 pounds, and for any other outcome, he must pay 1 pound. What is the maximum value of \(k\) such that the counterfeit coin can be found by spending no more than \(10\) pounds?
5. (25 points) There are \(n\) coins, exactly one of which is counterfeit (it is lighter than the genuine ones). You have a balance scale and a “coin slot” mechanism. Before each weighing, you must insert one coin into the slot. If the inserted coin is genuine, the scale reports the true outcome; if it is counterfeit, the outcome may be arbitrary. Coins inserted into the slot cannot be retrieved. What is the largest \(n\) such that you can guarantee to find \(n-10\) genuine coins?
6. (30 points) Assume we have a linear recurrence relation of order \(k\) \[f_{n+k}= \sum_{i=0}^{k-1}{c_i f_{n+i}}\] with characteristic polynomial \(P(x) = x^{k} - \sum_{i=0}^{k-1}{c_i x^i}\) (all \(c_{i}\) and \(f_{i}\) lie in an algebraically closed field \(\mathbb{F}\) of characteristic zero). Assume that \(c_{0}\ne0\), so all roots of \(P\) are nonzero.
   1. (10 points) Prove that if \(P\) has roots \(x_{0},x_{1},…,x_{d}\) with multiplicities \(m_{0},m_{1},…,m_{d}\) respectively, then the sequence \(e_{n} = n^{t} x_{0}^{n}\) satisfies our relation for integers \(t \ge 0\) with \(t<m_{0}\).
   2. (20 points) Prove that the set \(E = \{x_{0}^{n},…, n^{m_0-1}x_{0}^{n},x_{1}^{n},…,n^{m_d-1}x_{d}^{n}\}\) linearly spans all sequences satisfying our relation (that is, if \(g_{n}\) satisfies the relation, then there exist coefficients \(a_{0}, a_{1},… a_{k-1}\in \mathbb{F}\) such that \(g_{n} = \sum_{i=0}^{k-1}{a_i\cdot E_i}\)).
7. (30 points) Call the degree of the polynomial term \(g\) the non-homogeneity of the recurrence \[f_{n+k}= \sum_{i=0}^{k-1}{c_i \cdot f_{n+i}}+ g(n),\] and let \(s\) be the multiplicity of \(1\) as a root of the characteristic polynomial of \(f\) \[\begin{equation*}\left(P(x) = x^{k}-\sum_{i=0}^{k-1}{c_i x^i}\right).\end{equation*}\]
   1. (10 points) Assume that \(h_{n}\) is a homogeneous relation with the same characteristic polynomial, and that \(f_{n} = h_{n} + a\cdot n^{b}\), where \(b\ge s\) and \(a\neq 0\). What is the non-homogeneity of \(f\)?
   2. (5 points) Prove that the polynomial that makes \(f\) homogeneous is unique up to \(n^{s-1}\), i.e., if for two polynomials \(p\) and \(q\) the sequences \(a_{n} = f_{n}+p(n)\) and \(b_{n} = f_{n}+q(n)\) are both homogeneous, then \(\deg{(p-q)}\le s-1\).
   3. (10 points) Provide an algorithm to find such a unique polynomial.
   4. (5 points) What should we do if the non-homogeneous term is not a polynomial, but of the form “exponential times polynomial” \(g(n)\cdot a^{n}\), where \(a\ne0\)?