Coin change problem Given a set of coins $S = \{w^0, w^1, w^2, ....., w^n\}$, for a given $w$, how to test whether an amount $X$ can be changed for i.e. find such subsets $S1, S2$ such that $$\sum_{c \in S1} c + X = \sum_{c \in S2} c$$ $S1, S2 \subseteq S$ and $S1 \cap S2 = \emptyset$ i.e. each coin can be used at most once.
Both $n$ and $w$ can be as large as $1$ billion.
I can only think of a brute force solution. For each coin, there are three cases either it is not used or it is on the left side of equation else it is on the right side of equation. 
Rather, I need an insightful mathematical concept to apply here.  
Here are a couple of points I want myself clarified about(so please, try to enlighten me on all these points :D):


*

*The solution from the site I obtained this problem uses representing $X$ in base $w$ and after that I don't know what is done. (How)

*If $X \le w^k$, where $w^k$ is the smallest such coin, then all coins $w^{k + 2}, w^{k + 3}, ...w^{n}$ need not be considered. (How to prove this?).

*Often I make assertions while solving problems that sound logical, but
when I try to prove it mathematically, I get stuck. So, what should I do in such situation(I am in such situation with the proof of point 2)?
Right now what I am thinking about point 2 is this "To prove assertion 2, I need to prove that $w^{k+2}$ is not used in all of the valid solutions which means, $w^{k+2}$ doesn't occur either on the left or right side of the equation shown at the top. Now, if I could somehow prove that using $w^{k+2}$ in left side or right side, I cannot arrive at a solution I would be complete with my proof. I will first put $w^{k+2}$ in the left (along with $X$) and see. I have $X + w^{k+2}$ on the left, I also know that $X \le w^k$. I can't work any further.
Thank you.!!
 A: The amounts of change that can be made are the numbers of the form
$$\sum_{k=0}^n\epsilon_kw^k\;,\tag{1}$$
where each $\epsilon_k\in\{-1,0,1\}$, and if $\ell=\max\{k:\epsilon_k\ne 0\}$, then $\epsilon_\ell=1$. Equivalently they are the non-negative integers that can be expressed with at most $n+1$ digits, each of which is $-1,0$, or $1$, in a modified base $w$ notation that uses the digits $-1,0,1,2,\ldots,w-2$ instead of the usual $0,1,2,\ldots,w-1$. The usual algorithm for changing base, involving repeated division by $w$, still works, provided that one handles remainders of $w-1$ correctly. Perhaps the easiest way to explain is by an example.
Let $w=4$. If I want to convert $27$ to base $w$ in the usual way, I use the following algorithm:

Divide $27$ by $4$ to get a quotient of $6$ and a remainder of $3$. Replace $27$ by the quotient $6$ and repeat; you get a quotient of $1$ and a remainder of $2$. Replace the $6$ by the new quotient of $1$ and repeat; you get a quotient of $0$ and a remainder of $1$. Read off the remainders in reverse order to get $123$; this is the ordinary base four representation of $27$. 
As a check, $1\cdot4^2+2\cdot4+3=16+8+3=27$.

To convert to the modified base four notation, you have to replace remainders of $3$ by remainders of $-1$, which of course requires increasing the quotient by $1$. This time the steps are:

$$\begin{align*}
28&=4\cdot 6+3=4\cdot 7-1\\
7&=4\cdot 1+3=4\cdot 2-1\\
2&=4\cdot 0+2\;,
\end{align*}$$ so $28=2\cdot 4^2-1\cdot 4-1$. Using $\bar1$ to represent $-1$, we can write this $2\bar1\bar1$.

Since this modified base four representation of $27$ uses the digit $2$, $27$ is not an amount of change that can be made when $w=4$. $61$, however, can be made, provided that $n\ge 3$:

$$\begin{align*}
61&=4\cdot 15+1\\
15&=4\cdot 3+3=4\cdot 4-1\\
4&=4\cdot 1+0\\
1&=4\cdot 0+1\;,
\end{align*}$$ so $61$ is $10\bar11$, a representation that uses only $\bar 1,0$, and $1$.

Indeed, $61=(4^3+4^0)-4^1$.
Added: Note that the smallest amount $n$ that uses the coin $w^{k+2}$ is the number with the modified base $w$ representation
$$1\underbrace{\bar1\bar1\ldots\bar1\bar1}_{k+2}\;,$$
so
$$n=w^{k+2}-\sum_{i=0}^{k+1}w^i=w^{k+2}-\frac{w^{k+2}-1}{w-1}=\frac{w^{k+3}-2w^{k+2}+1}{w-1}\;.$$
If $w\ge 3$, then $w^{k+3}-2w^{k+2}+1>w^{k+2}(w-2)\ge w^{k+2}>w^{k+1}>w^k(w-1)$, and $n>w^k$. Thus, if $n\le w^k$, we won’t need the $w^{k+2}$ coin (or of course any larger coin). In fact, the calculation shows that we won’t even need the $w^{k+1}$ coin.
If $w=2$ none of the foregoing analysis is necessary, since every integer from $0$ through $2^{n+1}-1$ has a binary representation of length at $n+1$ and can be written as a sum of powers of $2$, the largest of which is at most $2^n$. In that case it’s still true that if $n\le 2^k$, the $2^k$ coin is the largest that we might need: the binary representation of $n$ will certainly not use any power of $2$ greater than $2^k$, and it will use $2^k$ only if $n$ is actually equal to $2^k$.
