Maths Olympiad Prep

Library / /14 of 144

Number theory Difficulty 7.6 National olympiad, round 2 Find the answer

Let n2n \ge 2 be an integer, and let AnA_n be the set An={2n2kkZ,0k<n}.A_n = \{2^n - 2^k\mid k \in \mathbb{Z},\, 0 \le k < n\}. Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of AnA_n .

[i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let's start by analyzing the set An={2n2kkZ,0k<n} A_n = \{ 2^n - 2^k \mid k \in \mathbb{Z},\, 0 \le k < n \} . This set consists of the elements of the form 2n1,2n2,,2n2n1 2^n - 1, 2^n - 2, \ldots, 2^n - 2^{n-1} .

We are tasked to find the largest positive integer that cannot be expressed as the sum of one or more (not necessarily distinct) elements of this set An A_n .

### Step 1: Analyze the Elements of An A_n

Each element 2n2k 2^n - 2^k for k=0,1,,n1 k = 0, 1, \ldots, n-1 , can be rewritten as:
2n1,2n2,2n4,,2n2n1 2^n - 1, 2^n - 2, 2^n - 4, \ldots, 2^n - 2^{n-1}

These elements can also be represented as:
a0=2n1,a1=2n2,a2=2n4,,an1=2n2n1 a_0 = 2^n - 1, \quad a_1 = 2^n - 2, \quad a_2 = 2^n - 4, \ldots, \quad a_{n-1} = 2^n - 2^{n-1}

### Step 2: Identify the Pattern

Every element is of the form 2nm 2^n - m where m m is a power of 2 less than 2n 2^n . We conclude that each element in An A_n can produce sums where some of them overlap as these elements have a geometric pattern.

### Step 3: Determine the Unreachable Number

We need to find the largest integer that cannot be formed by sums of elements in An A_n .

1. Recognize that each of the elements is a reduction from 2n 2^n based on a subset that forms a geometric series 1,2,4,,2n1 1, 2, 4, \ldots, 2^{n-1} .
2. The total sum of the powers is 2n1 2^n - 1 , equivalent to the choice of taking one of each form.
3. If that sum does not form zero, that number will not be able to be formed besides excluding multiples of the smallest number with gaps.

### Step 4: Mathematical Conclusion

Due to the nature and manipulation of these subsets' sums, the highest number that cannot be expressed will rely on gaps in this series of sums. This leads to the Frobenius number in elements expressed by a sequence not fully distinct.

Define the largest integer unreachable by these sequences of decreasing sums as:
(n2)2n+1 (n-2)2^n + 1

Therefore, the largest positive integer that cannot be represented as the sum of elements from An A_n is:
(n2)2n+1 \boxed{(n-2)2^n + 1}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.