prove that the sets $\{A_k\}$ are pairwise disjoint and that all numbers in $A_k$ are $\equiv (\frac{1}2 3^{k-1}, 3^{k-1}] \mod 3^{k}$ 
For a number n, write it in base three as $a_t\cdots a_2a_1$. Let $B$ be a positive integer and let $[B] = \{1,\cdots, B\}$. Construct the sets $A_1,A_2,\cdots$ inductively as follows. $A_1$ consists of all numbers that are at most $B$ for which $a_1 = 1$. For $k > 1, A_k$ consists of all numbers that are at most $B$ with $a_k = 0$ that weren't already placed in other sets (and that don't have $k$ zeroes at the end), together with the numbers satisfying $a_k = 1$ and $a_i = 0$ for $i < k$.



*

*Prove that all the $A_k$'s are disjoint.

*Prove that $A_k$ is the set of numbers in $[B]$ congruent to some integer in the interval $(\frac{1}2 3^{k-1}, 3^{k-1}]$ modulo $3^k$.

*Prove (without brute force, of course) that when $B=40,$ the sets $A_1,\cdots, A_4$ contain exactly the numbers from $1$ to $40$.


For a digit a, let $a^{(k)}$ denote a concatenated with itself k times.
I think it might be easier to prove the first claim by induction. It would probably be easiest to figure out the "form" of the numbers that $A_k$ contains. By definition, $A_j$ doesn't contain any numbers whose base three representation ends in at least $k$ zeroes for $j \leq k$, so in particular, $A_k$ will include all numbers in $[B]$ ending in $10^{(k-1)}$ (since none of $A_1,\cdots, A_{k-1}$ will contain such numbers). But $A_k$ does not include any numbers ending in $20^{(k - 1)}$. I'm not sure how to form the inductive hypothesis from this though.
For 2, I think an inductive proof will also work, and 1 will be useful for proving this. The base case when $k=1$ is trivial.
For part 3, one can probably prove this easily using parts 1 and 2. Note that no number $\leq 40$ can end in more than $3$ zeroes, and the only number $\leq 40$ whose base 3 representation ends in $3$ zeroes is $1000_3$. So we just need to show that $A_1,\cdots, A_4$ contain all integers $\leq B$ with less than $3$ zeroes in their base $3$ representation.
 A: Observation. If $n=\overline{a_t\ldots a_{k+1}a_k\ldots a_1}_{(3)}$ then $n\equiv \overline{a_k\ldots a_1}_{(3)}\pmod{3^k}$.
[1] I wouldn't prove it by induction. Let $i<k$ and let $n\in A_k$. Therefore, from the definition of $A_k$, either (i) $a_k=1$ and $a_i=0$ for $i<k$ or (ii) $n\notin A_i$. If (i) holds then $n\notin A_i$, since it has $i$ zeroes at the end. If (ii) holds then also $n\notin A_i$. This shows that if $n\in A_k$ then $n\notin A_i$, which shows that $A_i\cap A_k=\emptyset$.

Now let's analyse the numbers of the specific form.

*

*[a] If $n$ ends with $1(0)^{k-1}$ then $n\in A_k$.

*[b] If $n$ ends with $0a_{j}a_{j-1}\ldots a_{k+1}2(0)^{k-1}$ where $a_{k+1},\ldots,a_j\neq 0$ then $n\in A^{j+1}$.

*[c] If $a_k=0$ and $a_{j}\neq 0$ for some $i<k$ then $n\in \bigcup_{j=1}^k A_j$. Indeed, if $n\notin A_j$ for $j<k$ then, from the definition of $A_k$, we have $n\in A_k$.

*[d] If $n\equiv r\pmod{3^k}$ and $0<r\leq r_k:=\frac 12(3^{k-1}-1)=0{\underbrace{111\ldots 1}_{k-1}}{}_{(3)}$ then $n\in \bigcup_{j=1}^{k-1} A_j$. Indeed, if $r=r_k$ then $n\in A_1$. If $r<r_1$ then let $i=\max\{j<k:a_j\neq 1\}$. Then $a_i=0$ (comparison of numbers in positional numeral system). If $a_1=a_2=\ldots=a_{i-1}=0$ then $i<k-1$ and $n$ ends with $10^{(i)}$, so $n\in A_{i+1}$. If some of $a_1,a_2,\ldots,a_{i-1}$ are nonzero then from [c] we get $n\in A_i$.

*[e] Especially, from [1] we get that if $0<r\leq r_k$ then $n\notin A_k$.

[2] It's important to point out that $A_k$ isn't the set of all numbers in $[B]$ congruent to the numbers from a given interval. For example $7\in A_1$ so $7\notin A_3$, but $7\equiv 7\pmod 9$.
Observe that $A_1=\{n\in[B]:n\equiv 1\pmod 3\}$  and that $1\in (\frac 123^0,3^0]$.
Now let $k>1$ and $n\in A_k$. Let $n\equiv r\pmod{3^k}$ for $0\leq r<3^k$

*

*If $n\in A_k$ then $r\leq 3^{k-1}$ Indeed, if $a_k = 0$ then $r<3^{k-1}$. If $a_k=1$ then $r=3^{k-1}$.

*If $n\in A_k$ then $r>r_k$, so $r>\frac 123^{k-1}$. Indeed, if $r=0$ then $n$ ends with $0^{(k)}$ so $n\notin A_k$. If $0<r\leq r_k$ then $n\notin A_k$ (from [e])

[3] Observe that $40=1111_{(3)} = r_5$. Therefore $r$, the remainder $r$ modulo $3^5$ satisfies $0<r\leq r_5$. Then from [d], $n\in A_1\cup A_2\cup A_3\cup A_4$. Since $A_i\subset [40]$, the theorem is proven.
