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

[davidsilva98]

Bài toán tổ hợp:

Cho $49$ học sinh giải $3$ bài tập. Điểm của mỗi bài là số nguyên dương từ $0$ đến $7$. Chứng minh rằng tồn tại $2$ học sinh $A$ và $B$ sao cho trong mỗi bài điểm của $A$ không nhỏ hơn $B$

[cobk54]

Để sinh ra mâu thuẫn, ta giả sử ko tồn tại $2$ người như $A$, $B$ như vậy.
Bạn tạo $1$ table $T$ có số column là $49$ và số row là $3$, như hình dưới:

$\begin{vmatrix}p_{1,1} & ... & p_{7,1} &p_{8,1} & ... & p_{15,1} &... &p_{n-6,1} & ... & p_{n,1}\\ p_{1,2} & ... & p_{7,2} &p_{8,2} & ... & p_{15,2} &... &p_{n-6,2} & ... & p_{n,2}\\ p_{1,3} & ... & p_{7,3} &p_{8,3}& ... & p_{15,3} &... &p_{n-6,3} & ... & p_{n,3}\end{vmatrix}$

Ở đây $n = 49$, và $p_{i,j}$ là điểm môn $j$ của người $i$, với $i=: 1 \to 49$, $j=: 1 \to 3$.
Ko mất tính tổng quát, ta giả sử $p_{1,1}, $ $p_{2,1},...,$ $ p_{n,1}$ là dãy ko giảm.
Từ đó theo nguyên lý Dirichlet thì số điểm bằng nhau trong dãy thứ $2$:
$p_{1,2}, $ $p_{2,2},...,$ $ p_{n,2}$ sẽ ko ít hơn $7$.

 

Case $1$: Có ít nhất $8$ người có số điểm bằng nhau trong row $2$:
Trong $8$ người có cùng điểm đó, ta xét row thứ $3$ là
$p_{1,3}, $ $ p_{2,3},..., $ $ p_{n,3}$
thì sẽ tồn tại $2$ người (trong ít nhất $8$ người ở trên) cùng số điểm, tức là có ít nhất $2$ người mà trong đó có $1$ người có số điểm cả $3$ môn đều ko vượt quá người kia. (Mâu thuẫn vs giả thiết !).

 

Case $2$: Nếu ko là case $1$, thì ở row $2$, số người cùng số điểm $1, 2,..., 7$ lần lượt đều là $7$.
Trong số người cùng số điểm ở row $2$ thì những người gần bên trái hơn sẽ có số điểm ở row $3$ cao hơn. Điều đó cho phép ta biểu diễn lại $3$ rows đó như sau:

$\begin{vmatrix}p_{1,1} & ... & p_{7,1} &p_{8,1} & ... & p_{15,1} &... &p_{n-6,1} & ... & p_{n,1}\\ p_{1,2} & ... & p_{7,2} &p_{8,2} & ... & p_{15,2} &... &p_{n-6,2} & ... & p_{n,2}\\ 7 & ... & 7 &6 & ... & 6 &... &1 & ... & 1\end{vmatrix}$

Tương tự, trong bộ bảy số $7$ của row $3$, thì ứng vs nó trong row $2$, số điểm phải giảm dần. Ta lại có thể biểu diễn $3$ rows lại như sau:

$\begin{vmatrix}p_{1,1} & ... & p_{7,1} &p_{8,1} & ... & p_{15,1} &... &p_{n-6,1} & ... & p_{n,1}\\ 7 & ... & 1 &7 & ... & 1 &... &7 & ... & 1\\ 7 & ... & 7 &6 & ... & 6 &... &1 & ... & 1\end{vmatrix}$

Tới đây ta nhìn $3$ rows này dưới $7$ tables con, mỗi cái $3$x$7$. Trong mỗi table con, nếu tồn tại $2$ số bằng nhau trong row $1$, thì dễ thấy ngay mâu thuẫn với giả thiết vì row $2$ và $3$ là giảm dần trong mỗi table con.
Tức vậy trong mỗi table con, điểm của row $1$ sẽ phải tăng dần, và ta thu được cách xếp duy nhất là:

$\begin{vmatrix}1 & ... & 7 &1 & ... & 7 &... &1 & ... & 7\\ 7 & ... & 1 &7 & ... & 1 &... &7 & ... & 1\\ 7 & ... & 7 &6 & ... & 6 &... &1 & ... & 1\end{vmatrix}$

Nhìn vào table này dễ thấy lại mâu thuẫn, ví dụ column $7$ vs $14$.
Kết luận, làm kiểu gì cũng mâu thuẫn nên đành phải tuân theo kết luận đề ra

Bài viết đã được chỉnh sửa nội dung bởi cobk54: 02-08-2014 - 12:15