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

Latest revision as of 23:05, 12 March 2025

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

Solution 2 (logic)

If we assume that a is a whole number, you could say that the last term is automatically a multiple of n, and from there you can add the first term and the penultimate term, $ \alpha $+$ \alpha $ * (n-1) to get n*$ \alpha $ so all the previous terms can be paired up likewise with 2*$ \alpha $+$ \alpha $ * (n-2), ... and they will always add up too n* $ \alpha $. From there we know that when n is a even number such as 4 the sum is $ \alpha $+2$ \alpha $+3$ \alpha $+4$ \alpha $. The last term is once again automatically divisible, but in sequences such as this, all the other terms can add up to the last term except for the term in the middle, in this case it would be 2$ \alpha $ , to solve this problem $ \alpha $ must always be even, so that n/2* $ \alpha $=n* $ \alpha $ /2 and alpha is still a whole number. Following the pattern above, all the terms can be added to become n*whole number, and the term in the middle is n* $ \alpha $/2, so $ \alpha $ always works when even.

The number cannot have a fraction or every few sequences it will add a number, but, if the number n is the number direclly after the fraction adds one, like if the fraction was 1/3, and n was three, it would add one to the sequence, which would already be divisible by n, but one plus a multiple of n/2 (if $ \alpha $ is odd it will add 1/2n* $ \alpha $ to the sequence) is never a multiple of n unless n is one, or two, and if n was one, the fraction it would would accompany would be 1/1 which would be a whole number already. If n was 2 , then $ \alpha $ would be, an odd number +1/2, if $ \alpha $ was an odd number +1/2 then we can easily disprove it by setting n to 3, in which case it would be a multiple of n+2 , so n would have to be 2 for it to be divisible, but we already set n to 3, so it is impossible. Therefore there cannot be fractions added to the starting number.

~LIUGRA001

Solution 3 (Casework)

Let's determine all $\alpha$ such that $\lfloor\alpha\rfloor + \lfloor 2\alpha\rfloor + \cdots + \lfloor n\alpha\rfloor$ is divisible by $n$ for every positive integer $n$ .

First, even integers work: if $\alpha = 2m$ where $m$ is an integer, then $\lfloor\alpha\rfloor + \lfloor 2\alpha\rfloor + \cdots + \lfloor n\alpha\rfloor = 2m + 4m + \cdots + 2mn = mn(n+1)$ which is divisible by $n$ .

Conversely, let $\alpha = k + \varepsilon$ where $k \in \mathbb{Z}$ and $0 \leq \varepsilon < 1$ . Then $\lfloor\alpha\rfloor + \lfloor 2\alpha\rfloor + \cdots + \lfloor n\alpha\rfloor = \frac{kn(n+1)}{2} + \lfloor\varepsilon\rfloor + \lfloor 2\varepsilon\rfloor + \cdots + \lfloor n\varepsilon\rfloor$

Case 1: $k$ is even. Then $\frac{kn(n+1)}{2}$ is divisible by $n$ , so $\lfloor\varepsilon\rfloor + \lfloor 2\varepsilon\rfloor + \cdots + \lfloor n\varepsilon\rfloor$ must be divisible by $n$ .

By induction, we can show $\lfloor n\varepsilon\rfloor = 0$ for all $n \geq 1$ , which implies $\varepsilon = 0$ . Thus $\alpha$ is an even integer.

Case 2: $k$ is odd. Using similar reasoning, we can derive that $\lfloor n\varepsilon\rfloor = n-1$ for all $n \geq 1$ , which implies $1-\frac{1}{n} \leq \varepsilon < 1$ for all $n$ . This is impossible.

Therefore, only even integers satisfy the condition.

