5
$\begingroup$

Consider the following sequence: $a_1=6$, $a_2=4$, $a_3=1$, $a_4=2$, and $a_n=a_{n-4}$ for $n \geqslant 5$.

Let $S^{k}_{n}$ be the sum of $k + 1$ elements from $a_n$ of the previous sequence. For example:

$ S^{0}_{3} = 1 \\ S^{0}_{4} = 2 \\ S^{1}_{3} = 2 + 1 = 3 \\ S^{0}_{2} = 4 \\ S^{1}_{2} = 4 + 1 = 5 \\ … \\ S^{6}_{2} = 4 + 1 + 2 + 6 + 4 + 1 + 2 = 20 \\ … \\ $

Show that any positive integer can be expressed as $S^{k}_{n}$.

This question was on an entrance exam for graduation. I wrote it from my memory, as the exam is not available online yet, maybe the wording is not 100% precise but I hope the examples are clear.

$\endgroup$
  • 2
    $\begingroup$ I think you meant $S_2^6$ $\endgroup$ – 57Jimmy Jan 9 '18 at 21:12
  • $\begingroup$ You're right, @57Jimmy, thanks! $\endgroup$ – rodorgas Jan 9 '18 at 21:15
4
$\begingroup$

As you notice, the sequence $a_n$ is by definition periodic: $6,4,1,2,6,4,1,2,6,4,1,2,...$

The sum of a whole "period" is $6+4+1+2=13$.

You can easily check that every number between $1$ and $12$ can be obtained as a sum of CONSECUTIVE numbers in the sequence $a_n$ (for instance, $9=1+2+6$). Then you just write any desired number $k$ (choose for example $k=139$) as a multiple of $13$ plus a number between $0$ and $12$ (in the example, $139 = 13 \cdot 10 + 9$). Then it just suffices to choose the right starting point and the right number of elements (in the example: to get $9$ you need to start at some $1$ in the sequence, so that you get $1+2+6=9$; for example, $S_3^{42} = 1+2+6+4+1+2+6+4+...+1+2+6= 13 \cdot 10 + 9 = 139$).

$\endgroup$
4
$\begingroup$
  1. First, you can show exhaustively that you can produce every integer between 1 and 12. (See below.)
  2. Then, note that the sum of any four consecutive elements in this sequence is 13: $S_n^3=13$.
  3. Hence you can construct any other integer $N$ as follows:
    • Let $S_n^k = N \pmod{13}$, which we have already shown you can construct.
    • Every four additional terms we take, say $S_{n}^{k+4}$, adds 13 to our result: $$S_{n}^{k+4} = [N\pmod{13}] + 12, \qquad\qquad S_{n}^{k+4+4} = [N\pmod{13}] + 13+13,$$ and so on.
    • So putting $\ell = \lfloor N/13\rfloor$, we find that $S_n^{k+4\ell} = N$.


Proof that you can produce every number between 1 and 12:

  • 12 = 2 + 6 + 4
  • 11 = 6 + 4 + 1
  • 10 = 6 + 4
  • 9 = 1 + 2 + 6
  • 8 = 2 + 6
  • 7 = 4 + 1 + 2
  • 6 = 6
  • 5 = 4 + 1
  • 4 = 4
  • 3 = 1 + 2
  • 2 = 2
  • 1 = 1
$\endgroup$
  • $\begingroup$ Thanks. But is it 12 or should it be 13? $S_{n}^{k+4} = [N\pmod{13}] + 12$ $\endgroup$ – rodorgas Jan 9 '18 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.