Tabiques que separan los triples

Question

Deje $A=\{1,2,\dots,n\}$, e $\mathcal{A}_1,\dots,\mathcal{A}_k$ ser particiones de $A$ en tres sets. Supongamos que para cada uno de los pares distintos $x,y,z\in A$ existe $1\leq i\leq k$ tal que $x,y,z$ son todos en diferentes conjuntos en la partición de $\mathcal{A}_i$. ¿Cuál es el mínimo posible de $k$?

Puesto que estamos interesados en las particiones en tres conjuntos, se podría querer escribir cada elemento de a $A$ en base a tres. Entonces podemos tener $\mathcal{A}_i$ ser la partición en tres grupos de acuerdo a si el $i$th dígito es $0,1,$ o $2$. Pero esto no es suficiente, debido a que los tres pares distintos elementos $x,y,z$ podría no tener un dígito en el que todos son distintos.

Answer 1

Un argumento de probabalistic dice que va como $\log n$. Gran $n$ allí son $\frac {n^3}6$ trillizos y una partición determinada (si las tres piezas son del mismo tamaño) cubre el $\frac {n^3}{27}$ de ellos. Si asignamos aleatoriamente la partición cubrimos $\frac 6{27}$ de los tríos, así que un trío no se cubre con oportunidad $\frac 79$ a esperar menos de un trío sin cubrir, tenemos particiones de $k$ $\frac {n^3}6\left(\frac 79\right)^k \lt 1$ o $k \gt \frac {\log \frac {n^3}6}{-\log \frac 79}\approx 3 \log n$