Udowodnić przez zaprzeczenie następujące stwierdzenie

[iglomosh]

Witam,
mam problem z przeprowadzeniem dowodu.

Zadanie pochodzi z książki autorstwa J. Jaworskiego, Z. Palki i J. Szymańskiego pt. "Matematyka dyskretna dla informatyków. Część I: Elementy kombinatoryki" (Wydawnictwo Naukowe UAM).

Treść:
Udowodnić przez zaprzeczenie następujące stwierdzenie:

Niech \(\displaystyle{ m _{1} , m _{2} , ... , m _{n}}\) będą dodatnimi liczbami całkowitymi. Jeżeli \(\displaystyle{ k}\) kul,
\(\displaystyle{ k = m _{1} + m _{2} + ... + m _{n} - n + 1}\),
włożymy do \(\displaystyle{ n}\) szufladek, to pierwsza szufladka będzie zawierać co najmniej \(\displaystyle{ m _{1}}\) kul lub druga szufladka zawierać będzie co najmniej \(\displaystyle{ m _{2}}\) kul, lub ..., lub n-ta szufladka zawierać będzie co najmniej \(\displaystyle{ m _{n}}\) kul.

Rozwiązanie:

Założenia:
\(\displaystyle{ m _{1} , m _{2} , ..., m _{n} \in \mathbb{Z ^{+}}}\)
\(\displaystyle{ k = m _{1} + m _{2} + ... + m _{n} - n + 1}\)
Teza:
\(\displaystyle{ M(1) \ge m _{1} \vee M(2) \ge m _{2} \vee ... \vee M(n) \ge m _{n}}\), gdzie \(\displaystyle{ M(i)}\) - ilość kul w i-tej szufladce.
Dowód:
Zakładamy, że:
\(\displaystyle{ M(1) < m _{1} \wedge M(2) < m _{2} \wedge ... \wedge M(n) < m _{n}}\)

Nie wiem co dalej musiałbym zrobić, by pokazać, że przy prawdziwych założeniach "początkowych" i przy założeniach z dowodu uzyskane wyrażenie logiczne jest fałszywe.

[mattrym]

Dowód:
Załóżmy, że:
\(\displaystyle{ M(1) < m _{1} \wedge M(2) < m _{2} \wedge ... \wedge M(n) < m _{n}}\).
Wówczas prawdziwe jest wyrażenie:
\(\displaystyle{ M(1) \le m _{1} - 1 \wedge M(2) \le m _{2} - 1 \wedge ... \wedge M(n) \le m _{n} - 1}\).
Po dodaniu powyższych nierówności otrzymamy, że:
\(\displaystyle{ M(1) + M(2) + ... + M(n) \le m _{1} + m _{2} + ... + m _{n} - n}\).
A z tego wynika też, że:
\(\displaystyle{ M(1) + M(2) + ... + M(n) < m _{1} + m _{2} + ... + m _{n} - n +1}\)
Natomiast z założenia wynika, że mamy \(\displaystyle{ k}\) wszystkich kul i wszystkie kule zostały przydzielone do szufladek (nie została żadna kula bez szufladki), a zatem:
\(\displaystyle{ m _{1} + m _{2} + ... + m _{n} - n + 1 = k = M(1) + M(2) + ... + M(n) < m _{1} + m _{2} +...+m _{n} - n +1}\).
Otrzymaliśmy sprzeczność z założeniem, co należało dowieść.

[iglomosh]

Dzięki, teraz już wszystko jasne. Powiem szczerze, że brakuje mi "otrzaskania" w dowodach i używanie takich tricków jak pomniejszenie prawej strony nierówności nie jest dla mnie oczywiste