Given a positive integer $n$, a collection $\mathcal{S}$ of $n-2$ unordered triples of integers in $\{1,2,\ldots,n\}$ is $n$-admissible if for each $1 \leq k \leq n - 2$ and each choice of $k$ distinct $A_1, A_2, \ldots, A_k \in \mathcal{S}$ we have $$ \left|A_1 \cup A_2 \cup \cdots A_k \right| \geq k+2.$$Is it true that for all $n > 3$ and for each $n$-admissible collection $\mathcal{S}$, there exist pairwise distinct points $P_1, \ldots , P_n$ in the plane such that the angles of the triangle $P_iP_jP_k$ are all less than $61^{\circ}$ for any triple $\{i, j, k\}$ in $\mathcal{S}$? Ivan Frolov, Russia
Problem
Source: RMM 2024 Problem 3
Tags: geometry, combinatorics, linear algebra, combinatorial geometry, RMM, Sets
29.02.2024 23:27
The answer is yes. By complex numbers, $z_1a+z_2b+z_3c=0$ forms triangles $ABC$ similar to a fixed triangle if $z_1+z_2+z_3=0$, so put some coefficients $z_i$ into a matrix $A$ such that $Ap=0$ implies the vector $p$ has the points satisfying the conditions. Treat all nonzero elements of the matrix as variables. The rank of $A$ is at most $n-2$ so the null space has dimension at least $2$. One element of the null space is $(1,1,\ldots,1)$. To show no two elements of $p$ are equal, WLOG by translation $p_{n-1}=p_n=0$ and show that $p$ cannot be part of the null space, so delete columns $n-1$ and $n$. This forms an $(n-2)\times(n-2)$ matrix $A'$ which we will show has nonzero determinant which is sufficient. Since column $n$ contained at least one $z$ variable, the other $z$ variables in that row have no conditions, so if the determinant of $A'$ is zero for all choices of $z$, the matrix formed by removing that row and column must have determinant $0$ for both choices of $z$. By Hall, there exists $n-2$ nonzero entries sharing no rows or columns. We can repeat this process over and over by picking one of the $n-2$ nonzero entries that are still remaining until we get a $1\times1$ determinant by the condition since it ensures no $k\times k$ submatrix has three nonzero entries in every row. Thus, since the null space has dimension at least $2$ and contains no element with two equal entries for some choice of $z$ variables, there exists a suitable vector $p$ containing all of the points satisfying the conditions.
01.03.2024 00:34
I wonder if this problem becomes harder (psychologically) to solve if you replace "less than 61 degrees" with "acute"
01.03.2024 00:37
IAmTheHazard wrote: I wonder if this problem becomes harder (psychologically) to solve if you replace "less than 61 degrees" with "acute" not for my solution
01.03.2024 02:59
IAmTheHazard wrote: I wonder if this problem becomes harder (psychologically) to solve if you replace "less than 61 degrees" with "acute" People have been locked up for lesser crimes.
01.03.2024 12:35
Really nice.
03.03.2024 05:49
Can we use the same method in 2022 CTST P6 to show that we can triple-colour every elements in $\{1,…,n\}$ s.t. for all $\mathcal{A}\in\mathcal{S}, \mathcal{A}$ has three elements in the same color or in different colors?I tried to apply Hall theorem but didn't work out.Anyway cool problem with linear algebra.
04.03.2024 10:35
basically same as above -- The answer is yes. We induct on $n \ge 3$. Call each integer triple in $\mathcal{S}$ a triangle. The key claim is the following: Claim. There exists a $3$-coloring of $\{1, 2, ..., n\}$ such that each triangle is either monochromatic or properly $3$-colored (i.e., its numbers have pairwise distinct colors), and that all three colors are used at least once. Proof. It suffices to solve $x_i + x_j + x_k = 0$ for each triangle $\{i, j, k\}$ in $\mathbb{F}_3^{n}$. There are $n-2$ equations and $n$ variables, so the dimension of the solution space is at least $2$. Hence we can find a solution not in $\{ c \times (1, 1, ..., 1) : c \in \mathbb{F}_3\}$. $\square$ Let $C_i$ be the set of numbers colored with color $i$. Then $\max (|C_0|, |C_1|, |C_2|) < n$. Let $S_i$ be the set of triangles whose numbers are entirely contained in $C_i$. Then by the condition we have either $|C_i| \ge \left|\cup_{A \in S_i} A \right| \ge |S_i| +2$ or $|S_i|=0$. In both cases, there is a configuration of points $\mathcal{P}_i := \{P_j : j \in C_i \}$ such that any triangle in $S_i$ has angles smaller than $61^{\circ}$. Now fix a large equilateral triangle $A_0A_1A_2$ (say, with side length $10^{10}$). We will "shrink down and translate" those configurations $\mathcal{P}_i$ so that they become sufficiently small (say, each pair of points have distance $\le 10^{-9}$) and that the distance from each point in $\mathcal{P}_i$ to $A_i$ is at most $10^{-9}$. Since each triangle is either monochromatic or properly colored, it is easy to check that this construction works. We're done.
08.03.2024 20:54
Actually, the idea is the same as in the above post, but with a bit more combinatorial approach. Consider a bipartite graph $G(A,V)$ with vertices $A:=\{A_1,A_2,\dots,A_{n-2}\}$ and $V:=\{1,2,\dots, n\}$, Connect each vertex $A_i\in A$ with the elements of the set $A_i$. We prove that the vertices in $V$ can be colored in three colors such that at lest two colors are present and the following condition holds: For each $a\in A$, the set of its neighbours $N(a)$ is either monochromatic or a rainbow (all three colors are present). Call such a coloring proper. Interpret each color as an element of $\mathbb{Z}_3$. For each coloring $f:V\to\mathbb{Z}_3$ of vertices in $V$ we assign a coloring $g:A\to \mathbb{Z}_3$ of vertices of $A$ by the formula $$g(a):=\sum_{v\in N(a)} f(v), \forall a\in A \qquad(1).$$Note that the number of all colorings $f$ of $V$ is $3^n$ and the number of colorings of $A$ are $3^{n-2}$. This means that there exists at least $9$ distinct colorings $f_0,f_1,\dots,f_8$ that are mapped, using the formula in $(1)$, to the same coloring $g$ (actually, 4 such colorings are enough). By linearity of $(1)$ we get $$0=\sum_{v\in N(a)} (f_i-f_0)(a),\forall a\in A, i=1,2,3 \qquad (2).$$Since $f_i-f_0\not\equiv 0$, at least one of these $3$ functions(colorings), say $f_1-f_0$ is not constant. But the condition $(2)$ means that the coloring $f:=f_1-f_0$ is a proper coloring and not a constant. Further, we partition the indices in $[n]$ into groups of equally colored and we place the corresponding points of the triangles near the vertices of a equilateral triangle with large enough side length. For each of these indices we apply the same procedure - proper coloring and placing them at (near) the vertices of equilateral triangle and so on till each monochromatic group consists of just 1 point. Remark. It's just an attempt to make the solution more combinatorial, though it's a pure linear algebra problem. Any attempt to make it combinatorial, makes it more difficult.