[10] Show that a DNA sequence is not (Kolmogorov) random.

Consider sequences, over {A, C, G, T }, such that starting from any position 3k + 1, for k = 0, 1,..., in the sequence, the next three letters must be one of 22 combinations (corresponding to 20 amino acids, and begin, end instructions). Prove that such sequences cannot have maximum Kolmogorov complexity. (Note, we ignored the junk information between end and next begin instruction, occurring in a real DNA sequence.)