Maths Olympiad Prep

Library / /465 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

We call a natural number nn balanced if n=1n=1 or if nn can be written as the product of an even number of (not necessarily distinct) prime factors. For every pair (a,b)(a, b) of positive integers, let P(x)=(x+a)(x+b)P(x)=(x+a)(x+b).
a) Are there two different positive integers aa and bb such that all numbers P(1),P(2),,P(50)P(1), P(2), \ldots, P(50) are balanced?
b) Prove: If P(m)P(m) is balanced for all positive integers mm, then a=ba=b.

Solution

a) The answer is "Yes". For P(x)P(x) to be balanced, x+ax+a and x+bx+b must either both have an even or both have an odd number of prime factors. However, there are only 2502^{50}, i.e., a finite number of different patterns among 50 consecutive natural numbers. Therefore, there exist two natural numbers mm and nn such that they are the starting points of two identical such patterns. With a=m1a=m-1 and b=n1b=n-1, the balance of P(1),P(2),,P(50)P(1), P(2), \ldots, P(50) follows.
b) We assume that there are two different natural numbers aa and bb under the given condition; without loss of generality, let b>ab>a. Then for every natural number m>am>a, P(ma)=m(m+ba)P(m-a)=m(m+b-a) is balanced. The evenness or oddness of the number of prime factors thus occurs periodically with period bab-a for natural numbers greater than aa. In particular, all multiples of bab-a are of the same type, provided they are greater than aa. However, such a multiple k(ba)k(b-a) has one fewer prime factor than 2k(ba)2k(b-a), leading to a contradiction with the assumption. Therefore, a=ba=b.
Hint: The contradiction can be derived in various ways. Often, theorems about prime numbers in arithmetic sequences or suitable square numbers were used. For part a), 4 points were awarded, and for part b), 6 points were awarded.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.