Beaver Math Olympiad - Revision history

Sligocki: Move BMO12 to solved

2026-11-12T21:19:39Z

Move BMO12 to solved

← Older revision		Revision as of 21:19, 12 November 2026
Line 141:		Line 141:
	The question is whether there exists some finite sequence of rewrite steps, starting from <math>w^{(0)}</math>, after which the rightmost occurrence of <math>\#</math> is not		The question is whether there exists some finite sequence of rewrite steps, starting from <math>w^{(0)}</math>, after which the rightmost occurrence of <math>\#</math> is not
	active. In other words, does there exist a rewrite order such that the rightmost <math>\#</math> can no longer be rewritten?		active. In other words, does there exist a rewrite order such that the rightmost <math>\#</math> can no longer be rewritten?

	~~=== 12. [[Fractran#Size 24: Energy Vampire\|[2/15, 1/6, 441/2, 11/3, 25/7, 6/11]]] ===~~
	~~Let <math>(h_n)_{n \ge 1}</math> and <math>(w_n)_{n \ge 1}</math> be two sequences such that <math>(h_1, w_1) = (1, 2)</math> and~~

	~~<math display="block">h_{n+1} = \left\lceil \frac{8 h_n}{3} \right\rceil</math>~~

	~~<math display="block">~~
	~~w_{n+1} = \begin{cases}~~
	~~w_n - 1 & \text{if }h_n \equiv 0 \pmod{3} \\~~
	~~w_n & \text{if }h_n \equiv 1 \pmod{3} \\~~
	~~w_n + 1 & \text{if }h_n \equiv 2 \pmod{3}~~
	~~\end{cases}</math>~~

	~~for all positive integers <math>n</math>. Does there exist a positive integer <math>n</math> such that <math>w_n = 0</math>?~~

	~~Preliminary finding is that <math>w_{495141375730} = 0</math>: https://discord.com/channels/960643023006490684/1438019511155691521/1565647448452636672. Waiting for confirmation.~~

	== Solved problems ==		== Solved problems ==

	=== 3. {{TM\|1RB0RB3LA4LA2RA_2LB3RA---3RA4RB\|non-halt}} and {{TM\|1RB1RB3LA4LA2RA_2LB3RA---3RA4RB\|non-halt}} ===		=== 3. {{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		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
Line 175:		Line 159:
	Formalised solution: [https://discord.com/channels/960643023006490684/1259770421046411285/1488737894943166604 Initial announcement], [https://discord.com/channels/960643023006490684/1259770421046411285/1488743526882738276 Lean proof], [https://discord.com/channels/960643023006490684/1259770421046411285/1488781537699696821 LLM-translated Rocq proof], [https://discord.com/channels/960643023006490684/1259770421046411285/1488898995865784442 Proof of closure of existing mid-level rules].		Formalised solution: [https://discord.com/channels/960643023006490684/1259770421046411285/1488737894943166604 Initial announcement], [https://discord.com/channels/960643023006490684/1259770421046411285/1488743526882738276 Lean proof], [https://discord.com/channels/960643023006490684/1259770421046411285/1488781537699696821 LLM-translated Rocq proof], [https://discord.com/channels/960643023006490684/1259770421046411285/1488898995865784442 Proof of closure of existing mid-level rules].

	=== 4. {{TM\|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB\|non-halt}} ===		=== 4. {{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:		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:
Line 199:		Line 183:
	</div></div>		</div></div>

	=== 7. {{TM\|1RB1RF_1RC0RA_1LD1RC_1LE0LE_0RA0LD_0RB---\|non-halt}} ===		=== 7. {{TM\|1RB1RF_1RC0RA_1LD1RC_1LE0LE_0RA0LD_0RB---\|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>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>.

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

	=== 9. {{TM\|1RB1LA_1RC0RD_1LA---_1RE1RD_1LF0LA_---0LE\|undecided}} ===		=== 9. {{TM\|1RB1LA_1RC0RD_1LA---_1RE1RD_1LF0LA_---0LE\|undecided}}===

	Let <math>\mathbb{N}=\{0,1,2,\ldots\}</math>. Consider configurations given by infinite sequences of non-negative integers,		Let <math>\mathbb{N}=\{0,1,2,\ldots\}</math>. Consider configurations given by infinite sequences of non-negative integers,
Line 262:		Line 246:

	where <math>\mathbf x^{(n+1)}=T(\mathbf x^{(n)})</math> whenever the right-hand side is not <math>\mathrm{Halt}</math>.		where <math>\mathbf x^{(n+1)}=T(\mathbf x^{(n)})</math> whenever the right-hand side is not <math>\mathrm{Halt}</math>.

			=== 12. [[Fractran#Size 24: Energy Vampire\|[2/15, 1/6, 441/2, 11/3, 25/7, 6/11]]] ===
			Let <math>(h_n)_{n \ge 1}</math> and <math>(w_n)_{n \ge 1}</math> be two sequences such that <math>(h_1, w_1) = (1, 2)</math> and

			<math display="block">h_{n+1} = \left\lceil \frac{8 h_n}{3} \right\rceil</math>

			<math display="block">
			w_{n+1} = \begin{cases}
			w_n - 1 & \text{if }h_n \equiv 0 \pmod{3} \\
			w_n & \text{if }h_n \equiv 1 \pmod{3} \\
			w_n + 1 & \text{if }h_n \equiv 2 \pmod{3}
			\end{cases}</math>

			for all positive integers <math>n</math>. Does there exist a positive integer <math>n</math> such that <math>w_n = 0</math>?

			Jason Yuen found that <math>w_{495141375730} = 0</math>: https://discord.com/channels/960643023006490684/1438019511155691521/1565647448452636672

	== Practice Problems ==		== Practice Problems ==

Sligocki: Note BMO12 preliminary solution.

2026-11-04T02:51:20Z

Note BMO12 preliminary solution.

← Older revision		Revision as of 02:51, 4 November 2026
Line 155:		Line 155:

	for all positive integers <math>n</math>. Does there exist a positive integer <math>n</math> such that <math>w_n = 0</math>?		for all positive integers <math>n</math>. Does there exist a positive integer <math>n</math> such that <math>w_n = 0</math>?

			Preliminary finding is that <math>w_{495141375730} = 0</math>: https://discord.com/channels/960643023006490684/1438019511155691521/1565647448452636672. Waiting for confirmation.

	== Solved problems ==		== Solved problems ==

HelpMe: link

2026-10-28T15:37:07Z

link

← Older revision		Revision as of 15:37, 28 October 2026
Line 142:		Line 142:
	active. In other words, does there exist a rewrite order such that the rightmost <math>\#</math> can no longer be rewritten?		active. In other words, does there exist a rewrite order such that the rightmost <math>\#</math> can no longer be rewritten?

	=== 12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11] ===		=== 12. [[Fractran#Size 24: Energy Vampire\|[2/15, 1/6, 441/2, 11/3, 25/7, 6/11]]] ===
	Let <math>(h_n)_{n \ge 1}</math> and <math>(w_n)_{n \ge 1}</math> be two sequences such that <math>(h_1, w_1) = (1, 2)</math> and		Let <math>(h_n)_{n \ge 1}</math> and <math>(w_n)_{n \ge 1}</math> be two sequences such that <math>(h_1, w_1) = (1, 2)</math> and

Sligocki: /* 12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11] */

2026-10-26T20:12:28Z

12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11]

← Older revision		Revision as of 20:12, 26 October 2026
Line 151:		Line 151:
	w_n - 1 & \text{if }h_n \equiv 0 \pmod{3} \\		w_n - 1 & \text{if }h_n \equiv 0 \pmod{3} \\
	w_n & \text{if }h_n \equiv 1 \pmod{3} \\		w_n & \text{if }h_n \equiv 1 \pmod{3} \\
	w_n + 1 & \text{if }h_n \equiv 2 \pmod{3} \\		w_n + 1 & \text{if }h_n \equiv 2 \pmod{3}
	\end{cases}</math>		\end{cases}</math>

Sligocki: /* 12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11] */ Simplify h update rule

2026-10-26T20:12:11Z

12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11]: Simplify h update rule

← Older revision		Revision as of 20:12, 26 October 2026
Line 144:		Line 144:
	=== 12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11] ===		=== 12. [2/15, 1/6, 441/2, 11/3, 25/7, 6/11] ===
	Let <math>(h_n)_{n \ge 1}</math> and <math>(w_n)_{n \ge 1}</math> be two sequences such that <math>(h_1, w_1) = (1, 2)</math> and		Let <math>(h_n)_{n \ge 1}</math> and <math>(w_n)_{n \ge 1}</math> be two sequences such that <math>(h_1, w_1) = (1, 2)</math> and

			<math display="block">h_{n+1} = \left\lceil \frac{8 h_n}{3} \right\rceil</math>

	<math display="block">		<math display="block">
	~~(h_{n+1},~~ w_{n+1}) = \begin{cases}		w_{n+1} = \begin{cases}
	~~(\frac{8 h_n}{3},~~ w_n - 1) & \text{if }h_n \equiv 0 \pmod{3} \\		w_n - 1 & \text{if }h_n \equiv 0 \pmod{3} \\
	~~(\frac{8 h_n + 1}{3},~~ w_n) & \text{if }h_n \equiv 1 \pmod{3} \\		w_n & \text{if }h_n \equiv 1 \pmod{3} \\
	~~(\frac{8 h_n + 2}{3},~~ w_n + 1) & \text{if }h_n \equiv 2 \pmod{3} \\		w_n + 1 & \text{if }h_n \equiv 2 \pmod{3} \\
	\end{cases}</math>		\end{cases}</math>

Sligocki: Add BMO12

2026-10-26T20:00:30Z

Add BMO12

@@ Line 141: / Line 141: @@
 The question is whether there exists some finite sequence of rewrite steps, starting from <math>w^{(0)}</math>, after which the rightmost occurrence of <math>\#</math> is not
 active.  In other words, does there exist a rewrite order such that the rightmost <math>\#</math> can no longer be rewritten?
 == Solved problems ==

Mxdys: BMO9 was solved

2026-09-24T14:35:54Z

BMO9 was solved

@@ Line 55: / Line 55: @@
 for all positive integers <math>n</math>. Does there exist a positive integer <math>i</math> such that <math>a_n = \left\lfloor \frac{b_n}{2} \right\rfloor + 1</math>?
 === 10. {{TM|1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC---|undecided}} ===
@@ Line 246: / Line 197: @@
 Link to Discord discussion: https://discord.com/channels/960643023006490684/1421782442213376000/1431483206208852001
 == Practice Problems ==

C1: Improved the consistency of the content.

2026-08-04T00:29:29Z

Improved the consistency of the content.

← Older revision		Revision as of 00:29, 4 August 2026
Line 181:		Line 181:
	occurrence may be chosen arbitrarily; there is no prescribed reduction order.		occurrence may be chosen arbitrarily; there is no prescribed reduction order.

	At any stage, call a symbol <math>\#</math> active if it is the leftmost symbol of an occurrence of one of the ~~four~~ left-hand sides above. Equivalently, a <math>\#</math> is		At any stage, call a symbol <math>\#</math> active if it is the leftmost symbol of an occurrence of one of the five left-hand sides above. Equivalently, a <math>\#</math> is
	active if the word beginning at that <math>\#</math> starts with one of		active if the word beginning at that <math>\#</math> starts with one of

Mxdys: add BMO11

2026-08-03T16:41:01Z

add BMO11

@@ Line 141: / Line 141: @@
 :<math>
 \#0,\qquad \#100,\qquad \#110,\qquad \#1010.
 </math>

Mxdys: add BMO10

2026-08-01T09:27:05Z

add BMO10

← Older revision		Revision as of 09:27, 1 August 2026
Line 104:		Line 104:

	where <math>\mathbf x^{(n+1)}=T(\mathbf x^{(n)})</math> whenever the right-hand side is not <math>\mathrm{Halt}</math>.		where <math>\mathbf x^{(n+1)}=T(\mathbf x^{(n)})</math> whenever the right-hand side is not <math>\mathrm{Halt}</math>.

			=== 10. {{TM\|1RB0LB_0RC0LD_1LD1RE_0LA0RF_0RD1RF_0RC---\|undecided}} ===

			Let <math>\Sigma=\{0,1,\#\}</math>. Consider two-sided infinite words over <math>\Sigma</math>. The initial word is

			:<math>
			w^{(0)}=\cdots 10\#10\#10\#10\#0000\cdots,
			</math>

			that is, a left-infinite repetition of <math>10\#</math>, followed by a right-infinite tail of <math>0</math>'s.

			The rewrite rules are

			:<math>
			\#0 \to 1,
			</math>

			:<math>
			\#100 \to 000\#,
			</math>

			:<math>
			\#110 \to 000\#,
			</math>

			:<math>
			\#1010 \to 1010\#\#.
			</math>

			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 <math>\#</math> active if it is the leftmost symbol of an occurrence of one of the four left-hand sides above. Equivalently, a <math>\#</math> is
			active if the word beginning at that <math>\#</math> starts with one of

			:<math>
			\#0,\qquad \#100,\qquad \#110,\qquad \#1010.
			</math>

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

	== Solved problems ==		== Solved problems ==