Generally, we see that the prodoct of two balanced numbers is, as well as the product of two nonbalanced numbers, balanced whereas the product of a balanced and a nonbalanced number is nonbalanced. To each sequence of integers, we assign a balance-sequence of $b$'s and $n$'s, denoting which numbers of the sequence are balanced and nonbalanced, respectively (for example, the balance-sequence of $1,2,3,4$ would be $b,n,n,b$). In part $(a)$, we want to prove that there exist two different sequences, namely the sequences $a+1, a+2, \ldots, a+50$ and $b+1, b+2, \ldots, b+50$, of consecutive positive integers and length $50$ that have the same balance-sequences. Therefore, we consider $2^{50}+1$ pairwise different sequences of length $50$. As there only exist $2^{50}$ different balance-sequences of length $50$, among the considered sequences there exist at least two differnt sequences having the same balance-sequence, which proves the desired. For part $(b)$, assume that there exist integers $a<b$ such that $P(n)$ is balanced for all positive integers $n$. We see that the numbers $(a+n)$ and $(b+n)$ are for any $n$ either both balanced or both nonbalanced. In particular, we see that all sequences of the form $a_n=a_0+n(b-a)$ with $a_0\geqslant a$ either consist of balanced or of nonbalanced integers only. However, there can't exist an arithmetic sequence that only contains balanced numbers because by Dirichlet, each arithmetic sequence contains infinitely many primes (and primes are obviously nonbalanced). The only remaining possibility would be that all integers are nonbalanced - but this is obviously wrong. A contradiction. Thus, $P(n)$ is balanced for all positive integers $n$ if and only if $a=b$. In my opinion, this problem is not very difficult but very nice .

Another solution for (b): Suppose such $a,b$ existed with $a > b$. This implies that for any integer $n > b$, $n$ is balanced if and only if $n + (b-a)$ is balanced, and hence $n$ is balanced if and only if $n + k(b-a)$ is for any positive integer $k$. Pick $M$ such that $M(b-a)$ is greater than $b$. Then $M(b-a)$ is balanced iff $2M(b-a)$ is balanced. But the quotient of these two numbers is prime, so one is balanced and one isn't. Contradiction. Re the above: arithmetic sequences contain infinitely many primes only if the common difference is relatively prime to the first term, so you still have a bit of work to do at the end.

where do you get the +1 in $2^{50} + 1?$ Thank you.

And yet another solution for part b: The problem is equivalent to showing that if $x(x+a)$, $a \geq 0$, is balanced for all sufficiently large $x$, then $a=0$. Suppose for the sake of contradiction that $a \neq 0$. Then it is true that for all sufficiently large $y$, if $x = ay$, $ay(ay+a) = a^2 y(y+1)$ is balanced, that is, $y(y+1)$ must be balanced for all sufficiently large $y$. But this is impossible, since the solutions to the Pell's equation $a^2 - 2b^2 = 1$ include those with arbitrarily large $a$ and $b$, and setting $y = 2b^2$ for some sufficiently large $b$ will make $y(y+1)$ imbalanced. EDIT: I jumped to Pell equations and did not notice the even easier finish (by andersonw.) We have that $y(y+1)$ is balanced for all sufficiently $y$, which implies by induction that past a certain point, each natural number is either always balanced or always imbalanced, which is absurd (concrete examples: $n^2$ is balanced, $2n^2$ is not, and we can make $n$ as large as we want.)

Wow. Although, I am pretty bad at hard problems (esp. problems that are not geometry), after seeing that solution to part (a), I think that this problem should definitely have been on the IMO. Either as problem 2 or with part (a) alone as problem 4.

; Part a) P(x)= (x+a)(x+b) Define f(x) = 0 if P(x) is balanced and f(x) = 1 if P(x) is not balanced. Consider the following sequence: f(n+1), f(n+2)....... f(n+50). Observe that there are only $2{}^5{}^0$ distinct sequences because the sequence is made up of 50 digits, each 0 or 1 by the definition of f(x). On the other hand, there are infinitely many natural numbers, so by pigeonhole principle, there is another sequence, say f(m+1), f(m+2),....... f(m+50) that is identical to the original sequence. Hence, if n+i is balanced for a positive integer i less than or equal to 50, then so is m+i and vice versa. Therefore f[(m+i)(n+i)] = 0 for all i less than or equal to 50. Take a=m, b=n and we are done. This isn't my own solution

my solution: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=350097&p=2223521#p2223521 for part a it is similar to the solutions posted above but a little different for the part b.

it's easy to prove that every pair of numbers whose difference is $2(a-b)$ are both divine or not divine(sufficiently large),but in sequence ${2(a-b)k+1}$ there exists infinitely many prime numbers they are all not divine numbers.so any term of this sequence is not divine.but we can choose a prime $p$ in it,then $p^2$ is a divine number in this sequence, a contradiction.hence our problem is proved.

Let $\Omega(n)$ be the number of prime divisors of $n$ counting multiplicity. Then for (a), we need $\Omega(x+a) \equiv \Omega(x+b)$ (mod $2$), for $x=1, ..., 50$. Now, consider $I_k = (\Omega(k+1),...,\Omega(k+50)) \in \mathbb{Z}_2^{50}$. There are only $2^{50}$ possibilities, so we must have $I_a=I_b$ for some $a$ and $b$. These work. For part (b), simply note that $\Omega(kd)=\Omega(k)+\Omega(d)$ is constant mod $2$ for $k$ big enough, and so $\Omega$ eventually becomes constant, clearly false.

another solution for part b: Assume that $a \neq b$. We know that $P(a-2b) = (a+a-2b)(b+a-2b)=(2a-2b)(a-b)$ must be balanced. Then $2(a-b)^2$ must be a balanced number that is not equal to 0, since a does not equal b. This is clearly a contradiction, since $(a-b)^2$ is divisible by an even number of primes so $2(a-b)^2$ is divisible by an odd number of primes.

This solution requires that $b < a < 2b$, which might not be the case...

April wrote: A positive integer $N$ is called balanced, if $N=1$ or if $N$ can be written as a product of an even number of not necessarily distinct primes. Given positive integers $a$ and $b$, consider the polynomial $P$ defined by $P(x)=(x+a)(x+b)$. (a) Prove that there exist distinct positive integers $a$ and $b$ such that all the number $P(1)$, $P(2)$,$\ldots$, $P(50)$ are balanced. (b) Prove that if $P(n)$ is balanced for all positive integers $n$, then $a=b$. Proposed by Jorge Tipe, Peru For part I, for each $n$ assign a coordinate $(\varepsilon_1, \dots, \varepsilon_{50})$ with $\varepsilon_i \in \{0,1\}$ such that $\varepsilon_{i}=\Omega(i+n) \pmod{2}$. By pigeonhole principle, it is possible to find $1 \le a<b \le 2^{50}+1$ with both being assigned the same coordinate. Hence $P(x)=(x+a)(x+b)$ satisfies $P(i)$ is balanced for $1 \le i \le 50$. For part II, let consider $Q(x)=x(x+c)$ for an integer $c>0$, such that $Q(x)$ is balanced for all sufficiently large $x>0$. Let $x=cN^2-c$ and $(N, M)$ be a solution of the pell's equation $N^2-2M^2=1$. Hence $Q(x)=2(cNM)^2$, so $Q$ is not balanced! $\blacksquare$

There's another nice way of seeing part $(b)$, as follows. Impatient; then jump to last paragraph. If $b>2a$; then, letting $x=b-2a$; we have $P(x)=2(b-a)^2$; which can't be balanced. Hence, $b\leq 2a$. In fact, $b<2a$; since, for $b=2a$; $x=2a$ gives an impossibility. Having done so, notice that, $1<\frac{x+b}{x+a}<2$. Hence, one may try to make this $m/n$; where $(m,n)=1$, $n<m<2n$ (easy to do). These steps will yield $\ell(\ell+1)$ is balanced, for every $\ell$, sufficiently large. There is a quick way of doing this. $\ell(\ell+1)$ is balanced; and $(\ell+1)(\ell+2)$ is balanced; yields, $\ell(\ell+2)$ is balanced. Similarly, this, together with, $(\ell+2)(\ell+3)$ is balanced yields $\ell(\ell+3)$ is balanced. Go like this, and get $\ell(\ell+\ell)$ is balanced at the end; which is impossible. $\blacksquare$

You don't need direchlet's for this problem... Part b): Suppose $a<b$, substitute x-a in for x, we only consider x larger than a. Thus, $x$ is balanced iff $x+b-a$ is balanced. We see that $(b-a)^{2k}$ is balanced(for any k), since $(b-a)|(b-a)^{2k}$ we see that all multiples of b-a are balanced for arbitrarily large numbers. Thus both $(b-a)^{2k+1}$ and $[2(b-a)]^{2k+1}$ are balanced which is a contradiction.

