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.

BMO problems have been formalized in Lean and added to the DeepMind formal-conjectures database (Github).

Unsolved problems

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

Let $(a_n{)}_{n\ge 1}$ and $(b_n{)}_{n\ge 1}$ be two sequences such that $(a_1,b_1)=(1,2)$ and

$$(a_{n+1},b_{n+1})=\{\begin{array}{ll}(a_n-b_n,4b_n+2)& \text{if }{a}_n\ge b_n\\ (2a_n+1,b_n-a_n)& \text{if }{a}_n<b_n\end{array}$$

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\ge 0}$ be a sequence such that $a_{n+1}=a_n+\lfloor \frac{a_n}{2}\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\ge 1}$ and $(b_n{)}_{n\ge 1}$ be two sequences such that $(a_1,b_1)=(0,5)$ and

$$(a_{n+1},b_{n+1})=\{\begin{array}{ll}(a_n+1,b_n-f(a_n))& \text{if }{b}_n\ge f(a_n)\\ (a_n,3b_n+a_n+5)& \text{if }{b}_n<f(a_n)\end{array}$$

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. Space Needle

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?

8. 1RB0LD_0RC1RB_0RD0RA_1LE0RD_1LF---_0LA1LA (bbch)

Let $(a_n{)}_{n\ge 1}$ and $(b_n{)}_{n\ge 1}$ be two sequences such that $(a_1,b_1)=(10,12)$ and

$$(a_{n+1},b_{n+1})=\{\begin{array}{ll}(a_n-\lfloor \frac{b_n}{2}\rfloor -3,3\lfloor \frac{b_n+1}{2}\rfloor +6)& \text{if }{a}_n>\lfloor \frac{b_n}{2}\rfloor \\ (3a_n+5,b_n-2a_n)& \text{if }{a}_n\le \lfloor \frac{b_n}{2}\rfloor \end{array}$$

for all positive integers $n$. Does there exist a positive integer $i$ such that $a_n=\lfloor \frac{b_n}{2}\rfloor +1$?

9. 1RB1LA_1RC0RD_1LA---_1RE1RD_1LF0LA_---0LE (bbch)

Let $\mathbb{\mathbb{N}}=\{0,1,2,\dots \}$. Consider configurations given by infinite sequences of non-negative integers,

${\mathbb{\mathbb{N}}}^{\omega }=\{(x_0,x_1,x_2,\dots ):x_i\in \mathbb{\mathbb{N}}\}.$

Define a partial transition map

$T:{\mathbb{\mathbb{N}}}^{\omega }\to {\mathbb{\mathbb{N}}}^{\omega }\cup \{\mathrm{H}\mathrm{a}\mathrm{l}\mathrm{t}\}$

by the following rewrite rules. For all $a,b,c\in \mathbb{\mathbb{N}}$ and every infinite tail sequence $\mathbf{𝐫}\in {\mathbb{\mathbb{N}}}^{\omega }$,

$(0,a,c,\mathbf{𝐫})\mapsto (3+a+c,\mathbf{𝐫}),$

$(1,0,\mathbf{𝐫})\mapsto \mathrm{H}\mathrm{a}\mathrm{l}\mathrm{t},$

$(1,1+a,c,\mathbf{𝐫})\mapsto (a,0,1,1+c,\mathbf{𝐫}),$

$(2+a,b,c,\mathbf{𝐫})\mapsto (a,1+b,1+c,\mathbf{𝐫}).$

The initial configuration is

${\mathbf{𝐱}}^{(0)}=(0,0,0,0,\dots ).$

The question is whether the orbit of ${\mathbf{𝐱}}^{(0)}$ under repeated application of $T$ eventually halts; that is, whether there exists some $n\in \mathbb{\mathbb{N}}$ such that

$T({\mathbf{𝐱}}^{(n)})=\mathrm{H}\mathrm{a}\mathrm{l}\mathrm{t},$

where ${\mathbf{𝐱}}^{(n+1)}=T({\mathbf{𝐱}}^{(n)})$ whenever the right-hand side is not $\mathrm{H}\mathrm{a}\mathrm{l}\mathrm{t}$.

10. 1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC--- (bbch)

Let $\mathrm{\Sigma }=\{0,1,\mathrm{\#}\}$. Consider two-sided infinite words over $\mathrm{\Sigma }$. The initial word is

$w^{(0)}=\cdots 10\mathrm{\#}10\mathrm{\#}10\mathrm{\#}10\mathrm{\#}0000\cdots ,$

that is, a left-infinite repetition of $10\mathrm{\#}$, followed by a right-infinite tail of $0$'s.

The rewrite rules are

$\mathrm{\#}0\to 1,$

$\mathrm{\#}100\to 000\mathrm{\#},$

$\mathrm{\#}110\to 000\mathrm{\#},$

$\mathrm{\#}1010\to 1010\mathrm{\#}\mathrm{\#}.$

A rewrite step consists of choosing any occurrence of the left-hand side of one of these rules in the current word and replacing it by the corresponding right-hand side. The occurrence may be chosen arbitrarily; there is no prescribed reduction order.

At any stage, call a symbol $\mathrm{\#}$ active if it is the leftmost symbol of an occurrence of one of the four left-hand sides above. Equivalently, a $\mathrm{\#}$ is active if the word beginning at that $\mathrm{\#}$ starts with one of

$\mathrm{\#}0,\mathrm{\#}100,\mathrm{\#}110,\mathrm{\#}1010.$

The question is whether there exists some finite sequence of rewrite steps, starting from $w^{(0)}$, after which the rightmost occurrence of $\mathrm{\#}$ is not active. In other words, does there exist a rewrite order such that the rightmost $\mathrm{\#}$ can no longer be rewritten?

11. 1RB0LD_0LC0RE_1LA0RD_0RB0LC_1RC1RF_0LD--- (bbch)

Let $\mathrm{\Sigma }=\{0,1,\mathrm{\#}\}$. Consider two-sided infinite words over $\mathrm{\Sigma }$. The initial word is

$w^{(0)}=\cdots 10\mathrm{\#}10\mathrm{\#}10\mathrm{\#}10\mathrm{\#}0000\cdots ,$

that is, a left-infinite repetition of $10\mathrm{\#}$, followed by a right-infinite tail of $0$'s.

The rewrite rules are

$\mathrm{\#}0\to 1,$

$\mathrm{\#}100\to 010\mathrm{\#},$

$\mathrm{\#}1010\to 1010\mathrm{\#}\mathrm{\#},$

$\mathrm{\#}10110\to 10101,$

$\mathrm{\#}11\to 10.$

A rewrite step consists of choosing any occurrence of the left-hand side of one of these rules in the current word and replacing it by the corresponding right-hand side. The occurrence may be chosen arbitrarily; there is no prescribed reduction order.

At any stage, call a symbol $\mathrm{\#}$ active if it is the leftmost symbol of an occurrence of one of the five left-hand sides above. Equivalently, a $\mathrm{\#}$ is active if the word beginning at that $\mathrm{\#}$ starts with one of

$\mathrm{\#}0,\mathrm{\#}100,\mathrm{\#}1010,\mathrm{\#}10110,\mathrm{\#}11.$

The question is whether there exists some finite sequence of rewrite steps, starting from $w^{(0)}$, after which the rightmost occurrence of $\mathrm{\#}$ is not active. In other words, does there exist a rewrite order such that the rightmost $\mathrm{\#}$ can no longer be rewritten?

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\ge 0}$ be a sequence such that

$$a_n=\{\begin{array}{ll}2& \text{if }n=0\\ a_{n-1}+2^{v_2(a_{n-1})+2}-1& \text{if }n\ge 1\end{array}$$

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

Formalised solution: Initial announcement, Lean proof, LLM-translated Rocq proof, Proof of closure of existing mid-level rules.

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

Bonnie the beaver was bored, so she tried to construct a sequence of integers $\{a_n{\}}_{n\ge 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{array}{ll}{2}^n+\frac{7}{3}& \text{if }n\equiv 0(\mathrm{mod}4)\\ 2^n-2& \text{if }n\equiv 1(\mathrm{mod}4)\\ 2^n+1& \text{if }n\equiv 2(\mathrm{mod}4)\\ 2^n+2& \text{if }n\equiv 3(\mathrm{mod}4)\end{array}$$

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.

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

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

Let $(a_n{)}_{n\ge 0}$ be a sequence such that $a_0=1$ and $a_{n+1}=f^{n+2}\left(\lfloor \frac{a_n}{2}\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)

Link to Discord discussion: https://discord.com/channels/960643023006490684/1421782442213376000/1431483206208852001

Practice Problems

Problems that are not BMO-level, but provide counter-examples to certain probvious intuition:

• 1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0RD (bbch)
• 1RB0RD_0LC1RA_0RA1LB_1RE1LB_1LF1LB_---1LE (bbch)