Let $(x_1,x_2,x_3,\dots,x_{77})$ be positive numbers. Use the pigeonhole principle to show that, if $\sum_{i=1}^{77}{x_{i}} = 140$, then there exist $j$ and $k$ such that $\sum_{i=j}^{k}{x_{i}} = 13$.
Asked
Active
Viewed 352 times
2
-
2What numbers? Positive integers? – Henry Jan 03 '14 at 11:52
-
yes. sorry.I edit the question.. – roi Jan 03 '14 at 11:59
-
1Do you mean that there exist $i$ and $j$ such that $\sum_{k=i}^{j}{x_{k}} = 13$ or that there exist $a_{1},\ldots,a_{j}$ such that $x_{a_{1}}+\ldots+x_{a_{k}} = 13$? – madprob Jan 03 '14 at 12:10
-
I didn't fully understand the question. the "chosen" numbers are folowing in the sequence. – roi Jan 03 '14 at 12:32
1 Answers
2
Consider the fact that $\sum\limits_{k=i}^{j}x_{k}=\sum\limits_{k=1}^{j}x_{k}-\sum\limits_{k=1}^{i-1}x_{k}$. In other word, you only need to care about the partial sum $s_{i}=\sum\limits_{k=1}^{i}x_{k}$.
Possible value of all $s_{i}$ and $s_{i}+13$ run from $1$ to $140+13=153$. No 2 partial sum have the same value. Assuming there is no 2 partial sum with a difference of $13$, then every partial sum with value $s_{i}$ will rule out 1 more possible value $s_{i}+13$ in the range from $1$ to $153$. Hence each $s_{i}$ would rule out a total of $2$ value.
There are $77$ possible partial sum. If each of them rule out $2$ possible value among $153$ possible value, then there would be contradiction since $77\times 2=154>153$.
Gina
- 5,338
-
There can be overlaps that rule out the same sums. If there are sequences that sum to 11,37,63,99,125 we only rule out five others, not 10 – Ross Millikan Jan 03 '14 at 12:18
-
@RossMillikan: no: 11 rule out 11 and 24; 37 rule out 37 and 50; 63 rule out 63 and 76; 99 rule out 99 and 112; 125 rule out 125 and 138. 5 other, but total is 10. We only rule out upward, so there is no overlap. Your comment would have applied if all 3 $s_{i}-13,s_{i},s_{i}+13$ are ruled out; which is why I only rule out $s_{i},s_{i}+13$ to avoid overlap issue. – Gina Jan 03 '14 at 12:31
-
@roi: each number is positive. In fact, the partial sums are strictly increasing. – Gina Jan 03 '14 at 12:44
-
-
thank you very much. but I didn't fully understand the final prove. I would say that if we rule out every s+13, we will have maximum 76 sums but there are 77 so 1 sum must be s+13 and we proved it.. – roi Jan 03 '14 at 13:03
-
Well it's essentially the same thing. Since you want to use pigeon hole, which I why I wrote that way. – Gina Jan 03 '14 at 13:09
-