Martin N. wrote: Generally, we see that the prodoct of two balanced numbers is, as well as the product of two nonbalanced numbers, balanced whereas the product of a balanced and a nonbalanced number is nonbalanced. To each sequence of integers, we assign a balance-sequence of $b$'s and $n$'s, denoting which numbers of the sequence are balanced and nonbalanced, respectively (for example, the balance-sequence of $1,2,3,4$ would be $b,n,n,b$). In part $(a)$, we want to prove that there exist two different sequences, namely the sequences $a+1, a+2, \ldots, a+50$ and $b+1, b+2, \ldots, b+50$, of consecutive positive integers and length $50$ that have the same balance-sequences. Therefore, we consider $2^{50}+1$ pairwise different sequences of length $50$. As there only exist $2^{50}$ different balance-sequences of length $50$, among the considered sequences there exist at least two differnt sequences having the same balance-sequence, which proves the desired. For part $(b)$, assume that there exist integers $a<b$ such that $P(n)$ is balanced for all positive integers $n$. We see that the numbers $(a+n)$ and $(b+n)$ are for any $n$ either both balanced or both nonbalanced. In particular, we see that all sequences of the form $a_n=a_0+n(b-a)$ with $a_0\geqslant a$ either consist of balanced or of nonbalanced integers only. However, there can't exist an arithmetic sequence that only contains balanced numbers because by Dirichlet, each arithmetic sequence contains infinitely many primes (and primes are obviously nonbalanced). The only remaining possibility would be that all integers are nonbalanced - but this is obviously wrong. A contradiction. Thus, $P(n)$ is balanced for all positive integers $n$ if and only if $a=b$. In my opinion, this problem is not very difficult but very nice . I had a virtually identical solution for part b, however, I do not believe the finish here provided is correct. Martin N. wrote: However, there can't exist an arithmetic sequence that only contains balanced numbers because by Dirichlet, each arithmetic sequence contains infinitely many primes (and primes are obviously nonbalanced). Dirichlet does not assure that ANY arithmetic progression will have primes, just that any arithmetic progression where the first term and $(b-a)$ are relatively prime will have an infinite number of primes. However, this is an easy fix. Assume that any progression where the initial term $a_0$ is such that $gcd(a_0,b-a)=1$ has all terms non-balanced. Now, take some $x>b$ such that $gcd(x,b-a)=1$. $x^2=a_0$ (mod $b-a$) for some $a_0$ fulfiling $gcd(a_0,b-a)=1$. That implies that $x^2$ is in one of the sequences we previously assumed to be all non-balanced, but all squares are balanced, a contradiction. Is this correct?

Define a function $f$ from the positive integers to the set $\{-1,1\}$, such that $f(n) = 1$ if $n$ is balanced, and $f(n) = -1$ if $n$ is unbalanced. Note that $f$ is multiplicative. (a) For any positive integer $k$, define its $balance-sequence$ $t_1, t_2, t_3, ....$ by the relation $t_n = f(n+k)$. Note that for any finite $m$, the finite sequence $t_1, t_2, ......, t_m$ has at most $2^m$ distinct possibilities. As there are infinitely many positive integers, there must exist distinct integers $a$ and $b$ for whom this finite sequence is the same. And we're done. (b) Suppose there were to exist distinct positive integers $a$ and $b$ satisfying the given property. WLOG, $b > a$. Let $p = b - a$. Then, we have that $f(n) = f(n+p)$ for all $n > a$. For any $r$ large enough such that $rp > a$, $f(r+1)f(p) = f((r+1)p) = f(rp) = f(r)f(p)$, implying $f(r+1) = f(r)$ i.e. $f$ eventually becomes constant. This is clearly not true, hence giving the required contradiction.

(a) What a troll. Clearly, $(a+i)(b+i)$ is balanced if and only if either $a+1$ and $b+1$ are both balanced or if both are not balanced. Let $f(x)$ be 1 if $x$ is balanced, and 0 otherwise. Let $S(x)$ be the ordered vector $(f(x+1),\ldots,f(x+50))$. Since $S(x)$ is a binary vector of length $50$, and there are only $2^{50}$ such vectors, we know that there exists $1\le a<b \le 2^{50}+1$ such that $S(a)=S(b)$. Then, $f(a+i)=f(b+i)$ for all $1\le i \le 50$. (b) It is not hard to see that $k^2$ is balanced, since the exponents of all primes in the prime factorization is even, and $2k^2$ is not balanced for all $k$. We claim there must exist $k,\ell,n$ such that $n+a=k^2$ and $n+b=2\ell^2$. This means $2\ell^2-k^2=b-a$, and this has infinitely many solutions if $b-a\not = 0$ since this is a Pell's equation. Then, $n+a$ is balanced and $n+b$ is not balanced, so $(n+a)(n+b)$ is not balanced, contradiction. Hence, $a=b$.

a) Consider the sequence $\{a_i\}$ where $a_i$ is the remainder mod 2 of the number of prime factors of $(i+a)(i+b)$. As there are only $2^{50}$ possible consecutive tuples of $50$ elements, we can find $i,j$ such that $a_{i+k}=a_{j+k}$ for $k=1,\ldots 50$. Then, just take $a=i,b=j$ b) Suppose the contrary, and WLOG $b>a$. Then, we get that $i\equiv j\pmod {b-a}\implies a_i=a_j$. So, consider all numbers $1\pmod {b-a}$. By Dirichlet, there exists a prime in this sequence. However, there also exists a square (i.e. $1$). So, all $a_i$ in this sequence must be both 0 and 1, which is a contradiction. So, $a=b$, as desired.

It can be generalized for any multiplicative function $\mathbb{N}\to \{-1,1\}$, instead of the Liouville one. Defining $$\lambda(n):=\begin{cases} +1 & n \text{ is balanced}\\ -1 & \text{ otherwise} \end{cases} $$we obtain exactly the Liouville function. It is multiplicative, which follows by the definition. Only this property of $\lambda$ is used below, so the claim holds for any such multiplicative function. a) Put $m$ instead of $50$. It's enough to find $x,y\in\mathbb{N},x\neq y$ with $\lambda(x+i)=\lambda(y+i), i=0,1,\dots,m-1$. Consider the ordered $m$-tuple of $-1$'s and $+1$'s, $P(x):=( \lambda(x),\lambda(x+1),\dots,\lambda(x+m-1) ), x\in\mathbb{N}$. Since $P(x)$ takes only finitely many values, there are two distinct $x,y$ with $P(x)=P(y)$. b) It says $\lambda(x)$ is not periodic. For the sake of getting contradiction, suppose it is periodic and for some $N, T\in\mathbb{N}$ it holds $\lambda(n)=\lambda(n+T), \forall n\ge N$. The multiplicativity of $\lambda$ yields $$\lambda(2x)=\lambda(2)\lambda(x)= -\lambda(x) \,\,\,\,\,\,\,\,\,\,(*)$$We choose $x=kT$ for some large enough natural $k$. Then $\lambda(2x)=\lambda(x+kT)=\lambda(x)$, but on the other side, it contradicts $(*)$. Remark. For each $x\in\mathbb{N}$, $P(x):=( \lambda(x),\lambda(x+1),\dots,\lambda(x+m-1) )$ is a sign pattern in $\{-1,1\}^m$. There is a more general result of Terence Tao & Co, stating that for each sign pattern in $\{-1,1\}^m$ , it equals $P(x)$ for a set of natural numbers $x$ of positive lower density. https://terrytao.wordpress.com/2015/09/06/sign-patterns-of-the-mobius-and-liouville-functions/

Note that $a $ and $b$ are balanced if and only if $ab $ is balanced. Another observation is that a integer is balanced if and only if $2|\Omega(n)$ or if it is equal to 1. Now a)It suffices to show that $\Omega (a+i) $ and $\Omega(b+i) $ have the same parity for $1 \le i\le 50$ This is clear by the pigeonhole principle:Choose $x_k (a) $ to be a sequence defined by the remainder obtained when $\Omega (a+1) $ is divided by $2$ Clearly $x_k (a) \in [0,1] $,so we are done. b)Just choose $a>b $ and proceed then $\Omega (b (b-a)) \equiv \Omega (2b (b-a)) \equiv 1+\Omega (b (b-a)) \pmod 2$ which is absurd.

Part A: Let $B(x)$ be a function $\mathbb{Z}^+\Rightarrow \{0,1\}$ so that $B(x)=0$ if $x$ is balanced, and $1$ otherwise (when $x$ is a product of an odd number of not necessarily distinct primes). For a positive integer $x$, let the summary of $x$ be the $50$-digit binary string found from concatenating the values $B(x+1), B(x+2), \ldots, B(x+50)$ in that order. Notice that there are only a finite number ($2^{50}$) of summaries, and thus by the Pigeonhole Principle there are two distinct positive integers with the same summary, say $a$ and $b$. We claim this pair of $a$ and $b$ works. For any $1\le i\le 50$, notice that by construction $B(a+i)=B(b+i)$, and thus the parity of (not necessarily distinct) prime factors in $a+i$ and $b+i$ is the same. The number of (not necessarily distinct) prime factors in $P(i)=(a+i)(b+i)$ is equal to the sum of the number (not necessarily distinct) prime factors of $a+i$ and $b+i$, which is even as they have the same parity. Part B: Suppose for contradiction that $a\neq b$. WLOG let $b>a$. Let two integers $j$ and $k$ be similar if $B(j)=B(k)$ If $P(x)$ is balanced for all positive integers $x$, then $a+x$ and $b+x$ is similar. Therefore, any two sufficiently large numbers that differ by $b-a$ are similar, and so there is an infinite arithmetic progression with common difference $b-a$ so that all terms are similar. Divide every term of this arithmetic progression by the GCD of all the terms to make the new GCD equal to $1$. This ensures that all terms are relatively prime with the new common difference. This does not change the similarity condition. By Dirichlet's Theorem, this new arithmetic sequence contains a prime, and thus $B(i)=1$ must be true for all terms $i$ in the progression. Let $p$ be the smallest prime that does not divide the common difference of the progression. Consider all terms that are divisible by $p$, which create a new arithmetic sequence (whose common difference is $p$ times the original). Divide each term by $p$, creating a new arithmetic progression with the same common difference as the last one. It is clear that all terms are relatively prime with the common difference. According to our previous result, we must have $B(i)=0$ for all $i$ in this progression. However, by Dirichlet's theorem, this progression must contain a prime, contradiction.

$\textbf{For part (a)}$. define $f(n)$ to be the parity of the number of not necessarily distinct prime divisors of $N$. Then, let $s(a)$ be the vector in $\{0,1\}^{50}$ of the values of $f()$ applied to $a+1,a+2,\ldots a+50$. By pigeonhole, there exist integers $a,b$ such that $s(a)=s(b)$, so clearly $P(x)=(x+a)(x+b)$ is balanced at $P(1),\ldots P(50)$. $\textbf{For part (b)}$. Let $x\equiv y$ if $f(x)= f(y)$. Then, assume $b>a$, then we have that $a+1\equiv b+1 \equiv 2b-a+1 \equiv 3b-2a+1 \equiv \cdots \equiv (k+1)b-ka+1$. Thus, we have an infinite arithmetic progression starting at $a+1$ with difference $b-a$ of congruent integers. In general this is impossible for any sequence $a+nd$. WLOG, $\gcd(a,d)=1$, because dividing out keeps all numbers congruent. By dirichlet's, this sequence contains a prime. Then, takes some $p$ relatively prime to $a,d$, and consider a new sequence $S'$ which takes $n$ such that $a+nd \equiv 0 \pmod{p} \Longrightarrow n\equiv -d^{-1}a\pmod{p}$. Divide $S'$ by $p$, which also satisfies dirichlet's conditions, so there's another prime $q\in S'$. Thus, both $p,pq \in \{a+nd\}$ but $f(p)\neq f(pq)$ and we're done.

Let $a_n=1$ if $n$ is balanced and $0$ otherwise. For part a, consider the possible values of $(a_{k+1},a_{k+2},\ldots,a_{k+50})$ for some $k \geq 1$. Clearly there are $2^{50}$, which is finite, so by infinite pigeonhole there must exist some $m\neq n$ such that $(a_{m+1},\ldots,a_{m+50})=(a_{n+1},\ldots,a_{n+50})$. Then, as $(x+a)(x+b)$ is balanced iff $a_{x+a}=a_{x+b}$, taking $a=m,b=n$ finishes. $\blacksquare$ For part $b$, suppose otherwise, so we have $a_{x+a}=a_{x+b}$ for some $a \neq b$. Letting $k=|a-b|$, it follows that for sufficiently large $n$, $(a_n)$ is periodic with periodicity $k$. But then by Dirichlet we may choose some sufficiently large prime $p$ such that $p \equiv 1 \pmod{k}$, so $p^2 \equiv p \pmod{k} \implies a_p=a_{p^2}$. However, it is clear that $p$ isn't balanced while $p^2$ is, which is a contradiction. Thus we must have $a=b$, as desired. $\blacksquare$ Part a is one of those "number theory" problems where you don't have to actually do any number theory

