Official

A - Ternary Decomposition Editorial by evima


For a given \(N\), let’s consider the values of \(K\) for which a solution can be constructed.

First, the sum of the digits when \(N\) is represented in ternary notation is the minimum value of such \(K\) (let’s denote it as \(L\)). For example, if \(N=11\), then \(L=3\), and \(11\) can be expressed as \(11=3^2+3^0+3^0\).

Next, consider increasing \(K\) from this state. If you choose one term (let’s denote it as \(3^m\)) such that \(m>0\) and divide it into three \(3^{m-1}\), you can increase the number of terms by \(2\). In the previous example, you can make \(11=3^1+3^1+3^1+3^0+3^0\). This operation is possible until all terms become \(3^0=1\), that is, until \(K=N\).

Therefore, for a \(K\) that is between \(L\) and \(N\) and has the same parity as \(N\) (or \(L\)), it is possible to express it in a desired way. Also, since \(3^m\) is odd, it is impossible if the parity does not match.

(Modified the first draft written by GPT-4.)

posted:
last update: