probability group students to maximize expectation Given $3n$ people that the $i^{\text{th}}$ person can pass a test with probability $p_i$, now you are required to divide them to $n$ groups that each group has $3$ people. The score of one group equals $1$ if at least two people pass the test, $0$ otherwise. In order to maximize the expectation of total score, how do you group them?
I've thought about this problem for a bit, and I think intuitively it makes sense to group two large $p_i$ with a small $p_i$. Also, I've thought about in the optimal arrangement, swapping any two $p_i$ from different groups should lower the expectation. I can write out mathematically the difference in expectation when swapping two of the students, but it doesn't seem to give any obvious result. I've hit a wall.
 A: You can solve the problem via integer linear programming by using the following set partitioning formulation.  Let $S=\{1,\dots,3n\}$ be the set of students, and let $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$ be the set of triples of students. For $(i,j,k)\in T$, let binary decision variable $x_{i,j,k}$ indicate whether triple $(i,j,k)$ is assigned to a group.  If $x_{i,j,k}=1$, the pass probability for that group is
\begin{align}
P_{i,j,k}&:=p_i p_j p_k+(1-p_i) p_j p_k+p_i (1-p_j) p_k+p_i p_j (1-p_k)\\
&=p_i p_j + p_i p_k + p_j p_k - 2 p_i p_j p_k.
\end{align}
The problem is to maximize
$$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$
subject to
\begin{align}
\sum_{(i,j,k)\in T:\\ s\in\{i,j,k\}} x_{i,j,k} &= 1 &&\text{for $s\in S$} \tag2
\end{align}
The objective function $(1)$ is the expected total score. Constraint $(2)$ assigns each student to exactly one group.
Numerical experimentation for small $n$ and uniformly distributed $p_i$ confirms your intuition of two large and one small probability per group.  In fact, the smallest probability appears with the two largest, the next smallest with the next two largest, and so on.  For example, if the students are relabeled in increasing order of $p_i$ (without loss of generality), then $n=6$ yields groups $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$
Update: here is a small counterexample with $n=2$.  Take $p=(0,0,0.1,0.6,0.8,0.8)$.  Then groups $\{\{1,2,3\},\{4,5,6\}\}$ yield an expected score of $0.832$, while groups $\{\{1,5,6\},\{2,3,4\}\}$ yield a smaller expected score of $0.7$.
A: Here's a way to simplify the problem. Let $p_i = x_i + 1/2$. Then we wish to maximise  the expression
\begin{align*}
&\sum_{(i,j,k)\in T}p_ip_jp_k+(1-p_i)p_jp_k+p_i(1-p_j)p_k+p_ip_j(1-p_k)\\
=&\sum_{(i,j,k)\in T}\frac12+\frac12(x_i+x_j+x_k)-2x_ix_jx_k\\
=&N/2 +\frac12\sum_{i<3N}x_i-2\sum_{(i,j,k)\in T}x_ix_jx_k \end{align*}
in which only the last term depends on the partition $T$. So we have simplified the problem to finding the $T$ which minimizes the sum of the products of the $x$s in each group of three.
$$\sum_{(i,j,k)\in T}x_ix_jx_k$$
