Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bureau filling

  1. Jan 29, 2009 #1
    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, [tex]A = \{a_j : j \in 1,2,..,n\}[/tex]. Each aj 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 aj and B might be countably infinite.

    Intuitively,one might think of each aj 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 si, 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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted