RMM2011, P 4, Day 2 - Arithmetic function

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

RMM2011, P 4, Day 2 - Arithmetic function

G H J

Reveal topic tags

number theory proposed

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.

15142 posts

#1 h Feb 26, 2011, 5:15 PM • 9 Y

Y by FlakeLCR, Davi-8191, tenplusten, AlastorMoody, DofL, Adventure10, kimyager, Mango247, and 1 other user

Given a positive integer $\displaystyle n = \prod_{i=1}^s p_i^{\alpha_i}$ , we write $\Omega(n)$ for the total number $\displaystyle \sum_{i=1}^s \alpha_i$ of prime factors of $n$ , counted with multiplicity. Let $\lambda(n) = (-1)^{\Omega(n)}$ (so, for example, $\lambda(12)=\lambda(2^2\cdot3^1)=(-1)^{2+1}=-1$ ).
Prove the following two claims:

i) There are infinitely many positive integers $n$ such that $\lambda(n) = \lambda(n+1) = +1$ ;
ii) There are infinitely many positive integers $n$ such that $\lambda(n) = \lambda(n+1) = -1$ .

(Romania) Dan Schwarz

Z K Y

The post below has been deleted. Click to close.

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

1354 posts

#2 h Feb 26, 2011, 5:54 PM • 2 Y

Y by Adventure10, Mango247

i)Use the identity $a^2 -1 = (a-1)(a+1)$ we can construct solutions:

$(15,16)$ --> $( {31^2} -1 , 31^2 )$ ---> $( (2 \times 31^2 -1)^2 -1 , (2 \times 31^2 -1)^2 )$ --- > ....

Z K Y

The post below has been deleted. Click to close.

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

1354 posts

#3 h Feb 26, 2011, 6:45 PM • 2 Y

Y by Adventure10, Mango247

ii) Choose an arbitrary $k$ such that $\lambda(k+1)= \lambda(k) =-1$

then look at the solutions of $(k+1)x^2 - ky^2 =1$ they are infinte and also
$\lambda((ky^2 ))= \lambda((k+1)x^2) =-1$

Z K Y

The post below has been deleted. Click to close.

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

1857 posts

Bugi

#4 h Feb 26, 2011, 7:38 PM • 1 Y

Y by Adventure10

i)
Let's assume that there are only finitely many integers n such that $\lambda(n)=\lambda(n+1)=1$

Then there exists an integer $N$ such that for all $a>N$ , $\lambda(a)=1 \Longrightarrow \lambda(a+1)=-1$

Take some even $a>N$ , then $(a-1,a+1)=1$ , and as $\lambda(a^2)=1$ , $\lambda(a-1)$ and $\lambda(a+1)$ have opposite signs. Continuing, we see that $\lambda(a+1)$ and $\lambda(a+3)$ have opposite signs, and we can do that until we reach $\lambda(a^2+1)$

Because of the assumption, we get $\lambda(a)=\lambda(a+2)=...=\lambda(a^2)=-1$ , which is impossible, contradiction with the assumption.

ii) Start as in i)

Let $a$ be an odd number, $a>2N$ , such that $\lambda(a)=-1$ . Then if both $\lambda(a+1)$ and $\lambda(a-1)$ are 1, we get that $\lambda(\frac{a-1}2)=\lambda(\frac{a+1}2)=-1$ , so we reach a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#5 h Feb 26, 2011, 8:50 PM • 3 Y

Y by FlakeLCR, Adventure10, kimyager

Of course, the question that immediately comes to mind is if one can find infinitely many consecutive triplets equal to $+1$ (respectively $-1$ ); then groups of four, etc., $k\geq 3$ . We have no answer as of yet for this ...

Z K Y

The post below has been deleted. Click to close.

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

801 posts

#6 h Feb 27, 2011, 9:23 PM • 1 Y

Y by Adventure10

Solution to (1)

