Is it is possible to choose 24 distinct points in the space such that no three of them lie on the same line and choose 2019 distinct planes in a way that each plane passes through at least 3 of the chosen points and each triple belongs to one of the chosen planes?
Problem
Source: Hong Kong Team Selection Test 1
Tags: combinatorics, Hong Kong, combinatorics solved, combinatorial geometry
19.08.2018 08:25
23.12.2019 07:25
Basically we want the number of planes formed to be $2019$. By finding the total number of planes and then subtracting the ones which contain four or more points (which are overcounted), we find that the total number of planes formed is ${24\choose 3}-({x_1\choose 3}-1+...+{x_k\choose 3}-1)=2019$. This would mean ${24\choose 3}-2019=5$ is the sum of a bunch of things in the form ${x\choose 3}-1$, which is impossible since ${x\choose 3}-1$ can only be $0, 3, 9, ...$.
14.06.2020 02:49
We claim the answer is no. If all of the $\binom{24}{3}$ planes were disjoint, then we would have $2024$ planes. Let $a_1, a_2, \ldots, a_k$ denote the number of points on each plane with more than $3$ points. Then the total number of planes can be found by subtracting out the double counting for each plane: \[ 2024 - \sum_{i=1}^k \left( \binom{a_i}{3} -1 \right) = 2019 \]However each of the terms in the sum can only take the values $3,9,19,\ldots$, so it is not possible.
31.05.2021 22:42
If no four points are coplanar, notice that the set of points would then define 24C3=2024 planes. Suppose that some sets of k_1,k_2...>3 points are coplanar; then, the amount of planes would be of the form 2024-\sum [(k_iC3)-1], which is obviously impossible as the sum is either equal to 3 or >6.
29.06.2022 05:57
The answer is no. We proceed with contradiction. Suppose no $4$ distinct points are coplanar. Then, we'd have $\binom{24}{3} = 2024$ distinct planes, which is absurd. Henceforth, we assume at least one of our planes contains $4$ or more points. Now, suppose we have a plane with $5$ points. Then, we'd have at most $$2024 - \left(\binom{5}{3} - 1 \right) = 2015$$distinct planes, which is also absurd. Similarly, we deduce it's impossible to have a plane with $6$ or more points. It follows that all of our distinct planes must contain $3$ or $4$ points (such that at least one of the planes has $4$ points). Now, suppose we have exactly $1$ plane with $4$ points. Then, we'd have $$2024 - \left(\binom{4}{3} - 1 \right) = 2021$$distinct planes, which is absurd. If we had $2$ or more planes with $4$ points, then we'd have at most $$2024 - 2 \left(\binom{4}{3} - 1 \right) = 2018$$distinct planes, which is also absurd. Because we have exhausted all possible cases, the proof is complete. $\blacksquare$ Remarks: I completely missed the modulo $3$ argument, so I ended up doing some unnecessary bounding (oh well). Also, Switzerland TST 2002/1 is very similar to this problem.
21.01.2023 02:28
The answer is no. As ${24 \choose 3} = 2024$, we need to delete at most 5 planes. But if four points are coplanar, we can only delete $3$ of the planes, and if five or more points are coplanar, we need to delete much more than 5 planes. Thus, this is not possible.
04.04.2023 06:48
We claim the answer is no. FTSOC assume yes. We count quadruplets $(A,B,C,\mathcal{P})$ such that $A$, $B$, $C$, are points in $\mathcal{P}$. Notice this count is equal to both $\binom{24}{3}=2024$ and \[\sum_{i=1}^{2019}\binom{|\mathcal{P}_i|}{3}\]where $|\mathcal{P}_i|$ is the number of points on plane $\mathcal{P}_i$. The latter sum is at least $2019$ and each term can only be increased by $3$, $9$ or some larger number. Hence, the latter sum cannot ever equal $2024$, so we have a contradiction. $\square$
05.04.2023 00:07
No, it is not possible. Let $a_i \ge 3$ denote the number of points on the $i$th plane. Since three noncollinear points uniquely determine a plane, we conclude that \[ \sum_{i=1}^{2019} \binom{a_i}{3} = \binom{24}{3} = 2024. \]Note that this implies $a_i < 5$ for every $i$, since otherwise we would have $\sum_{i=1}^{2019} \binom{a_i}{3} \ge 10 + 2018 \binom 33 > 2028$. Thus $a_i \in \{3,4\}$ for every $i$. However, if $k$ of the $a_i$ are equal to $4$ and the other $2019-k$ are equal to $3$, we get \[ 2024 = k \binom 43 + (2019-k) \binom 33 = 2019 + 3k \]which implies $k = 5/3$, but $k$ was supposed to be an integer. This is a contradiction.
13.05.2023 07:13
I claim that the answer is $\boxed{\text{no}}$. Assume FTSOC that it is possible to find $24$ such points and exactly $2019$ planes that satisfy the condition. Notice that if no $4$ were coplanar, we would require $\tbinom{24}{3}=2024$ planes. Therefore, we must have $\text{5}$ planes that need to be eliminated somehow. Notice how having $\emph{k}$ points coplanar means eliminating $\tbinom{k}{3}-1$ planes. This means maximum of $4$ points in the same plane; but if we have $\text{4}$ points coplanar, we eliminate $\text{3}$ planes, and $\text{5}$ isn't a multiple of $\text{3}$. So we have a contradiction, as desired. $\blacksquare$
18.10.2023 00:41
The answer is negative. Assume for the sake of contradiction that the given statement is possible. If no four of the points are coplanar, we have that there are $\binom{24}{3}=2024$, so we must remove that extra $5$. However, having $5$ points on a plane removes $9$ planes, too much, and having $4$ points on a plane removes $3$. Since $3 \nmid 5$, we have obtained a contradiction. $\square$
01.12.2023 07:38
I claim that it’s not possible. Let the 2019 planes be $p_1$, $p_2$, $\dots$, $p_{2019}$, with $p_i$ having $a_i$ points. Since every triple of three distinct points is on a plane and must be on a unique plane because every three distinct points determines a unique plane. This gives us that \[\binom{a_1}{3}+\binom{a_2}{3}+\dots+\binom{a_{2019}}{3}=\binom{24}{3}=2024.\]However, since each plane passes through at least three points, we have that $a_i\ge 3$ for all $i$. Assuming that $a_1=a_2=\dots=a_{2019}=3$, we have that \[\binom{a_1}{3}+\binom{a_2}{3}+\dots+\binom{a_{2019}}{3}=2019,\]but since we want a total of 2024, note that this implies that $2024-2019=5$ is a sum of $\binom{k}{3}-1$ values for integers $k$. However, these such values only take values of $3$, $9$, and greater, meaning that $5$ cannot be composed of a sum of $\binom{k}{3}-1$ values. Therefore it is impossible to find $24$ points satisfying the problem conditions.
26.12.2023 19:31
For each plane, consider all sets of $3$ points that it covers. Note that $\binom{24}{3}=2024$, which is $5$ off. However, when you "merge" the planes for four points into one, that gets rid of $3$, but when you merge five points, that gets rid of $9$, which is already too much, so we can't get rid of exactly $5$. $\blacksquare$
28.12.2023 07:28
The answer is no. Number the planes $1, 2, \ldots, 2019$ such that plane $i$ passes through $x_i$ planes. Then for the problem statement to be true we must have $$\sum_{i = 1}^{2019} \binom{x_i}{3} = \binom{24}{3} = 2024,$$and $x_i \ge 3$ for all $i$. Evidently, we cannot have all of the $x_i$ equal $3$. If exactly $2018$ of the $x_i$ equal $3$, then $\tbinom{x_k}{3} = 6$ for some $k$, which is impossible. If exactly $2019 - d$ of the $x_i$ equal $3$ for $d \ge 2$, then the sum of $\tbinom{x_i}{3}$ across all $i$ is at least $2019 - d + d\tbinom{4}{3} = 2019 + 3d > 2024$, so the problem statement is indeed false.
23.07.2024 18:58
If all triples lie on a different plane then we would have $\binom{24}{3}=2024$ different planes, which is clearly too many, so we need to count and subtract away the number of triples that lie on the same plane. Let $a_i$ be the number of points lying on the $i$-th plane. Then the value are are trying to count is just $$\sum_{i=1}^{2019}(\binom{a_i}{3}-1)$$, so we have $$2024-\sum_{i=1}^{2019}(\binom{a_i}{3}-1)=2019$$which means $$\sum_{i=1}^{2019}(\binom{a_i}{3}-1)=5$$but note that $\binom{a_i}{3}-1 \in \{0,3,9,\ldots\}$ which means we could only create values that are $0 \mod{3}$ when we try to keep the LHS less than $6$, which clearly doesn't include $5$.
08.08.2024 00:32
Note that if every plane had precisely $3$ points there would be $\binom{24}{3} = 2024$, call this configuration $\clubsuit$. Hence, in the $2019$ plane configuration some plane contains at least $p \ge 4$ points. Note that $p = 4$ since if $p \ge 5$ considering from $\clubsuit$ we would have reduced by at least $\binom{5}{3} - 1 = 9$ planes, and $2024 - 9 < 2019$. Now we claim another plane also contains at least $q \ge 4$ points. Suppose otherwise, then our configuration has $\binom{24}{3} - \binom{4}{3} + 1 = 2021$ points which is not $2019$. So this other plane has $q \ge 4$ points, but this implies we have at most $\binom{24}{3} - 2 \binom{4}{3} + 2 = 2018$ points. Hence, we can never have a configuration with $2019$ planes and we are done.
24.11.2024 20:14
The answer is no. Assume otherwise, and let $a_i$ be the number of points on the $i$th plane. Note that $$\dbinom{24}{3}=\sum_{i=1}^{2019} \dbinom{a_i}{3}=2024.$$If $a_i>4$ for some $i$, we would have a contradiction. Therefore, there are $k$ values $i$ so that $a_i=4$ and $2019-k$ values $i$ so that $a_i=3$. The equation becomes $$4k+2019-k=2024\implies k=\frac{5}{3},$$a contradiction.
29.11.2024 18:19
09.12.2024 03:32
The answer is no, as expected. If no four points are coplanar, then there are $\binom{24}{3}=2024$ planes, so we need to decrease this number by $5$. The only way this could happen is by moving one of the points onto the plane of some other set of points. Its clear that if this set has size exactly three, the size decreases by $3$ and if the size is four it decreases by $9$. (in general it is $\binom{n+1}{3}-1$). Therefore, this is impossible and we are done.