cobk54's Content
There have been 4 items by cobk54 (Search limited from 02-06-2020)
#408593 Bài 2- 200 người thi giải toán- Chùm bài Counting in two ways
Posted by cobk54 on 28-03-2013 - 17:10 in Tổ hợp và rời rạc
#516901 Tồn tại 5 cây bao trùm trong graph bậc 5?
Posted by cobk54 on 01-08-2014 - 16:08 in Tổ hợp và rời rạc
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á
#516936 $S=d(\frac{m}{1})+d\left ( \frac...
Posted by cobk54 on 01-08-2014 - 18:26 in Tổ hợp và rời rạc
Với mọi số thực $t$ $>$ $0$, gọi $d(t)$ là số các phân số tối giản $\frac{p}{q}$ mà $0$ $<$ $p,q$$\leq$ $t$
Vói $m,n$ $\in \mathbb{Z}^{+}$ ,hãy tính tổng
$S=d(\frac{m}{1})+d\left ( \frac{m}{2} \right )+...+ d\left ( \frac{m}{n} \right )$
Mình đang thắc mắc là d(t) ở đây là tổng các phân số p/q thoả mãn điều kiện hay là chỉ là 1 phân số p/q nào đó thôi bạn?
#516944 Chứng minh tồn tại $2$ học sinh $A$ và $B$ sao...
Posted by cobk54 on 01-08-2014 - 18:56 in Tổ hợp và rời rạc
Để 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
- Diễn đàn Toán học
- → cobk54's Content