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
:)
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$.