Given $1989$ points in the space, any three of them are not collinear. We divide these points into $30$ groups such that the numbers of points in these groups are different from each other. Consider those triangles whose vertices are points belong to three different groups among the $30$. Determine the numbers of points of each group such that the number of such triangles attains a maximum.
Problem
Source: China Mathematical Olympiad 1989 problem5
Tags: combinatorics unsolved, combinatorics
06.04.2016 18:02
This problems looks hard. Any solution to this ??
06.04.2016 19:08
So we have $30$ positive integer, $x_1,x_2,...,x_{30}$ such that $\sum_{i=1}^{30}{x_i}=1989$ And we want to find maximum value of $\sum_{1\leq i<j<k\leq 30}{x_i\cdot x_j \cdot x_k}$ Let $f(x_1,x_2,...,x_{30})=\sum_{1\leq i<j<k\leq 30}{x_i\cdot x_j \cdot x_k}$ If there exist $a.b$ such that $x_b-x_a \geq 2$ We will prove that $f(x_1,x_2,...x_a,...,x_b,...,x_{30}) \leq f(x_1,x_2,...x_a+1,...,x_b-1,...,x_{30})$ Since $f(x_1,x_2,...,x_a+1,...,x_b-1,...,x_{30}) -f(x_1,x_2,...,x_a,...,x_b,...,x_{30})=((x_a+1)(x_b-1)-x_ax_b)(\sum_{1\leq i \leq 30,i\neq a,b}{x_i}) =(x_b-x_a-1)(\sum_{1\leq i \leq 30,i\neq a,b}{x_i}) >0$ So maximum attain at for all $i,j \in \{1,2,...,30\}$, $|x_i-x_j| \leq 1$ Which mean there exist $p,q,t\in \mathbb{Z}^+$ such that $p+q=30$ and $pt+q(t+1)=1989$, give us $p=21,q=9,t=66$ So there are $21$ groups with $66$ points and $9$ groups with $67$ points
20.04.2016 06:44
ThE-dArK-lOrD wrote: So we have $30$ positive integer, $x_1,x_2,...,x_{30}$ such that $\sum_{i=1}^{30}{x_i}=1989$ And we want to find maximum value of $\sum_{1\leq i<j<k\leq 30}{x_i\cdot x_j \cdot x_k}$ Let $f(x_1,x_2,...,x_{30})=\sum_{1\leq i<j<k\leq 30}{x_i\cdot x_j \cdot x_k}$ If there exist $a.b$ such that $x_b-x_a \geq 2$ We will prove that $f(x_1,x_2,...x_a,...,x_b,...,x_{30}) \leq f(x_1,x_2,...x_a+1,...,x_b-1,...,x_{30})$ Since $f(x_1,x_2,...,x_a+1,...,x_b-1,...,x_{30}) -f(x_1,x_2,...,x_a,...,x_b,...,x_{30})=((x_a+1)(x_b-1)-x_ax_b)(\sum_{1\leq i \leq 30,i\neq a,b}{x_i}) =(x_b-x_a-1)(\sum_{1\leq i \leq 30,i\neq a,b}{x_i}) >0$ So maximum attain at for all $i,j \in \{1,2,...,30\}$, $|x_i-x_j| \leq 1$ Which mean there exist $p,q,t\in \mathbb{Z}^+$ such that $p+q=30$ and $pt+q(t+1)=1989$, give us $p=21,q=9,t=66$ So there are $21$ groups with $66$ points and $9$ groups with $67$ points But it is mentioned in the problem jred wrote: Given $1989$ points in the space, any three of them are not collinear. We divide these points into $30$ groups such that the numbers of points in these groups are different from each other . Consider those triangles whose vertices are points belong to three different groups among the $30$. Determine the numbers of points of each group such that the number of such triangles attains a maximum. So anyone with a better/complete solution?