partitionAug 31, 2026

Challenge: matching two equal-sum partitions

idriss-bado

Member · Research discussion

Votes

Answers

Views

Challenge: matching two equal-sum partitions

Let

P=\{P_1,\ldots,P_r\}, \qquad Q=\{Q_1,\ldots,Q_s\}

be two partitions such that

S(P)=S(Q),

where

S(P)=\sum_{i=1}^{r} P_i, \qquad S(Q)=\sum_{j=1}^{s} Q_j.

The question is the following.

Can we partition the elements of $P$ and $Q$ into corresponding blocks

> P=P^{(1)}\sqcup\cdots\sqcup P^{(k)}, > \qquad > Q=Q^{(1)}\sqcup\cdots\sqcup Q^{(k)} >

such that

> \sum_{x\in P^{(i)}}x > = > \sum_{y\in Q^{(i)}}y >

for every $i=1,\ldots,k$ ?

In other words, although the two partitions have the same global sum, can this equality always be decomposed into a collection of local equal-sum correspondences?

If this is not always possible under additional restrictions, what conditions on $P$ and $Q$ guarantee such a matching?

A constructive characterization or an efficient algorithm would be particularly interesting.

Challenge: matching two equal-sum partitions

Challenge: matching two equal-sum partitions

Replies

No replies yet

Your answer