MathDB

Approximating with sums of subsets of a geometric series

Source: Balkan MO 2012 - Problem 3

April 28, 2012

inductioninequalitiesfloor functionlogarithmscombinatorics unsolvedcombinatorics

Problem Statement

Let

n

be a positive integer. Let

P_n=\{2^n,2^{n-1}\cdot 3, 2^{n-2}\cdot 3^2, \dots, 3^n \}.

For each subset

X

of

\emptyset

, we write

S_X

for the sum of all elements of

X

, with the convention that

S_{\emptyset}=0

where

\emptyset

is the empty set. Suppose that

y

is a real number with

0 \leq y \leq 3^{n+1}-2^{n+1}.

Prove that there is a subset

Y

of

P_n

such that

0 \leq y-S_Y < 2^n

Back to Problems View on AoPS