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 "2024 IMO Problems/Problem 1"
(→‎Solution 1)
 
(10 intermediate revisions by 6 users not shown)
Line 4: Line 4:
  
 
is a multiple of <math>n</math>. (Note that <math>\lfloor z \rfloor</math> denotes the greatest integer less than or equal to <math>z</math>. For example, <math>\lfloor -\pi \rfloor = -4</math> and <math>\lfloor 2 \rfloor = \lfloor 2.9 \rfloor = 2</math>.)
 
is a multiple of <math>n</math>. (Note that <math>\lfloor z \rfloor</math> denotes the greatest integer less than or equal to <math>z</math>. For example, <math>\lfloor -\pi \rfloor = -4</math> and <math>\lfloor 2 \rfloor = \lfloor 2.9 \rfloor = 2</math>.)
 +
 +
==Solution 1==
 +
To solve the problem, we need to find all real numbers \( \alpha \) such that, for every positive integer \( n \), the integer
 +
 +
<cmath>
 +
S_n(\alpha) = \lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \dots + \lfloor n\alpha \rfloor
 +
</cmath>
 +
 +
is divisible by \( n \), i.e., \( S_n(\alpha) \equiv 0 \mod n \).
 +
 +
Step 1: Break Down \( \alpha \) into Integer and Fractional Parts
 +
 +
Let \( \alpha = m + f \), where \( m = \lfloor \alpha \rfloor \in \mathbb{Z} \) and \( f = \{\alpha\} \in [0,1) \) is the fractional part of \( \alpha \).
 +
 +
Step 2: Express the Sum in Terms of \( m \) and \( f \)
 +
 +
Using this, we have:
 +
 +
<cmath>
 +
\lfloor k\alpha \rfloor = \lfloor k(m + f) \rfloor = km + \lfloor kf \rfloor.
 +
</cmath>
 +
 +
So, the sum becomes:
 +
 +
<cmath>
 +
S_n(\alpha) = m \sum_{k=1}^{n} k + \sum_{k=1}^{n} \lfloor kf \rfloor = m \frac{n(n+1)}{2} + \sum_{k=1}^{n} \lfloor kf \rfloor.
 +
</cmath>
 +
 +
Step 3: Modulo \( n \) Simplification
 +
 +
We are interested in \( S_n(\alpha) \mod n \):
 +
 +
<cmath>
 +
S_n(\alpha) \equiv \left( m \frac{n(n+1)}{2} + \sum_{k=1}^{n} \lfloor kf \rfloor \right) \mod n.
 +
</cmath>
 +
 +
Since \( m \frac{n(n+1)}{2} \) is divisible by \( n \), the expression simplifies to:
 +
 +
<cmath>
 +
S_n(\alpha) \equiv \sum_{k=1}^{n} \lfloor kf \rfloor \mod n.
 +
</cmath>
 +
 +
Step 4: Analyze the Fractional Part \( f \)
 +
 +
Our goal is to find all \( f \in [0,1) \) such that:
 +
 +
<cmath>
 +
\sum_{k=1}^{n} \lfloor kf \rfloor \equiv 0 \mod n \quad \text{for all } n \in \mathbb{N}.
 +
</cmath>
 +
 +
Step 5: Test \( f = 0 \)
 +
 +
If \( f = 0 \), then \( \lfloor kf \rfloor = 0 \) for all \( k \), so:
 +
 +
<cmath>
 +
\sum_{k=1}^{n} \lfloor kf \rfloor = 0,
 +
</cmath>
 +
 +
which satisfies the condition for all \( n \).
 +
 +
Step 6: Consider \( f \in (0,1) \)
 +
 +
For \( f \in (0,1) \), let's test small values of \( n \) and \( f \). It turns out that the sum \( \sum_{k=1}^{n} \lfloor kf \rfloor \) does not satisfy the congruence \( 0 \mod n \) for all \( n \). For example, if \( f = \frac{1}{2} \):
 +
 +
<cmath>
 +
\sum_{k=1}^{2} \lfloor k \cdot \frac{1}{2} \rfloor = \lfloor \frac{1}{2} \rfloor + \lfloor 1 \rfloor = 0 + 1 = 1 \not\equiv 0 \mod 2.
 +
</cmath>
 +
 +
Thus, \( f \ne 0 \) fails the condition.
 +
 +
Step 7: Conclude that Only \( f = 0 \) Works
 +
 +
Since \( f \ne 0 \) does not satisfy the condition, the only possible value is \( f = 0 \), meaning \( \alpha \) must be an integer.
 +
 +
Step 8: Verify for Integer \( \alpha \)
 +
 +
Let \( \alpha = m \in \mathbb{Z} \). Then:
 +
 +
<cmath>
 +
S_n(\alpha) = m \sum_{k=1}^{n} k = m \frac{n(n+1)}{2}.
 +
</cmath>
 +
 +
This sum is divisible by \( n \) if and only if \( m \) is even.
 +
 +
Because \( \frac{n(n+1)}{2} \) times any even integer \( m \) is divisible by \( n \).
 +
 +
But \( \frac{n(n+1)}{2} \) times an odd integer \( m \) is not, if n is even.
 +
 +
The only real numbers \( \alpha \) satisfying the condition are the even integers.
 +
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Athmyx Athmyx]
 +
 +
==Video Solution(In Chinese)==
 +
