ai có thể chứng minh bổ đề bắt tay cho em cái đc ko ạ ( trong sách khó hiểu quá!!)
chứng minh bổ đề bắt tay?
Bắt đầu bởi vamath16, 04-02-2018 - 08:24
#1
Đã gửi 04-02-2018 - 08:24
#2
Đã gửi 10-07-2018 - 13:50
ai có thể chứng minh bổ đề bắt tay cho em cái đc ko ạ ( trong sách khó hiểu quá!!)
Trong một hội nghị, mỗi người sẽ bắt tay với người khác một số lần. Chứng minh rằng số người có số lần lẻ bắt tay với người khác là một số chẵn
(mỗi người không bắt tay với chính mình và không bắt tay với người khác nhiều hơn 1 lần). \\
Gọi $ P_1,P_2,...,P_n $ là \textit{n} người có trong hội nghị. Gọi $ x_i $ là số cái bắt tay của $ P_i $ với người khác, $ y $ là tổng số cái bắt tay. Ta sẽ đếm số các cặp $ (P_i,P_j) $ bằng hai cách:
\begin{itemize}
\item Cách 1: $ P_i $ bắt tay với $ P_j $ là $ x_i $ lần. Do đó tổng số cặp $ (P_i,P_j) $ là:
\begin{center}
$ \displaystyle\sum_{i=1}^{n} x_i $ (1)
\end{center}
\item Cách 2: Mỗi cái bắt tay tương ứng với 2 cặp $ (P_i,P_j) $ và $ (P_j,P_i) $. Do đó tổng số cặp $ (P_i,P_j) $ là: \begin{center}
$ 2y $ (2)
\end{center}
\end{itemize}
Từ (1) và (2) suy ra:
$ \displaystyle\sum_{i=1}^{n} x_i = 2y
\Leftrightarrow \displaystyle\sum_{x_i\text{lẻ}} x_i = 2y -\displaystyle\sum_{x_i\text{chẵn}} x_i $ (3) \\
Từ (3) suy ra phải có một số chẵn các $ x_i $ lẻ. Suy ra điều phải chứng minh.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh