Prove that with every given 10 primes $p_1,p_ 2,\ldots,p_{10}$,there always exist 10 number which are not simultaneously equal to $0$, get one of three values: $-1$, $0$, $1$ satisfied that: $\sum\limits_{ i=1}^{10}a_ip_i$ is a multiple of 1000
Making a $1,0,-1$ linear commbination of primes a multiple of $1000$
1
$\begingroup$
combinatorics
-
0Please post one question at a time, or explain the relationship you perceive between the questions. – 2012-12-10
-
0thanks for your comment. i have just edited:). To Gerry Myerson: that is symbol familiar in my country, so sorry, edited of course – 2012-12-10
2 Answers
4
The pigeonhole principle takes care of this. There are $2^{10}-1=1023$ non-empty sums, so two are congruent modulo $1000$, etc., etc.
-
0please more specific, if there are two sum congruent modulo 1000, what do you do next? for example, if $p_1$ exists in two sum, how can you contruct a sum satisfies that $a_1=1$ – 2012-12-10
-
1I'm intentionally leaving some work for you to do. Don't you want the pleasure of solving a problem on your own? – 2012-12-10
-
1ok.i proved. thanks. – 2012-12-10
-
0Good. Now *you* can post a complete solution here. After a while, you can even accept your own solution. – 2012-12-10
3
Following the guide of Gerry Myerson, i think here is solution of this problem. First, we'll built 1,0 linear combination of 10 primes. There are $2^{10}$ combination except for one Zero combination, so we get $2^{10}-1=1023$ non zero combination. Then exists two of them congruents modulo 1000, take their subtraction, we have 1,0,-1 linear combination which is multiple of 1000. This is not so difficult problem, and we can replace "prime" hypothesis by "abitrary integer". and the number 1000 can replaced by $1
-
0Out of curiosity: What is the linear combination in this case? – 2012-12-10
-
0@A.Schulz, the linear combination (or combinations --- there could be several) will depend, of course, on which $10$ primes are given. – 2012-12-10
-
0@GerryMyerson: Oh I see. I misread the question. I thought the $p_i$s are the first 10 primes. – 2012-12-11
-
0@A.Schulz, for the first $10$ primes, you can take $2+3-5$, with all the other coefficients zero, or $3+5+11-19$, or any of a number of other solutions. – 2012-12-11
-
0@Schulz:don't let your intention to hypothesis "prime". this solution can apply for any 10 integer^^ – 2012-12-11