Partitions that separate all triples Let $A=\{1,2,\dots,n\}$, and $\mathcal{A}_1,\dots,\mathcal{A}_k$ be partitions of $A$ into three sets. Suppose that for each pairwise distinct $x,y,z\in A$, there exists $1\leq i\leq k$ such that $x,y,z$ are all in different sets in the partition $\mathcal{A}_i$. What is the minimum possible $k$?
Since we are interested in partitions into three sets, we might want to write each element of $A$ in base three. Then we can have $\mathcal{A}_i$ be the partition into three sets according to whether the $i$th digit is $0,1,$ or $2$. But this is not enough, because three pairwise distinct elements $x,y,z$ might not have a digit in which they are all distinct.
 A: A probabalistic argument claims it goes as $\log n$.  For large $n$  there are $\frac {n^3}6$ triplets and a given partition (if the three pieces are the same size) covers $\frac {n^3}{27}$ of them.  If we randomly assign the partition we cover $\frac 6{27}$ of the triplets, so a triplet is not covered with chance $\frac 79$  To expect less than one triplet uncovered, we need $k$ partitions with $\frac {n^3}6\left(\frac 79\right)^k \lt 1$ or $k \gt \frac {\log \frac {n^3}6}{-\log \frac 79}\approx 3 \log n$
A: Here is a deterministic algorithm to achieve $O(\log n)$. 
We will build the solution adding partitions one at a time. Say currently we have the partitions $P_1, P_2, \ldots, P_r$. Call a triplet $(x, y, z) $ satisfied if there exists a partition $P_i$ in which $x, y, z$ belong to different sets. Say we currently have $T$ unsatisfied triplets. We'll prove that there exists a deterministic way to find a partition $P_{r + 1}$ which splits atleast $\frac{T}{8}$ of these unsatisfied triplets.
First, we create a bipartition $(U, V)$ such that atleast $\frac{T}{4}$ of the unsatisfied triplets have exactly one element in $U$. To do this, add elements one by one in arbitrary order. When adding $x$, add it to the side which has lesser number of pairs $(y, z)$ such that both $y$ and $z$ have been processed and $(x, y, z)$ is an unsatisfied triple, breaking ties arbitrarily.
Note that, from the added vertices, we will always have lesser unsatisfied triplets with all elements on the same side than those not having all elements on the same side. So, in the end we have atleast $\frac{T}{2}$ unsatisfied triplets which have exactly one element in $U$ and exactly two elements in $V$ or vice-versa.
WLOG, we can assume that $E \geq \frac{T}{4} $ triplets have exactly one element in $U$ and two in $V$. Consider a multigraph $G$ with the vertex set $V$. For each unsatisfied triplet $(x, y, z)$ with $x \in U$ and $y, z \in V$, add an edge $(y, z)$ to $G$. We have $E \geq \frac{T}{4}$ edges in $G$. Find a cut in $G$ using a similar greedy algorithm, adding vertices one by one to the side having lesser neighbors. This cut (say $(V_1, V_2)$) has $\geq \frac{E}{2} \geq \frac{T}{8} $ edges.
Clearly, after adding the partition {$U, V_1, V_2$}, we have $\leq \frac{7T}{8}$ unsatisfied triplets left. We continue till all triplets are satisfied. Clearly, this uses $O(\log n)$ partitions.
A: This is a low-$n$ analysis but is too long for a comment:
Let $k(n)$ be the minimum number of partitions of $\{1\cdots n\}$ such that there exists a set of partitions $S_n \{A_1, \ldots , A_k\}$ that splits every triplet of $\{1\cdots n\}$.
Clearly $k(3) = 1$ and $k(4) = 2$. The latter can be proven by noting that any 3-partition of four numbers must have two numbers in the same box, so $k(4)>1$, and an example of a two element set that covers all the triplets among  $\{1\cdots 4\}$ is
$$
S_4 = \left\{ \matrix{(1|2|34) \\ (12|3|4)}\right\}
$$
This trival proof is presented because it provides a pattern for one way to determine $k(n)$.
Clearly if $m<n$ then $k(m)\leq k(n)$. So our next two cases can be handled together. 
$k(5) > 2$ since a partition of $5$ numbers can cover at most $4$ triplets, and there are $\binom{5}{3}=10$ triplets to be covered. Yet $k(6) \leq 3$ because the following example covers all the triplets among $\{1\cdots 6\}$:
$$
S_6 = \left\{ \matrix{(12|34|56) \\ (23|45|61)\\ (14|25|36)}\right\}
$$
Therefore $k(6) = 3$ and $k(5) = 3$ (a valid $S_5$ may be obtained simply by omitting all instances of the number $6$ from $S_6$).
It turns out that all valid $S_6$ sets of partitions can be obtained from the one presented, by permutations of the numbers $\{1\cdots 6\}$; in that sense, the answer for $n=6$ is unique.
$k(7)$ is more difficult but still tractable.  First, although a partition of 
$\{1\cdots 7\}$ can cover (that is, split up) twelve triplets (if the partition groups one group of three and two groups of two numbers), ad $3\times 12 = 36 > \binom{7}{3} = 35$, nonetheless $k(7) > 3$.  Proof:
If you have $S_7$ and eliminate all instances of the number $7$, you are left with a valid partitioning of six numbers, which we just saw must (up to permutations) be the $S_6$ presented above.  But then when you add $7$ back into the mix, it will be in a box of three numbers, thus forming a triplet which will neet to be covered elsewhere.  Without loss of generality, we might place $7$ with $12$ in $A_1$, then  $7$ must either share a box with $45$ in $A_2$, or share a box with $36$ in $A_3$ (or both).
If $7$ shares a box with $45$ then since you need to split $(7,2,3)$ the $7$ must share the box with $14$ in $A_3$; but then $(1,4,7)$ is unsplit. 
If $7$ shares a box with $35$ then since you need to split $(7,1,4)$ the $7$ must share the box with $23$ in $A_2$; but then $(2,3,7)$ is unsplit.  Therefore, $k(7) > 3$.
Then $k(7) = 4$; here is an example $S_7$:
$$
S_7 = \left\{ \matrix{(123|45|67) \\ (124|36|57) \\ (246|17|35)\\ (135|467|2) }\right\}
$$
This is beginning to remind me of Ramsey theory. I would now be very surprised if $k(n)$ can be shown to grow logarithmically with $n$, but sub-linear growth is not out of the question.
