Russian 77 puzzle
John Scholes
a_i <= 2 a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s =
b_1 a_1 + ... + b_n a_n with each b_i = 1 or -1, so that 0 <= s <= a_1.
NOTES
1. Please conceal spoilers in follow-ups (with Ctrl-L or plenty of blank
lines).
2. The problem is also shown on the website:
A hint goes up on the website after 24 hours, and a solution 24 hours
after that. The website also gives the earlier problems.
--
John Scholes
Mark J. Tilford
Is that all that's given? It looks like n=1, a_1 = 5, s=3 is a
counterexample.
--
-----------------------
Mark Jeffrey Tilford
til...@cco.caltech.edu
Jonathan Dushoff
: On Mon, 2 Nov 1998 08:34:41 +0000, John Scholes wrote:
: >Given non-negative real numbers a_1, a_2, ... , a_n, such that a_i-1 <=
: >a_i <= 2 a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s =
: >b_1 a_1 + ... + b_n a_n with each b_i = 1 or -1, so that 0 <= s <= a_1.
: Is that all that's given? It looks like n=1, a_1 = 5, s=3 is a
: counterexample.
S is not chosen in advance; it would be clearer if it said "some sum s".
In this case, the s that works is 5.
Jonathan
il...@isgtec.com
John Scholes <jsch...@kalva.demon.co.uk> wrote:
> Given non-negative real numbers a_1, a_2, ... , a_n, such that a_i-1 <=
> a_i <= 2 a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s =
> b_1 a_1 + ... + b_n a_n with each b_i = 1 or -1, so that 0 <= s <= a_1.
>
>
SPOILER
For n = 1 and n = 2 forming this sum is trivial (using 1 and (-1, 1) for the
b_i respectively.
We now assume that this is true up to n = k.
In the case of n = k+1 we have a_1,a_2,...,a_k-1,a_k,a_k+1. We replace a_k
and a_k+1 with a_k+1-a_k. This number must be between 0 and 2*a_k.
If it is between a_1 and 2*a_k we move a_k+1-a_k to a new position so that
the numbers will again be in ascending order. We now have a series of k
numbers which satisfies the original requirements, and thus the b_i can be
found.
If a_k+1-a_k < a_1, we discard it. We have a series of k-1 numbers which
satisfies the original requirements, and thus the b_i can be found for it.
If the sum s is less than a_k+1-a_k, we switch the signs of the b_i and add
a_k+1-a_k with coefficient 1; otherwise we just add a_k+1-a_k with coefficient
-1. Now, for the original series, the b_i will be the same ones as before for
a_1,a_2,...,a_k-1, -b for a_k, and b for a_k+1, where b is the coefficient
previously assigned to a_k+1-a_k.
__/\__
\ /
__/\\ //\__ Ilan Mayer
\ /
/__ __\ Toronto, Canada
/__ __\
||
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
John Scholes
>>a_i <= 2 a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s =
>>b_1 a_1 + ... + b_n a_n with each b_i = 1 or -1, so that 0 <= s <= a_1.
>Is that all that's given? It looks like n=1, a_1 = 5, s=3 is a
>counterexample.
I am not sure what you mean. If you take n=1, a_1=5, then you can take
b_1=1. That gives s=5 which satisfies the condition 0 <= s <= a_1.
Indeed the result is trivial for n=1 because you can always take b_1=1.
The givens are a_1, ... , a_n. You then try to find b_1, ... , b_n each
1 or -1 to give s in the required range.
--
John Scholes
Gerhard J. Woeginger
>From: John Scholes <jsch...@kalva.demon.co.uk>
>Subject: Russian 77 puzzle
>Date: Mon, 2 Nov 1998 08:34:41 +0000
>Given non-negative real numbers a_1, a_2, ... , a_n, such that a_i-1 <=
>a_i <= 2 a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s =
>b_1 a_1 + ... + b_n a_n with each b_i = 1 or -1, so that 0 <= s <= a_1.
Spoiler space
.
.
.
.
.
.
.
.
.
Proof by induction. The case n=1 is trivial, so let us assume n>1. Then the
numbers a_2,a_3,...,a_n form a sequence of length n-1 that fulfills the
conditions of the induction hypothesis. Hence, there exist coefficients b_i
such that the value x:= b_2a_2+...+b_na_n lies between 0 and a_2.
(a) If x>=a_1, then choose b_1=-1. The resulting sum s fulfills
0 <= s = x-a_1 <= a_2-a_1 <= a_1.
(b) If x < a_1, then choose b_1=+1 and reverse the signs of all other b_i.
The resulting sum fulfills 0 <= a_1-x <= a_1.
Remark: In this proof, we only need the condition a_i <= 2a_{i-1}.
Gerhard Woeginger (TU Graz, Austria)
___________________________________________________________
Gerhard J. Woeginger (gwo...@opt.math.tu-graz.ac.at)
Joseph W. DeVincentis
>a_i <= 2 a_i-1 for i = 2, 3, ... , n. Show that you can form a sum s =
>b_1 a_1 + ... + b_n a_n with each b_i = 1 or -1, so that 0 <= s <= a_1.
SPOILER
Proof by induction.
For n=1, you have s=a_1.
For n=2, since a_1 <= a_2 <= 2 a_1, then s=a_2 - a_1 is between
0 and a_1 inclusive.
For n=k+1, given that for n=k you can find a set of signs such that the
sum s is between 0 and a_1, inclusive, find that sum for the largest k
numbers (a_2 through a_k+1). This sum is given to be between 0 and a_2,
or thus between 0 and 2 a_1, inclusive. If it is greater than a_1,
subtract a_1 from it (assign b_1=-1), and you will have a sum between
0 and a_1. Otherwise, subtract it from a_1 (reverse the signs of the
other numbers and assign b_1=1) and you will have a sum between
0 and a_1.
/dev/joe