Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2025 IMO Problems/Problem 1"

(Created page with "A line in the plane is called <math>sunny</math> if it is not parallel to any of the <math>x</math>–axis, the <math>y</math>–axis, or the line <math>x+y=0</math>. Let <ma...")
 
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
A line in the plane is called <math>sunny</math> if it is not parallel to any of the <math>x</math>–axis, the <math>y</math>–axis, or the line <math>x+y=0</math>.
+
A line in the plane is called <i>sunny</i> if it is <b>not</b> parallel to any of the <math>x</math>–axis, the <math>y</math>–axis, and the line <math>x+y=0</math>.
  
 
Let <math>n\ge3</math> be a given integer. Determine all nonnegative integers <math>k</math> such that there exist <math>n</math> distinct lines in the plane satisfying both of the following:
 
Let <math>n\ge3</math> be a given integer. Determine all nonnegative integers <math>k</math> such that there exist <math>n</math> distinct lines in the plane satisfying both of the following:
  
−
- 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> lies 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 ==
+
==Video Solution==
−
https://www.youtube.com/watch?v=kJVQqugw_JI [includes motivational discussion]
+
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 <math>k \ge 4</math>.
 +
<cmath>
 +
\text{Claim: One of the } n \text{ lines must be } x=1, y=1, \text{ or } x+y=n.
 +
</cmath>
 +
Proof: Assume for the sake of contradiction not. Then, the following holds:
 +
<cmath>
 +
\quad \text{1. } x=1 \text{ is not in our lines.}
 +
</cmath>
 +
Otherwise, two points with <math>x=1</math> are on the same line. This implies that each point with <math>x</math>-coordinate <math>1</math> must lie on distinct lines, hence there exists a bijection between the lines and points with <math>x</math>-coordinate <math>1</math>. It follows with similar reasoning that:
 +
<cmath>
 +
\quad \text{2. Lines are bijective with points with } y \text{-coordinate.}
 +
</cmath>
 +
<cmath>
 +
\quad \text{3. Lines are bijective with points } x+y=n+1.
 +
</cmath>
 +
Consider the points on <math>x+y=n+1</math> that are not <math>(1,n)</math> or <math>(n,1)</math>. Then, because there exists a bijection, any such point must have a line through a point with <math>x</math>-coordinate <math>1</math> and <math>y</math>-coordinate <math>1</math> that are not <math>(1,n)</math> or <math>(n,1)</math> (otherwise <math>x+y=n+1</math> exists). But this cannot be possible if the point is not <math>(1,1)</math>. Since <math>n \ge 3</math>, by the Pigeonhole Principle there must be at least <math>1</math> point that has to pass through this condition, hence we have proved the claim. <math>\square</math>
 +
*We can find the constructions for <math>0,1,3</math> easily.
 +
----
 +
 
 +
Hence, remove one of the <math>x=1, y=1,</math> or <math>x+y=n+1</math> lines. We then get a valid covering for <math>n-1</math> with the same number of sunny lines! Thus, any possible number of sunny lines for <math>n</math> must be possible for <math>n-1</math>.
 +
For <math>n=3</math>, we have possibilities <math>k=0, k=1, \text{ or } k=3</math>. By our induction above, we conclude that for any <math>n</math>, the possible <math>k</math> is a subset of <math>\{0,1,3\}</math>. <math>\blacksquare</math>
 +
 
 +
~MC
 +
 
 +
 
 +
 
 +
==See Also==
 +
* [[2025 IMO]]
 +
* [[IMO Problems and Solutions, with authors]]
 +
* [[Mathematics competitions resources]]
 +
{{IMO box|year=2025|before=First Question|num-a=2}}

Latest revision as of 09:52, 22 July 2025

A line in the plane is called sunny if it is not parallel to any of the $x$–axis, the $y$–axis, and the line $x+y=0$.

Let $n\ge3$ be a given integer. Determine all nonnegative integers $k$ such that there exist $n$ distinct lines in the plane satisfying both of the following:

  • for all positive integers $a$ and $b$ with $a+b\le n+1$, the point $(a,b)$ is on at least one of the lines; and
  • exactly $k$ of the $n$ 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

Consider a valid construction for $k \ge 4$. \[\text{Claim: One of the } n \text{ lines must be } x=1, y=1, \text{ or } x+y=n.\] Proof: Assume for the sake of contradiction not. Then, the following holds: \[\quad \text{1. } x=1 \text{ is not in our lines.}\] Otherwise, two points with $x=1$ are on the same line. This implies that each point with $x$-coordinate $1$ must lie on distinct lines, hence there exists a bijection between the lines and points with $x$-coordinate $1$. It follows with similar reasoning that: \[\quad \text{2. Lines are bijective with points with } y \text{-coordinate.}\] \[\quad \text{3. Lines are bijective with points } x+y=n+1.\] Consider the points on $x+y=n+1$ that are not $(1,n)$ or $(n,1)$. Then, because there exists a bijection, any such point must have a line through a point with $x$-coordinate $1$ and $y$-coordinate $1$ that are not $(1,n)$ or $(n,1)$ (otherwise $x+y=n+1$ exists). But this cannot be possible if the point is not $(1,1)$. Since $n \ge 3$, by the Pigeonhole Principle there must be at least $1$ point that has to pass through this condition, hence we have proved the claim. $\square$

  • We can find the constructions for $0,1,3$ easily.

Hence, remove one of the $x=1, y=1,$ or $x+y=n+1$ lines. We then get a valid covering for $n-1$ with the same number of sunny lines! Thus, any possible number of sunny lines for $n$ must be possible for $n-1$. For $n=3$, we have possibilities $k=0, k=1, \text{ or } k=3$. By our induction above, we conclude that for any $n$, the possible $k$ is a subset of $\{0,1,3\}$. $\blacksquare$

~MC


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_IMO_Problems/Problem_1&oldid=255008"