Đến nội dung

wanderboy

wanderboy

Đăng ký: 09-06-2016
Offline Đăng nhập: 28-07-2018 - 04:42
-----

#649879 Marathon Tổ hợp và rời rạc VMF

Gửi bởi wanderboy trong 16-08-2016 - 15:20

Bài 16:Đánh số n người đó theo các số từ 1 đến n theo 1 chiều xác định, khi đó chiều ngược lại: $\Rightarrow 2\rightarrow n,3\rightarrow n-1,...$

Chia n người đó làm 2 phần sao cho độ dài cung từ vị trí ban đầu đến vị trí cần tới(ngược lại) là nhỏ nhất thì ta cần sắp dãy $q,q+1,...,k-1,k\rightarrow k,k-1,...q+1,q$ Với k=2 thì hiển nhiên cần ít nhất 1 lần đổi chỗ

Giả sử với k=m ta cần ít nhất a lần đỗi chỗ thì với k=m+1 ta cần ít nhất a+m-1 lần vì khi đó $k \rightarrow q$ cần m-1 lượt và khi đó ta phải sắp dãy k-1 số còn lại giống với TH k=m và vì khi $k \rightarrow q$ vị trí tương đối của k-1 số còn lại không đổi nên dù thay đổi thứ tự di chuyển k thì ta vẫn cần ít nhất a lần để thực hiên sắp xếp dãy còn lại Vậy Với k=m thì ta cần ít nhất số lượt là : $\sum_{1}^{m-1}= \frac{m(m-1)}{2}$

Với n lẻ ta được 2 phần là $\frac{n+1}{2},\frac{n-1}{2}\rightarrow a= \frac{(n-1)^2}{4}$

Với n chẵn ta được 2 phần là $\frac{n-2}{2},\frac{n+2}{2}\rightarrow a= \frac{(n-1)^2+3}{4}$




#649772 Marathon Tổ hợp và rời rạc VMF

Gửi bởi wanderboy trong 15-08-2016 - 18:17

Em làm thử bài 14: Gọi 2 phần tử của A là x và y(x>y),số các số có dạng $k=a_{i}+x\left ( \Leftrightarrow k \in x\right )$ là t(>0) theo đề bài ta có :

$tx+(2019-t)y=0\rightarrow t(x-y)=-2019y=s(1)$ Với mỗi cặp x,y mỗi số của dãy chỉ viết được bằng 2 cách $k=a_{i}+y,k=a_{i-s}+y+s$

Vì x>y nên $a_{i}=1\in y \rightarrow a_{j<i}\in x,a_{m(1< m\leq x)}\in y$ Vậy ta chỉ có duy nhất 1 cách viết dãy s số đầu tiên như sau :$x+1,x+2,...,s-1,s,1,2,...,x$

Tương tự như vậy với các nhóm s số tiếp theo cũng chỉ có 1 cách viết và nếu nhóm không được viết đủ sẽ không được một dãy các số liên tiếp như đề bài

(vì x ở đầu dãy và x+1 ở cuối dãy) nên x-y\left |2019\rightarrow x-y\in  \left \{ 1,673,3,2019 \right \}

TH1:x-y=1 không có No thỏa mãn

TH2:x-y=3 có 2 No y thỏa mãn ......$\rightarrow$ có 2692 giá trị của y $\Leftrightarrow$ 2692 cặp x,y

Vậy có 2692 hoán vị của dãy 

p/s: Em hỏi bài 16 nếu tất cả trả lời giống nhau thì sao ạ




#646886 Tổ hợp: Ai còn sống trên vương quốc đảo hoang

Gửi bởi wanderboy trong 28-07-2016 - 12:56

không thể là vì ngư lâm không thể giết hết rắn khi rắn giết hết 99 công chúa ( vì tổng các số chẵn # lẻ nên tồn tại 1 con rắn lẻ ) , tương tự công chúa không giết hết dc ngư lâm khi ngư lâm giết hết 101 rắn
~> cư dân đó là mãng xà