Consider the sets $A=\{ m^2 -1 | m \in \mathbb{N} \}$ and $B = \{ m^2 | m \in \mathbb{N} \}$ . We define a natural number $n$ to be good if it satisfies that $\lambda(n)=\lambda(n+1)=1$ . If there are infinitely many $n \in A$ or $n \in B$ such that $n$ is good, then the claim is proven. Suppose that there are only finitely many good $n \in A$ and $n \in B$ . Since $A$ and $B$ are infinite, this implies that there are infinitely many $m$ such that $\lambda(m^2 -1) = \lambda(m^2 +1)=-1$ since otherwise one of the numbers $m^2 -1$ or $m^2$ is a good number. However, this implies that $\lambda(m^4 -1) = \lambda(m^2-1) \lambda (m^2 +1) = 1$ . Since $\lambda(m^4) = 1$ , this implies that $m^4 -1$ is good. Since there are infinitely many $m$ satisfying this condition, there are infinitely many good numbers.

This post has been edited 1 time. Last edited by SnowEverywhere, Mar 4, 2012, 12:07 AM

Z K Y

The post below has been deleted. Click to close.

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

433 posts

leshik

#7 h Mar 3, 2011, 8:44 PM • 2 Y

Y by Adventure10, Mango247

Well, the problem can be killed by using a little bit of "theory".
Pell"s equation $x^2-6y^2=1,$ which has infinitely many solutions implies the first part of the problem.
Equation $3x^2-2y^2=1,$ which also has infinitely many solutions takes care of the second part.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#8 h Mar 3, 2011, 8:55 PM • 3 Y

Y by FlakeLCR, Adventure10, Mango247

Indeed, those equations are verbatim listed among the alternative proofs in the official solution

Z K Y

The post below has been deleted. Click to close.

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

372 posts

#9 h Mar 20, 2011, 2:26 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

i) Note that $\lambda(x^2) = 1$ for all integers $x$ . Now note that either there exist infinitely many integers $\alpha$ such that $\lambda(\alpha^2 - 1) = 1$ or there don't. If infinitely many such $\alpha$ exist, then we are done. If only finitely many such $\alpha$ exist, then there exists a positive integer $M$ such that for all $\alpha > M$ , we have $\lambda(\alpha^2 - 1) = -1$ . This would imply that for all $\alpha > M$ , we have $\lambda(\alpha - 1) = -\lambda(\alpha + 1)$ , since $\lambda$ is clearly a multiplicative function. Then after a certain point, the values of $\lambda$ would cycle $1,1,-1,-1,1,1,-1,-1,\dots$ etc., so we are done.

ii) Note that $\lambda(px^2) = -1$ for all integers $x$ and primes $p$ . Now note that there are infinitely many integer solutions in integers $(r,s)$ to the equation $3s^2 - 2r^2 = 1$ ; if $(r,s)$ is a solution, then $(4r + 5s, 5r + 6s)$ is a solution, and $(1,1)$ is a solution. Thus we are done.

Z K Y

The post below has been deleted. Click to close.

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

2043 posts

Zhero

#10 h Mar 20, 2011, 2:29 AM • 3 Y

Y by Adventure10 and 2 other users

Another solution to part i:

Observe that $\lambda$ is multiplicative. Consider the numbers $2^{2^n} - 1, 2^{2^n}, 2^{2^n} + 1$ . If $\lambda(2^{2^n} + 1)$ is 1 for infinitely many positive integers $n$ , then $\lambda(2^{2^n}) = \lambda(2^{2^n} + 1) = 1$ holds for infinitely many $n$ . Otherwise, we may suppose that for all sufficiently large $n$ , $\lambda(2^{2^n} + 1) = -1$ . Hence, for any sufficiently large $n$ , if $\lambda(2^{2^n} - 1) = 1$ , since $\lambda(2^{2^n}) = 1$ , we are done; otherwise, we have $\lambda(2^{2^{n+1}} - 1) = \lambda(2^{2^n} - 1) \lambda(2^{2^n} + 1) = -\lambda(2^{2^n} - 1) = 1 = \lambda(2^{2^{n+1}})$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

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

