powers of 2

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

powers of 2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: BxMO 2025 P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

69 posts

#1 h Apr 26, 2025, 11:18 AM

Y by

Let $a_0, a_1, \ldots, a_{10}$ be integers such that, for each $i \in \{0,1,\ldots,2047\}$ , there exists a subset $S \subseteq \{0,1,\ldots,10\}$ with
$\sum_{j \in S} a_j \equiv i \pmod{2048}.$ Show that for each $i \in \{0,1,\ldots,10\}$ , there is exactly one $j \in \{0,1,\ldots,10\}$ such that $a_j$ is divisible by $2^i$ but not by $2^{i+1}$ .

Note: $\sum_{j \in S} a_j$ is the summation notation, for instance, $\sum_{j \in \{2,5\}} a_j = a_2 + a_5$ , while for the empty set $\varnothing$ , one defines $\sum_{j \in \varnothing} a_j = 0$ .

This post has been edited 1 time. Last edited by ErTeeEs06, Apr 26, 2025, 11:18 AM
Reason: -

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

47 posts

#2 h Apr 27, 2025, 11:33 AM

Y by

We claim this is true by induction on the number of variables ( $n=1$ is trivial.) Note that if we multiply all of them by some odd number, the restriction remains the same. Note that there must be an odd number in the set. Multiply the set to WLOG assume it is equal to 1. This means that the sums of the sets of the $n-1$ other numbers are either all odd numbers or all even numbers, but the empty set has an even sum so the sums of the sets are all evens, but that implies all of the other numbers are even, so we can divide all of them by 2 and proceed by induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9045 posts

#3 h Apr 27, 2025, 11:41 AM • 1 Y

Y by observer04

Another nice solution is via generating functions:
The condition implies (and is essentially equivalent to the fact) that
$(1+x^{a_0})(1+x^{a_1})\dots (1+x^{a_{10}})=1+x+x^2+\dots+x^{2047}$ whenever $x^{2048}=1$ i.e. $x$ is a $2048$ -th root of unity.
But for any such root $x \ne 1$ , the RHS is just $0$ , hence the LHS must vanish.
Plugging in $x=-1$ , we see that one $a_i$ must be odd.
Plugging in $x=i$ , we see that one $a_i$ must be even, but not a multiple of $4$ .
Plugging in a primitive eigth root of unity, we see that one $a_i$ must be a multiple of $4$ , but not of $8$ .
etc.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GeorgeMetrical123

8 posts

GeorgeMetrical123

#4 h May 2, 2025, 11:33 AM

Y by

There must be at least one odd element (otherwise, all sums are even and 1 cannot be made).
Multiplying the set with an odd constant still makes the statement hold true, so multiply it by the multiplicative inverse of an odd element so 1 is in the set. It suffices to proof the statement for this new set.
Because there are $2^{11}$ possible sum and the same amount of residue classes, no 2 sums can coincide. So look at the sum of $2^{11}-1$ . 1 must be used in this sum, otherwise we add 1 to the sum and we get a sum of 0,, coinciding with the sum of the empty set, contradiction.
So we can make $2^{11} -2$ without using a $1$ . Now, we again see that in order to make $2^{11}-3$ , we have to use a 1, otherwise we can make 2 $^{11}-2$ in two different ways. Inducting on this we see that we use a $1$ to make all the odd residues.
From this it follows that all the other numbers are even, as if there was another odd number, taking it out or adding it to a sum changes it's parity, which isn't possible.
Now looking at the other residues and dividing by 2, we can see that it's exactly the case for n-1 variables, meaning we are done by induction!
Q.E.D.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a