Solving the Multiset Filling Problem

[mXSCNT]

This is closely related to the problem posed in https://www.physicsforums.com/showthread.php?t=287947, but stated in simpler, non-probabilistic terms.

Suppose we have a set, $$A = \{a_j : j \in 1,2,..,n\}$$. Each a_j is a multiset (meaning repetitions are allowed) of positive real numbers, where $$\sum_{y \in a_j} y = 1$$. We want to find a multiset B of positive real numbers, such that for each j, there is a surjective function $$f_j : B \rightarrow a_j$$ such that

$$\forall y \in a_j, y = \sum_{x \in f_j^{-1}(y)} x$$.

Additionally we would like to minimize |B|.

Also of interest is the generalization of the problem to the case when the a_j and B might be countably infinite.

Intuitively,one might think of each a_j as a bureau with drawers of varying size, and we seek a collection of varying-size bricks B that will fill any bureau exactly.

One possible solution for the finite case (which does not necessarily minimize |B|) is to let
$$B = \{\prod_{j=1}^n s_{ij} : \forall j, s_{ij} \in a_j\}$$.
What I mean by that notation is, for each sequence s_i, there is an element of B; since B is a multiset the same product may appear more than once.

Then, for each $$x_i = \prod_j s_{ij} \in B$$, we can let let $$f_j(x_i) = s_{ij}$$. Thus, since $$y \in a_j$$ is some $$s_{ij}$$,

$$\sum_{x_i \in f_j^{-1}(s_{ij})} x_i = s_{ij} \sum_i (\prod_{k \neq j} s_{ik}) = s_{ij} = y$$.

As an example, let A = {{0.6,0.4},{0.5,0.5}}. Then with the above solution, B = {0.3, 0.3, 0.2, 0.2}, and 0.6 = 0.3 + 0.3, 0.4 = 0.2 + 0.2, 0.5 = 0.3 + 0.2, 0.5 = 0.3 + 0.2.

As an example of where the above solution does NOT produce a minimal |B|, let A = {{0.5, 0.5},{0.5, 0.5}}. Then the above solution gives B = {0.25, 0.25, 0.25, 0.25}, which works, but B = {0.5, 0.5} works and is smaller.

$$|B| = \prod_j |a_j|$$ by the above method. In the special case when the elements of each $$a_j$$ are all the same, it is possible to find a B where $$|B| = lcm(a_1, a_2, ..., a_n)$$ (as I did in the preceding paragraph). I believe that it is never possible to find a B where $$|B| < lcm(a_1, a_2, ..., a_n)$$, no matter what A is.

 

[fresh_42]

I cannot see why any requirement should prevent me from calling $A=B$ a solution.