Pigeonhole Principle(Strong Form) proof

1.5k Views Asked by At

Pigeonhole Principle(Strong Form) says:

Let $q_1$,$q_2$,...,$q_n$ are positive integers

If we put $q_1+q_2+...+q_n-n+1$ objects into n boxes
then
box1 contains q1 or more objects xor
box2 contains q2 or more objects xor
...
...
...
boxn contains qn or more objects

I am trying to do the proof by contradiction

Proof:
Suppose $q_1+q_2+...+q_n-n+1$ objects are put into n boxes
then
box1 contains at most $q_1$-1 objects $\Leftarrow\Rightarrow$
box2 contains at most $q_2$-1 objects $\Leftarrow\Rightarrow$
...
...
...
boxn contains at most $q_n$-1 objects

$(q_1-1) + (q_2-1) + ... + (q_n-1) = q_1 + q_2 + ... + q_n - n$ !!!
This is a contradiction because by hypothesis we have $q_1+q_2+...+q_n-n+1$ objects

therefore Pigeonhole Principle(Strong Form) is valid

is proof correct?

Notes: Negation of xor is if and only if
:)

1

There are 1 best solutions below

1
On

The theorem is false. It becomes true if you change "XOR" to "OR" and your proof becomes correct if you replace $\Leftarrow\Rightarrow$ with $\wedge$.