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

[DSH]

Có 15 nam và 15 nữ ngồi xung quanh một bàn tròn. Chứng minh rằng tồn tại 6 người ngồi cạnh nhau trong đó có đúng 3 nam và 3 nữ,

[takarin1512]

Giả sử không chọn được nhóm 6 bạn thỏa mãn yêu cầu bài toán.

Ta đánh số thứ tự cho các bạn nam từ $1$ đến $15$ theo chiều kim đồng hồ, gọi $x_i$ là số bạn nữ giữa bạn nam thứ $i$ và $i+1 \left ( 1\leq i\leq 14 \right )$ và $x_{15}$ là số bạn nữ giữa bạn nam thứ $15$ và thứ $1$.

Ta có $\sum_{1}^{15}x_i=15$

Điều kiện để chọn ra nhóm 6 bạn ngồi cạnh nhau mà thỏa mãn điều kiện bài toán là tồn tại $i$ sao cho $x_i+x_{i+1}\leq 3$ và trong hai số $x_{i-1}, x_{i+2}$ luôn có một số mà tổng nó với $x_i, x_{i+1}$ không nhỏ hơn 3.

 

Nếu trong $x_i$ tồn tại một số không nhỏ hơn 3, giả sử $x_1\geq 3$, nếu $x_2+x_3\leq 3$ thì ta chọn được bạn nam số $2,3,4$ (vô lý); do đó $x_2+x_3\geq 4$, nếu $x_3+x_4\geq 3$ thì ta chọn được bạn nam số $3,4,5$ (vô lý), do đó $x_3+x_4\geq 4$, cứ làm như vậy ta được $x_i+x_{i+1}\geq 4\left ( 2\leq i\leq 14 \right )$, suy ra $\sum_{1}^{15}x_i=x_1+\left ( x_2+x_3 \right )+...+\left ( x_{14}+x_{15} \right )\geq 3+7.4>15$ (vô lý).

Do đó $x_i$ chỉ nhận các giá trị $0,1,2$, nếu $x_i=1$ với mọi $i$ thì ta điều giả sử vô lý do đó trong $x_i$ có ít nhất 1 số bằng $0$ và 1 số bằng $2$.

Ta viết dãy $x_i$ thành dãy 15 số $0,1,2$, nhận thấy số số 0 phải bằng số số 2.

Vì có ít nhất một số 2 nên không mất tính tổng quát giả sử số đầu tiên là 2, nếu có tồn tại hai số 1 và 2 hoặc hai số 2 nằm liên tiếp nhau thì ta có thể chọn được các bạn thỏa mãn bài toán (vô lý với giả sử) nên ta với mỗi số 2 thì hai bên cạnh nó phải là hai số 0. Do đó số số 0 nhiều hơn số số 2(vô lý)(số số 0 bằng số số 2 chỉ trong trường hợp dãy có chẵn số và các số 2, 0 xếp xen kẽ nhau nhưng dãy có 15 số nên điều này không xảy ra được).

Vậy điều giả sử sai, luôn chọn được nhóm 6 bạn thỏa mãn yêu cầu bài toán.