View source for 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 every non-essential details (e.g. 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 ==

=== {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}} ===

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

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(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{cases}</math>

for all positive integers <math>n</math>. Does there exist a positive integer <math>i</math> such that <math>a_i = b_i</math>?

The first 10 values of <math>(a_n, b_n)</math> are <math>(1, 2), (3, 1), (2, 6), (5, 4), (1, 18), (3, 17), (7, 14), (15, 7), (8, 30), (17, 22)</math>.

=== [[Hydra]] and [[Antihydra]] ===

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_{n+1} = a_n+\left\lfloor\frac{a_n}{2}\right\rfloor</math> for all non-negative integers <math>n</math>.

# If <math>a_0=3</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many even numbers as odd numbers? ([[Hydra]])
# If <math>a_0=8</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many odd numbers as even numbers? ([[Antihydra]])

== Solved problems ==

=== {{TM|1RB0RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} and {{TM|1RB1RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} ===

Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>. Let <math>(a_n)_{n \ge 0}</math> be a sequence such that

<math display="block">a_n = \begin{cases}
2 & \text{if } n=0 \\
a_{n-1}+2^{v_2(a_{n-1})+2}-1 & \text{if } n \ge 1
\end{cases}</math>

for all non-negative integers <math>n</math>. Is there an integer <math>n</math> such that <math>a_n=4^k</math> for some positive integer <math>k</math>?

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

=== {{TM|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB|non-halt}} ===

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

* If <math>a_n \equiv 0\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n}{3}+2^n+1</math>.
* If <math>a_n \equiv 2\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n-2}{3}+2^n-1</math>.

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

<div class="toccolours mw-collapsible mw-collapsed">'''Solution'''<div class="mw-collapsible-content">
How to guess the closed-form solution: Firstly, notice that <math>a_n \approx \frac{3}{5} \times 2^n</math>. Secondly, calculate the error term <math>a_n - \frac{3}{5} \times 2^n</math>. The error term appears to have a period of 4. This leads to the following guess:

<math display="block">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}</math>

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

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