Is this the real problem? (Oh it is.)

I got the answer, better not to give hint.

@post 13: nice! i really liked this problem (both natural and cute), although I was a little bit dismayed that "start higher means end higher" was not necessary in the bounding.

naman12 wrote:

Shouldn't finishing points be different?

Where is the "starts higher also finishes higher" assumption used?

danepale wrote: Where is the "starts higher also finishes higher" assumption used? I dont know anyone who used it lol.

PedroBigMan wrote: danepale wrote: Where is the "starts higher also finishes higher" assumption used? I dont know anyone who used it lol. One can misread the problem and still solve it correctly, lol. EDIT: On a serious note, what even? Doesn't this go against the problemsetting etiquette?

Some examples for $k=n^2-n$ can didn't work with this assumption.

Any Idea about the cutoffs this time?

This problem was proposed by India

micliva wrote: This problem was proposed by India Each cable car connects a station to a higher one thus no directed cycles. Am I being dumb?

This problem reminded me of the fun fact that for any graph $G = (V, E)$, $\chi{(G)} \cdot \chi{(\overline G)} \geq |V|$

All the solutions above are wrong.

What time is it now, in UK ?

danepale wrote: PedroBigMan wrote: danepale wrote: Where is the "starts higher also finishes higher" assumption used? I dont know anyone who used it lol. One can misread the problem and still solve it correctly, lol. EDIT: On a serious note, what even? Doesn't this go against the problemsetting etiquette? Khina's solution uses that. If the starts higher also finishes higher condition doesnt hold then there is a better bound.

For those who like the 12-hour format, it's 10:24 pm there.

neyft wrote: All the solutions above are wrong. why?

rmtf1111 wrote: Khina's solution uses that. If the starts higher also finishes higher condition doesnt hold then there is a better bound. wut i don't think i used the condition...

Let the $n^2$ stations be the vertices $v_1, v_2, \cdots v_{n^2}$ where $v_i$ is at a greater height that $v_j$ if $i>j$. We color the directed edges of company $A$ blue and company $B$ red. We claim that the smallest possible $k$ is $n^2-n+1$. The lower bound can be achieved with the following construction: We connect $$v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$$$$v_{n+1} \rightarrow v_{n+2} \rightarrow \cdots \rightarrow v_{2n}$$$$\vdots$$$$v_{n^2-2n+1} \rightarrow v_{n^2-2n+2} \rightarrow \cdots \rightarrow v_{n^2-n}$$in the blue graph and we connect $$v_1 \rightarrow v_{n+1} \rightarrow \cdots \rightarrow v_{n^2-n+1}$$$$v_{2} \rightarrow v_{n+2} \cdots \rightarrow v_{n^2-n+2}$$$$\vdots$$$$v_{n} \rightarrow v_{2n} \cdots \rightarrow v_{n^2}$$in the red graph. $\blacksquare$ Now, for the upper bound, we define a series of directed edges to be chains, we note that all these chains must be disjoint because of the problem condition and therefore there must be at most $n-1$ chains and therefore there must be a chain in, say, the blue graph with at least $\left \lceil \frac{n^2}{n - 1} \right \rceil=n+2$ vertices. Now, by the pigeonhole principle, there must be two vertices in one of the $n-1$ cycles of the red graph which also occur in the chain with $n+2$ vertices of the blue graph. $\blacksquare$

The answer is $\boxed{n^2-n+1}$. We can solve the identical problem: Modified IMO 2020/4 wrote: Consider $x$ groups of cells taking up $k+x$ cells total on an $n\times n$ grid such that each group contains at least two cells, and another $y$ groups of cells taking up $k+y$ cells total on the same grid. Find the smallest integer $k$ for which one can guarantee that there exists two groups that intersect (share a cell) twice. The $y$ groups of cells can take up $(n^2-k-x)+xy$ cells at the maximum, so we want $n^2+xy-x-y=n^2-1+(x-1)(y-1)\geq 2k$. Suppose $k\geq n^2-n+1$. We have $(x-1)(y-1)\leq n^2-4n+4$ which means $n^2-1+(x-1)(y-1)\leq 2n^2-4n+3< 2n^2-2n+2\leq 2k$ which is a contradiction, and a construction for $n^2-n$ is when the $x$ groups are the rows and the $y$ groups are the columns. If $k<n^2-n$ simply "split" some of the groups; it is easy to verify that this is still valid. edit: oops i think this might be incorrect edit edit: i think i fixed it

