Uniqueness of the permutations

combinatoricscomputer sciencepermutationsreference-request

Consider two sets of real numbers
$$
\mathcal{A}\equiv \{a_1,a_2,a_3,a_4,a_5,a_6\}\\
\mathcal{B}\equiv \{b_1,b_2,b_3,b_4,b_5,b_6\}\\
\mathcal{C}\equiv \{c_1,c_2,c_3,c_4,c_5,c_6\}\\
$$

where $c_j\equiv a_j+b_j$ for $j=1,…,6$.

Assume that:

(A.1) $c_1>c_2>…>c_6$. $c_j\in [0,1]$ for each $j=1,…,6$. $\sum_{j=1}^6 c_j=1$.

(A.2) I know the numbers contained in the set $\mathcal{A}$ but I don't know which of these numbers is $a_1$, which is $a_2$, …, which is $a_6$. These numbers are all in $[0,1]$.

(A.3) I know the numbers contained in the set $\mathcal{B}$ but I don't know which of these numbers is $b_1$, which is $b_2$, …, which is $b_6$. These numbers are all in $[0,1]$.

I want to compute $c_1,\dots, c_6$.


Computing $c_1,\dots, c_6$ is not possible under A.1,A.2,A.3 because the maximum of the sum if less or equal (and it is not necessarily equal) to the sum of the maxima.

A sufficient (and, perhaps, necessary?) condition for computing $c_1,\dots, c_6$ is the following:

(A.4) Let $d,e,f,g,h,j$ be the numbers contained in $\mathcal{A}$ that are known under A.2. Let $k,l,m,n,o,p$ be the numbers contained in $\mathcal{B}$ that are known under A.3. There exists only one way of ordering $d,e,f,g,h,j$ (and I denote by $r_1,…,r_6$ the ordered numbers) and only one way of ordering $k,l,m,n,o,p$ (and I denote by $y_1,…,y_6$ the ordered numbers) such that
$$
r_1+y_1>r_2+y_2>r_3+y_3>r_4+y_4>r_5+y_5>r_6+y_6
$$


Question:

  • Is A.4 necessary to compute $c_1,…,c_6$, or can you think of other less restrictive assumptions that can allow me to compute $c_1,…,c_6$?

  • Is there any "technical" name in algebra for A.4? Like, an ordering assumption? A labelling assumption? Or, is there any well known algorithm in computer science that resembles (or checks) A.4?

Best Answer

I think that A.4 is not necessary to compute $c_1,...,c_6$.

If $$ \mathcal{A}=\{0.15,0.15,0.05,0.05,0.05,0.02\}\\ \mathcal{B}=\{0.15,0.15,0.11,0.05,0.05,0.02\}$$ then $$c_1=0.3,c_2=0.2,c_3=0.17,c_4=0.16,c_5=0.1,c_6=0.07$$ where $$\begin{cases}a_1=0.15,a_2=0.05,a_3=0.15,a_4=0.05,a_5=0.05,a_6=0.02, \\\\b_1=0.15,b_2=0.15,b_3=0.02,b_4=0.11,b_5=0.05,b_6=0.05\end{cases}$$ or $$\begin{cases}a_1=0.15,a_2=0.15,a_3=0.02,a_4=0.05,a_5=0.05,a_6=0.05, \\\\b_1=0.15,b_2=0.05,b_3=0.15,b_4=0.11,b_5=0.05,b_6=0.02\end{cases}$$

Proof :

If we fix the order of the elements of $\mathcal{B}$ as $(0.15,0.15,0.11,0.02,0.05,0.05)$, then the only possibilities for the order of the elements of $\mathcal{A}$ to consider are

  • $(0.15,0.05,0.05,0.02,0.15,0.05)$ for which $0.2$ appears more than once as a sum.

  • $(0.15,0.05,0.02,0.05,0.15,0.05)$ for which $0.2$ appears more than once as a sum.

  • $(0.15,0.05,0.05,0.05,0.15,0.02)$ for which $0.2$ appears more than once as a sum.

  • $(0.15,0.02,0.05,0.05,0.15,0.05)$ works.

  • $(0.15,0.05,0.05,0.15,0.05,0.02)$ works.

  • $(0.15,0.05,0.15,0.05,0.05,0.02)$ for which $0.07$ appears more than once as a sum.

  • $(0.05,0.02,0.05,0.15,0.15,0.05)$ for which $0.2$ appears more than once as a sum.

  • $(0.05,0.02,0.15,0.05,0.15,0.05)$ for which $0.2$ appears more than once as a sum.

Related Question