2025 IMO Problems/Problem 1: Difference between revisions
Mathcosine (talk | contribs) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 5: | Line 5: | ||
* for all positive integers <math>a</math> and <math>b</math> with <math>a+b\le n+1</math>, the point <math>(a,b)</math> is on at least one of the lines; and | * for all positive integers <math>a</math> and <math>b</math> with <math>a+b\le n+1</math>, the point <math>(a,b)</math> is on at least one of the lines; and | ||
* exactly <math>k</math> of the <math>n</math> lines are sunny. | * exactly <math>k</math> of the <math>n</math> lines are sunny. | ||
==Video Solution== | |||
https://www.youtube.com/watch?v=kJVQqugw_JI (includes motivational discussion) | |||
https://youtu.be/4K6wbEuNooI (includes exploration to show motivation behind arguement) | |||
Solution from Edutube: https://www.youtube.com/watch?v=n2Ct4z0eUhg | |||
==Solution 1== | ==Solution 1== | ||
| Line 31: | Line 38: | ||
~MC | ~MC | ||
== | ==Solution 2== | ||
A Short Story | |||
Please don't read this solution if you have already perfectly understood other solutions suggested :)) After solving this problem on my own, I LaTeXed the solution as I thought it is an original solution... It turned out to be the exact same solution as listed above :( Anyhow, hoping this would benefit others, I am just posting this :) | |||
Finding all <imath>k</imath> for each <imath>n</imath> value will lead to the answer. Starting with <imath>n=3</imath>, it is easy to see that <imath>k \in \{0, 1, 3\}</imath> are the only solutions. | |||
Notice that for the rest of the cases, if a line is a "long line" (<imath>x=1, y=1, x+y=n+1</imath>), the case would be identical to its previous case <imath>n-1</imath>. Therefore, investigating a case where no "long lines" are included will lead to a new potential value of <imath>k</imath>. | |||
Notice that each line must contain exactly one points from each long lines. However, no such case exists as most triples of dots will form a triangle. Therefore, by induction, all cases lead to <imath>n=3</imath>, when <imath>k \in \{0, 1, 3\}</imath>. <imath>\blacksquare</imath> | |||
~MaPhyCom | |||
==See Also== | ==See Also== | ||
Latest revision as of 00:43, 9 November 2025
A line in the plane is called sunny if it is not parallel to any of the 
–axis, the 
–axis, and the line 
.
Let 
be a given integer. Determine all nonnegative integers 
such that there exist 
distinct lines in the plane satisfying both of the following:
- for all positive integers
and 
with 
, the point 
is on at least one of the lines; and - exactly
of the 
lines are sunny.
and 
with 
, the point 
is on at least one of the lines; andVideo Solution
https://www.youtube.com/watch?v=kJVQqugw_JI (includes motivational discussion)
https://youtu.be/4K6wbEuNooI (includes exploration to show motivation behind arguement)
Solution from Edutube: https://www.youtube.com/watch?v=n2Ct4z0eUhg
Solution 1
Consider a valid construction for 
.
![\[\text{Claim: One of the } n \text{ lines must be } x=1, y=1, \text{ or } x+y=n.\]](http://latex.artofproblemsolving.com/d/4/9/d49731709e3565416e832cb438b7ece36ee4a281.png)
Proof: Assume for the sake of contradiction not. Then, the following holds:
![\[\quad \text{1. } x=1 \text{ is not in our lines.}\]](http://latex.artofproblemsolving.com/d/c/3/dc3ad2cbfc191ecba0fb4729d3b24c210d48a7f8.png)
Otherwise, two points with 
are on the same line. This implies that each point with -coordinate 
must lie on distinct lines, hence there exists a bijection between the lines and points with -coordinate . It follows with similar reasoning that:
![\[\quad \text{2. Lines are bijective with points with } y \text{-coordinate.}\]](http://latex.artofproblemsolving.com/c/e/6/ce6f79f2febcb44a29026fb4e670160b54ed51b5.png)
![\[\quad \text{3. Lines are bijective with points } x+y=n+1.\]](http://latex.artofproblemsolving.com/7/e/7/7e77ba7a89f8630374d7e70b604aa245ef3bb80f.png)
Consider the points on 
that are not 
or 
. Then, because there exists a bijection, any such point must have a line through a point with -coordinate and -coordinate that are not or (otherwise exists). But this cannot be possible if the point is not 
. Since 
, by the Pigeonhole Principle there must be at least point that has to pass through this condition, hence we have proved the claim. 
- We can find the constructions for
easily.
easily.Hence, remove one of the 
or lines. We then get a valid covering for 
with the same number of sunny lines! Thus, any possible number of sunny lines for must be possible for .
For 
, we have possibilities 
. By our induction above, we conclude that for any , the possible is a subset of 
. 
~MC
Solution 2
A Short Story
Please don't read this solution if you have already perfectly understood other solutions suggested :)) After solving this problem on my own, I LaTeXed the solution as I thought it is an original solution... It turned out to be the exact same solution as listed above :( Anyhow, hoping this would benefit others, I am just posting this :)
Finding all for each value will lead to the answer. Starting with , it is easy to see that 
are the only solutions.
Notice that for the rest of the cases, if a line is a "long line" (
), the case would be identical to its previous case . Therefore, investigating a case where no "long lines" are included will lead to a new potential value of .
Notice that each line must contain exactly one points from each long lines. However, no such case exists as most triples of dots will form a triangle. Therefore, by induction, all cases lead to , when .
~MaPhyCom
See Also
| 2025 IMO (Problems) • Resources | ||
| Preceded by First Question |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
| All IMO Problems and Solutions | ||
