MathDB

Two conditions for colouring natural numbers

Source: Bulgarian National Olympiad 2012 Problem 2

May 21, 2012

geometric sequencenumber theoryprime factorizationcombinatorics proposedcombinatorics

Problem Statement

Prove that the natural numbers can be divided into two groups in a way that both conditions are fulfilled: 1) For every prime number

p

and every natural number

n

, the numbers

p^n,p^{n+1}

and

p^{n+2}

do not have the same colour. 2) There does not exist an infinite geometric sequence of natural numbers of the same colour.