Đến nội dung

the unknown

the unknown

Đăng ký: 10-03-2016
Offline Đăng nhập: 15-04-2023 - 15:30
****-

Trong chủ đề: VN TST 2018

05-04-2018 - 15:56

Giả sử chọn $k = 2016$, và có $2^{2016}+1$ dòng, trong số các dòng này chứa tất cả các chuỗi nhị phân độ dài $k$ và có đúng 2 chuỗi giống nhau, xét hai chuỗi giống nhau ở cột thứ $2017$, một chuỗi chứa 0 một chuỗi để trống, ở cột thứ $2018$ thì chuỗi để trống ở cột $2017$ chứa 0 còn chuỗi còn lại thì để trống. Khi đó thì không thể xóa đi dòng nào được đâu bạn ạ.

 

Bảng này không phải bảng đầy đủ nhé bạn, lấy dãy nhị phân giống 2016 cột đầu của hai hàng này và đằng sau cho hai số 1,1 là thấy rõ.


Trong chủ đề: VN TST 2018

03-04-2018 - 23:18

Bài 2:

Câu b đã là gợi ý cho câu a. Một bảng gồm $2^k$ xâu nhị phân độ dài là $k$ và phần còn lại chừa trống thỏa mãn điều kiện là bảng tối giản.

câu b ta sẽ chứng minh nếu $m>2^k$ thì ta sẽ xóa được một dòng sao cho bảng vẫn còn là tối giản. Điều này có nghĩa là chứng minh rằng tất cả chuỗi nhị phân sinh ra từ dòng bị xóa sẽ thu được bằng cách thêm vào $0,1$ ở các dòng khác. Ta chỉ quan tâm tới cách sinh ra các chuỗi nhị phân với $k$ cột chứ $0,1$. Bây giờ xét tập A gồm $2^k$ chuỗi nhị phân có độ dài $k$. Mỗi một bước ta chọn một dòng của bảng (chỉ $k$ cột chứa 0,1), và xóa đi tất cả những chuỗi nhị phân trong A có thể sinh ra được bằng cách thêm $0,1$ vào các ô còn trống của dòng này. Với một dòng mà ta không xóa được trong A bất kì một chuỗi nào thì có nghĩa tất cả các chuỗi nhị phân sinh ra từ dòng đó có thể được sinh ra bởi các dòng khác, tức là xóa đi dòng đó bảng vẫn tối giản. A chỉ có $2^k$ phần tử mà ta có $m>2^k$ dòng thì dĩ nhiên sẽ chọn được một dòng chẳng xóa đi phần tử nào trong tập A được.

 

Thực ra lúc mình thi thì mình nhớ rằng ý b) không có điều kiện "tất cả các cột còn lại đều trống". Thực ra điều kiện chỉ cần có đúng $k$ cột có chứa hai số $0,1$ là đủ rồi. Lời giải của bạn vẫn đúng về ý tưởng nhưng có một xíu cải tiến như sau. Vẫn xét hàng mà chúng ta có thể xóa được trong lập luận của bạn, nếu nó không có phần tử nào ở các cột còn lại thì có thể xóa nó đi. Nhưng nếu nó có, và giả sử là số $0$ chẳng hạn ở một cột nào đó ngoài $k$ cột này thì ta vẫn có thể chứng minh mọi dãy nhị phân sinh ra từ hàng này thì có thể sinh ra từ một hàng khác bởi nếu không ta có thể lập luận và tạo thêm một cột nữa có chứa cả hai số $0,1$ và ta có điều vô lý.


Trong chủ đề: $n=a_{i_1}+2017a_{i_2}+...+2017^{2016}...

16-09-2017 - 13:50

Kết quả bài này hình như không đúng lắm. 

Ta xét số $m$ sao cho $a_m$ $=$ $m^{2017}$. Ký hiệu $f(i_1,...,i_{2017})$ $=$ $a_{i_1}+2017a_{i_2}+...+2017^{2016}a_{i_{2017}}$

Do $a_m$ $=$ $m^{2017}$ nên $ \left \{ 0,1,...,m^{2017}-1 \right \} $ $\subset $ $\left \{ f(i_1,i_2,...,i_{2017}) | i_j < m \forall j = 1,2,...,2017 \right \}$ mà $\left | \left \{ f(i_1,i_2,...,i_{2017}) | i_j < m \forall j = 1,2,...,2017 \right \} \right | \leq m^{2017}$ $=$ $\left | \left \{ 0,1,...,m^{2017} -1 \right \} \right |$ nên $f(i_1,i_2,...,i_{2017})$ là đôi một phân biệt với mọi $i_j$ $<$ $m$. Từ đây đánh giá dễ thấy $a_{m-1-2017k-r}$ $=$ $a_{m-1} - k(2016A + 1) - r$ với $A$ $=$ $\frac{2017^{2017} - 1}{2016}$