The answer is $n^2-n+1$. To show that it's necessary, consider the following construction: A operates every station from $kn+i$ to $kn+i+1$ for integers $0\le k\le n-1,1\le i\le n$, and B operates every station from $m$ to $m+n$ for integers $1\le m\le n^2-n$. This uses $n^2-n$ cars for each company and there are no two stations reachable by both companies. To show that it's sufficient, let $G$ be the obvious directed graph drawn with cars of company A. I claim that $G$ has a path of length at least $n+1$. Proof: at most $n-1$ stations can have indegree $0$, so there are at most $n-1$ paths. The claim then follows by pigeonhole. Toggle every vertex in a path of length at least $n+1$ orange. Now, consider the directed graph $H$ on the same set of vertices drawn by cars of company B. Since $H$ also has at most $n-1$ paths, we, in fact, must have at least $2$ pairs of orange vertices belonging to the same path.

We claim the answer is $n^2-n+1$. For $k=n^2-n$, $A$ connecting all stations exactly $n$ apart and $B$ connecting stations $x-1,x$ for all applicable $x$ which are not multiples of $n$ gives a counterexample. Let a chain for a company be a maximal set of numbers $\{x_1,x_2,\ldots,x_m\}$ such that all $x_i$ are between $1$ and $n^2$, $x_1<x_2<\ldots<x_m$, and stations $x_i$ and $x_{i+1}$ are connected for $1\le i\le m-1$. Clearly any two stations in the same chain are linked. In addition, notice that any two stations that are directly linked are in the same chain. Claim: If a company operates $k$ cars, that company will have $n^2-k$ chains. Proof. Use induction. The base case $k=0$ is trivial. Suppose that the statement is true for $k=i$. Then consider $k=i+1$; now remove a cable car between $X$ and $Y$. This breaks up the chain containing $X$ and $Y$ into two chains, one ending at $X$ and one beginning at $Y$. By the induction hypothesis, we now have $n^2-i$ chains, accounting for the one we broke, for $k=i+1$ we have $n^2-i-1$ chains, and the induction is done. $\blacksquare$ When $k=n^2-n+1$, by the claim both companies have $n-1$ chains. By Pigeonhole a chain in $A$ has at least $\lceil \frac{n^2}{n-1} \rceil = n+2$ stations in it; moreover, by Pigeonhole again there must exist a pair of stations in this chain that are also in the same chain for Company B. This pair of stations must be linked for both companies.

We claim that the answer is $n^2-n+1.$ In order to show that $k=n^2-n$ does not guarantee the condition, we group the stations into $n$ consecutive groups of $n$. We have the first company connect each pair of adjacent stations within a group, and the second company connect each station that is not in the $n$ highest to its corresponding station in the group above it, so that company A only connects stations within each group, but company B only connects stations in different groups. This is $n^2-n$ connections for each company. We partition the positive integers from 1 to $n^2$ into disjoint increasing sequences, such that $i$ and $j$ are in the same sequence if and only if stations $i$ and $j$ are linked by company $A$. We see that for each connection for company $A$, the number of sequences decreases by 1, as two sequences are merged together, so there are $n^2-k$ sequences. We do the same based on company B, and we get $n^2-k$ more sequences. Let $k=n^2-n+1$. Then, each company has $n-1$ sequences. We rephrase the problem as follows: The positive integers up to $n^2$ are split into $n-1$ disjoint sets in two different ways. Show that there is always a pair of numbers that are in the same sequence in both ways. Note that at least one set in the first way contains at least $n+2$ numbers, as $(n+1)(n-1)<n^2.$ However, since the second way uses only $n-1$ sequences, we cannot split all $n+2$ of these into different sets, so there is a pair that are linked by both companies.