Note that the product of two balanced numbers, or two unbalanced numbers is balanced and the product of one balanced number and one unbalanced number is unbalanced. Let $f$ be a sequence where $f_i$ $1$ is $i$ is unbalanced and $0$ otherwise. Note that by pigeonhole principle, there must be two consecutive subsequences of $a$ with size $50$ which are congruent. Thus, let the subsequences be $f_{a+1},f_{a+2},\dots,f_{a+50}$ and $f_{b+1},f_{b+2},\dots,f_{b+50}$ then $P(1),P(2),\dots,P(50)$ will be balanced. If $P(n)$ is balanced for all $n$ then unless $a=b$, the sequence is periodic, which is a contradiction because there exists a prime in the form $p=k(b-a)+1$, but $1$ is balanced so $p$ is balanced, contradiction.

Let $\Omega(n)$ be the number of not necessarily distinct prime factors of $n$. The condition is equivalent to $\Omega(a) \equiv \Omega(b) \pmod{2}$. (a) Consider the set $\{\Omega(m+1) \pmod{2}, \Omega(m+2) \pmod{2}, \cdots , \Omega(m+50) \pmod{2}\}$ for the first $2^{50}+1$ numbers. By PhP, two of these sets must be the same giving us the desired construction for this part. (b) Assume not and WLOG $b>a$. If we can find a $k> a$ with $\Omega(k+1) \not \equiv \Omega(k+2) \pmod{2}$, then taking $n=k(b-a)+b-2a > 0$ we would get that $$\Omega(k(b-a)+b-2a+a) \equiv \Omega(k+1)+\Omega(b-a) \not \equiv \Omega(k+2) + \Omega(b-a) \equiv \Omega(k(b-a)+b-2a+b) \pmod{2},$$would give the desired contradiction. To prove this exists, consider the set $\{\Omega(a+2) \pmod{2}, \Omega(a+3) \pmod{2}, \cdots , \Omega(2a+4) \pmod{2}\}$. Note that $\Omega(a+2) \not \equiv \Omega(2a+4) \pmod{2}$. This means that at some point in the set, a consecutive pair of terms must switch or else the sequence would be constant a contradiction. Taking this pair of terms, say $\Omega(a+2+r) \pmod{2}$, and $\Omega(a+3+r) \pmod{2}$, we can take $k=a+1+r$ which works. This gives the desired contradiction, so $a=b$ and we are done.

(a) Notice that for $(x+a)(x+b)$ to be balanced, both $x+a$ and $x+b$ are both balanced or unbalanced. But such $a$ and $b$ clearly exists by pigeonhole. (b) Let $a>b$. Suppose $(x+a)(x+b)$ is balanced for all $x$. Again, this implies $x+a$ and $x+b$ are both balanced or both unbalanced. Thus, we will consider a function $\text{GARY} \colon \mathbb{N} \to \{0,1\}$ where $\text{GARY}(n)=0$ if $n$ is balanced and $1$ otherwise. Thus $\text{GARY}(x+a)= \text{GARY}(x+b)$ which implies $\text{GARY}$ is periodic with difference $d:=a-b$. If $d=1$ then this is clearly contradiction since $\text{GARY}$ is surjective. Thus, assume $d>1$. Let $p \equiv 1$ (mod $d$) be a prime. Notice that $\text{GARY}(p)=1$. But, we see $p^2 \equiv 1$ (mod $d$) and $\text{GARY}(p^2)=0$ which contradicts period $d$.

Call two positive integers equally balanced if they are both balanced or both unbalanced. Call two lists of positive integers equally balanced if they have the same number of elements and their pairs of elements at corresponding positions are equally balanced. Part a. Consider all intervals of $50$ positive integers. There are a maximum of $2^{50}$ possible intervals that are pairwise not equally balanced, so by pigeonhole, there must be two distinct intervals that are equally balanced, say $(a+1,a+2,\dots,a+50)$ and $(b+1,b+2,\dots,b+50)$. Then $(a,b)$ suffices. Part b. Suppose that $P(n)$ is balanced when $a<b$. Then $a+1$ and $b+1$ are equally balanced, $a+2$ and $b+2$ are equally balanced, etc. Then let $k=a(b-a)+1$. Since $k^2$ is balanced, $k^2+(b-a)$ is balanced, $k^2+2(b-a)$ is balanced, etc. But since $k^2$ and $b-a$ are coprime, this violates Dirichlet's(since this arithmetic sequence cannot have an infinite number of primes, which are unbalanced, anymore), contradiction.

