This is closely related to the problem posed in https://www.physicsforums.com/showthread.php?t=287947, but stated in simpler, non-probabilistic terms.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Bureau filling

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**