What are the solutions to Problem of the Week #240 - Nov 07, 2016?

[Ackbach]

So, I am ashamed to admit it, but this is the very first break in the weekly POTW since it started. I have a good excuse, though: my twin brother was visiting, and I was quite distracted by the wonderful company. So here is this week's POTW:

-----

Let $A_1=0$ and $A_2=1$. For $n>2$, the number $A_n$ is defined by concatenating the decimal expansions of $A_{n-1}$ and $A_{n-2}$ from left to right. For example $A_3=A_2 A_1=10$, $A_4=A_3 A_2 = 101$, $A_5=A_4 A_3 = 10110$, and so forth. Determine all $n$ such that $11$ divides $A_n$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 240 - Nov 07, 2016

This was Problem A-4 in the 1998 William Lowell Putnam Mathematical Competition.

Congratulations to Opalg and kaliprasad for their correct solutions. Also, honorable metion to kiwi for a good, though incomplete, answer. kaliprasad's solution is here:

Spoiler

Let us define a sequence $B_n$ with the property that
$B_1 = A_1$ , $B_2 = A_2$
$B_n = B_{n-1} + B_{n-2}$ when $A_{n-2}$ has even number of digits
and $B_n = - B_{n-1} + B_{n-2}$ where $A_{n-2}$ has odd number of digits
as per the given rule $A_n = 10^{x_{n-2}}A_{n-1} + A_{n-2}$ where $x_n$ is number of digits in $A_n$ hence we have
$B_n \equiv A_n \pmod {11}$
number of digits in $A_n$ is even when n is divisible by 3 and odd otherwise
now $B_3 = A_1 - A_2$
$B_4 = - B_3 + B_2 = A_2 - A_1 + A_2 = 2A_2 - A_1$
$B_5 = B_4 + B_ 3 = (2A_2 - A_1) + (A_1 - A_2) = A_2$
$B_6 = B_4 - B_5 = 2A_2 - A_1 - A_2 = A_2 - A_1$
$B_7 = - B_6 + B_5 = A_1$
$B_8 = -B_7 + B_6 = A_2$
so we get $B_{n+6} = B_n$ it is zero for n = 1 or for n = 6k+1 for $k>=0$
so $A_n$ is divisible by 11 for n = 6k+1 ($k>=0$)

Opalg's solution is here:

Spoiler

To start with, some facts about Fibonacci numbers. I prefer to start the numbering at $0$ rather than $1$, in other words $F_0 = F_1 = 1$, and then $F_2 = 2,$ $F_3 = 3,$ $F_4 = 5,$ $F_5 = 8$ and so on.

The parity of the Fibonacci numbers goes odd, odd, even, odd, odd, even, ... . In other words, $F_n$ is odd if $n\equiv 0 \text{ or }1\pmod3$, and $F_n$ is even if $n\equiv 2\pmod3.$

Now looking at the numbers $A_n$, it is clear that $A_n$ has $F_{n-1}$digits. The concatenation $A_n = A_{n-1}A_{n-2}$ can be described arithmetically as follows: multiply $A_{n-1}$ by $10^{F_{n-3}}$ (because $F_{n-3}$ is the number of digits in $A_{n-2}$), and then add $A_{n-2}.$ In symbols, $ A_n = 10^{F_{n-3}}A_{n-1} + A_{n-2}.$

Next, we want to work mod $11$. Since $10 \equiv -1\pmod{11}$, it follows that $$\begin{aligned} A_n &\equiv (-1)^{F_{n-3}}A_{n-1} + A_{n-2} \pmod{11}\\ &\equiv \begin{cases}-A_{n-1} + A_{n-2} &\text{ if }n \equiv 0 \text{ or }1\pmod3 \\ A_{n-1} + A_{n-2} &\text{ if }n \equiv 2\pmod3 \end{cases} \pmod{11}. \end{aligned}$$

Using that relation, you can find the values of $A_n\pmod{11}$ as follows:
$$\begin{array}{c|cccccccccc}n & 1&2&3&4&5&6&7&8&9&\ldots \\ \hline A_n\pmod{11} & 0 &1 & -1 & 2&1&1&0&1&-1&\ldots \end{array}$$ Notice that $A_n\pmod{11}$ is $0$ when $n = 1$ or $7$, and it is $1$ when $n=2$ or $8$. Since the value of each term in the sequence $(A_n)$ depends only on the two previous terms, it follows that the whole sequence has period $6$. In particular, $A_n = 0 \pmod{11}$ when $n\equiv1 \pmod6.$