There are $44$ distinct holes in a line and $2017$ ants. Each ant comes out of a hole and crawls along the line with a constant speed into another hole, then comes in. Let $T$ be the set of moments for which the ant comes in or out of the holes. Given that $|T|\leq 45$ and the speeds of the ants are distinct. Prove that there exists two ants that don't collide.
Problem
Source: Vietnam TST 2017
Tags: combinatorics
guangzhou-2015
27.03.2017 08:02
I can't solve it. But i think this is a perfect problem
talkon
27.03.2017 08:09
First, I believe that two ants coming out of one hole at the same time doesn't count as a collision (else all ants can come out at the same time from a hole and they'll all collide) There are a total of at most $44\times 45 = 1980$ possible pairs of (moments, holes) - but there are $2017$ ants, so two ants must come out of the same hole at the same time. As their speed are distinct, they will not collide.
Lam.DL.01
13.08.2017 19:00
Here is my solution during the test . Denote (t_i, v_i ) be the the time and the speed of the ant i We have a graph G , which have 44.45 edges and 2017 vertices . We must prove that there is 2 edges that don't cut each another. I think it's clear now
Mikefuryccdy
14.08.2017 05:44
talkon wrote: First, I believe that two ants coming out of one hole at the same time doesn't count as a collision (else all ants can come out at the same time from a hole and they'll all collide) There are a total of at most $44\times 45 = 1980$ possible pairs of (moments, holes) - but there are $2017$ ants, so two ants must come out of the same hole at the same time. As their speed are distinct, they will not collide. Sr. I have the full one. And it said that two ants coming from the same hole at the same time are considered to be collide
Lam.DL.01
14.08.2017 11:17
Mikefuryccdy wrote: talkon wrote: First, I believe that two ants coming out of one hole at the same time doesn't count as a collision (else all ants can come out at the same time from a hole and they'll all collide) There are a total of at most $44\times 45 = 1980$ possible pairs of (moments, holes) - but there are $2017$ ants, so two ants must come out of the same hole at the same time. As their speed are distinct, they will not collide. Sr. I have the full one. And it said that two ants coming from the same hole at the same time are considered to be collide It's not the solution from Ministry of Education in fact
alexiaslexia
09.12.2020 09:51
Again, might look really cute, when the statement in the Claim might throw you out for ages. Very similar to official solution but posting anyway since the statement and the Claim is very nice (and the process behind it is worth sharing.) $\color{green} \rule{25cm}{3pt}$ $\textcolor{green}{\textbf{\text{LINEAR ROUTES!}}}$ First we throw the ants on to a 2-D cartesian plane, with the $x$-axis representing distance and $y$-axis representing time. To be exact, say that the ant's position $p$ in the initial line in time $t$ be $(x,y) = (p,t)$. Then, since the speed of the ant(s) is constant, the routes of the $2017$ ants form line segments, as with a shift of time, the ant's distance will move proportionally according to its speed (a.k.a. the gradient). Each ant will do so until it reaches the other endpoint of its line segment where it stops moving, and enter to its hole of destination. $\blacksquare$ $\color{green} \rule{25cm}{0.5pt}$ $\textcolor{red}{\textbf{\text{Finishing --- yet after Claim is established.}}}$ In the linear board we just established, since there are $45$ holes the ants can come out from, and $44$ moments ants can choose to exit their holes from, there are $1980$ possible endpoints of the ants' line segments. If we have proven that for every $n$ points and $n+1$ segments with those points as endpoints there must be $2$ non-coliding (non-inter-cutting) segments, then we are done. $\color{red}\rule{25cm}{0.5pt}$ $\textcolor{magenta}{\textbf{\text{The Claim.}}}$ Basically $\textcolor{red}{\textbf{\text{Finishing}}}$'s last sentence. $\textcolor{magenta}{\textbf{\text{The Proof.}}}$ We will prove the maximal of pairwise intersecting segments is $n$. Consider a segment $s$ which has $v_1$ and $v_2$ as its endpoints, and consider the two half-planes $\mathcal{H}_1$ and $\mathcal{H}_2$ which is formed by the line $\overline{v_1v_2}$.
Now, if either $v_1$ or $v_2$ is connected to no other segment rather than $s$, we can remove that vertex and obtain a $"\text{graph}"$ (a.k.a. configuration) with $1$ less vertex and $1$ less edge, and we can easily proceed with induction. On the other hand, if some segment connected to $v_1$ (which, of course, does not pass through $v_2$, otherwise their gradient would overlap, contrary to the statment that ants' speed must be different) lies on half-plane $\mathcal{H}_1$ but a segment connected to $v_2$ lies on half-plane $\mathcal{H}_2$ then they do not collide, a contradiction. Then, all segments different from $s$ adjacent to $v_1$ or $v_2$ must lie in one of the half-planes, WLOG $\mathcal{H}_2$. However, if say $v_1$ has degree $3$ or more, then consider one of the $"\text{middle}"$ segments (to be more rigorous, the segment which doesn't form the biggest angle w.r.t. $s$) connected to $v_1$. For the sake of notation name the middle segment $m$ and the biggest-angle segment $b$. Then $m$'s endpoint, say $v$, must have degree $1$ (if it has more than one, it has to choose half-plane, between cutting $s$ and non-coliding $b$ or cutting $b$ and non-colliding $s$.) Then we can remove said middle segment and said vertex $v$ to obtain a configuration with $1$ less vertex and $1$ less edge. So, each vertex has degree $2$ (since it can't be $1$ or $\geq 3$ for any vertex). Then the total number of edges is exactly $n$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
S1 (2.5 + 2.5 = 5 points). Soft tech 1 (Velocity = Linear) + Hard Tech finalization ("Algebra"): Realizing that the path is behaving linearly, and following up accordingly to Cartesian. First, I decided to project the time in $"\text{another dimension}"$, as when I considered the relative position of an ant which has holes, say $h_1$ out to $h_2$ and (starting time, end time) = $(t_1,t_2)$ its position is representable as
\[ \bigg(t, \dfrac{t_2-t}{t-t_1} \cdot (h_2-h_1) + h_1 \bigg)
\]uncannily similar to the standard linear equation (in a modified form, of course.) Then, I discovered that their position is untrackable in $t \leq t_1$ and $t \geq t_2$ (i.e. before and after they exit their holes), so it's reasonable to expect that their graph is kind-of-bounded; all the more inviting to sketch arbitrary bounded collision as a $"\text{graph}"$ with intersections. $\textcolor{green}{\text{ End of section 1.}}$
The problem lies in deciding what to consider when we have a strange condition $"\textbf{any two segments intersect}"$. If two segments have the same endpoints are considered to $"\text{intersect}"$ then any vertex must have degree at most $1$, counterintuitive to the problem statement which "wants us" to relate $2017$ to $1980$. Thus began my journey to play with $n+1$ segments and $n$ vertices.
S2 (10 points). Soft Tech 2 (General scouting): Looking at connected components and substructures of graphs, and try to find ways to categorize intersections. Then I stumbled upon my lead, as I discovered first configuration
[asy][asy]usepackage("tikz");
label("\begin{tikzpicture}[scale=0.8]
\draw[orange](0,0)--(4,3); \draw[orange](0,0)--(5.5,3); \draw[orange](0,0)--(7,3); \draw[orange](0,0)--(4,4.5); \draw[orange](0,0)--(5.5,4.5); \draw[orange](0,0)--(7,4.5);
\draw[red,very thick](0,3)--(4,0); \draw[orange](0,3)--(5.5,0); \draw[orange](0,3)--(7,0); \draw[orange](0,4.5)--(4,0); \draw[green,very thick,dashed](0,4.5)--(5.5,0); \draw[fill=gray,thick,->](-1,-0.7)--(7.2,-0.7); \draw[fill=gray,thick,->](-0.7,-1)--(-0.7,5);
\node[font=\footnotesize]at(3.5,-1.4) {max edge $\approx$ $n-$constant;}; \node[font=\footnotesize]at(3.5,-1.8){here, constant=$2$};
\draw[fill=orange](0,0)circle(2pt); \draw[fill=orange](4,0)circle(2pt); \draw[fill=orange](5.5,0)circle(2pt); \draw[fill=orange](7,0)circle(2pt); \draw[fill=orange](0,3)circle(2pt); \draw[fill=orange](4,3)circle(2pt); \draw[fill=orange](5.5,3)circle(2pt); \draw[fill=orange](7,3)circle(2pt); \draw[fill=orange](0,4.5)circle(2pt); \draw[fill=orange](4,4.5)circle(2pt); \draw[fill=orange](5.5,4.5)circle(2pt); \draw[fill=orange](7,4.5)circle(2pt);
\end{tikzpicture}");[/asy][/asy]
which, at first glance, must consist of only $"\text{trees}"$ (and two connected components) as any addition of an edge will create a cycle which I consider to be catastrophic (and would solve the problem.) However, I really did not see a significance of $"\text{connected components}"$ playing a huge role here (what does connected component even mean, and what would they imply?)
At this point I hadn't thought to consider $n$ points in general position, and I tried to represent the movements of the ants using vectors; an ant could move by $(1,1)$ when it moves $1$ hole right in $1$ time period, $(1,2)$ and even $(2,-1)$ (theoretically it couldn't, but it would be the same as $(-2,1)$, which could happen by moving $2$ holes left.) I was stuck in this for so long because of the "majestic property" that all $(1,1)$-type segments cannot intersect at all.
However, I realized that arbitrarily different-types segments can or cannot intersect, and it really seemed arbitrary. Example below is for $(3,1)$ and $(2,2)$ (not to mention the negatives are hard to control too.)
[asy][asy]usepackage("tikz");
label("\begin{tikzpicture}
\draw[green,thick](0,0)--(3.5,1); \draw[green,thick](2,0)--(4.5,2); \draw[fill=green](0,0)circle(2pt); \draw[fill=green](1,0)circle(2pt); \draw[fill=green](2,0)circle(2pt); \draw[fill=green](3.5,0)circle(2pt); \draw[fill=green](4.5,0)circle(2pt); \draw[fill=green](3.5,1)circle(2pt); \draw[fill=green](4.5,1)circle(2pt); \draw[fill=green](4.5,2)circle(2pt);
\end{tikzpicture}");[/asy][/asy]
$\textcolor{green}{\text{Section 2 End.}}$
S3 (5 points). Hard Tech 2 (C, finding obscure constructions): Finally noticing earlier "regular" efforts fail, and it's better to view it more general/globally. Giving up, I now considered my last resort, which are trees. It is clear that the trees do have to be some specifically-particular type (which I didn't realize must closely resemble star graphs, or else there exists vertices such as $v_1$ or $v_2$ with $"\text{dead}"$ neighbors, but problem solving doesn't work in a $"\textbf{linear way}"$ ... pun fully intended.)
For example, a particular construction of trees which are easily eliminated are
[asy][asy]usepackage("tikz");
label("\begin{tikzpicture}
\draw[green,thick](0,2)--(0,0); \draw[green,thick](0,0)--(3,0); \draw[green,thick](0,1)--(3,1); \draw[green,thick](0,2)--(3,2); \draw[fill=green](0,0)circle(2pt); \draw[fill=green](0,1)circle(2pt); \draw[fill=green](0,2)circle(2pt); \draw[fill=green](1,0)circle(2pt); \draw[fill=green](1,1)circle(2pt); \draw[fill=green](1,2)circle(2pt); \draw[fill=green](2,0)circle(2pt); \draw[fill=green](2,1)circle(2pt); \draw[fill=green](2,2)circle(2pt); \draw[fill=green](3,0)circle(2pt); \draw[fill=green](3,1)circle(2pt); \draw[fill=green](3,2)circle(2pt);
\end{tikzpicture}
\begin{tikzpicture}
\node at (0,0){};
\node at (0,1) {$\quad$ $\rightarrow$ $\quad$};
\end{tikzpicture}
\begin{tikzpicture}
\draw[green,thick](-0.1,2.1)--(0.9,1.9);\draw[green,thick](0.1,0.9)--(-0.1,2.1); \draw[green,thick](0.1,0.9)--(-0.1,0.1); \draw[green,thick](-0.1,0.1)--(1,-0.1); \draw[green,thick](0.1,0.9)--(1.1,1.1); \draw[green,thick](-0.1,2.1)--(0.9,1.9); \draw[green,thick](0.9,1.9)--(2.1,2.1); \draw[green,thick](2.1,2.1)--(3.1,1.9); \draw[green,thick](1.1,1.1)--(1.9,1); \draw[green,thick](3.1,1)--(1.9,1); \draw[green,thick](1,-0.1)--(2.1,0.1); \draw[green,thick](2.1,0.1)--(2.9,-0.1);
\draw[fill=green](-0.1,0.1)circle(2pt); \draw[fill=green](0.1,0.9)circle(2pt); \draw[fill=green](-0.1,2.1)circle(2pt); \draw[fill=green](2.9,-0.1)circle(2pt); \draw[fill=green](3.1,1)circle(2pt); \draw[fill=green](3.1,1.9)circle(2pt); \draw[fill=green](1,-0.1)circle(2pt); \draw[fill=green](1.1,1.1)circle(2pt); \draw[fill=green](0.9,1.9)circle(2pt); \draw[fill=green](2.1,0.1)circle(2pt); \draw[fill=green](1.9,1)circle(2pt); \draw[fill=green](2.1,2.1)circle(2pt);
\end{tikzpicture}");[/asy][/asy]
upon which I realized that when I toggled it a bit to remove the prospect of two segments that are parallel (a condition which is restricted by "speed of ants are distinct), that I finally decided that $\textbf{if it works on toggled environments}$ then $\textbf{it must work on general environments}$ (like the recent 2019 C6 where toggling doesn't change the angle conditions, but I digress.)
So I considered a particular edge of a tree (after all, we are trying to bound edges based on its vertices) and followed the local arguments in the first two paragraphs of $\textcolor{magenta}{\textbf{\text{The Proof.}}}$
I took a bit of a detour by not considering the degree of $v_1$ in particular, and instead consider where the segments with endpoints $v_4$ and $v_5$ must be; they must also intersect $s$ and reach $\mathcal{H}_1$. Then, to my dismay, no contradiction can be attained, as we can just construct a $C_5$ in the form of a pentagram, of which the vertices' degree is all $2$.
[asy][asy]usepackage("tikz");
label("\begin{tikzpicture}
\draw[green,thick](-0.6,1.5)--(1.5,-1.1)--(-1.5,0)--(1.5,0)--(-1.6,-1.1)--(0.6,1.5); \draw[green,thick](-1.5,0)--(1.9,-0.5);
\node[font=\footnotesize,left](A)at(-1.5,0){$v_1$};
\node[font=\footnotesize,right](B)at(1.5,0){$v_2$}; \node[font=\footnotesize,right](C)at(1.9,-0.5){$v_3$}; \node[font=\footnotesize,below right](D)at(1.5,-1.1){$v_4$}; \node[font=\footnotesize,below left](E)at(-1.6,-1.1){$v_5$}; \node(F)at(0.6,1.5){}; \node(G)at(-0.6,1.5){};
\end{tikzpicture}\begin{tikzpicture}
\node at (0,0){};
\node at (0,1.2) {$\quad$ $\rightarrow$ $\quad$};
\end{tikzpicture}
\begin{tikzpicture}
\node at (0,-1.5){};
\draw[green,thick](-1.5,0)--(1.2,-1.2)--(0,1)--(-1.2,-1.2)--(1.5,0)--cycle;
\end{tikzpicture}
");[/asy][/asy]
However, if $"\text{two triangles}"$ are formed, when two pairs of segments from $v_1$ and $v_2$ have the same endpoint as following:
[asy][asy]usepackage("tikz");
label(" \begin{tikzpicture}
\draw[green,thick](0,-1.8)--(-1.5,0)--(1.5,0); \draw[green,thick](-1.2,-1.8)--(1.5,0); \draw[green!50!black,thick](1.5,0)--(0,-1.8); \draw[green!50!black,thick](-1.5,0)--(-1.2,-1.8); \node[font=\footnotesize,above]at(1.5,0){$2$}; \node[font=\footnotesize,above]at(-1.5,0){$1$}; \node[font=\footnotesize,below]at(0,-1.8){$\Delta_{(1)}$}; \node[font=\footnotesize,below]at(-1.2,-1.8){$\Delta_{(2)}$}; \node[font=\footnotesize,red]at(0,-2.8){Triangle Config $\#1$};
\end{tikzpicture}
\begin{tikzpicture}
\draw[green,thick](-1.5,0)--(1.5,0)--(0,-1); \draw[green,thick](0,-2.2)--(-1.5,0); \draw[green!50!black,thick](-1.5,0)--(0,-1); \draw[green!50!black,thick](1.5,0)--(0,-2.2); \node[font=\footnotesize,above]at(1.5,0){$2$}; \node[font=\footnotesize,above]at(-1.5,0){$1$}; \node[font=\footnotesize,below]at(0,-1){$\Delta_{(1)}$}; \node[font=\footnotesize,below]at(0,-2.2){$\Delta_{(2)}$}; \node[font=\footnotesize,red]at(0,-3){Triangle Config $\#2$};
\end{tikzpicture}");[/asy][/asy]
then there are two segments which don't collide. $\textcolor{green}{\text{Section 3 End.}}$
S4 (5 points). Soft Tech 3 (Pattern spotting): Finding exactly what to look for, and going back from global structures to individual degrees. Seeing as considering "large structures" may or may not yield a contradiction (and also the patterns are strange, since it seems that "two $C_3$s" yields contradiction but a single $C_5$ doesn't) so I gave up on that idea.
Finally, I stumbled upon a vertex I hadn't considered yet, which is the key to pointing out a point which $"\textit{doesn't socialize much}"$ with other vertices; a.k.a. those in the middle. I realized that I was being stupid and I could've repeated the same argument I applied in the first two paragraphs of $\textcolor{magenta}{\textbf{\text{The Proof.}}}$ to $v_3$ and win. $\textcolor{green}{\text{Section 4 End.}}$
Final rating : 25 points, converted to 25M in MOHS. May be that I just didn't find the central thread at first, the problem has $"\text{lots of misleading leads}"$ and $"\text{strange but valid configurations}"$ and that amplified by my stupidity of not realizing that $\textbf{the easiest way to compute edge cardinality is by degree counting.}$