Define $A_1 = \emptyset$ and $B_1 = \{420\}$ to be our starting sets. We generate a sequence of sets as such $$A_{n+1} = \{x + 1 : x \in B_n \}$$$$B_{n+1} = (A_n \cup B_n) - (A_n \cap B_n)$$Show that $B_n = \{420\}$ if and only if $n$ is a power of $2$. Note: $\emptyset$ denotes the empty set, $\cup$ denotes set union, $\cap$ denotes set intersection and $-$ denotes set difference.
Problem
Source: 2022 IGMO Round 2 #2 International Gamma Mathematical Olympiad
Tags: Sets, algebra
pco
20.12.2023 09:02
parmenides51 wrote: Define $A_1 = \emptyset$ and $B_1 = \{420\}$ to be our starting sets. We generate a sequence of sets as such $$A_{n+1} = \{x + 1 : x \in B_n \}$$$$B_{n+1} = (A_n \cup B_n) - (A_n \cap B_n)$$Show that $B_n = \{420\}$ if and only if $n$ is a power of $2$. Note: $\emptyset$ denotes the empty set, $\cup$ denotes set union, $\cap$ denotes set intersection and $-$ denotes set difference. 1) $420+k\in B_n$ $\iff$ $n-k-1\ge k\ge 0$ and $\binom{n-k-1}k$ is odd
Let sequence $u_n^k$ ($n\in\mathbb Z_{>0},k\in\mathbb Z_{\ge 0}$) defined as $u_n^k=1$ if $420+k\in B_n$ and $ 0$ otherwise.
Definitions imply :
$u_n^0=1$ $\forall n\in\mathbb Z_{>0}$ ($420$ always belongs to any $B_n$ and in none $A_n$)
$u_1^k=0$ $\forall k\in\mathbb Z_{>0}$ ($B_1=\{420\}$)
$u_2^k=0$ $\forall k\in\mathbb Z_{>0}$ ($B_2=\{420\}$)
$u_{n+2}^k=u_{n+1}^k\oplus u_n^{k-1}$ $\forall n,k\in\mathbb Z_{>0}$ where $\oplus$ is "XOR - exclusive or".
Consider now sequence $a_n^k$ ($n\in\mathbb Z_{>0},k\in\mathbb Z_{\ge 0}$) defined as :
$a_n^0=1$ $\forall n\in\mathbb Z_{>0}$
$a_1^k=0$ $\forall k\in\mathbb Z_{>0}$
$a_2^k=0$ $\forall k\in\mathbb Z_{>0}$
$a_{n+2}^k=a_{n+1}^k+ a_n^{k-1}$ $\forall n,k\in\mathbb Z_{>0}$
We obviously have $a_n^k\equiv u_n^k\pmod 2$
And we rather easily have $a_n^k=\binom{n-k-1}k$ (with convention $0$ if $n-k-1<k$)
So $u_n^k=0$ if $\binom{n-k-1}k$ is even, and $ 1$ otherwise.
Q.E.D.
So $B_n=\{420\}\iff$ $\binom{n-k-1}k$ is even $\forall k$ such that $n-k-1\ge k\ge 1$ Note that, using Legendre formula $v_2(n!)=n-S_2(n)$ where $S_2(n)$ is the number of "one" in the binary representation of $ n$, we have $v_2(\binom {n-k-1}k)=S_2(k)+S_2(n-2k-1)-S_2(n-k-1)$ 2) If $n$ is not a power of two, there exists $k\ge 1$ such that $\binom{n-k-1}k$ is odd
We can write $n=2^p+2^{p+1}U$ for some $U\ge 1$ and some $p\ge 0$
Choosing then $k=2^p$ we have :
$S_2(k)=1$, $S_2s(n-2k-1)=p+S_2(U-1)$ and $S_2(n-k-1)=p+1+S_2(U-1)$
And so $v_2(\binom {n-k-1}k)=0$ and $\binom {n-2^p-1}{2^p}$ is odd
Q.E.D.
3) If $n=2^p$, then $\binom {n-k-1}k$ is even whatever is $k$ such that $n-k-1\ge k\ge 1$
If $n=2^p$ and $k<2^{p-1}$, then $S_2(n-k-1)=S_2(n-2k-1)(=p-S_2(k))$
And so $v_2(\binom {n-k-1}k)=S_2(k)\ge 1$
Q.E.D.