Let the stations be $S_1,S_2,\dots,S_{n^2}$, with $S_i$ higher than $S_j$ if and only if $i>j.$ We claim that the answer is $n^2-n+1.$ When $k=n^2-n$ we can let $A$'s cable cars go \[an+1\to an+2, an+2\to an+3, an+3\to an+4,\dots, an+n-1 \to an+n\]for $0\le a\le n-1.$ We can let $B$'s cable cars go \[a+1\to n+a+1,n+a+1\to 2n+a+1,\dots, (n-2)n+a+1\to(n-1)n+a+1.\] Now, let $k=n^2-n+1.$ Let an $A$-maximal path be a sequence of integers $a_1,a_2,\dots,a_i$ such that you can, through $A$'s cable cars, go from \[a_1\to a_2,a_2\to a_3,\dots a_{i-1}\to a_i\], and there do not exist $x,y$ such that you can go from $x\to a_1$ or $a_i\to y.$ Note that each time we remove a cable car of $A$, at most one new maximal path is introduced. Thus, there are at most $n-1$ $A$-maximal paths and similarly at most $n-1$ $B$-maximal paths. By pigeonhole principle, there is an $A$-maximal path of size $n+2$, and again by pigeonhole principle, there is a $B$-maximal path that shares two stations with the $A$-maximal path.

The answer is $n^2 - n + 1$. First we give a construction that shows $k = n^2 - n$ fails. For company $A$, choose each cable car to go from station $i$ to station $i + 1$ for any $i$ not a multiple of $n$. For company $B$, choose each cable car from station $i$ to station $i + n$ for any $i\le n^2 - n$. To see this shows $k = n^2 - n$ fails, notice that if two stations are linked by company $B$, then they must be the same modulo $n$, which means there is a multiple of $n$ between them. However, $an$ is not a starting point of a company $A$ cable car for any integer $a$, so any two cable cars linked by $B$ cannot be linked by $A$. Now we show that $k = n^2 - n + 1$ works. Suppose not. If $k = n^2 - n + 1$, any chain of cable cars contains exactly one car that is not a starting point, and one car that is not a finishing point (furthermore, a cable car that is not connected to any other car counts as a one element chain). Each cable car is in exactly one chain. Hence we can have at most $n ^2 - k = n - 1$ chains for each company. By Pigeonhole Principle, there exists a chain with at least $\left\lceil \frac{n^2}{n-1} \right\rceil = n + 2$ cars for company $A$, then these cars must be in all different chains for company $B$. This is a contradiction since there are at most $n-1$ chains in total.

The answer is $k = n^2-n+1$. For $k = n^2-n$, consider the following construction: let $B$ have cable cars pointing $i \to i+1$ for every $i$ such that $i \not \equiv -1 \pmod n$, and let $A$ have cable cars pointing $i \to i+n$ for every $i \leq n^2-n$. This construction obviously satisfies all the conditions. For $k \geq n^2-n+1$, consider partitioning the graph on the directed cable car routes for $A$ into disjoint paths; there are at most $n-1$ such paths (as every path contributes an endpoint from which an edge does not emanate), so there is a path of length at least $n+2$. On the other hand, each of the $n+2$ vertices in this path must be in different paths in $B$, yet there are at most $n-1$ paths in $B$ too, contradiction.

