- #1

mXSCNT

- 315

- 1

Suppose we have a set, [tex]A = \{a_j : j \in 1,2,..,n\}[/tex]. Each a

_{j}is a multiset (meaning repetitions are allowed) of positive real numbers, where [tex]\sum_{y \in a_j} y = 1[/tex]. We want to find a multiset B of positive real numbers, such that for each j, there is a surjective function [tex]f_j : B \rightarrow a_j[/tex] such that

[tex]\forall y \in a_j, y = \sum_{x \in f_j^{-1}(y)} x[/tex].

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

[tex]B = \{\prod_{j=1}^n s_{ij} : \forall j, s_{ij} \in a_j\}[/tex].

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 [tex]x_i = \prod_j s_{ij} \in B[/tex], we can let let [tex]f_j(x_i) = s_{ij}[/tex]. Thus, since [tex]y \in a_j[/tex] is some [tex]s_{ij}[/tex],

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

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.

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