We call a natural number balanced if or if can be written as the product of an even number of (not necessarily distinct) prime factors. For every pair of positive integers, let .
a) Are there two different positive integers and such that all numbers are balanced?
b) Prove: If is balanced for all positive integers , then .
Solution
a) The answer is "Yes". For to be balanced, and must either both have an even or both have an odd number of prime factors. However, there are only , i.e., a finite number of different patterns among 50 consecutive natural numbers. Therefore, there exist two natural numbers and such that they are the starting points of two identical such patterns. With and , the balance of follows.
b) We assume that there are two different natural numbers and under the given condition; without loss of generality, let . Then for every natural number , is balanced. The evenness or oddness of the number of prime factors thus occurs periodically with period for natural numbers greater than . In particular, all multiples of are of the same type, provided they are greater than . However, such a multiple has one fewer prime factor than , leading to a contradiction with the assumption. Therefore, .
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.