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:

Ở đâ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:

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:

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à:

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

Cho graph $G$ (link dưới) có $16$ đỉnh: $0$, $1$, $2$,..., $15$ được xếp theo thứ tự lần lượt trên đường tròn. Ta định nghĩa khoảng cách giữa $2$ đỉnh bất kỳ $x$, $y$ trên $G$ là $d(x,y) = \left | {x-y} \right|$, và $2$ đỉnh đó được nối với nhau bởi $1$ cạnh có độ dài $d(x,y)$ khi và chỉ khi $d(x,y)$ bằng $1$ hoặc $6$ hoặc là $8$.

Không mất tính tổng quát, ta xem đỉnh $0$ là gốc (root) của $G$. Hỏi $G$ có thể tồn tại $5$ cây bao trùm (spanning tree) đôi một độc lập hay ko? Ở đây $2$ cây bao trùm được gọi là độc lập nếu: Đối với một đỉnh $v$ bất kỳ khác $0$ của G, path $0-v$ trên $2$ cây đó là độc lập, $($$2$ path là độc lập nếu chúng ko có đỉnh nào chung ngoại trừ $0$ và $v$$)$.

Link to $G$: https://drive.google...dit?usp=sharing

P/s: mọi thắc mắc các bạn cứ comment nhiệt tình, mình đang cần ý tưởng để đi, bí quá