IMC 2017 Problem 3

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

IMC 2017 Problem 3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

1476 posts

math90

#1 h Aug 2, 2017, 2:01 PM • 7 Y

Y by GoJensenOrGoHome, test20, Davi-8191, Rounak_iitr, Adventure10, Mango247, mathematicsy

For any positive integer $m$ , denote by $P(m)$ the product of positive divisors of $m$ (e.g $P(6)=36$ ). For every positive integer $n$ define the sequence
$a_1(n)=n,\qquad a_{k+1}(n)=P(a_k(n))\quad (k=1,2,\dots,2016)$ Determine whether for every set $S\subset\{1,2,\dots,2017\}$ , there exists a positive integer $n$ such that the following condition is satisfied:

For every $k$ with $1\leq k\leq 2017$ , the number $a_k(n)$ is a perfect square if and only if $k\in S$ .

This post has been edited 2 times. Last edited by jlacosta, Sep 13, 2022, 6:12 PM
Reason: Fixing format

Z K Y

The post below has been deleted. Click to close.

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

29 posts

ArmOl

#2 h Aug 2, 2017, 8:21 PM • 2 Y

Y by XbenX, Adventure10

Let $P_1(x)=x, P_2(x)=\frac{x(x+1)}2, \dots, P_{k+1}=\frac {P_k(x)(P_k(x)+1)} 2$ . For prime $p$ , we have $a_k(p^a)=p^{P_k(a)}.$ It remains to prove that for any $e=(e_1, \dots, e_n)\in (F_2)^n$ there exists an integer $a>0$ with $(P_1(a), \dots, P_n(a))\equiv e (mod\,\, 2).$

Lemma 1: $\frac{a(a+1)}2 \equiv \frac{b(b+1)}2 (mod\,\, 2^k)$ iff $a\equiv b (mod\,\, 2^{k+1})$ or $a\equiv -b-1 (mod\,\, 2^{k+1})$ .

Lemma 2: $(P_1(a), \dots, P_n(a))\equiv (P_1(b), \dots, P_n(b)) (mod\, 2)$ iff $a\equiv b (mod\,\, 2^n)$ .
Easy to prove using Lemma 1 repeatedly: $P_n(a)\equiv P_n(b) (mod\, 2) \implies P_{n-1}(a)\equiv P_{n-1}(b) (mod\, 4) \implies \dots \implies P_{1}(a)\equiv P_{1}(b) (mod\, 2^n)$ .

Thus the map $a\in F_{2^n}\mapsto (P_1(a), \dots, P_n(a))\in (F_2)^n$ is injective and therefore surjective, hence the result.

This post has been edited 2 times. Last edited by ArmOl, Aug 2, 2017, 8:23 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a