Maths Olympiad Prep

Library / /10 of 14

Number theory Difficulty 6.4 National Olympiad Find the answer

Let nn to be a positive integer. Given a set {a1,a2,,an}\{ a_1, a_2, \ldots, a_n \} of integers, where ai{0,1,2,3,,2n1},a_i \in \{ 0, 1, 2, 3, \ldots, 2^n -1 \}, i\forall i, we associate to each of its subsets the sum of its elements; particularly, the empty subset has sum of its elements equal to 00. If all of these sums have different remainders when divided by 2n2^n, we say that {a1,a2,,an}\{ a_1, a_2, \ldots, a_n \} is *nn-complete*.

For each nn, find the number of *nn-complete* sets.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let n n be a positive integer, and consider the set of integers {a1,a2,,an} \{ a_1, a_2, \ldots, a_n \} where each ai a_i is an element of the set {0,1,2,,2n1} \{ 0, 1, 2, \ldots, 2^n - 1 \} . We associate each subset of this set with the sum of its elements, and the empty subset is associated with the sum 0 0 .

A set {a1,a2,,an} \{ a_1, a_2, \ldots, a_n \} is defined to be n n -complete if all possible sums have distinct remainders when divided by 2n 2^n .

### Problem Analysis

For an n n -complete set, each of the 2n 2^n possible sums of subsets corresponds to a distinct remainder when divided by 2n 2^n . Therefore, it must cover all remainders from 0 0 to 2n1 2^n - 1 .

#### Step 1: Counting Subsets

There are 2n 2^n subsets of a set with n n elements, including the empty subset. Each subset sum must have a unique remainder when divided by 2n 2^n .

#### Step 2: Remainder and Full Rank Condition

The requirement for distinct remainders implies a linear independence condition on the binary representations of a1,a2,,an a_1, a_2, \ldots, a_n when viewed as n n -bit vectors. The sum of subsets can be thought of as linear combinations of these vectors.

For linear combinations to result in distinct sums modulo 2n 2^n , the set of vectors must be linearly independent over Z/2Z \mathbb{Z}/2\mathbb{Z} . This means the binary matrix formed by the vectors has full rank n n .

#### Step 3: Calculating the Number of Sets

The number of n n -complete sets thus corresponds to the number of ways to select n n linearly independent vectors over the field Z/2Z \mathbb{Z}/2\mathbb{Z} (a dimension n n vector space). This is known to be 2n(n1)/2 2^{n(n-1)/2} . Each selection of vectors corresponds directly to an n n -complete set.

### Conclusion

Therefore, the number of n n -complete sets is:

2n(n1)/2 \boxed{2^{n(n-1)/2}}

This completes the solution process for determining the number of n n -complete sets as defined in the problem.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.