Chủ đề này có 1 trả lời

[phanquockhanh]

Trong 1 căn phòng có 2n+1 người ,sao cho với n người bất kì luôn tồn tại 1 người quen với tất cả n người đó.Chứng minh có 1 người quen với tất cả mọi nguời trong phòng này.

[LNH]

Trong 1 căn phòng có 2n+1 người ,sao cho với n người bất kì luôn tồn tại 1 người quen với tất cả n người đó.Chứng minh có 1 người quen với tất cả mọi nguời trong phòng này.

Ta sẽ chứng minh trong nhóm người này có một nhóm $n+1$ người đôi một quen nhau (gọi là nhóm $A$). Từ đó, xét $n$ người còn lại. Theo giả thiết, có 1 người trong nhóm $A$ quen với $n$ người này. Suy ra người này quen với tất cả mọi người.

Để chứng minh khẳng định về sự tồn tại của nhóm $A$, ta giả sử $k$ là kích thước (số người) lớn nhất của một nhóm người đôi một quen nhau. Ta cần chứng minh $k\geq n+1$. Giả sử ngược lại $k\leq n$. Theo giả thiết,tồn tại 1 người trong số những người còn lại quen với $k$ người này. Bổ sung người này vào nhóm, ta được nhóm gồm $k+1$ người đôi một quen nhau. Mâu thuẫn với điều giả sử $k$ lớn nhất.

Bài viết đã được chỉnh sửa nội dung bởi lenhathoang1998: 28-07-2013 - 15:51