- #1
mXSCNT
- 310
- 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, A = \{a_j : j \in 1,2,..,n\}. Each aj 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 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
B = \{\prod_{j=1}^n s_{ij} : \forall j, s_{ij} \in a_j\}.
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 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.
Suppose we have a set, A = \{a_j : j \in 1,2,..,n\}. Each aj 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 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
B = \{\prod_{j=1}^n s_{ij} : \forall j, s_{ij} \in a_j\}.
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 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.
