Let $m$ be the maximum of the $a_i$. Multiply by $3^m$ in the second equation. Let $b_i = m - a_i$ Then we get $3^m =\sum i\cdot 3^{b_i} \equiv \sum i = \frac{n(n+1)}2 \mod 2$ From this we get that $n \equiv 1 \text{ or } 2 \mod 4$ $n = 1: \ \ \ \ \frac 11 = \frac 11 = 1$ $n = 2: \ \ \ \ \frac 12 + \frac 12 = \frac 13 + \frac 23 = 1$ $n = 5: \ \ \ \ \frac 14 + \frac 14 + \frac 14 + \frac 18 + \frac 18 = \frac 19 + \frac 29 + \frac 39 + \frac 4{27} + \frac 5{27} =1$ $n = 6: \ \ \ \ \frac 14 + \frac 14 + \frac 18 + \frac 18 + \frac 18 + \frac 18 = \frac 19 + \frac 29 + \frac 3{27} + \frac 4{27} +\frac 5{27} + \frac 6{27} = 1$ So my guess is that it is true for every $n \equiv 1 \text{ or } 2 \mod 4$. We will need to find a construction.

m.candales wrote: ... $n = 6: \ \ \ \ \frac 14 + \frac 14 + \frac 18 + \frac 18 + \frac 18 + \frac 18 = \frac 19 + \frac 29 + \frac 3{27} + \frac 4{27} +\frac 5{27} + \frac 6{27} = 1$ So my guess is that it is true for every $n \equiv 1 \text{ or } 2 \mod 4$. We will need to find a construction. For $n = 9$: $n = 9: \ \ \ \ \frac 14 + \frac 18 + \frac 18 + \frac 18 + \frac 18 + \frac 1{16} + \frac 1{16} + \frac 1{16} + \frac 1{16} $ $\ \ \ \ = \frac 19 + \frac 2{27} + \frac 3{27} + \frac 4{27} +\frac 5{27} + \frac 6{81} + \frac 7{81} + \frac 8{81} + \frac 9{81} $ $\ \ \ \ = 1$ But I haven't found the general construction yet. It seems that finding the construction in the general case will require at least three distinct exponents (eg $\frac 14$, $\frac 18$, and $\frac 1{16}$ for the powers of $2$ in the above example). For $n = 9$ it is possible to solve the first part using just two distinct powers of $2$ uniquely as: $\frac 18 + \frac 18 + \frac 18 + \frac 18 + \frac 18 + \frac 18 + \frac 18 + \frac 1{16} + \frac 1{16} = 1$. But this doesn't lead to any solution for the powers of $3$ part of the equation. This makes the $n = 9$ case qualitatively different from the solutions found for lower $n$ by m.candales, because all of those required just two distinct exponents.

Well, it is not hard at all to prove that if we have a solution for some odd $n$, then there is a solution for $n+1$ Indeed, let $(a_1, ..., a_k, ... , a_n)$ be such solution for $n$ odd, where $k = \frac {n+1}{2}$ The identities: $\frac{1}{2^{a_k}} = \frac{1}{2^{a_k+1}} + \frac{1}{2^{a_k+1}}$ $\frac{k}{3^{a_k}} = \frac{k}{3^{a_k+1}} + \frac{2k}{3^{a_k+1}} = \frac{k}{3^{a_k+1}} + \frac{n+1}{3^{a_k+1}}$ imply that $(a_1, ..., a_k+1, ..., a_n, a_k+1)$ is a solution for $n+1$.

So most likely the road from $4n-2$ to $4n+1$ is also done by a set of identities ?!?

m.candales wrote: Well, it is not hard at all to prove that if we have a solution for some odd $n$... For the case $n \equiv 6 \mod 8$ then a similar construction works to solve the $n+3$ case (which is the next higher value for which there could be a solution). Take $n=8k+6$. We can use the following two identities to expand the solution for $n$ to a solution for $n+3$: $\frac{1}{2^{a_{3k+3}}} = \frac{1}{2^{a_{3k+3}+2}} + \frac{1}{2^{a_{3k+3}+2}} + \frac{1}{2^{a_{3k+3}+2}} + \frac{1}{2^{a_{3k+3}+2}}$ $\frac{3k+3}{3^{a_{3k+3}}} = \frac{27k+27}{3^{a_{3k+3}+2}} $ $= \frac{3k+3}{3^{a_{3k+3}+2}} + \frac{8k+7}{3^{a_{3k+3}+2}} + \frac{8k+8}{3^{a_{3k+3}+2}} + \frac{8k+9}{3^{a_{3k+3}+2}}$ $= \frac{3k+3}{3^{a_{3k+3}+2}} + \frac{n+1}{3^{a_{3k+3}+2}} + \frac{n+2}{3^{a_{3k+3}+2}} + \frac{n+3}{3^{a_{3k+3}+2}}$ It now remains only to solve the $n+3$ case given that we have a solution for $n \equiv 2 \mod 8$ (since for $n$ even we already know $n \equiv 2 \mod 4$).

I was hoping for a while that the answer would be more interesting, but here's a somewhat messy construction that hopefully works... The main idea is that we can replace $a/3^r$ by $(3a-x)/3^{r+1}+x/3^{r+1}$ for any $x\in(0,3a)$ (as $1/2^r=1/2^{r+1}+1/2^{r+1}$). Denote this operation by $a\to\{x,3a-x\}$. For $n=1,5,9,13,17,21$, constructions are easy to find with enough patience. Now it suffices to show that for any $m\ge0$ we can do $4m+1\to 4m+2$ and for any $m\ge1$ we can do $12m+1\to 12m+13$, $12m+5\to 12m+17$, and $12m+9\to 12m+21$. 1) $4m+1\to 4m+2$. Just do $2m+1\to\{2m+1,4m+2\}$. 2) $12m+1\to 12m+13$. For the evens $2k\in(12m+1,12m+13]$, just do $k\to\{k,2k\}$ (here we use $m\ge1$). Since we can do $4m+2\to\{4m+2,8m+4\}$ and $8m+4\to\{12m+3,12m+9\},\{12m+5,12m+7\}$, we can do \begin{align*} 4m+2\to\{4m+2,8m+4\}&\to\{4m+2,8m+4,8m+4\} \\ &\to\{4m+2,12m+3,12m+9,12m+5,12m+7\}, \end{align*}and we can similarly do \[4m+4\to\{4m+4,8m+8\}\to\{4m+4,12m+11,12m+13\},\]as desired. 3) $12m+5\to 12m+17$. For the evens $2k\in(12m+5,12m+17]$, just do $k\to\{k,2k\}$ (here we use $m\ge1$). Since we can do $4m+4\to\{4m+4,8m+8\}$ and $8m+8\to\{12m+7,12m+17\},\{12m+9,12m+15\},\{12m+11,12m+13\}$, we can do \begin{align*} 4m+4\to\{4m+4,8m+8\}&\to\{4m+4,8m+8,8m+8\} \\ &\to\{4m+4,8m+8,8m+8,8m+8\} \\ &\to\{4m+4,12m+7,12m+17,12m+9,12m+15,12m+11,12m+13\}, \end{align*}as desired. 4) $12m+9\to 12m+21$. For the evens $2k\in(12m+9,12m+21]$, just do $k\to\{k,2k\}$ (here we use $m\ge1$). Since we can do $4m+6\to\{4m+6,8m+12\}$ and $8m+12\to\{12m+15,12m+21\},\{12m+17,12m+19\}$, we can do \begin{align*} 4m+6\to\{4m+6,8m+12\}&\to\{4m+6,8m+12,8m+12\} \\ &\to\{4m+6,12m+15,12m+21,12m+17,12m+19\}, \end{align*}and we can similarly do \[4m+4\to\{4m+4,8m+8\}\to\{4m+4,12m+11,12m+13\},\]as desired. Edit: OK, I agree that 21 is not as easy as the others, but we can use most of (4): just do $k\to\{k,2k\}$ for even $2k\in\{12,14,16,18\}$ and then $5\to\{5,10\}\to\{5,10,20\}$ to finish off the evens (the rest is the same). Edit: I should clarify that if we can do $x\to\{x\}\cup S$ and $x\to\{x\}\cup T$ for two disjoint sets $S,T$ not containing $x$, then we can in fact do $x\to\{x\}\cup S\cup T$. Indeed, my notation above was a bit sloppy.

Good solution, math154. I agree with you that basis step constructions for $n=1,5,9,13,17$ are "easy to find". But I had more trouble with $n=21$. Can you show how you did that construction for $n=21$? As you correctly note your inductive argument only works for $m\ge 1$ so it won't allow us to inductively construct $n=21$ from $n=9$.

There is still a problem with your amended approach for dealing with the $n=21$ case. The issue is that you are using $6$ twice both for the evens and the odds! For the evens you are using $6\rightarrow \{6,12\}$ and for the odds you are using $6\rightarrow \{6,15,17,19,21\}$. Not sure that will work too well!

Actually on reflection I think it does work since you could do $6\rightarrow \{6,12\}\rightarrow \{6,12,15,17,19,21\}$ so it should be OK.

My way of construction: First it is easy to show that all $n=0$ or $3$ $(mod 4)$ cannot be done since the numerator will be even. Before the inductive part, we shall introduce two kinds of "substitution" as follow: 1) $\frac{1}{2^k} = \frac{1}{2^{k+1}} + \frac{1}{2^{k+1}}$ and $\frac{a}{3^k} = \frac{a}{3^{k+1}} + \frac{2a}{3^{k+1}}$ 2) $\frac{1}{2^k} = \frac{1}{2^{k+2}} + \frac{1}{2^{k+3}} + \frac{1}{2^{k+3}} + \frac{1}{2^{k+3}} + \frac{1}{2^{k+3}} + \frac{1}{2^{k+3}} + \frac{1}{2^{k+3}}$ and $\frac{a}{3^k} = \frac{a}{3^{k+2}} + \frac{4a-5}{3^{k+3}} + \frac{4a-3}{3^{k+3}} + \frac{4a-1}{3^{k+3}} + \frac{4a+1}{3^{k+3}} + \frac{4a+3}{3^{k+3}} + \frac{4a+5}{3^{k+3}}$ Starting from the base cases: $n=1,5,9$, which can be found easily, we will show that: a) $n=4m+1\to n=4m+2$. Simply do the first substitution once (by taking $a=2m+1$). b) $n=4m+2\to n=4m+13$. First we do the second substitution (by taking $a=m+2$), after that we apply the first substitution repeatedly, taking $a=2m+2, 2m+3... 2m+6$. And the proof is complete by inductive hypothesis.

Note that: i) $\frac{1}{2^{x}}=\frac{1}{2^{x+1}}+\frac{1}{2^{x}}$ $ \frac{k}{3^{x}}=\frac{k}{3^{x+1}}+\frac{2k}{3^{x+1}}$ ii) $\frac{1}{2^{x}}=\frac{1}{2^{x+1}}+\frac{1}{2^{x+2}}+\frac{1}{2^{x+2}}$ $\frac{k}{3^{x}}=\frac{k}{3^{x+1}}+\frac{3k-j}{3^{x+2}}+\frac{3k+j}{3^{x+2}}$ j =(3,1,2) Then we have:(*) are: $2k+1 \to 2k$ $12k-2 \to 12k+1 \to 12k+2 \to 12k+9$ $12k+6 \to 12k+17 \to 12k+8 \to 12(k+1)+6$ And n must : 4k+1. 4k+2 (**) with (*) and (**) we are done