AndreiAndronache

88 posts

AndreiAndronache

#11 h Mar 3, 2012, 6:36 PM • 1 Y

Y by Adventure10

Otherwise : i) We observe that $\lambda(a^2)=\lambda (6a^2)=1$ and we use the Pell's equation.

Z K Y

The post below has been deleted. Click to close.

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

314 posts

#12 h Oct 30, 2014, 5:00 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

i)First,assume contrary,now we have that for some $N$ ,it holds that if $a>N$ we have that if $f(a)=1$ then $f(a+1)=-1$ and opposite.Now,just pick ann odd integer such $f(n)=1$ (it is obvious that it exists) such that is larger than $2N$ .Now,we have that $f(n+1)=-1$ and $f(n-1)=-1$ ,so $f(n+1/2)=f(n-1/2)=1$ ,so we are finished.
ii) Just pick an odd n such that $f(n)=-1$ and the rest is the same.

Z K Y

The post below has been deleted. Click to close.

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

366 posts

#13 h Jan 21, 2015, 7:11 PM • 2 Y

Y by Adventure10, Mango247

Assume (i) is false. Then for $n>N$ , $\lambda(n)=\lambda(n+1)=1$ is false, so for $n>2N$ even, $\lambda(n)=\lambda(n+2)=-1$ is false. Take any $\lambda(n+1)=1$ , this implies an immediate contradiction. (ii) is same.

This is completely trivial

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#14 h Jan 21, 2015, 7:51 PM • 2 Y

Y by FlakeLCR, Adventure10

Not so fast ... you only know $\lambda(n)$ and $\lambda(n+2)$ are not both equal to $-1$ for even $n$ 's (thus at least one is equal to $1$ ). Who tells you that you can find some $\lambda(n+1)=1$ for an even $n$ ? For example, the alternating sequence, starting from an even value of $n>2N$ , given by $1,-1,1,-1,1,-1,\ldots$ has no $\lambda(n) = \lambda(n+1) =1$ , nor $\lambda(n) = \lambda(n+2) = -1$ for $n$ even. The problem is not that trivial.

Z K Y

The post below has been deleted. Click to close.

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

366 posts

#15 h Jan 21, 2015, 9:31 PM • 2 Y

Y by Adventure10, Mango247

mavropnevma I thought about addressing this in my first post but I thought it looked nicer as a one-liner

Just take $n+1 = x^2$ with $x$ odd. For the case where we prove (ii), take $n+1= 3x^2$ with $x$ odd.

Z K Y

The post below has been deleted. Click to close.

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

1980 posts

#16 h Sep 4, 2015, 11:26 PM • 3 Y

Y by mijail, Adventure10, Mango247

Cute problem but a little easy for RMM P4
a.) take $n=m^2$ and let $m^2+1=10d^2$ This is a Pell type equation and kills a.)
b.) take $n=2m^2$ let $2m^2+1=3t^2$ . This again is a Pell type equation killing b.)

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#18 h Aug 19, 2021, 3:59 PM

Y by

For part a) take $x^2-6y^2=1$ and for part b) $3x^2-2y^2=1$

This post has been edited 1 time. Last edited by Sprites, Aug 19, 2021, 3:59 PM

Z K Y

The post below has been deleted. Click to close.

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

892 posts

#19 h Apr 19, 2023, 8:05 AM • 1 Y

Y by Amy_Chen

a) If $(2k-1)^2$ and $(2k+1)^2$ do not satisfy the condition then $\lambda (\frac{(2k-1)^2+1}{2} \frac{(2k+1)^2+1}{2})$ is even. Thus $4k^4$ satisfies the conditions.

Z K Y

The post below has been deleted. Click to close.

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

4184 posts

#20 h May 11, 2023, 3:03 AM

Y by