~brandonyee

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]
+==Solution 2 (logic)==
+If we assume that a is a whole number, you could say that the last term is automatically a multiple of n, and from there you can add the first term and the penultimate term,  \( \alpha \)+\( \alpha \) * (n-1) to get n*\( \alpha \) so all the previous terms can be paired up likewise with 2*\( \alpha \)+\( \alpha \) * (n-2), ... and they will always add up too n* \( \alpha \). From there we know that when n is a even number such as 4 the sum is \( \alpha \)+2\( \alpha \)+3\( \alpha \)+4\( \alpha \). The last term is once again automatically divisible, but in sequences such as this, all the other terms can add up to the last term except for the term in the middle, in this case it would be 2\( \alpha \) , to solve this problem \( \alpha \) must always be even, so that n/2* \( \alpha \)=n* \( \alpha \) /2 and alpha is still a whole number. Following the pattern above, all the terms can be added to become n*whole number, and the term in the middle is n* \( \alpha \)/2, so \( \alpha \) always works when even.
+The number cannot have a fraction or every few sequences it will add a number, but, if the number n is the number direclly after the fraction adds one, like if the fraction was 1/3, and n was three, it would add one to the sequence, which would already be divisible by n, but one plus a multiple of n/2 (if \( \alpha \) is odd it will add 1/2n* \( \alpha \) to the sequence) is never a multiple of n unless n is one, or two, and if n was one, the fraction it would would accompany would be 1/1 which would be a whole number already. If n was 2 , then \( \alpha \) would be, an odd number +1/2, if \( \alpha \) was an odd number +1/2 then we can easily disprove it by setting n to 3, in which case it would be a multiple of n+2 , so n would have to be 2 for it to be divisible, but we already set n to 3, so it is impossible. Therefore there cannot be fractions added to the starting number.
+~[https://artofproblemsolving.com/wiki/index.php/User:LIUGRA001 LIUGRA001]
+==Solution 3 (Casework)==
+Let's determine all <math>\alpha</math> such that <math>\lfloor\alpha\rfloor + \lfloor 2\alpha\rfloor + \cdots + \lfloor n\alpha\rfloor</math> is divisible by <math>n</math> for every positive integer <math>n</math>.
+First, even integers work: if <math>\alpha = 2m</math> where <math>m</math> is an integer, then
+<cmath>\lfloor\alpha\rfloor + \lfloor 2\alpha\rfloor + \cdots + \lfloor n\alpha\rfloor = 2m + 4m + \cdots + 2mn = mn(n+1)</cmath>
+which is divisible by <math>n</math>.
+Conversely, let <math>\alpha = k + \varepsilon</math> where <math>k \in \mathbb{Z}</math> and <math>0 \leq \varepsilon < 1</math>. Then
+<cmath>\lfloor\alpha\rfloor + \lfloor 2\alpha\rfloor + \cdots + \lfloor n\alpha\rfloor = \frac{kn(n+1)}{2} + \lfloor\varepsilon\rfloor + \lfloor 2\varepsilon\rfloor + \cdots + \lfloor n\varepsilon\rfloor</cmath>
+Case 1: <math>k</math> is even. Then <math>\frac{kn(n+1)}{2}</math> is divisible by <math>n</math>, so <math>\lfloor\varepsilon\rfloor + \lfloor 2\varepsilon\rfloor + \cdots + \lfloor n\varepsilon\rfloor</math> must be divisible by <math>n</math>.
+By induction, we can show <math>\lfloor n\varepsilon\rfloor = 0</math> for all <math>n \geq 1</math>, which implies <math>\varepsilon = 0</math>. Thus <math>\alpha</math> is an even integer.
+Case 2: <math>k</math> is odd. Using similar reasoning, we can derive that <math>\lfloor n\varepsilon\rfloor = n-1</math> for all <math>n \geq 1</math>, which implies <math>1-\frac{1}{n} \leq \varepsilon < 1</math> for all <math>n</math>. This is impossible.
+Therefore, only even integers satisfy the condition.
+~brandonyee
 ==Video Solution(In Chinese)==
-https://www.youtube.com/watch?v=LW54i7rWkpI
+https://youtu.be/LW54i7rWkpI
 ==Video Solution==
@@ Line 21: / Line 140: @@
 ~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}}

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 23:05, 12 March 2025

Contents

Solution 1

Solution 2 (logic)

Solution 3 (Casework)

Video Solution(In Chinese)

Video Solution

Video Solution

Video Solution

See Also