Beaver Math Olympiad

Beaver Mathematical Olympiad (BMO) is an attempt to re-formulate the halting problem for some particular Turing machines as a mathematical problem in a style suitable for a hypothetical math olympiad.

The purpose of the BMO is twofold. First, statements where non-essential details (related to tape encoding, number of steps, etc.) are discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard question could appear deceptively simple.

Unsolved problems

1. 1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE (bbch)

Let $(a_{n})_{n\geq 1}$ and $(b_{n})_{n\geq 1}$ be two sequences such that $(a_{1},b_{1})=(1,2)$ and

$$(a_{n+1},b_{n+1})={\begin{cases}(a_{n}-b_{n},4b_{n}+2)&{\text{if }}a_{n}\geq b_{n}\\(2a_{n}+1,b_{n}-a_{n})&{\text{if }}a_{n}<b_{n}\end{cases}}$$

for all positive integers $n$. Does there exist a positive integer $i$ such that $a_{i}=b_{i}$?

The first 10 values of $(a_{n},b_{n})$ are $(1,2),(3,1),(2,6),(5,4),(1,18),(3,17),(7,14),(15,7),(8,30),(17,22)$.

2. Hydra and Antihydra

Let $(a_{n})_{n\geq 0}$ be a sequence such that $a_{n+1}=a_{n}+\left\lfloor {\frac {a_{n}}{2}}\right\rfloor$ for all non-negative integers $n$.

1. If $a_{0}=3$, does there exist a non-negative integer $k$ such that the list of numbers $a_{0},a_{1},a_{2},\dots ,a_{k}$ have more than twice as many even numbers as odd numbers? (Hydra)
2. If $a_{0}=8$, does there exist a non-negative integer $k$ such that the list of numbers $a_{0},a_{1},a_{2},\dots ,a_{k}$ have more than twice as many odd numbers as even numbers? (Antihydra)

5. 1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE (bbch)

Let $(a_{n})_{n\geq 1}$ and $(b_{n})_{n\geq 1}$ be two sequences such that $(a_{1},b_{1})=(0,5)$ and

$$(a_{n+1},b_{n+1})={\begin{cases}(a_{n}+1,b_{n}-f(a_{n}))&{\text{if }}b_{n}\geq f(a_{n})\\(a_{n},3b_{n}+a_{n}+5)&{\text{if }}b_{n}<f(a_{n})\end{cases}}$$

where $f(x)=10\cdot 2^{x}-1$ for all non-negative integers $x$.

Does there exist a positive integer $i$ such that $b_{i}=f(a_{i})-1$?

6. 1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD (bbch)

Let $f(b)=b+k+3a$, where $k$ and $a$ are non-negative integers satisfying $b=(2a+1)\cdot 2^{k}$.

Now consider the iterated application of the function $f^{n+1}(b)=f(f^{n}(b)))$, $f^{0}(b)=b$. Does there exist a non-negative integer $n$ such that $f^{n}(6)$ equals a power of 2?

7. 1RB1RF_1RC0RA_1LD1RC_1LE0LE_0RA0LD_0RB--- (bbch)

Let $v_{2}(n)$ be the largest integer $k$ such that $2^{k}$ divides $n$.

Let $f(n)=n+1+(v_{2}(n+1){\bmod {2}})$.

Now consider the iterated application of the function $f^{n+1}(b)=f(f^{n}(b)))$, $f^{0}(b)=b$.

Let $(a_{n})_{n\geq 0}$ be a sequence such that $a_{0}=1$ and $a_{n+1}=f^{n+2}\left(\left\lfloor {\frac {a_{n}}{2}}\right\rfloor \right)$ for all non-negative integers $n$.

Does there exist a non-negative integer $k$ such that $a_{k}$ is even?

(for simplicity, this question is slightly stronger than the halting problem of this TM)

Solved problems

3. 1RB0RB3LA4LA2RA_2LB3RA---3RA4RB (bbch) and 1RB1RB3LA4LA2RA_2LB3RA---3RA4RB (bbch)

Let $v_{2}(n)$ be the largest integer $k$ such that $2^{k}$ divides $n$. Let $(a_{n})_{n\geq 0}$ be a sequence such that

$$a_{n}={\begin{cases}2&{\text{if }}n=0\\a_{n-1}+2^{v_{2}(a_{n-1})+2}-1&{\text{if }}n\geq 1\end{cases}}$$

for all non-negative integers $n$. Is there an integer $n$ such that $a_{n}=4^{k}$ for some positive integer $k$?

Link to Discord discussion: https://discord.com/channels/960643023006490684/1084047886494470185/1252634913220591728

4. 1RB3RB---1LB0LA_2LA4RA3LA4RB1LB (bbch)

Bonnie the beaver was bored, so she tried to construct a sequence of integers $\{a_{n}\}_{n\geq 0}$. She first defined $a_{0}=2$, then defined $a_{n+1}$ depending on $a_{n}$ and $n$ using the following rules:

• If $a_{n}\equiv 0{\text{ (mod 3)}}$, then $a_{n+1}={\frac {a_{n}}{3}}+2^{n}+1$.
• If $a_{n}\equiv 2{\text{ (mod 3)}}$, then $a_{n+1}={\frac {a_{n}-2}{3}}+2^{n}-1$.

With these two rules alone, Bonnie calculates the first few terms in the sequence: $2,0,3,6,11,18,39,78,155,306,\dots$. At this point, Bonnie plans to continue writing terms until a term becomes $1{\text{ (mod 3)}}$. If Bonnie sticks to her plan, will she ever finish?

Solution

How to guess the closed-form solution: Firstly, notice that $a_{n}\approx {\frac {3}{5}}\times 2^{n}$. Secondly, calculate the error term $a_{n}-{\frac {3}{5}}\times 2^{n}$. The error term appears to have a period of 4. This leads to the following guess:

$$a_{n}={\frac {3}{5}}{\begin{cases}2^{n}+{\frac {7}{3}}&{\text{if }}n\equiv 0{\pmod {4}}\\2^{n}-2&{\text{if }}n\equiv 1{\pmod {4}}\\2^{n}+1&{\text{if }}n\equiv 2{\pmod {4}}\\2^{n}+2&{\text{if }}n\equiv 3{\pmod {4}}\\\end{cases}}$$

This closed-form solution can be proven correct by induction. Unfortunately, the induction may require a lot of tedious calculations.

For all $k$, we have $a_{4k}\equiv 2{\text{ (mod 3)}}$ and $a_{4k+1}\equiv a_{4k+2}\equiv a_{4k+3}\equiv 0{\text{ (mod 3)}}$. Therefore, Bonnie will never finish.