IMO ShortList 1998, combinatorics theory problem 2
Source: IMO ShortList 1998, combinatorics theory problem 2
October 22, 2004
combinatoricsinvariantalgorithmIMO Shortlist
Problem Statement
Let be an integer greater than 2. A positive integer is said to be attainable if it is 1 or can be obtained from 1 by a sequence of operations with the following properties:
1.) The first operation is either addition or multiplication.
2.) Thereafter, additions and multiplications are used alternately.
3.) In each addition, one can choose independently whether to add 2 or
4.) In each multiplication, one can choose independently whether to multiply by 2 or by .
A positive integer which cannot be so obtained is said to be unattainable.
a.) Prove that if , there are infinitely many unattainable positive integers.
b.) Prove that if , all positive integers except 7 are attainable.