Difference between revisions of "2020 IMO Problems/Problem 4"
(Created page with "Problem 4. There is an integer n > 1. There are n 2 stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, A and B, operates k cable c...") |
Etmetalakret (talk | contribs) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | Problem | + | == Problem == |
| − | 2 | + | There is an integer <math>n > 1</math>. There are <math>n^2</math> stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, <math>A</math> and <math>B</math>, operates <math>k</math> cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The <math>k</math> cable cars of <math>A</math> have <math>k</math> different starting points and <math>k</math> different finishing points, and a cable car that starts higher also finishes higher. The same conditions hold for <math>B</math>. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed). |
| − | stations on a slope of a mountain, all at | + | |
| − | different altitudes. Each of two cable car companies, A and B, operates k cable cars; each cable | + | Determine the smallest positive integer k for which one can guarantee that there are two stations that are linked by both companies. |
| − | car provides a transfer from one of the stations to a higher one (with no intermediate stops). The | + | |
| − | k cable cars of A have k different starting points and k different finishing points, and a cable car | + | == Video solution == |
| − | + | https://www.youtube.com/watch?v=dTqwOoSfaAA [video covers all day 2 problems] | |
| − | are linked by a company if one can start from the lower station and reach the higher one by using | + | |
| − | one or more cars of that company (no other movements between stations are allowed). | + | ==See Also== |
| − | Determine the smallest positive integer k for which one can guarantee that there are two stations | + | |
| − | that are linked by both companies | + | {{IMO box|year=2020|num-b=3|num-a=5}} |
| + | |||
| + | [[Category:Olympiad Combinatorics Problems]] | ||
Latest revision as of 10:31, 14 May 2021
Problem
There is an integer 
. There are 
stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, 
and 
, operates 
cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The cable cars of have different starting points and different finishing points, and a cable car that starts higher also finishes higher. The same conditions hold for . We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed).
Determine the smallest positive integer k for which one can guarantee that there are two stations that are linked by both companies.
Video solution
https://www.youtube.com/watch?v=dTqwOoSfaAA [video covers all day 2 problems]
See Also
| 2020 IMO (Problems) • Resources | ||
| Preceded by Problem 3 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 5 |
| All IMO Problems and Solutions | ||
