Finding the smallest positive integer from the fancy number

Finding the smallest positive integer from the fancy number

Problem 2.

A positive integer is called fancy if it can be expressed in the form

Also Read:

where a1,a2, … , a100 are non-negative integers that are not necessarily distinct. Find the smallest positive integer n such that no multiple of n is a fancy number.

(APMO 2016 problem 2)

Answer: The answer is n = 2101 – 1.

Solution. Let k be any positive integer less than 2101 – 1. Then k can be expressed in binary notation using at most 100 ones, and therefore there exists a positive integer r and non-negative integers a1, a2, … , ar such that \leq 100 and k = 2a1 + … + 2ar. Notice that for a positive integer s we have:

This shows that k has a multiple that is a sum of r + s powers of two. In particular, we may take s=100-r\geq 0, which shows that k has a multiple that is a fancy number. We will now prove that no multiple of n = 2101 – 1 is a fancy number. In fact we will prove a stronger statement, namely, that no multiple of n can be expressed as the sum of at most 100 powers of 2.

For the sake of contradiction, suppose that there exists a positive integer c such that cn is the sum of at most 100 powers of 2. We may assume that c is the smallest such integer. By repeatedly merging equal powers of two in the representation of cn we may assume that

where r\leq 100 and a1 < a2 < … < ar are distinct non-negative integers. Consider the following two cases:

  • If ar \geq 101, then 2ar – 2ar – 101 = 2ar – 101n. It follows that 2a1 + 2a2 + … + 2ar-1+ 2ar – 101 would be a multiple of n that is smaller than cn. This contradicts the minimality of c.
  • If ar \leq 100, then {a1,…, ar} is a proper subset of {0, 1, …, 100} Then

This is also a contradiction.

From these contradictions we conclude that it is impossible for cn to be the sum of at most 100 powers of 2. In particular, no multiple of n is a fancy number.

×

Like us on Facebook

%d bloggers like this: