Minimize the absolute difference of the sum of two dijoint sets in which terms are in the powers of $p$.

Question

Given $n(n>=1)$ integers $k_1,k_2 \cdots k_n(k_i>=0)$, and an integer $p>=1$, Johny picks $p^{k_i}$ from $i-th$ category for each category , and he wants to divide them into two disjoint sets, minimizing the absolute difference between sums of numbers in each set.

let's sort the k array in non decreasing order.

Suppose if $\sum_{i=1}^{n−1}p^{k_i}<p^{k_n}$ then we put $p^{k_n}$ in one set and the remaining powers in other set and compute the powers and their difference.

Now if $\sum_{i=1}^{n−1}p^{k_i}>=p^{k_n}$ ,How do I prove that there exists $j$ such that $\sum_{i=j}^{n−1}p^{k_i}=p^{k_n}$,so that we could put $p^{k_n}$ in one set and $\sum_{i=j}^{n−1}p^{k_i}$ in other set to make their absolute difference $0$ and go on to index $j−1$ and repeat the process?

Answer 1

Suppose that

\begin{equation}\sum _{i = j+1}^{n-1} {p}^{{k}_{i}} < {p}^{{k}_{n}} \leqslant \sum _{i = j}^{n-1} {p}^{{k}_{i}}\end{equation}

then dividing by $ {p}^{{k}_{j}}$, we get

\begin{equation}S := \sum _{i = j+1}^{n-1} {p}^{{k}_{i}-{k}_{j}} < {p}^{{k}_{n}-{k}_{j}} \leqslant 1+\sum _{i = j+1}^{n} {p}^{{k}_{i}-{k}_{j}} = 1+S\end{equation}

Since all quantities are integers, it follows that

\begin{equation}{p}^{{k}_{n}-{k}_{j}} = 1+S\end{equation}

hence

\begin{equation}{p}^{{k}_{n}} = \sum _{i = j}^{n-1} {p}^{{k}_{i}}\end{equation}