Perhaps the construction below works (for the general case $k \geq 3$): For $n=8k+1$, we have $\frac{6k+2}{3^{8k}}+\frac{6k+4}{3^{8k}}+\frac{8k+1}{3^{8k-1}}+\frac{8k-1}{3^{8k-2}}+\frac{8k}{3^{8k-3}}+\frac{8k-3}{3^{8k-4}}+\frac{8k-2}{3^{8k-5}}+...$ $+\frac{6k+5}{3^{6k+4}}+\frac{6k+6}{3^{6k+3}}+\frac{6k+3}{3^{6k+2}}+\frac{6k+1}{3^{6k+1}}+\frac{6k-1}{3^{6k}}+\frac{6k}{3^{6k-1}}+...+\frac{1}{3^2}+\frac{2}{3^1}=1$. For $n=8k+2$, we change the above first three terms to $\frac{6k+2}{3^{8k+1}}+\frac{6k+4}{3^{8k+1}}+\frac{8k+1}{3^{8k}}+\frac{8k+2}{3^{8k-1}}$. For $n=8k+5$, we have $\frac{6k+4}{3^{8k+4}}+\frac{6k+8}{3^{8k+4}}+\frac{8k+5}{3^{8k+3}}+\frac{8k+3}{3^{8k+2}}+\frac{8k+4}{3^{8k+1}}+\frac{8k+1}{3^{8k}}+\frac{8k+2}{3^{8k-1}}+...$ $+\frac{6k+9}{3^{6k+8}}+\frac{6k+10}{3^{6k+7}}+\frac{6k+7}{3^{6k+6}}+\frac{6k+5}{3^{6k+5}}+\frac{6k+6}{3^{6k+4}}+\frac{6k+3}{3^{6k+3}}+\frac{6k+1}{3^{6k+2}}+\frac{6k+2}{3^{6k+1}}...$ $+\frac{1}{3^2}+\frac{2}{3^1}=1$. For $n=8k+6$, we change the above first three terms to $\frac{6k+4}{3^{8k+5}}+\frac{6k+8}{3^{8k+5}}+\frac{8k+5}{3^{8k+4}}+\frac{8k+6}{3^{8k+3}}$.

Does anybody know how many points participants got for every of this nesessary steps? m.candales wrote: Let $m$ be the maximum of the $a_i$. Multiply by $3^m$ in the second equation. Let $b_i = m - a_i$ Then we get $3^m =\sum i\cdot 3^{b_i} \equiv \sum i = \frac{n(n+1)}2 \mod 2$ From this we get that $n \equiv 1 \text{ or } 2 \mod 4$ m.candales wrote: Well, it is not hard at all to prove that if we have a solution for some odd $n$, then there is a solution for $n+1$ Indeed, let $(a_1, ..., a_k, ... , a_n)$ be such solution for $n$ odd, where $k = \frac {n+1}{2}$ The identities: $\frac{1}{2^{a_k}} = \frac{1}{2^{a_k+1}} + \frac{1}{2^{a_k+1}}$ $\frac{k}{3^{a_k}} = \frac{k}{3^{a_k+1}} + \frac{2k}{3^{a_k+1}} = \frac{k}{3^{a_k+1}} + \frac{n+1}{3^{a_k+1}} $ imply that $(a_1, ..., a_k+1, ..., a_n, a_k+1)$ is a solution for $n+1$. My guess is 1+1. Though.. if I could I gave 2 points for the first step.

pavel kozlov wrote: My guess is 1+1. Your guess is correct.

If $X=(a_1,a_2,...a_{2n+1})$be a permutation of $(1,2,...2n+1)$, and let $G=(1,2,3,...2n,2n)$, another set with $2n+1$ elements. Define $D(X)= \sum {a_i/3^{g_i}}$. We are done if we can find can a permutation $X$ such that $D(X)=1$, since $\sum{1/2^{g_i}}=1$. If $X=(2,1,4,3,6,5,...2n,2n-1,2n+1)$, then it is straightforward to show by induction that $D(X) = 1+ n/3^{2n}$. Now assume $n$ even and $n=2m$. If $X=(2,1,4,3,...,2m,2m-1,2m+2,2m+1,...,4m,4m-1,4m+1)$, then define $Y=(2,1,4,3,...,2m,2m-1,2m+1,...4m,4m-1,4m+1,2m+2)$. (The $2m+1th$ term is moved to the end.) Calculation shows that $D(X)-D(Y)=2m/3^{4m}$, so $D(Y)=1$. Earlier posts show that it is easy to prove that $4m+2$ works once the validity of $4m+1$ is established.

First,we've $\sum\frac{i}{3^i}=1\implies 1-\sum i =\sum i(\frac {1-3^i}{3^i})$ and that implies $\sum i -1$ is even and so $n(n+1)$ is odd, thus $n\equiv 1,2(mod 4)$. Lets denote $f(n)=\sum_{i=1}^{n}\frac {i}{3^i}=1$ where for that $n$ we get such $n$ numbers. Suppose true for some $4n+7$ now, $f(4n-7)=\sum_{i=1}^{4n-7}\frac {i}{3^i}=x_n+\frac{n}{3^x}$. More preciously, write that as $f(4n-7)=x'_n+\frac{n}{3^x}+\frac {2n-3}{3^a}+\frac {2n-2}{3^b}+\frac {2n}{3^c}+\frac {2n+1}{3^d}$. So we've $S_2(x'_n)+x+a+b+c+d=1$ where $S_2(y)$ is taken as $\sum t_i$ where $y=\sum\frac {t_i}{2^{t_i}}$. So, $f(4n-7)=x'_n+\frac{n}{3^x}+\frac {2n-3}{3^{a+1}}+\frac{4n-6}{3^{a+1}}+\frac {2n-2}{3^{b+1}}+\frac{4n-4}{3^{b+1}}+\frac {2n}{3^{c+1}}+\frac{4n}{3^{c+1}}+\frac {2n+1}{3^{d+1}}+\frac{4n+2}{3^{d+1}}$. So we can write $f(4n-7)=x'_n+\sum \frac{even}{3^i}+\frac{n}{3^x}$. Now so we need of evens, but surprisingly we're getting odds from, $\frac {n}{3^x}=\frac {3n+ \sum_{i=-3}^{2}(4n+2i+1)}{3^{x+3}}$. Now so we can see $f(4n-7)=1\implies f(4n+5)=1$.Thus by induction(base case is easy) we get $\sum_{i=1}^{4n+1}\frac {i}{3^i}=1$ for all $n\in\mathbb N$. Now just write $\frac {2n+1}{3^x}=\frac {2n+1}{3^{x+1}}+\frac {4n+2}{3^{x+1}}$. So also $f(k)=1$ for all $k\equiv 1,2 (mod 4)$.

math154 wrote: I was hoping for a while that the answer would be more interesting, but here's a somewhat messy construction that hopefully works... The main idea is that we can replace $a/3^r$ by $(3a-x)/3^{r+1}+x/3^{r+1}$ for any $x\in(0,3a)$ (as $1/2^r=1/2^{r+1}+1/2^{r+1}$). Denote this operation by $a\to\{x,3a-x\}$. For $n=1,5,9,13,17,21$, constructions are easy to find with enough patience. Now it suffices to show that for any $m\ge0$ we can do $4m+1\to 4m+2$ and for any $m\ge1$ we can do $12m+1\to 12m+13$, $12m+5\to 12m+17$, and $12m+9\to 12m+21$. 1) $4m+1\to 4m+2$. Just do $2m+1\to\{2m+1,4m+2\}$. 2) $12m+1\to 12m+13$. For the evens $2k\in(12m+1,12m+13]$, just do $k\to\{k,2k\}$ (here we use $m\ge1$). Since we can do $4m+2\to\{4m+2,8m+4\}$ and $8m+4\to\{12m+3,12m+9\},\{12m+5,12m+7\}$, we can do \begin{align*} 4m+2\to\{4m+2,8m+4\}&\to\{4m+2,8m+4,8m+4\} \\ &\to\{4m+2,12m+3,12m+9,12m+5,12m+7\}, \end{align*}and we can similarly do \[4m+4\to\{4m+4,8m+8\}\to\{4m+4,12m+11,12m+13\},\]as desired. 3) $12m+5\to 12m+17$. For the evens $2k\in(12m+5,12m+17]$, just do $k\to\{k,2k\}$ (here we use $m\ge1$). Since we can do $4m+4\to\{4m+4,8m+8\}$ and $8m+8\to\{12m+7,12m+17\},\{12m+9,12m+15\},\{12m+11,12m+13\}$, we can do \begin{align*} 4m+4\to\{4m+4,8m+8\}&\to\{4m+4,8m+8,8m+8\} \\ &\to\{4m+4,8m+8,8m+8,8m+8\} \\ &\to\{4m+4,12m+7,12m+17,12m+9,12m+15,12m+11,12m+13\}, \end{align*}as desired. 4) $12m+9\to 12m+21$. For the evens $2k\in(12m+9,12m+21]$, just do $k\to\{k,2k\}$ (here we use $m\ge1$). Since we can do $4m+6\to\{4m+6,8m+12\}$ and $8m+12\to\{12m+15,12m+21\},\{12m+17,12m+19\}$, we can do \begin{align*} 4m+6\to\{4m+6,8m+12\}&\to\{4m+6,8m+12,8m+12\} \\ &\to\{4m+6,12m+15,12m+21,12m+17,12m+19\}, \end{align*}and we can similarly do \[4m+4\to\{4m+4,8m+8\}\to\{4m+4,12m+11,12m+13\},\]as desired. Edit: OK, I agree that 21 is not as easy as the others, but we can use most of (4): just do $k\to\{k,2k\}$ for even $2k\in\{12,14,16,18\}$ and then $5\to\{5,10\}\to\{5,10,20\}$ to finish off the evens (the rest is the same). Edit: I should clarify that if we can do $x\to\{x\}\cup S$ and $x\to\{x\}\cup T$ for two disjoint sets $S,T$ not containing $x$, then we can in fact do $x\to\{x\}\cup S\cup T$. Indeed, my notation above was a bit sloppy. That's the official solution you brought it exactly from the book.

start with (9,27,9,81,81,81,81,81,81) multiply 4th, 5th, last-2nd and last-4th term by 3 (9,27,9,243,243,243,81,243,81) add 4 terms equal to the numbers in red to the end of the above sequence, this is a solution for n=13 (9,27,9,243,243,243,81,243,81,243,243,243,243) using the same algorithm, the solution for n=17 is (9,27,9,729,729,243,81,243,81,729,243,729,243,729,729,729,729) this algorithm create solutions for 9,13,17,21,25,29,...

