# Partitioning tuples

Given are tuples $$(a_{11},\dots,a_{1k}), (a_{21},\dots,a_{2k}), \dots, (a_{n1},\dots,a_{nk})$$. We want to know if there is a partition of the tuples into two parts, so that for every coordinate $$i=1,\dots,k$$, the sum of each part is equal to the sum of the other part.

Has this problem been studied before? If $$k=1$$, it is of course the famous Partition problem. But I cannot find this generalization under the section "Variants and generalizations" in the Wikipedia page.

## 1 Answer

This is essentially the same problem as partition. Let $$M$$ be a large enough integer, and replace each tuple $$(a_{i1},\ldots,a_{ik})$$ with the single integer $$\sum_j a_{ij} M^j$$. You now have an equivalent instance of PARTITION.

Your problem appears in the literature, under the name multidimensional two-way number partitioning, in Jelena Kojić, Integer linear programming model for multidimensional two-way number partitioning problem.