Answer is $n^2-n+1$. Consider an $n\times n$ matrix where the cell in the $a$th row and $b$th column is $n(a-1)+b$. Simple counterexample for $n^2-n$ is then taking the chains formed by the rows to be cables for $A$, and chains formed by the columns to be cables for $B$. Now note that the DAG formed by cable cars in $A$ can be decomposed into $x$ disjoint paths. Each path is of the form $a_1\to \dots\to a_i$ where the numbers are increasing. Define $y$ disjoint paths for $B$ similarly. If there are $n^2-n+1$ cable cars (we just need to prove this case and we're fine) then $x,y\le n-1$, as the total number of stations is at least $n^2-n+1+x$ and $n^2-n+1+y$. Also note that any two paths, one in $A$ and one in $B$, should intersect at most once, hence there are at most $xy\le n^2-2n+1$ intersections among the cable cars in $A$ and $B$. However notice that there are at least \[n^2-n+1-(n-1)=n^2-2n+2\]intersections among the cable cars in $A$ and $B$, a contradiction.

skullers The answer is $n^2-n+1$. Note that for a given vale of $k$, there are $n^2-k$ chains of cable cars formed by the connections. $n^2-n$ fails Consider the chains $(1,2,3\dots,n)$, $(n+1,n+2\dots,2n)$ and so on until $(n^2-n+1,n^2-n+2,\dots,n^2)$ and say $A$ takes these. Then, let $B$ take chains which consist of cable cars that are equivalent modulo $n$. Clearly no pair is shared between $A$ and $B$ since all pairs in $A$ are $<n$ apart and all pairs in $b$ are $\geq n$ apart. $n^2-n+1$ works Now, there are $n-1$ chains. By pigeonhole, one chain has at least $n+1$ elements. It then becomes clear that there must be a pair in said chain that appears in a chain in $B$. If not, then each chain in $B$ contains at most $1$ element in the previosuly mentioned chain, which is absurd.

Answer: $n^2 - n + 1$. Firstly, we'll prove that if there are at least $n^2 - n + 1$ cable cars, then there exists two stations that are linked by both companies. Assume not. Focus on company $A$ for now, and let the cable cars be edges on a graph with $n^2$ vertices. Call this graph $G_A$. We define $G_B$ similarly. Then it is clear that $G_A$ and $G_B$ are made from chains. Let $x, y$ be the number of chains in $G_A, G_B$, respectively. Then length of any chain in $A$ does not exceed $y-1$ and similarly, the length of any chain in $B$ does not exceed $x-1$. Hence $k \le (x-1)y$ and $k \le (y-1)x$. Since there are $n^2$ vertices, so $xy \le n^2$. Therefore $n^2 - n + 1 \le k \le xy - (\frac{x+y}{2}) \le xy - \sqrt{xy} \le n^2 - n$, a contradiction. By construction, we show that $n^2-n$ linkages are insufficient for the problem condition. For $A$, connect stations $i \rightarrow i+1 $ whenever $i$ is not a multiple of $n$. For $B$, connect stations $i \rightarrow i+n$ when $i \le n^2-n$. Clearly, this graph does not satisfy the problem condition, so we must have that $k > n^2-n$, as needed. $\blacksquare$

In the Official IMO 2020 Shortlist there is a comment that for $N$ cable cars the answer similarly is $N - \lceil \sqrt{N} \rceil + 1$. I can see how the Pigeonhole argument would work for the bound, but can anyone help out with the example? (Is it arranging vertices in something like $\lceil \sqrt{N} \rceil \times \lceil \sqrt{N} \rceil$ square and then remove some top vertices? The calculations did not work out as expected here though.)

The answer is $n^2-n+1$. We will provide the construction for $n=3$, which clearly generalizes. 1 2 3 4 5 6 7 8 9 Let $A$ have all the horizontal edges here, and let $B$ have all the vertical edges here. Clearly this works. Now consider the structure of the graph of say the connections of $A$. Note that they are exactly a collection of disjoint increasing chains. Add some chains of length $0$ to fill in the rest of the nodes. Let $m$ be the length of the longest chain. Then there are at least $n^2/m$ chains in $A$, meaning that there are at most $n^2-n^2/m$ edges in $A$. Now note that any chain of $B$ cannot overlap with a chain of $A$ more than once. Therefore, there will be at least $m$ chains for $B$ (including the ones with length $0$), so there are at most $n^2-m$ edges in $B$. The $m$ that maximizes $\min(n^2-n^2/m,n^2-m)$ is exactly $n$, as desired. $\blacksquare$

Please contact westskigamer@gmail.com if there is an error with my solution for cash bounties by 3/18/2025. Start higher end higher made me very paranoid but it seems that it's obsolete