$20$ $$ $$

Bump.....

Too lazy for writing algebric expressions ! So sketch only ! 1. Consider a 3 - partite graph on ${a_i}$,${b_i}$,${c_i}$ for $i=1,2,...,n$ 2.Note that $2n\ge avg$ $deg$ 3. Find the lower bound of avg deg. in terms of $n$ [ Note here we use $\left | S \right |\ge 2018,\, \left | T \right |\ge 2018.$ ] Now solve for $n$ . Note that by this process we achieve a lower bound of $n$

bump????

solution ?

To #4: From your sketch I don’t think you could get the right answer. More technic is needed.

Bumpty Bump

lminsl wrote: Bumpty Bump It has been a year after the question has been posted. Yet, nobody has solved it. This clearly tells us the level of difficulty of the question.(Of course difficult because it is a China TST question).

It seems that CeuAzul and neel02 solved it , maybe the solution is quite long, which can discourage people to share it.

We claim that the answer is $\boxed{20}$. For construction, take $\{a_i\}, \{b_i\},\{c_i\}$ to be $7$ copies of $0.05$ and $13$ copies of $0.8$. Then $0.05\cdot 3 < 0.05\cdot 2 + 0.8 < 1 < 0.8\cdot 2 + 0.05 < 2 < 0.8\cdot 3$, hence $|S| = 7^3 + 3\cdot 7^2 \cdot 13 = 2254$ and $|T| = 13^3 = 2197$. Now suppose $n \le 19$. Suppose $\{a_i\}$ consists $x_i$ copies of the number $\alpha_i, i = 1,...,m_a$, similarly define $y_i, \beta_i,m_b$ and $z_i \gamma_i, m_c$. For each point $(\alpha_i,\beta_j,\gamma_k)$ write next to the point its weight $x_iy_jz_k$. Then $|S| = \sum_{\alpha_i + \beta_j + \gamma_k < 1} x_iy_jz_k$ and we can obtain a similar expression for $|T|$. Now we will smooth the variables $x_i,y_j,z_k$ without decreasing $|S|, |T|$. Note $S, T$ are both linear expressions in each of the weights $x_i,y_j,z_k$. Consider any three variables $x_1, x_2, x_3$ with sum $k$ and suppose $|S| = S_1x_1 + S_2x_2 + S_c (S_1,S_2, S_c \ge 0)$. Write $|T| = \sum_{i=1}^2 T_ix_i + T_c$ analogously. We keep $|S|$ fixed and consider when $|T|$ achieves maximum as we move $(x_1,x_2)$ along all possible positions. Note that $|S|-S_c = S_1x_1 + S_2x_2$ describes a line passing through some point inside the triangular region defined by $0\le x_1, x_2, x_1 + x_2 \le k$ and the set of all possible positions is its intersection with the triangular region. Since $T$ is linear, the maximum can be achieved at one of the boundary points, in which case either $x_1x_2 = 0$ or $x_1 + x_2 = k (\implies x_3 = 0)$. This way we can smooth one of any three weights to $0$. Repeating this procedure leaves us with at most $2$ weights in each of the $3$ dimensions. The bounding part is left to the interested reader.

For the lower bound, the problem boils down to the following curious question Suppose two sets $ S,T$ of 3D lattice points are given inside the lattice $ [1..n]^3$. It is known the projections of $ S$ and $ T$ on each of the planes $ Oxy, Oxz, Oyz$ do not intersect. What condition $ |S|$ and $ |T|$ should satisfy? I commented it here.

Many were curious about the official solution to this problem, so I shall put it here for archive. Indeed, the main idea is well illustrated in #12 and #13, the rest is just (rather messy) estimations and inequalities.

Attachments:
document.pdf (49kb)

Sorry for the revive but can someone tell me from where can I get the official solutions for the China TST problems???

We will show a lower bound $n\ge 18,$ which can be easily proved by Projection Inequality.

Consider $S,T$ be the set of points on a three dimension space. Then notice that $S_{xy}\cap T_{xy}=\varnothing$.Reason

Therefore $|S_{xy}|+|T_{xy}|\le n^2$, similarly $|S_{yz}|+|T_{yz}|\le n^2,|S_{zx}|+|T_{zx}|\le n^2.$ Then by Projection Inequality and Holder we have \begin{align*}2\cdot 2018^{2/3}&\le |S|^{2/3}+|T|^{2/3}\\&\le |S_{xy}|^{1/3}\cdot |S_{yz}|^{1/3}\cdot |S_{zx}|^{1/3}+|T_{xy}|^{1/3}\cdot|T_{yz}|^{1/3}\cdot |T_{zx}|^{1/3}\\&\le(|S_{xy}|+|T_{xy}||)^{1/3}(|S_{yz}|+|T_{yz}||)^{1/3}(|S_{zx}|+|T_{zx}||)^{1/3}\\ &\le n^2.\end{align*}By calculating $n\ge\sqrt 2\times\sqrt[3]{2018}>17,$ so $n\ge 18.\Box$ For the best bound, we need to define $S_k=S\cap\{z=k\},T\cap T\cap\{z=k\}=T_k,$ and use projection inequality on $S_k,T_k$. The rest is just difficult calculating.