They copied their problem!

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

They copied their problem!

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: FKMO 2025 P1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

185 posts

#1 h Mar 29, 2025, 10:03 AM

Y by

Sequence $a_1, a_2, a_3, \cdots$ satisfies the following condition.

(Condition) For all positive integer $n$ , $\sum_{k=1}^{n}\frac{1}{2}\left(1 - (-1)^{\left[\frac{n}{k}\right]}\right)a_k=1$ holds.

For a positive integer $m = 1001 \cdot 2^{2025}$ , compute $a_m$ .

This post has been edited 5 times. Last edited by pokmui9909, Mar 29, 2025, 10:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

185 posts

#3 h Mar 29, 2025, 10:19 AM

Y by

Exactly the same idea as KMO 2024 P6. I don't know why they made this.

This post has been edited 1 time. Last edited by pokmui9909, Mar 29, 2025, 10:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

21 posts

#4 h Mar 29, 2025, 12:27 PM

Y by

What’s the answer? I got Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

59 posts

#5 h Mar 29, 2025, 12:45 PM

Y by

Well, if @above is correct, I'm pretty screwed.
Actually I'm screwed anyways, so who cares? :/

solution sketch

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

185 posts

#6 h Mar 29, 2025, 12:50 PM

Y by

I got $-2^{2024}$ , too.

This post has been edited 1 time. Last edited by pokmui9909, Mar 29, 2025, 12:50 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

59 posts

#7 h Mar 29, 2025, 12:51 PM

Y by

thank god

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

21 posts

#9 h Mar 29, 2025, 1:12 PM

Y by

huh I got the same thing about the sum of a_d and stuff

I guess I miscalculated something after that

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

103 posts

#10 h Mar 29, 2025, 1:13 PM • 1 Y

Y by Chaiataops

pokmui9909 wrote:

I got $-2^{2024}$ , too.

Me too

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#11 h Mar 30, 2025, 1:11 PM

Y by

I got $-2^{2024}$ too, Yeah this is definitely the answer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

19 posts

Mapism

#13 h Mar 31, 2025, 4:04 PM

Y by

$\sum_{k=1}^{n}\frac{1}{2}\left(1 - (-1)^{\left[\frac{n}{k}\right]}\right)a_k=1=\sum_{k=1}^{n-1}\frac{1}{2}\left(1 - (-1)^{\left[\frac{n-1}{k}\right]}\right)a_k \implies \sum_{k=1}^{n}\left((-1)^{\left[\frac{n-1}{k}\right]} - (-1)^{\left[\frac{n}{k}\right]}\right)a_k=0$ $\left(\left[\frac{n}{k}\right]\ne \left[\frac{n-1}{k}\right]\iff k|n\right) \implies \sum_{d|n}(-1)^{\frac{n}{d}}a_d=0$
Now it's easy to see that $a_{2^\alpha}=2^{\alpha+1}$ so if $n$ is a power of $2$ then $\sum_{d|n}a_d=n$ .

Claim: $\sum _{d|n}a_d = \begin{cases} n & \text{if } n \text{ is a power of 2} \\ 0 & \text{else } \end{cases}$ Proof: Let $n=2^\alpha t$ where $t$ is odd.
$0=\sum_{d|2^\alpha t}(-1)^{\frac{2^\alpha t}{d}}a_d=\left(\sum_{d|2^{\alpha-1} t}a_d\right)-\left(\sum_{d|t}a_{2^\alpha d}\right)\implies \sum_{d|2^{\alpha-1} t}a_d=\sum_{d|t}a_{2^\alpha d}$
We proceed by induction, for the base case note that for any odd $t, \sum _{d|t}a_d =0$ . Assume that $\sum_{d|2^{\alpha-1} t}a_d=0$ , then $\sum_{d|2^{\alpha} t}a_d=\sum_{d|2^{\alpha-1} t}a_d+\sum_{d|t}a_{2^\alpha d}=0+0=0$ and this proves the claim.

Now define $g(n)=\sum _{d|n}a_d = \begin{cases} n & \text{if } n \text{ is a power of 2} \\ 0 & \text{else } \end{cases}$ By the mobius inversion formula $a_n=\sum _{d|n}\mu(d)g\left(\frac{n}{d}\right)$ so
$a_{1001\cdot 2^{2025}} =\mu(1001)g\left(2^{2025}\right)+\mu(2002)g\left(2^{2024}\right)=-2^{2025}+2^{2024}=-2^{2024}$ And the proof is complete.

This post has been edited 5 times. Last edited by Mapism, Apr 1, 2025, 6:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

50 posts

#14 h Apr 14, 2025, 3:22 AM

Y by

We have $\sum_{k=1}^n\frac12(1-(-1)^{\lfloor\frac nk\rfloor})a_k-\sum_{k=1}^{n-1}\frac12(1-(-1)^{\lfloor\frac{n-1}k\rfloor})a_k=0$ from the problem condition. Since $\lfloor\frac nk\rfloor\ne\lfloor\frac{n-1}k\rfloor$ when $k|n$ , we have $\sum_{k|n}(-1)^\frac nka_k=0$ for $n\ge2$ by cancelling out terms.

