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

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

@@ 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>.)
+==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)==
@@ Line 21: / Line 112: @@
 ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
+==Video Solution==
+https://youtu.be/lD3kQDGJ_Ng
 ==See Also==
-{{IMO box|year=2023|before=First Problem|num-a=2}}
+{{IMO box|year=2024|before=First Problem|num-a=2}}

2024 IMO (Problems) • Resources
Preceded by First Problem	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 2
All IMO Problems and Solutions

Page

Toolbox

Search

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

Latest revision as of 09:15, 20 November 2024

Contents

Solution 1

Video Solution(In Chinese)

Video Solution

Video Solution

Video Solution

See Also