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, [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.
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.