Xét $n$ $=$ $0,1, ... , 2016$ ta suy ra $a_i$ $=$ $i$ $\forall i = 0,1, ... , 2016$

Do đó $a_{m-1} - k(2016A+1)$ $=$ $2016$ nên $a_{m-1}$ $=$ $2016 + k(2016A +1)$

Mà ta có $m^{2017} - 1$ $=$ $a_{m-1}A$ nên $m^{2017} - 1$ $=$ $2016A + k(2016A^2+A)$ do đó $m^{2017} - 2017^{2017}$ $\vdots $ $2017^{2017} A$.

Chỗ này nếu chọn $m = 2017 A$ thì sao?

xin lỗi bạn, mình quên điều kiện cần thiết nữa là duy nhất (đã sửa)


Trong chủ đề: CM với mỗi $\alpha>0$,số giá trị của $k$ luô...

11-09-2017 - 18:39

Ta sẽ chứng minh bằng quy nạp mạnh theo $n$. Trước hết hãy cố định $\alpha$. Với $n=1$, xét 2 trường hợp:

 

Nếu $a_1>\alpha$ thì khi đó có đúng một giá trị $m_1$ thỏa $m_1>\alpha$ và do đó số giá trị này bé hơn $\frac{a_1}{\alpha}>1$.

 

Nếu $a_1\leq \alpha$ thì khi đó số giá trị $k$ thỏa $m_k>\alpha$ là $0<\frac{a_1}{\alpha}$.

 

Vậy giả thiết đúng với $n=1$, giả sử giả thiết đúng với mọi $1\leq k\leq n-1$. Ta sẽ chứng minh giả thiết đúng với $k=n$. Ta sẽ có hai trường hợp cho $m_n$ như sau:

TH1: $m_n\leq \alpha$ khi đó số giá trị $k$ ($1\leq k\leq n$) mà $m_k>\alpha$ bằng số giá trị $k$ ($1\leq k\leq n-1$) mà $m_k>\alpha$ và số giá trị này bé hơn $\frac{a_1+a_2+...+a_{n-1}}{\alpha}\leq \frac{a_1+a_2+...+a_n}{\alpha }$. (đúng)

TH2: $m_n>\alpha$ khi đó gọi $1\leq j\leq n$ là số thỏa $a_j+a_{j+1}+...+a_n>(n-j+1)\alpha$. Rõ ràng số các số $k$ ($1\leq k\leq n$) để $m_k>\alpha$ bằng tổng số các số $i$ ($1\leq i\leq j-1$) để $a_i>\alpha$ và tổng số các số $i$ ($j\leq i\leq n$) để $a_j>\alpha$. Theo giả thiết quy nạp thì tổng số các số này bé hơn

$\frac{a_1+a_2+..+a_{j-1}}{\alpha }+n-k+1< \frac{a_1+a_2+..+a_{j-1}}{\alpha }+\frac{a_j+a_{j+1}+...+a_n}{\alpha }=\frac{a_1+a_2+..+a_n}{\alpha }$ . (đúng)

 Vậy theo giả thiết quy nạp bài toán được chứng minh.


Trong chủ đề: ĐỀ VIỆT NAM TST 2017

29-03-2017 - 20:57

Bài 5: Trước hết trong tập ${1,2,3,...,2017}$ ta chọn ra một số $m$ sao cho giá trị $\sqrt[m]{a_m}$ là lớn nhất.

Ý tưởng chính của em cho bài toán số 5 là chỉ ra một số $N$ đủ lớn để với mọi số $n>N$ thì tồn tại cách phân tích $a_n$ thành tích các thừa số $a_i$, $1\leq i\leq 2017$, tức là $a_n=a_{i_1}.a_{i_2}...a_{i_k}$, $1\leq i_j\leq 2017$ và $a_1=a_2=a_m$. Ta sẽ đi chứng minh nhận xét trên (coi là nhận xét $(*)$)

Trước hết ta nhận thấy rằng từ điều kiện bài toán thì với bất kì một số $n>2017$ nào thì cũng có thể phân tích thành:

$a_n=a_{i_1}.a_{i_2}...a_{i_k}$ với  $i_1+i_2+...+i_k=n$, $1\leq i_j\leq 2017$ với mọi $1\leq j\leq k$

Thật vậy trước hết tồn tại $j_1,j_2,j_3$ sao cho $a_n=a_{j_1}.a_{j_2}.a_{j_3}$ và nếu trong các số $j_1,j_2,j_3$ có một số lớn hơn $2017$ thì ta tiếp tục phân tích ra tiếp như vậy. Do đó điều nhận xét là đúng. Hơn nữa trong cách phân tích cuối cùng để ra được ba nhân tử $a_i,a_j,a_k$ thì phải có $i+j+k>2017$ và không mất tính tổng quát ta có thể giả sử $i_1+i_2+i_3>2017$. Quy về như vậy ta được điều kiện cần của các số $i_1,i_2,...,i_k$ là:

$i_1+i_2+...+i_k=n$, $1\leq i_j\leq 2017$ với mọi $j\in {1,2,...,k}$ và $i_1+i_2+i_3>2017$ (điều kiện $(1)$)

Bây giờ ta xét tập các số $ j_1,j_2,...,j_t$ thỏa điều kiện $(1)$. Khi đó ta có: $a_n\geq a_{j_1}.a_{j_2}.a_{n-j_1-j_2}\geq ...\geq a_{j_1}.a_{j_2}....a_{j_t}$. từ đó kết luận rằng:

$a_n=max\left \{ a_{i_1}.a_{i_2}...a_{i_k}\mid (i_1,i_2,..,i_k) \mathbf{thoa} (1))\right \} $

Bây giờ ta xét $n$ là số thỏa $n\geq N=2.2017^2m+3.2017$. Do $ n=i_1+i_2+...+i_k\leq 2017k$ nên $k\geq 2.2017m+3$. Do đó theo nguyên lý Dirichlet thì trong $k-3$ số $a_{i_4},a_{i_5},...,a_{i_k}$ có ít nhất $2m$ số bằng nhau. Xét hai trường hợp:

Trường hợp 1: Nếu $2m$ số đó bằng $a_m$ thì do $2m\geq 2$ nên nhận xét $(*)$ được chứng minh.

Trường hợp 2: Nếu $2m$ số đó không phải là $a_m$ mà là $a_q$ với $j\neq m$ thì khi đó ta sẽ thay $2m$ số đó bằng $2q$ số $a_m$ và khi đó ta lập được một dãy mới các số $a_{j_1},a_{j_2},....,a_{j_t}$ với tổng các chỉ số $j_1,j_2,...,j_t$ có tổng vẫn bằng $n$ và vẫn thỏa mãn $j_1+j_2+j_3=i_1+i_2+i_3>2017$ và $1\leq j_a\leq 2017$ với mọi $1\leq a\leq t$. Tức là dãy $a_{j_1}.a_{j_2}....a_{j_t}$ thỏa điều kiện $(1)$ và suy ra:

$a_n\geq a_{j_1}.a_{j_2}....a_{j_t}$

Suy ra

$a_{i_1}.a_{i_2}...a_{i_k}\geq a_{j_1}.a_{j_2}....a_{j_t}$

Giản ước đi ta có: $a_q^{2m}\geq a_m^{2q}$ hay suy ra $\sqrt[q]{a_q}\geq \sqrt[m]{a_m}$. Theo tính chất lớn nhất suy ra $\sqrt[q]{a_q}= \sqrt[m]{a_m}$ hay $a_q^{2m}= a_m^{2q}$. Từ đó suy ra $a_{i_1}.a_{i_2}...a_{i_k}= a_{j_1}.a_{j_2}....a_{j_t}= a_n$. Và trong dãy  $a_{j_1},a_{j_2},....,a_{j_t}$ có ít nhất $2q\geq 2$ phần tử bằng $a_m$ hay nhận xét $(*)$ đúng.

Như vậy nhận xét $(*)$ đúng. từ đó ta thấy rằng $a_n=a_m.a_m.a_{i_1}.a_{i_2}...a_{i_k}\geq a_m^2.a_{n-2m}\geq a_m.a_m.a_{i_1}.a_{i_2}...a_{i_k}=a_n$ với $i_1+i_2+...+i_k=n-2m$. Suy ra $a_n=a_m^2.a_{n-2m}$ với $n\geq N=2.2017^2m+3.2017>2m$.

Tức là như vậy ta đã chứng minh được rằng tồn tại số $m\leq 2017$ và tồn tại số $N$ đủ lớn sao cho với mọi $n>N$ thì $a_n=a_m^2.a_{n-2m}$. Khi đó ta tiếp tục chọn $n$ đủ lớn để $n-2m>N$. Khi đó $a_{n-2m}=a_m^2.a_{n-4m}$. Khi đó:

$a_n.a_{n-4m}=a_{n-2m}.a_m^2.a_{n-4m}=a_{n-2m}^2$

Và như vậy bài toán được chứng minh hoàn toàn.