Solution: First of all, note that $v_2(\sum_{i=1}^{n} \frac{1}{3^{a_i}}) \geq 1$ if and only if $v_2(\frac{n(n+1)}{2})\geq 1$. But since that said sum should be $1$ in any solution for any particular $n$ we can see that $\frac{n(n+1)}{2}$ must be odd. So a solution for $n$ existing implies $n \equiv 1$ or $2$ mod $4$. We claim that the converse is also true. We solve this with constructions. We say that $a->b$ if a solution for $a$ existing implies a solution for $b$ existing, by finding a suitable construction. We will show that: 1.$4k+1->4k+2$. 2.$4k+1->4k+9$ for $k \geq 1$. Then we are done from the base cases $n=1,5,9$(solutions (in ordered tuples obviously) $(a_1)=0$, $(a_1,a_2,a_3,a_4,a_5)=(2,2,2,3,3)$, $(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9)=(2,2,4,4,4,3,4,4,4)$ respectively). Proof of $1$: Trivial. Consider the solution for $4k+1$. If $a_{2k+1}=m$ then change $a_{2k+1}$ to $m+1$ and also add $a_{4k+2}=m+1$ and this is our new solution for $4k+2$. Thus $4k+1->4k+2$. Proof of $2$: We will first show that we can choose a permutation $(a,b,c,d,e,f,g,h)$ of $(4k+2,4k+3,4k+4,4k+5,4k+6,4k+7,4k+8,4k+9)$ such that $3a+9b+9c+d+e+f+g+h=(a+b+c+d+e+f+g+h)+2a+8(b+c)=32k+44+2a+8(b+c)$ is a multiple of $80$. Trivially we can choose an even number $a$ such that $32k+44+2a$ is a multiple of $16$. Then, we can suitably choose two odd numbers $b,c$ such that $32k+44+2a+8(b+c)$ is a multiple of $5$. This gives the desired permutation $(a,b,c,d,e,f,g,h)$. We will call such a permutation a constructive permutation of $(4k+2,4k+3,4k+4,4k+5,4k+6,4k+7,4k+8,4k+9)$. Of course, since $k \geq 1$ we have that if $3a+9b+9c+d+e+f+g+h=80p$ for some positive integer $p$ then $p<4k+2$. Now, consider a solution of $4k+1$ for $k \geq 1$. Consider any constructive permutation $(a,b,c,d,e,f,g,h)$ of $(4k+2,4k+3,4k+4,4k+5,4k+6,4k+7,4k+8,4k+9)$. Let $a_p=j$ where $p$ is defined the same way as we obtained earlier. Do the following changes in the solution for $4k+1:$ Change $a_p$ to $j+4$ and add $a_a=j+3, a_b=a_c=j+2, a_d=a_e=a_f=a_g=a_h=j+4$ and this is a solution for $4k+9$, it can be verified. Thus $4k+1->4k+9$ as desired. Thus a solution for $n$ exists if and only if $n \equiv 1$ or $2$ mod $4$.

Here is a different solution which uses the steps $4k+1 \rightarrow 4k+2$ and $4k+2 \rightarrow 4k+9$ for $k \in \mathbb{N}$.

