341celestine, anda problem innoru vaati pakreya da? the nrs are 1 or -1
This time's Pan-African Olympiad had a problem that goes:
If, 1 \le i \le 2000, \ x_i \in \{-1,1\} is it possible to have
x_1 x_2 + x_2x_3+x_3x_4+....+x_{2000} x_1 = 999
-
UP 0 DOWN 0 0 15
15 Answers
9yes
assuming x1 = x2=......=x
2000x2 =999
x = √999/2000 which is a feasible solution
is it so simple ?
3419superb Q
theres an interesting derivation by which we can prove that no odd value is feasible
9oh ok i thout i shall wait for juniors anyway
let sum of 2000 terms = X
here
the product of those 2000 terms is positive ( why ? )
so there are even no of (-1)s and (1)s in the 2000 terms of (x1x2 , x2x3 ....)
let there be α 1 s and 2000-α -1s
then X = 2 ( α - 1000 )
9condescending
hmm nice learnt new vocabulary
1. act in a superior way: to behave toward other people as though they are less important or less intelligent than you are
2. make concessions for others: to do something that you would normally consider yourself too important or dignified to do
did u mean 1 or 2 sir ?
341lets stick to math here :D
there's one technique that I have seen used elsewhere that came to my mind for solving this problem.
If you first consider all the xi's to be 1
Then the sum will be 2000.
Now, one by one we flip the signs to reach a possible configuration of xi's to attain 999.
But each time we flip the sign of a variable, the sum either increases by 4, or decreases by 4 or remains the same.
Hence the sum changes in multiples of 4. So modulo 4 the sum remains same. 2000 and 999 are not equal modulo 4 (so that's a stronger result here!)