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

• MHB
• Ackbach
In summary, the conversation discussed the importance of time management and setting realistic goals. The speaker emphasized the need to prioritize tasks and avoid procrastination. They also mentioned the benefits of creating a schedule and breaking down large tasks into smaller, more manageable ones. Overall, the conversation highlighted the importance of being organized and disciplined in order to achieve success.
Ackbach
Gold Member
MHB
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$.

-----

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:

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:

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.$

## 1. What is the Problem of the Week #240 - Nov 07, 2016?

The Problem of the Week #240 - Nov 07, 2016 is a mathematical problem that was posted on November 7, 2016 on a website or platform. It is a challenge for individuals to solve and typically involves critical thinking and problem-solving skills.

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

The solutions to Problem of the Week #240 - Nov 07, 2016 can vary depending on the individual's approach and thought process. However, the most common and accepted solution is usually the one that is provided by the website or platform that posted the problem.

## 3. How can I solve Problem of the Week #240 - Nov 07, 2016?

There is no one right way to solve Problem of the Week #240 - Nov 07, 2016. However, some tips for solving this type of problem include carefully reading and understanding the problem, breaking it down into smaller parts, trying different approaches, and checking your work for accuracy.

## 4. Is there a time limit for solving Problem of the Week #240 - Nov 07, 2016?

The time limit for solving Problem of the Week #240 - Nov 07, 2016 can vary depending on the website or platform that posted the problem. Some may have a specific deadline, while others may allow individuals to solve it at their own pace.

## 5. Can I collaborate with others to solve Problem of the Week #240 - Nov 07, 2016?

This depends on the rules set by the website or platform that posted the problem. Some may allow collaboration, while others may require individuals to solve the problem on their own. It is important to follow the guidelines and rules set by the website or platform to ensure fair and accurate results.

• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
2K
• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
1K
• Math POTW for University Students
Replies
1
Views
2K
• Math POTW for University Students
Replies
1
Views
1K