We claim, $f(n)=\sum_{k|n}a_k=0$ when $n$ is not a power of $2$ . We prove by inducting on $v_2(n)$ , where the base case $v_2(n)=0$ is trivial since the exponent is always odd and $n\ge3$ . Now we assume all $v_2(n)=x-1$ satisfies the assertion, we prove for $v_2(n)=x$ . Indeed, we have
$\begin{align*} 0=\sum_{k|n}(-1)^\frac nka_k&=\sum_{k|\frac n2}(-1)^\frac nka_k+\sum_{k|\frac n{2^x}}(-1)^\frac n{2^xk}a_{2^xk}\\ &=f\left(\frac n2\right)-\sum_{k|\frac n{2^x}}a_{2^xk}\\ &=-\sum_{k|\frac n{2^x}}a_{2^xk} \end{align*}$ so $f(n)=f\left(\frac n2\right)+\sum_{k|\frac n{2^x}}a_{2^xk}=0.$ For $n=2^x$ , we have $a_n=2^{x-1}$ since $a_1=1,a_2=1$ and $a_{2^x}=\sum_{i=0}^{x-1}(-1)^{2^{x-i}}a_{2^i}=\sum_{i=0}^{x-1}a_{2^i}=2^{x-1}$ by induction.

Let $c=2^{2024}$ , now we have $a_{2c}=c$ , and for $k\in\{7,11,13\}$ we have $a_{2ck}+a_{2c}=f(2ck)-f(ck)=0,$ so $a_{2ck}=-c$ . For $k\ne l\in\{7,11,13\}$ we have $a_{2ckl}+a_{2ck}+a_{2cl}+a_{2c}=f(2ckl)-f(ckl)=0$ so $a_{2ckl}=c$ . And finally $a_{2002c}+c=a_{2002c}+\sum_{k\ne l\in\{7,11,13\}}a_{2ckl}+\sum_{k\in\{7,11,13\}}a_{2ck}+a_{2c}=f(2002c)-f(1001c)=0$ so $a_m=-2^{2024}$ and we are done. \qed

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

634 posts

cursed_tangent1434

#15 h Yesterday at 4:53 PM

Y by

We claim that the answer is $a_m=-2^{2024}$ . In order to show this, we first need the following key claim.

Claim : For all positive integers $n$ ,
$\sum_{\substack{d\mid n \\ (2\mid \frac{n}{d})}}a_d = \sum_{\substack{d\mid n \\ (2\nmid \frac{n}{d})}}a_d$

Proof : We know that for all positive integers $n$ and $k$ , $\left \lfloor \frac{n}{k} \right \rfloor = \left \lfloor \frac{n-1}{k} \right \rfloor$ if $k \nmid n$ and $\left \lfloor \frac{n}{k} \right \rfloor = \left \lfloor \frac{n-1}{k} \right \rfloor +1$ if $k \mid n$ . Using this we note,
$\begin{align*} \sum_{k=1}^{n-1} \frac{1}{2}\left(1-(-1)^{\lfloor\frac{n-1}{k}\rfloor}\right)a_k &= \sum_{k=1}^{n-1} \frac{1}{2}\left(1-(-1)^{\lfloor\frac{n}{k}\rfloor}\right)a_k \\ \sum_{\substack{d\mid n\\ (d<n)}} \frac{1}{2}\left(1-(-1)^{\lfloor\frac{n-1}{d}\rfloor}\right)a_d &= \sum_{d\mid n} \frac{1}{2}\left(1-(-1)^{\lfloor\frac{n}{d}\rfloor}\right)a_d \\ \sum_{\substack{d\mid n\\ (d<n)}}\frac{1}{2}\left(1-(-1)^{\frac{n}{d}-1}\right)a_d &= \sum_{d\mid n} \frac{1}{2}\left(1-(-1)^{\frac{n}{d}}\right)a_d \\ \sum_{\substack{d\mid n \\ (2\mid \frac{n}{d})}}a_d &= \sum_{\substack{d\mid n \\ (2\nmid \frac{n}{d})}}a_d \end{align*}$ as desired.

From here, we resort to bash which is not too bad since $m=1001\cdot 2^{2025} = 7 \cdot 11 \cdot 13 \cdot 2^{2025}$ . We first note that for any distinct odd primes $p,q,r$ we have,
$a_p+a_1=0$ so $a_p=-1$ and
$a_{pq}+a_p+a_q+a_1=0$ so $a_{pq}=1$ and
$a_{pqr}+a_{pq}+a_{qr}+a_{pr}+a_p+a_q+a_r+a_1=0$ so $a_{pqr}=-1$ . The rest we approach via induction.

First we claim that for all positive integers $m$ , $a_{2^m}=2^{m-1}$ . For this note the obvious base cases $a_1=a_2=1$ . Now, assuming the result for all $1 \le i \le m-1$ ,
$a_{2^m}=a_{2^{m-1}}+a_{2^{m-2}}+\dots + a_2+a_1 = \sum_{i=0}^{m-1}2^i+1=2^{m-1}$ as desired.

Next note,
$a_{2^mp}+a_{2^m}=\sum_{i=0}^{m-1}\left (a_{2^i}+a_{2^ip}\right)=0$ so $a_{2^mp}=-a_{2^m}=-2^{m-1}$ .

We then show via induction that $a_{2^mpq}+a_{2^mp}+a_{2^mq}+a_{2^m} = 0$ for all $m \ge 0$ . The base of $m=0$ being trivial, we note
$a_{2^mpq}+a_{2^mp}+a_{2^mq}+a_{2^m} = \sum_{i=0}^{m-1}\left(a_{2^ipq}+a_{2^ip}+a_{2^iq}+a_{2^i}\right) = 0$ which completes the induction. As a result, it follows that $a_{2^mpq}=2^{m-1}$ . Using an entirely similar inductive approach we may also show that $a_{2^mpqr}+a_{2^mpq}+a_{2^mqr}+a_{2^mpr} + a_{2^mp}+a_{2^mq}+a_{2^mr}+a_{2^m}=0$ from which it then follows that $a_{2^mpqr}=-2^{m-1}$ for all positive integers $m$ and distinct odd primes $p,q$ and $r$ .

Applying this result for the given integer we have that,
$a_{7\cdot 11 \cdot 13 \cdot 2^{2025}}=-2^{2024}$ as claimed.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a