Note that $(x+a)(x+b)$ is balanced if and only if $x+a$ and $x+b$ are both balanced or both unbalanced. Therefore, for part (a), we essentially want to prove that there exist two runs of 50 consecutive positive integers with the same corresponding "balancedness" states. However, there are only $2^{50}$ different balancedness states for 50 consecutive positive integers, so we can obviously find two runs of 50 consecutive positive integers with the same balancedness states, which solves part (a). For (b): we claim that balancedness is not eventually periodic (i.e. there does not exist $p$ such that $n$ is balanced if and only if $n+p$ is balanced for all sufficiently large $n$). Suppose otherwise, and let $p$ be the period. Then, $p^{2n}$ is obviously balanced, so if $n$ is large enough so that $p^{2n}$ enters the "eventually periodic" part, $2p^{2n}$ is also balanced, which is a contradiction since $2p^{2n}$ has one extra factor compared to $p^{2n}$. $P(n)$ being balanced for all $n$ is basically saying that starting from two different indices $a$ and $b$ with $b>a$ and get the same balancedness sequence starting at either one. This would require the balancedness sequence to be eventually periodic with period $b-a$, contradiction if $b\neq a$, so we are done.

Solved with GeNuAlCo_pi and Jbmm2004 Part a) Let, $f(x) = 0$ if the multiset of prime divisors of $x$ have even cardinality and $1$ otherwise. Clearly, $f(xy) = 0$ iff $f(x) = f(y)$. Let, $v_k = (f(1+k), f(2+k), \dots, f(50+k))$. There are finitely many possibilities for $v_k$. So we must get, $a,b$ s.t. $v_a = v_b$. Then clearly, all of $P(1), \dots, P(50)$ will be balanced. Part b) FTSOC, let, $a \neq b$. WLOG let, $b > a$ and $d = b-a$. So, $P(x) = (x+a)(x+a+d)$. Now, if we take $x+a = kd$ for large $k$ then $P(x) = d^2k(k+1)$. Now, if $P(x)$ is balanced iff $f(k) = f(k+1)$. But $f(p) = 1$ for prime $p$ and $f(k^2) = 0$. So $f$ can't be eventually constant. SO we are done. $\blacksquare$

Nice problem! Never thought an NT problem would be a few liner lol For convenience, denote unbalanced as 1 and balanced as 0. It's obvious that a number n=ab is balanced iff a and b have the same parity; in particular, by pigeonhole, if there's some string S_x=f(x+1),f(x+2),...,f(x+50), there exist two numbers $1\le c,d<2^50+1:S_c=S_d$, which readily implies each of P(1)=f(c+1)f(d+1),...,P(50) are balanced. As for part b, we prove the contrapositive: Suppose $a\ne b$ and we prove P(n) is not always balanced. Indeed, since i^2,2j^2 are balanced and unbalanced respectively, Pell's equation j^2-i^2=b-a has infinite solutions; in particular, 2j^2=n+b, i^2=n+a has different parity, so P(n)=(n+a)(n+b) is unbalanced.

This is the greatest problem of our generation, and the generation after that, and after that, and so on forever. For (a), this is equivalent to having two distinct sequences $a, a + 1, \dots, a + 50$ and $a, a + 1, \dots, a + 50$ such that $a + i$ has an odd number of prime divisors iff $b + i$ does. This is evidently possible by pigeonhole. Now for (b), FTSOC suppose that $P(x) = (x+a)(x+b)$ is always balanced for $a > b$. This implies that $k$ has the same parity of number of prime divisors as $k + (a - b)$ for $k > b$. However, comparing $3a^{1434}(a - b)$ and $4a^{1434}(a - b)$ gives a contradiction.

Easy but beautiful question My solution is no different