Say that a positive integer $n$ is red if $\lambda(n)=1$ , and blue otherwise. Then, the problem is asking to prove that there are infinitely many consecutive red pairs and consecutive blue pairs.

Claim: For any positive integer $n$ , at least one of $(n^2-1,n^2)$ , $(n^2,n^2+1)$ , or $(n^4-1,n^4)$ is a consecutive red pair. Clearly, $n^2$ and $n^4$ are both red. Then, if either one of $n^2-1$ and $n^2+1$ are red, then the claim would be true. However, if they are both blue, then their product, $n^4-1$ , would be red, so the claim is still true.

This claim clearly solves part (i). For part (ii), assume FTSOC there exists $m$ such that all blue numbers past $m$ are isolated. Then, pick $n>777770m$ such that $n$ is odd and blue (e.g. pick a sufficently large power of 3 that is not a power of 9). Then, $n-1$ and $n+1$ are both red by our FTSOC claim. However, this means that $(n-1)/2$ and $(n+1)/2$ are both blue, and they are consecutive integers, which contradicts our FTSOC claim since they are both still larger than $m$ . Hence, we are done.

Z K Y

The post below has been deleted. Click to close.

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

54 posts

#21 h Dec 11, 2023, 8:15 PM

Y by

First note that there are infinitely many values of $n$ such that $\lambda(n)=\lambda(n+1)$ . Indeed, if starting from some point the values of $\lambda$ alternated, then $\lambda(x)$ would be determined by the parity of $x$ (for $x$ large enough), which is an obvious contradiction (odd squares and even squares both give a $\lambda$ value of $1$ ).

We can thus find infinitely many $m$ such that $\lambda(m-1)=\lambda(m+1)$ (multiplying by $2$ the claim above), so that $\lambda(m^2-1)=\lambda(m^2)=1$ . This proves (i)

Now we deal with part (ii) : take some $a$ divisible by $6$ . If $\lambda(a^2+2)$ (resp. $\lambda(a^2+3)$ ) is equal to $1$ , then $-1=\lambda(a^2/2)=\lambda(a^2/2 +1)$ (resp. $-1=\lambda(a^2/3)=\lambda(a^2/3 +1)$ . If not, then $-1=\lambda(a^2+2)=\lambda(a^2+3)$ .
This proves (ii). $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1742 posts

oVlad

#22 h Dec 13, 2023, 11:11 AM

Y by

mavropnevma wrote:

Of course, the question that immediately comes to mind is if one can find infinitely many consecutive triplets equal to $+1$ (respectively $-1$ ); then groups of four, etc., $k\geq 3$ . We have no answer as of yet for this ...

This is a fairly state-of-the-art question. For $k=3$ Hildebrand [1] showed that all eight patters on $\pm 1$ occur infinitely often and much later Matomaki et al. [2] have shown that these patters occur with a positive frequency (I am talking about the generalised problem, but it turns our that the hardest part of the proof is dealing with the runs in question, namely $k$ consecutive 1's or -1's).

Unless some major advancements have been made in the last 5-ish years, it is still unkown whether all the patters for $k=4$ are present infinitely often. Of course, it is expected that for any $k{}$ , any pattern of signs occurs infinitely often - even more so, these patterns occur with equal frequencies - as stated by Chowla's conjecture.

I'm not entirely sure, but there are some connections between Chowla's conjecture and the Riemann Hypothesis, so perhaps it is completely out of reach as of now, let alone for an olympiad problem.

[1] A. Hildebrand – On consecutive values of the Liouville function. Enseign. Math. (2) 32 (1986), 219–226.
[2] K. Matomaki, M. Radziwill and T. Tao – Sign patterns of the Mobus and Liouville functions. Preprint, arXiv:1509:01545.

Edit: I just realised that the second paper I linked wasn't even published at the time of the competition. How time flies...

This post has been edited 2 times. Last edited by oVlad, Dec 13, 2023, 11:15 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a