(If anyone can fix my table that would be very much appreciated!, if you want a good table visit this link: https://latex.artofproblemsolving.com/miscpdf/uyjbvkqy.pdf?t=1591636145898) The answer is $n\equiv 1(\bmod\; 4)$ or $n\equiv 2(\bmod\; 4)$ Proof of Necessity: We take modulo 2: \[ \sum_{i=1}^n i3^{x-a_i}=3^x \] \[ \sum_{i=1}^n i\equiv 1(\bmod\; 2)\] So $4\nmid n(n+1)$ forcing $n\equiv 1(\bmod\; 4)$ or $n\equiv 2(\bmod\; 4)$. Proof of Sufficiency: The key idea is to use induction with the help of insertion. We want to go from $n\rightarrow n+12$ That is, given $n$ works, I want $n+12$ to work. Base Cases: \begin{center} \begin{tabular}{ | m{1cm} | m{5cm}|} \hline n&$(a_i)_{i=1}^n$\\ \hline 1& 0 \\ \hline 2 & 1,1 \\ \hline 5&2,2,2,3,3\\ \hline 6&2,2,3,3,3,3\\ \hline 9&2,3,2,4,4,4,4,4,4\\ \hline 10&2,3,2,4,5,4,4,4,4,5\\ \hline \end{tabular}\end{center} Now I go from $n\rightarrow n+12$. The key step is to "break" a $\frac{1}{2^{a_i}}$ term apart into $\frac{u}{3^{a_i+1}}+\frac{v}{3^{a_i+1}}$ such that $u+v=3i$, $a_u=a_v=a_i$. Observation: if I let $v=2u \therefore i=u$, then I can make $a_{2u}$ nonzero without making anything else zero. If I first pair the $11 (\bmod\; 12)$ and $1(\bmod\; 12)$ guys together in the set $\{n+1,n+2,\cdots,n+12\}$, and say after making them nonzero I made $2k$ zero (their sum is $6k$). Then I let the a of these terms be $a_{2k+1}$ and now I need to fill it, but this can be easily done by the observation. Similarly, I can pair the $3 (\bmod\; 12)$ and $9(\bmod\; 12)$, as well as the $5 (\bmod\; 12)$ and $7(\bmod\; 12)$. Now I simply need to fill a bunch of even terms and I'm done by the observation.

KaiDaMagical336 wrote: Now I go from $n\rightarrow n+12$. The key step is to "break" a $\frac{1}{2^{a_i}}$ term apart into $\frac{u}{3^{a_i+1}}+\frac{v}{3^{a_i+1}}$ such that $u+v=3i$, $a_u=a_v=a_i$. Observation: if I let $v=2u \therefore i=u$, then I can make $a_{2u}$ nonzero without making anything else zero. If I first pair the $11 (\bmod\; 12)$ and $1(\bmod\; 12)$ guys together in the set $\{n+1,n+2,\cdots,n+12\}$, and say after making them nonzero I made $2k$ zero (their sum is $6k$). Then I let the a of these terms be $a_{2k+1}$ and now I need to fill it, but this can be easily done by the observation. Similarly, I can pair the $3 (\bmod\; 12)$ and $9(\bmod\; 12)$, as well as the $5 (\bmod\; 12)$ and $7(\bmod\; 12)$. Now I simply need to fill a bunch of even terms and I'm done by the observation. Can you explain this step a little bit? I was trying to understand but with no success. As far as I understood, you tried e.g. build a solution for n=17 from n=5.

Johann Peter Dirichlet wrote: KaiDaMagical336 wrote: Now I go from $n\rightarrow n+12$. The key step is to "break" a $\frac{1}{2^{a_i}}$ term apart into $\frac{u}{3^{a_i+1}}+\frac{v}{3^{a_i+1}}$ such that $u+v=3i$, $a_u=a_v=a_i$. Observation: if I let $v=2u \therefore i=u$, then I can make $a_{2u}$ nonzero without making anything else zero. If I first pair the $11 (\bmod\; 12)$ and $1(\bmod\; 12)$ guys together in the set $\{n+1,n+2,\cdots,n+12\}$, and say after making them nonzero I made $2k$ zero (their sum is $6k$). Then I let the a of these terms be $a_{2k+1}$ and now I need to fill it, but this can be easily done by the observation. Similarly, I can pair the $3 (\bmod\; 12)$ and $9(\bmod\; 12)$, as well as the $5 (\bmod\; 12)$ and $7(\bmod\; 12)$. Now I simply need to fill a bunch of even terms and I'm done by the observation. Can you explain this step a little bit? I was trying to understand but with no success. As far as I understood, you tried e.g. build a solution for n=17 from n=5. My operation doesn't work for small numbers. I should actually fill the even terms first: if $a_k=x, a_{2k}$ is not filled, then I should have $a_k=a_{2k}=x+1$. Then for odd terms, if I sum them, their sum is divisible by 12, so the term I want is filled, as it is divisible by 4. Call them $u,v$ and $u+v=12k$. Since $4k$ is filled, let $x=a_{4k}$. First clear $a_{4k}$, and then fill $a_u$, $a_v$ with $x+1$. Now fill $a_{4k}$ with $a_{2k}$: let $y=a_{2k}$, then make $a_{2k}=a_{4k}=y+1$.

I did an adaptation to the solution of KaiDaMagical336. Part I: multiplying the leftmost equality by $3^M$ big enough, we will have something like this: $1 \cdot 3^b_1 + 2 \cdot 3^{b_2} + 3 \cdot 3^{b_3} + \ldots +n^{3^{b_n}} = 3^M$ Looking at it modulo 2: $1 + 2 + 3 + \ldots + n \equiv 1$ Splitting it in two cases: - n is even, $n=2x$ $1 + 3 + \ldots + 2x-1 \equiv 1$, in other words, x is odd, and then $n \equiv 2 \pmod{4}$ - n is odd, $n=2x-1$ $1 + 3 + \ldots + 2x-1 \equiv 1$, in other words, x is odd, and then $n \equiv 1 \pmod{4}$ Then, all possible values of $n$ are $4k+1$ or $4k+2$. Now we will generate them. In order to clarify the algorithm, I will treat the problem as "Find the set $A(n)=\{(1,a_1), (2,a_2), (3,a_3), \ldots, (n,a_n)\}$". The idea is to use a transformation (call it split): if we have a pair $(M,a)$, we can erase it and substitute by $(i,a+1), (j,a+1)$ with $i+j=3M$. Indeed, $\cfrac{1}{2^{a}} = \cfrac{1}{2^{a+1}} + \cfrac{1}{2^{a+1}}$ and $\cfrac{M}{3^{a}} = \cfrac{i}{3^{a+1}} + \cfrac{j}{3^{a+1}}$ Define a "non-destructive split" as a split from $(M,a)$ to $(M,a+1),(2M,a+1)$. That split doesn't "destroy" the pair containing $M$ as first coordinate, it just changes the second coordinate in order to create a new pair. On the other hand, sometimes we will need the more general split too; the idea will be to non-destructively split an already existent pair and then "destructively" generate two new pairs. Suppose we already solved our problem for $n \in \{1,2,5,6,9,10\}$. The idea is to fill the set from $A(n)$ to $A(n+12)$. We group the elements of $\{n+1, n+2, \ldots,n+12\}$ that way: if $j$ is even, it stays alone; else, pair it with the number such that the sum is a multiple of 12. (An example for $n=13$ is ${2},{3,9}, {4}, {5,7},{6},{8},{10},{11,13}$) Now, for the smallest to the biggest, we just do the following: - If the number is alone, it will be even; split its half. - If the number is coupled, let $p+q=12 \cdot S$ the sum of the couple (by construction, that sum will be a multiple of 12). Now do two splits: first we non-destructively generate from the pair $(2S,a)$ the pairs $(2S,a+1), (4S,a+1)$ and then we destructively generate $(p,a+2),(q,a+2)$. (Using our example: (1,1) (1,1), (2,1) (1,1), (2,2), (4,2) -> (1,1), (2,2), (3,3),(9,3) (1,1), (2,3), (3,3),(4,3),(9,3) (1,1), (2,4), (3,3),(4,3),(4,4),(9,3) -> (1,1), (2,4), (3,3),(4,3),(5,5),(7,5),(9,3) (1,1), (2,4), (3,4),(4,3),(5,5),(6,4),(7,5),(9,3) (1,1), (2,4), (3,4),(4,4),(5,5),(6,4),(7,5),(8,4),(9,3) (1,1), (2,4), (3,4),(4,4),(5,6),(6,4),(7,5),(8,4),(9,3),(10,6) (1,1), (2,4), (3,4),(4,4),(5,6),(6,4),(7,5),(8,4),(9,3),(10,6) (1,1), (2,4), (3,4),(4,5),(5,6),(6,4),(7,5),(8,4),(8,5),(9,3),(10,6) (1,1), (2,4), (3,4),(4,5),(5,6),(6,4),(7,5),(8,4),(9,3),(10,6),(11,6),(13,6) (1,1), (2,4), (3,4),(4,5),(5,6),(6,7),(7,5),(8,4),(9,3),(10,6),(11,6),(12,7),(13,6) Now I want to write a program in Scheme!)

Suppose some $n$ worked. Taking the powers of $3$ equation mod $2$ gives us \[1+2+\cdots+n \equiv 1\pmod{2},\]so $n\equiv 1,2\pmod{4}$. We claim all such $n$ work. Given a construction for some $n$, our goal is to make a construction for $n+k-1$, where $k$ is some fixed positive integer. These constructions will only work for $n$ in some residue class, so our goal is to cover all the $1,2\pmod{4}$ integers using various constructions of this form. We'll now describe the general construction. Fix some nonnegative integers $(b_1,\ldots,b_k)$ such that \[\sum_{t=1}^k\frac{1}{2^{b_t}} = 1.\]For some to-be-determined value $j$, we modify a working sequence $(a_1,\ldots,a_n)$ as follows. Construct a new sequence $(a_1',\ldots,a_{n+k-1}')$ by \[a_i' = \begin{cases}a_i&\text{ for }i\in\{1,2,\ldots,n\}\setminus\{j\}\\ a_j+b_1 &\text{ for }i=j \\ a_j+b_{i-n+1} &\text{ for }i\in\{n+1,\ldots,n+k-1\}. \end{cases}\]It is straightforward to check that $\sum 2^{-a_i'}=1$, and that $\sum i 3^{-a_i'}=1$ if and only if \[\frac{3^{b_1}-1}{3^{b_1}}j = (n-1)\left(\sum_{t=2}^k\frac{1}{3^{b_t}}\right) + \sum_{t=2}^k \frac{t}{3^{b_t}}\qquad(\star).\]In order for a solution $j\in\{1,\ldots,n\}$ to exist, there will be some modular restriction on $n$, and potentially a size restriction as well (though this won't matter much). We have a series of claims which are various incarnations of the above general construction. The notation $n\to n+c$ indicates that any construction for $n$ can be modified into a construction for $n+c$. Claim: If $n\equiv 1\pmod{2}$, then $n\to n+1$. Proof: Take $(b_1,b_2)=(1,1)$. It suffices to find a $j\in\{1,2,\ldots,n\}$ such that $(\star)$ is satisfied. Indeed, it is equivalent to \[\frac{2}{3}j = \frac{1}{3}(n-1)+\frac{2}{3},\]or $j=\frac{n+1}{2}$, which works. $\blacksquare$ Claim: If $n\equiv 6\pmod{8}$, then $n\to n+3$. Proof: Take $(b_1,b_2,b_3,b_4)=(2,2,2,2)$. It suffices to find a $j\in\{1,2,\ldots,n\}$ such that $(\star)$ is satisfied. Indeed, it is equivalent to \[\frac{8}{9}j = \frac{1}{3}(n-1)+1,\]or $j=\frac{3n+6}{8}$, which works. $\blacksquare$ Claim: If $n\equiv 1\pmod{3}$, then $n\to n+4$. Proof: Take $(b_1,b_2,b_3,b_4,b_5)=(2,2,2,3,3)$. It suffices to find a $j\in\{1,2,\ldots,n\}$ such that $(\star)$ is satisfied. Indeed, it is equivalent to \[\frac{8}{9}j = \frac{8}{27}(n-1)+\frac{24}{27},\]or $j=\frac{n+2}{3}$, which works. $\blacksquare$ Claim: If $n\equiv 1\pmod{4}$, then $n\to n+12$. Proof: Take $(b_t)_{t=1}^{13}=(2,2,3,3,6,6,6,5,6,6,6,4,4)$. It suffices to find a $j\in\{1,2,\ldots,n\}$ such that $(\star)$ is satisfied. Indeed, it is equivalent to \[\frac{8}{9}j = \frac{2}{9}(n-1)+\frac{8}{9},\]or $j=\frac{n+3}{4}$, which works. $\blacksquare$ It is easy to check that we can get to any $1,2\pmod{4}$ number using the above claims, and the trivial base case of $n=1$. Remark: In fact we only need the first and last claims if we include a lot more base cases, but the rest are included so the below motivation makes sense. Remark: Everything up to the last claim is extremely natural, and in particular I came up with all the previous claims by essentially plugging in random sequences $(b_t)$. The first $n$ missed by my progress was $n=13$. I realized that if we actually take $(b_t)$ to be a solution for $n=13$, then the second term of the right side of $(\star)$ becomes super nice, assuming we take $b_1$ to be small (at most $2$). Now, as long as we can rig a solution with $\sum_t 3^{-b_t}$ also having denominator with small $v_3$, then we should get a nice final claim. The sequence you see there is a product of a lot of experimentation trying to force $b_1=2,$, $\sum_t 2^{-b_t}=1$ and $v_3\left(\sum_t 3^{-b_t}\right)\ge -2$ simultaneously, and then essentially rigging a permutation to make $\sum t3^{-b_t}=1$. This worked after an hour of messing around.

Solved with nukelauncher. The answer is \(n\equiv1,2\pmod4\). These are obviously the only \(n\) that work, since if \(n\equiv3,4\pmod4\), then \[1=\frac1{3^{a_1}}+\frac2{3^{a_2}}+\cdots+\frac n{3^{a_n}}\equiv1+2+\cdots+n\equiv0\pmod2,\]contradiction. We will show all \(n\equiv1,2\pmod4\) by strong induction, with the following base cases: For \(n=1\), take \((a_1)=(0)\). For \(n=5\), take \((a_1,\ldots,a_5)=(2,2,2,3,3)\). For \(n=9\), take \((a_1,\ldots,a_9)=(2,3,3,3,3,4,4,4,4)\). Claim: If \(4k+1\) works, then so does \(4k+2\). Proof. Note the identities \[ \frac1{2^{a_{2k+1}}}=\frac1{2^{a_{2k+1}+1}}+\frac1{2^{a_{2k+1}+1}} \quad\text{and}\quad \frac{2k+1}{3^{a_{2k+1}}}=\frac{2k+1}{3^{a_{2k+1}+1}}+\frac{4k+2}{3^{a_{2k+1}+1}}. \] Now suppose \((a_1,\ldots,a_{4k+1})\) is a valid solution for \(n=4k+1\). Setting \(b_{2k+1}=b_{4k+2}=a_{2k+1}+1\) and \(b_i=a_i\) for all other \(i\), we obtain a valid solution \((b_1,\ldots,b_{4k+2})\) for \(n=4k+2\). \(\blacksquare\) Claim: If \(4k+1\) works, then so does \(4k+13\). Proof. Let \((x_1,\ldots,x_{13})=(2,2,3,3,6,6,6,5,6,6,6,4,4)\) satisfy \[\frac1{2^{x_1}}+\frac1{2^{x_2}}+\cdots+\frac1{2^{x_{13}}}=\frac1{3^{x_1}}+\frac2{3^{x_2}}+\cdots+\frac{13}{3^{x_{13}}}=1\quad\text{and}\quad\frac1{3^{x_1}}+\frac1{3^{x_2}}+\cdots+\frac1{3^{x_{13}}}=\frac13.\]It follows that the following identities hold: \[ \frac1{2^{a_{k+1}}}=\frac1{2^{a_{k+1}+2}}+\sum_{t=2}^{13}\frac1{2^{a_{k+1}+x_t}} \quad\text{and}\quad \frac{k+1}{3^{a_{k+1}}}=\frac{k+1}{3^{a_{k+1}+2}}+\sum_{t=2}^{13}\frac{4k+t}{3^{a_{k+1}+x_t}}. \] Now suppose \((a_1,\ldots,a_{4k+1})\) is a valid solution for \(n=4k+1\). Setting \(b_{k+1}=a_{k+1}+2\), \(b_{4k+t}=a_{k+1}+x_t\), and \(b_i=a_i\) for all other \(i\), we obtain a valid solution \((b_1,\ldots,b_{4k+13})\) for \(n=4k+13\). \(\blacksquare\) The induction follows by combining the two claims.

Taking mod 2 gives that $n\equiv 0,3 \pmod{4}$ do not work. We will show that all $n\equiv 1, 2 \pmod{4}$ work. First, notice the following identities for any $i\in\mathbb{N}$: \[\frac{a}{3^k} = \frac{a}{3^{k+1}} + \frac{3a-i}{3^{k+2}} + \frac{3a+i}{3^{k+2}} \text{ and } \frac{1}{2^k} = \frac{1}{2^{k+1}} + \frac{1}{2^{k+2}} + \frac{1}{2^{k+2}}; \tag{1}\]\[\frac{a}{3^k} = \frac{a}{3^{k+1}} + \frac{2a}{3^{k+1}} \text{ and } \frac{1}{2^k} = \frac{1}{2^{k+1}} + \frac{1}{2^{k+1}}. \tag{2}\]The idea is to use these substitution rules to generate constructions inductively. Start with the base cases $n=1,5,9$, which are easy to find. In the induction step, we only focus on the numerators. For example, $\{a\} \xrightarrow{a} \{a,3a-i,3a+i\}$ denotes the substitution rule (1), and $\{a\} \xrightarrow{a} \{a,2a\}$ denotes (2). We start with the sets $\{1\}$, $\{1,2,3,4,5\}$, and $\{1,2,3,4,5,6,7,8,9\}$. The induction steps are: \[[2n+1] \xrightarrow{n+1} [2n+2];\]\[[6n+3] \xrightarrow{2n+2} [6n+3] \cup \{6n+5, 6n+7\} \xrightarrow{3n+2, 3n+3} [6n+7];\]\[[6n+1] \xrightarrow{2n+2} [6n+1] \cup \{6n+3,6n+4,6n+5,6n+7,6n+8,6n+9\} \xrightarrow{3n+1,3n+3} [6n+9];\]\begin{align*} [6n+5] &\xrightarrow{2n+5} [6n+5] \cup \{6n+13,6n+14,6n+16,6n+17\} \\ &\xrightarrow{2n+4} [6n+5] \cup \{6n+9,6n+13,6n+14,6n+15,6n+16,6n+17\} \\ &\xrightarrow{2n+3} [6n+17]. \end{align*}This generates all solutions.

Bashing = relaxation? Answer: All $n \equiv 1, 2 \pmod 4$. Notice that by taking $RHS$ modulo $2$ we must have $n \equiv 1, 2 \pmod 4$, so it suffices to prove these cases. We proceed by weak induction by $8$. Base cases: $1 = 1, 1 = \frac{1}{3}+\frac{2}{3}, 1 = \frac{1}{9}+\frac{2}{9}+\frac{3}{9}+\frac{4}{27}+\frac{5}{27}, 1 = \frac{1}{9}+\frac{2}{9}+\frac{3}{27}+\frac{4}{27}+\frac{5}{27}+\frac{6}{27}$. Now, do induct up, we split into two cases: if $n \equiv 1 \pmod 4$, we pick $k = \frac{n+3}{4}$ and split the $\frac{k}{3^a}$ term using: $$k = \frac{k}{9}+\frac{n+2}{9}+\frac{n+1}{27}+\frac{n+3}{81}+\frac{n+4}{81}+\frac{n+5}{81}+\frac{n+6}{81}+\frac{n+7}{81}+\frac{n+8}{81}$$ Similarly, if $n \equiv 2 \pmod 4$, we pick $k = \frac{n+6}{4}$ and split the $\frac{k}{3^a}$ term as follows: $$k = \frac{k}{9}+\frac{n+7}{9}+\frac{n+3}{27}+\frac{n+1}{81}+\frac{n+2}{81}+\frac{n+4}{81}+\frac{n+5}{81}+\frac{n+6}{81}+\frac{n+8}{81}$$ One may check all of these equations are true, so by induction, we finish.