Throughout my solution, we will use the definition $$t(n)=\left( \sum_{\text{$p$ primes}} v_p(n) \right) \pmod{2}$$Note that $P(n)$ balance if and only if $t(n+a)=t(n+b)$. We also let $p_1=2,p_2=3,...$ be the sequence of all primes. For (a), consider the tuples $T_i=(t(i+1),t(i+2),...,t(i+50))$ for all integers $i\in \{1,2,...,2^{50}+1 \}$. Note, that there are only $2^{50}$ possibilities of the value $T_i$. As we considering $2^{50}+1$ tuples, by Pigeonhole Principle, there must be two indices $i<j$ in which $T_i=T_j$. This would later implies the polynomial $P(x)=(x+i)(x+j)$ satisfies the asked property. For (b), we have $t(n+a)=t(n+b)$ for all positive integers $n$. For the sake of contradiction, assume WLOG $b>a$. Notice that for all integers $k>\frac{a}{b-a}$, we have $$t(k(b-a)-a+a)=t(k(b-a)-a+b)\iff t(k(b-a))=t((k+1)(b-a)) \iff t(k)=t(k+1).$$This means, there exists positive integer $M>0$ such that the infinite sequence $t(M),t(M+1),...$ is constant. This is a contradiction as we can choose $d$ large enough such that $p_1p_2p_3...p_{2d+1}\ge M$, and $r$ large enough such that $r^2\ge M$. Hence, we must have $a=b$.

Every positive integer can be expressed as a product of either an even or odd number of not necessarily distinct primes. Naturally we can create a binary string $S$ from the integers $\{2,\dots,n,\dots\}$ using this definition. The first part asks to prove that there are two equal substrings of size $50$ at distinct positions in $S$, which is clearly true: there are infinitely many positions but finitely many substrings. The second part essentially states $S$ is periodic with period $d=|a-b|$ provided that $a\ne b$. However values $v\equiv 1\pmod d$ will hit infinitely many primes and yet also hit squares, and thus at these positions $S$ would contain both ones and zeros, a contradiction. $\blacksquare$

April wrote: A positive integer $N$ is called balanced, if $N=1$ or if $N$ can be written as a product of an even number of not necessarily distinct primes. Given positive integers $a$ and $b$, consider the polynomial $P$ defined by $P(x)=(x+a)(x+b)$. (a) Prove that there exist distinct positive integers $a$ and $b$ such that all the number $P(1)$, $P(2)$,$\ldots$, $P(50)$ are balanced. (b) Prove that if $P(n)$ is balanced for all positive integers $n$, then $a=b$. Proposed by Jorge Tipe, Peru Let $\Omega(n)$ be the number of not necessarily distinct prime factors of $n$. The condition is equivalent to $\Omega(a+n) \equiv \Omega(b+n) \pmod{2}$. (a) Consider the set $\{\Omega(m+1) \pmod{2}, \Omega(m+2) \pmod{2}, \cdots , \Omega(m+50) \pmod{2}\}$ for $2^{50}+1$ numbers. By PhP two of these sets must be the same giving us the desired construction for this part. (b) Assume not and WLOG $a>b$. Taking $n=m^2-b$ we have $\Omega(m^2+(a-b)) \equiv 0 \pmod{2}$ Taking $n=m^2+a-2b$ we have $\Omega(m^2+2(a-b)) \equiv 0 \pmod{2}$ Taking $n=m^2+2a-3b$ we have $\Omega(m^2+3(a-b)) \equiv 0 \pmod{2}$ Now be indaction we get that $\Omega(m^2+kc) \equiv 0 \pmod{2}$ for every $m,k$ with $c=a-b$ If we take $m=k=c$ we get $\Omega(c^2+c*c) \equiv \Omega(2c^2) \equiv \Omega(2)\equiv 1\pmod{2}$ Contradiction. So $a=b$

a) Consider the sequence of the parity of the number of prime divisors of each integer. There are a finite number of values for a consecutive group of $50$ terms to occupy, so at some point two groups of $50$ terms with indices $a + 1, a + 2, a + 3 \cdots$ and $b + 1, b +2 , b + 3 \cdots$ must have the same values, so we are done. b) Assume there exists some $a \neq b$ such that $P(n)$ is always balanced. For all sufficiently large $k$, we can find $x$ such that $\frac{x + b}{x + a} = \frac{k + 1}{k}$ (this reduces to $kx + kb = (k +1)x + (k + 1)a$, which has solutions whenever $\frac ab < \frac{k}{k + 1}$, which happens for sufficiently large $k$). Thus, this implies that for all sufficiently large $k$, $k$ and $k + 1$ have the same prime divisor parity, which is impossible since it would be imply that all sufficiently large $k$ have the same prime divisor parity, but this is obviously false since we can construct arbitrarily large integers with either prime divisor parity.

Really nice problem!