https://youtu.be/LW54i7rWkpI
  
 
==Video Solution==
 
==Video Solution==
 
https://www.youtube.com/watch?v=50W_ntnPX0k
 
https://www.youtube.com/watch?v=50W_ntnPX0k
 +
 +
==Video Solution==
 +
Part 1 (analysis of why there is no irrational solution)
 +
 +
https://youtu.be/QPdHrNUDC2A
 +
 +
Part 2 (analysis of even integer solutions and why there is no non-integer rational solution)
 +
 +
https://youtu.be/4rNh4sbsSms
 +
 +
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
 +
==Video Solution==
 +
https://youtu.be/lD3kQDGJ_Ng
 +
 +
==See Also==
 +
 +
{{IMO box|year=2024|before=First Problem|num-a=2}}

Latest revision as of 09:15, 20 November 2024

Determine all real numbers $\alpha$ such that, for every positive integer $n$, the integer

\[\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \dots +\lfloor n\alpha \rfloor\]

is a multiple of $n$. (Note that $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$. For example, $\lfloor -\pi \rfloor = -4$ and $\lfloor 2 \rfloor = \lfloor 2.9 \rfloor = 2$.)

Solution 1

To solve the problem, we need to find all real numbers \( \alpha \) such that, for every positive integer \( n \), the integer

\[S_n(\alpha) = \lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \dots + \lfloor n\alpha \rfloor\]

is divisible by \( n \), i.e., \( S_n(\alpha) \equiv 0 \mod n \).

Step 1: Break Down \( \alpha \) into Integer and Fractional Parts

Let \( \alpha = m + f \), where \( m = \lfloor \alpha \rfloor \in \mathbb{Z} \) and \( f = \{\alpha\} \in [0,1) \) is the fractional part of \( \alpha \).

Step 2: Express the Sum in Terms of \( m \) and \( f \)

Using this, we have:

\[\lfloor k\alpha \rfloor = \lfloor k(m + f) \rfloor = km + \lfloor kf \rfloor.\]

So, the sum becomes:

\[S_n(\alpha) = m \sum_{k=1}^{n} k + \sum_{k=1}^{n} \lfloor kf \rfloor = m \frac{n(n+1)}{2} + \sum_{k=1}^{n} \lfloor kf \rfloor.\]

Step 3: Modulo \( n \) Simplification

We are interested in \( S_n(\alpha) \mod n \):

\[S_n(\alpha) \equiv \left( m \frac{n(n+1)}{2} + \sum_{k=1}^{n} \lfloor kf \rfloor \right) \mod n.\]

Since \( m \frac{n(n+1)}{2} \) is divisible by \( n \), the expression simplifies to:

\[S_n(\alpha) \equiv \sum_{k=1}^{n} \lfloor kf \rfloor \mod n.\]

Step 4: Analyze the Fractional Part \( f \)

Our goal is to find all \( f \in [0,1) \) such that:

\[\sum_{k=1}^{n} \lfloor kf \rfloor \equiv 0 \mod n \quad \text{for all } n \in \mathbb{N}.\]

Step 5: Test \( f = 0 \)

If \( f = 0 \), then \( \lfloor kf \rfloor = 0 \) for all \( k \), so:

\[\sum_{k=1}^{n} \lfloor kf \rfloor = 0,\]

which satisfies the condition for all \( n \).

Step 6: Consider \( f \in (0,1) \)

For \( f \in (0,1) \), let's test small values of \( n \) and \( f \). It turns out that the sum \( \sum_{k=1}^{n} \lfloor kf \rfloor \) does not satisfy the congruence \( 0 \mod n \) for all \( n \). For example, if \( f = \frac{1}{2} \):

\[\sum_{k=1}^{2} \lfloor k \cdot \frac{1}{2} \rfloor = \lfloor \frac{1}{2} \rfloor + \lfloor 1 \rfloor = 0 + 1 = 1 \not\equiv 0 \mod 2.\]

Thus, \( f \ne 0 \) fails the condition.

Step 7: Conclude that Only \( f = 0 \) Works

Since \( f \ne 0 \) does not satisfy the condition, the only possible value is \( f = 0 \), meaning \( \alpha \) must be an integer.

Step 8: Verify for Integer \( \alpha \)

Let \( \alpha = m \in \mathbb{Z} \). Then:

\[S_n(\alpha) = m \sum_{k=1}^{n} k = m \frac{n(n+1)}{2}.\]

This sum is divisible by \( n \) if and only if \( m \) is even.

Because \( \frac{n(n+1)}{2} \) times any even integer \( m \) is divisible by \( n \).

But \( \frac{n(n+1)}{2} \) times an odd integer \( m \) is not, if n is even.

The only real numbers \( \alpha \) satisfying the condition are the even integers.

~Athmyx

Video Solution(In Chinese)

https://youtu.be/LW54i7rWkpI

Video Solution

https://www.youtube.com/watch?v=50W_ntnPX0k

Video Solution

Part 1 (analysis of why there is no irrational solution)

https://youtu.be/QPdHrNUDC2A

Part 2 (analysis of even integer solutions and why there is no non-integer rational solution)

https://youtu.be/4rNh4sbsSms

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Video Solution

https://youtu.be/lD3kQDGJ_Ng

See Also

2024 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_IMO_Problems/Problem_1&oldid=235140"