1

Can someone help me understand the following logic using the pigeonhole principle:

If a sequence of $n$ integers $x_1, x_2,...,x_n\;(n\geq2,x_i \geq 0)$ sums to $n^2-3n+2$, then either of the following is true:

  • at least one $x_i$ satisfies $x_i \geq n-1$

  • at least two $x_i$ satisfy $x_i =n-2$

pblpbl
  • 131
  • 4
    Don't bother with pigeonhole principle. Suppose otherwise. Then at most one $x_i=n-2$ and all other satisfy $x_i\leq n-3$. Then the largest possible sum of these is? – JMoravitz Sep 01 '20 at 04:01
  • 4
    As for the "exactly one of the following is true" that is incorrect. It could be the case that both are true simultaneously. With $n=7$ you have $20+5+5+0+0+0+0=30 = 7^2-3\cdot 7 + 2$ for instance. It should have read at least one of the following is true. – JMoravitz Sep 01 '20 at 04:04

0 Answers0