Proof by contradiction of a variant of PHP

Question

Let $a_1, a_2,\ldots , a_n$ be positive integers.

Prove that if $(a_1+a_2+\ldots+a_n)-n+1$ pigeons are to be put in $n$ pigeonholes, then for some $i$, the statement "The $i^{th}$ pigeonhole must contain at least $a_i$ pigeons" must be true.

My approach:

Let us assume that this hypothesis is incorrect.

Let $p(i)$ denote the number of pigeons in $i^{th}$ pigeonhole.

Thus no $i\in \mathbb N$ exists such that $i^{th}$ pigeonhole contains at least $a_i$ pigeons.

$$\therefore p(i)<a_i\space \forall\ i\in \mathbb N$$ $$\sum_{i=1}^{n} p(i)<\sum_{i=1}^{n} a_i$$ $$(a_1+a_2+\ldots+a_n)-n+1<(a_1+a_2+\ldots+a_n)$$ This gives us $1<n$ which certainly is true.

Where did I go wrong in my proof? Please help.

THANKS

Note: This is question number $3.3.12$ from the book 'The Art and Craft of Problem Solving' by Paul Zeitz.

Answer 1

Since $p(i)$ is an integer, $p(i)<a_i$ is equivalent to $p(i)\leq a_i-1$. Then we have the following,

$$\sum_{i=1}^{n}p(i)\leq\sum_{i=1}^{n}(a_i-1)\\\implies(a_1+a_2+\cdots+a_n)-n+1\leq(a_1+a_2+\cdots+a_n)-n$$ which is a contradiction!

Answer 2

You are misinterpreting the statement 'at least'. To ensure that no bin $i$ contains at least $a_i$ pigeons, you need to ensure that each bin $i$ contains at most $a_i-1$ of them. Therefore the total number of pigeons is $$ \sum_{i=1}^{n}p(i)\leq\sum_{i=1}^{n}(a_i-1)=(a_1+\cdots+a_n)-n<(a_1+\cdots+a_n)-n+1. $$