Đến nội dung

Hình ảnh

ĐỀ VIỆT NAM TST 2017


  • Please log in to reply
Chủ đề này có 20 trả lời

#1
Dinh Xuan Hung

Dinh Xuan Hung

    Thành viên nổi bật 2015

  • Thành viên nổi bật 2016
  • 1396 Bài viết
ĐỀ VIỆT NAM TST 2017

Bài 1. Cho $44$ cái lỗ phân biệt trên một cái rãnh là đường thẳng và $2017$ con kiến. Mỗi con kiến sẽ chui lên từ một cái lỗ và bò đến một cái lỗ khác với vận tốc không đổi rồi chui xuống đó. Gọi $T$ là tập các thời điểm mà con kiến chui lên hoặc chui xuống các cái lỗ. Biết rằng vận tốc của các con kiến đôi một khác nhau và $|T| \le 45.$ Chứng minh rằng tồn tại ít nhất hai con kiến nào đó không gặp nhau.

Bài 2. Với mỗi số nguyên dương $n$, đặt $x_n = C_{2n}^n$.
a) Chứng minh rằng nếu $\dfrac{2017^k}{2} < n < 2017^k$ với $k$ là số nguyên dương nào đó thì $x_n$ là bội của $2017$.
b) Tìm tất cả số nguyên dương $h > 1$ để tồn tại các số nguyên dương $N,T$ sao cho với mọi $n>N$ thì $x_n$ là dãy số tuần hoàn theo modulo $h$ với chu kỳ $T$.

Bài 3. Cho tam giác $ABC$ ngoại tiếp đường tròn $(I)$ và $(I)$ tiếp xúc với các cạnh $BC, CA, AB$
lần lượt tại $D, E, F.$ Gọi $I_b, I_c$ lần lượt là các tâm đường tròn bàng tiếp góc B, C của tam giác $ABC.$ Gọi $P, Q$ lần lượt là trung điểm $I_bE, I_cF.$ Giả sử $(PAC)$ cắt $AB$ tại $R$ và $(QAB)$ cắt $AC$ tại $S.$
a) Chứng minh rằng $PR, QS, AI$ đồng quy.
b) DE, DF lần lượt cắt $I_bI_c$ tại $K, J.$ $EJ$ cắt $FK$ tại $M$ và $PE, QF$ cắt $(PAC),(QAB)$ lần lượt tại $X,Y$. Chứng minh rằng $BY, CX, AM$ đồng quy.

Bài 4. Cho tam giác $ABC$ nội tiếp đường tròn $(O).$ Điểm $A$ di động trên $(O)$ sao cho $AB > BC$ và $M$ là trung điểm $AC.$ Đường tròn đường kính $BM$ cắt $(O)$ tại $R.$ Giả sử $RM$ cắt $(O)$ tại $Q,$ cắt $BC$ tại $P.$ Đường tròn đường kính $BP$ cắt $AB, BO$ lần lượt tại $K, S.$
a) Chứng minh rằng $SR$ đi qua trung điểm $KP.$
b) Gọi $N$ là trung điểm $BC.$ Trục đẳng phương của hai đường tròn đường kính AN, BM cắt SR tại $E.$ Chứng minh rằng $ME$ đi qua một điểm cố định.

Bài 5. Cho $2017$ số thực dương $a_1,a_1,...,a_{2017}.$ Với mỗi $n>2017,$ ta đặt 
\[a_n=\max \{a_{i_1}a_{i_2}a_{i_3}|i_1+i_2+i_3=n, 1 \le i_1 \le i_2 \le i_3 \le n-1 \}. \]

Chứng minh rằng tồn tại $m$ nguyên dương không vượt quá $2017$ và $N >4m$ sao cho $a_na_{n-4m}=a_{n-2m}^2$ với mọi $n>N$.

Bài 6. Với mỗi số nguyên dương $n$, xét $a_1,a_2, \ldots, a_{2n}$ là hoán vị của $2n$ số nguyên dương đầu tiên. Một hoán vị như thế được gọi là đẹp nếu với mọi $1 \le i < j \le 2n$ thì $a_i+a_{n+i}=2n+1$ và $a_i-a_{i+1}$ không đồng dư với $a_j-a_{j+1}$ theo modulo $2n+1$. Quy ước $a_{2n+1}=a_1$.

a) Với $n=6$, hãy chỉ ra một hoán vị đẹp.
b) Chứng minh rằng với mỗi $n$ nguyên dương thì luôn tồn tại một hoán vị đẹp.


Bài viết đã được chỉnh sửa nội dung bởi Dinh Xuan Hung: 26-03-2017 - 15:35


#2
Baoriven

Baoriven

    Thượng úy

  • Điều hành viên OLYMPIC
  • 1422 Bài viết

Đáp án $2$ bài hình đã được thầy Hùng đăng tại đây:

Ngày 1: http://analgeomatica...017-ngay-1.html

Ngày 2: http://analgeomatica...017-ngay-2.html


$$\mathbf{\text{Every saint has a past, and every sinner has a future}}.$$


#3
vietdohoangtk7nqd

vietdohoangtk7nqd

    Hạ sĩ

  • Thành viên
  • 59 Bài viết

có thánh nào làm bài 1 và bài 5 không, thi 2 ngày mà mình phế kinh khủng, chỉ làm được trọn vẹn 2 câu hình, câu 2 a, chém hết câu 6



#4
viet nam in my heart

viet nam in my heart

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 242 Bài viết

Bài 2. Với mỗi số nguyên dương $n$, đặt $x_n = C_{2n}^n$.

a) Chứng minh rằng nếu $\dfrac{2017^k}{2} < n < 2017^k$ với $k$ là số nguyên dương nào đó thì $x_n$ là bội của $2017$.
b) Tìm tất cả số nguyên dương $h > 1$ để tồn tại các số nguyên dương $N,T$ sao cho với mọi $n>N$ thì $x_n$ là dãy số tuần hoàn theo modulo $h$ với chu kỳ $T$.

 

a)Ta áp dụng định lý Lucas: 

Từ điều kiện đề bài đặt $n=y_{k-1}2017^{k-1}+...+y_{1}2017+y_0$(biểu diễn trong hệ cơ số $2017$)

Nếu $y_{k-1},...,y_1,y_0 \leq 1008$ thì ta có $n\leq 1008\left(2017^{k-1}+ \ldots + 1\right) < \dfrac{2017^k}{2}$ (loại)

Từ đó có một vị trí $y_{i}$ nào đó sao cho $y_i \geq 1009$. (gọi $i$ là vị trí đầu tiên như vậy trong biểu diễn cơ số $2017$ của $n$ tính từ bên phải)

Khi đó xét $2n$ thì vị trí đó có giá trị là $2n-2017$. Mặt khác $2n-2017 < n$ nên $C_{2n-2017}^n=0$ nên rõ ràng theo định lý $Lucas$ thì ta có điều phải chứng minh

b) Gọi $p$ là một ước nguyên tố của $h$

Nếu $x_n$ tuần hoàn theo modulo $h$ với $n$ đủ lớn thì nó cũng tuần hoàn theo modulo $p$ với $n$ đủ lớn

Mặt khác từ phần a thì rõ ràng ta chỉ được một khoảng các số $n$ liên tiếp sao cho $x_n$ chia hết cho $p$ với mọi $n$ thuộc khoảng này. Mà ta chọn được khoảng này đủ lớn về cả vị trí lẫn độ dài nên ta suy ra với mọi $n$ đủ lớn $\geq N_0$ thì $x_n$ phải chia hết cho $p$

Nếu $p>2$

Ta chọn số $n=111..1$($k$ số $1$) trong hệ cơ số $p$ thì theo định lý $Lucas$ thì $x_n$ chia $p$ dư $2^k$ suy ra $x_n$ không chia hết cho $p$ suy ra vô lý

Từ đó $p=2$

Do đó $h=2^t$ với $t$ là một số nguyên dương nào đó 

Ta chứng minh cũng tồn tại một khoảng đủ lớn về vị trí lẫn độ dài để $x_n$ chia hết cho $2^t$ với mọi $n$ thuộc khoảng này

Ta có: $x_n=C_{2n}^n=\dfrac{\left(2n\right)!}{\left(n!\right)^2}$

Do đó áp dụng công thức tính số mũ đúng của $2$ thì ta được $v_{2}(x_n)=2n-s_{2}(2n)-2n+2s_{2}(n)=2s_{2}(n)-s_{2}(2n)$

với $s_{2}(n)$ là tổng các chữ số trong biểu diễn cơ số $2$ của $n$

Ta cũng có thể thu gọn được $2s_{2}(n)-s_{2}(2n)=z$ với $z$ là số chữ số $1$ trong biểu diễn cơ số $2$ của $n$ 

  • Xét trong hệ cơ số $2$ 

Do đó ta xét khoảng các số liên tiếp từ $11..10..0$ ($u$ số $1$ đến $v$ số $0$) đến $11...1$ gồm có $u+v$ số $1$ thì khi chọn $u,v$ đủ lớn ta đều thu được $x_n$ chia hết cho $2^t$ với mọi $n$ thuộc khoảng này.

Chọn $u,v$ đủ lớn để độ dài khoảng này lớn hơn $2T$ và $11..10..0>N$ ($u$ số $1$ và $v$ số $0$)

Từ đó với mọi $n$ lớn hơn $N$ thì $x_{n}$ phải chia hết cho $2^t$

Mặt khác ta chọn $n=100...0$ với số số $0$ đủ lớn để $n$ đủ lớn thì $v_{2}(x_n)=2s_{2}(n)-s_{2}(2n)=1$ nên rõ ràng $t$ chỉ có thể bằng $1$

Khi đó ta dễ chứng minh mọi số hạng $x_n$ đều chia hết cho $2$

Vậy $h=2$


Bài viết đã được chỉnh sửa nội dung bởi viet nam in my heart: 26-03-2017 - 19:40

"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic


#5
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

  • Thành viên
  • 321 Bài viết

Thực ra bài 1 không khó nhưng có lẽ cách phát biểu nó làm các bạn hơi hoang mang. Dĩ nhiên là phải phản chứng, giả sử là 2 con kiến bất kì đều gặp nhau. Vận tốc của 2 con kiến bất kì khác nhau nên dĩ nhiên nếu 2 con cùng xuất phát ở 1 lỗ và ở cùng thời điểm thì chả bao giờ gặp nhau cả ( đi cùng chiều thì ko gặp rồi mà ngược chiều thì càng chẳng bao giờ gặp). 2017 con kiến mà 44 lỗ thì có 45 con cùng chuồng. Và dĩ nhiên để đáp ứng điều kiện phản chứng thì 45 con này xuất phát thời điểm khác nhau, cộng thêm cái thời điểm của cái con xuất phát trễ nhất nó chui vào lỗ nữa thì phải có ít nhất 46 thời điểm. Mâu thuẫn!

Các bài còn lại mình chỉ có chút ý tưởng, bài 2 thì định lí Lucas, bài 5 thì mình chỉ thấy một tính chất là $a_(n+k)/a_n$ bị chặn trên và dưới với $k$ cố định (hình như thế :D) nhưng ko biết dùng được không (^_^). Còn bài 6 thì khả năng là cái dãy này nó sắp xếp theo quy luật để đạt được điều kiện, chỉ cần thử với vài số mò ra quy luật, chỉ ra là coi như chứng minh được rồi.



#6
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Lời giải này sai. Minh có đưa ra lời giải khác ở dưới:

 

 

Bài 6. Với mỗi số nguyên dương $n$, xét $a_1,a_2, \ldots, a_{2n}$ là hoán vị của $2n$ số nguyên dương đầu tiên. Một hoán vị như thế được gọi là đẹp nếu với mọi $1 \le i < j \le 2n$ thì $a_i+a_{n+i}=2n+1$ và $a_i-a_{i+1}$ không đồng dư với $a_j-a_{j+1}$ theo modulo $2n+1$. Quy ước $a_{2n+1}=a_1$.

a) Với $n=6$, hãy chỉ ra một hoán vị đẹp.
b) Chứng minh rằng với mỗi $n$ nguyên dương thì luôn tồn tại một hoán vị đẹp.

Lời giải. Do $a_i+a_{n+i}=2n+1$ nên ta chỉ việc xây dựng $a_1,a_2, \cdots, a_n$ là đủ. Ta làm như sau:

 

Với các vị trí lẻ $a_1,a_3, \cdots, $ ta viết các số bắt đầu từ $1$ và tăng dần $1,2,3, \cdots$ (các số được viết cho tới khi không tìm được vị trí lẻ) và với vị trị chẵn $a_2,a_4, \cdots$ ta viết các số bắt đầu từ $n$ theo thứ tự giảm dần $n,n-1,n-2, \ldots$ Khi đó dãy các số $a_1, \cdots , a_n$ sẽ là một hoán vị của $n$ số nguyên dương đầu tiên. Ta sẽ chứng minh rằng trong dãy này, không tồn tại $1\le i<j < n$ sao cho $a_i-a_{i+1} \equiv a_j-a_{j+1} \pmod{2n+1}$. Trước hết, để ý rằng $-n+1 \le a_i-a_{i+1} \le n-1$ với mọi $1 \le i< n$ nên $a_i-a_{i+1} \equiv a_j-a_{j+1} \pmod{2n+1}$ khi và chỉ khi $a_i-a_{i+1}=a_j-a_{j+1}$. Tuy nhiên, không khó để chứng minh bằng quy nạp rằng trong dãy $a_1, \ldots , a_n$, với mọi $1 \le i<n$ thì $a_i-a_{i+1}=(-1)^{i}(n-i)$. Do đó $a_i-a_{i+1} \ne a_j-a_{j+1}$ với mọi $1 \le i<j < n$ hay $a_i-a_{i+1} \not\equiv a_j-a_{j+1} \pmod{2n+1}$ với mọi $1 \le i<j< n$.

 

Như vậy ta đã xây dựng xong dãy $a_1, \ldots, a_n$ thoả mãn $a_i-a_{i+1}=(-1)^{i}(n-i)$ với mọi $1 \le i<n$. Do đó $a_{i+n}-a_{i+1+n}=a_{i+1}-a_i=(-1)^{i+1}(n-i)$. Từ đây ta suy ra rằng với cách xây dựng trên thì $-n+1 \le a_i-a_{i+1} \le n-1$ với mọi $1 \le i<2n$. Do đó $a_i-a_{i+1} \equiv a_j-a_{j+1} \pmod{2n+1}$ khi và chỉ khi $a_i-a_{j+1}=a_j-a_{j+1}$. Ta đã chứng minh rằng $a_i-a_{i+1} \ne a_j-a_{j+1}$ cho mọi $1 \le i<j<n$ và hoàn toàn tương tự, điều này cũng đúng với $n \le i<j<2n$. Trường hợp còn lại chưa chứng minh là khi $1\le i<n \le j<2n$. Khi đó $a_i-a_{i+1}=a_j-a_{j+1}=a_{j+1-n}-a_{j-n}$ suy ra tồn tại $1 \le i<j<n$ sao cho $a_i-a_{i+1}=-(a_j-a_{j+1})$ mâu thuẫn theo phép xây dựng của dãy $a_1, \ldots , a_n$ cho rằng $|a_i-a_{i+1}|=(n-i)>(n-i-1)=|a_{i+1}-a_{i+2}|$ với mọi $1 \le i \le n-2$.

 

Vậy, với mọi $1 \le i<j<2n$ thì $a_i-a_{i+1} \not\equiv a_j-a_{j+1} \pmod{2n+1}$. Ta chỉ cần kiểm tra cho trường hợp $j=2n$, tức cần chứng minh $a_{2n}-a_{2n+1}=a_{2n}-a_1 \not\equiv a_i-a_{i+1} \pmod{2n+1}$ (chú ý rằng ta không thể đưa về chứng minh $a_{2n}-a_1 \ne a_i-a_{i+1}$ được vì ta không thể khẳng định $-n+1 \le a_{2n}-a_1 \le n-1$). Để ý rằng $a_{2n} =2n+1-a_n$ và ta theo phép xây dựng trên, ta có thể chứng minh rằng $a_n=\left \lfloor \frac n2 \right \rfloor +1$. Do đó $a_{2n}=2n+1- \left \lfloor \frac n2 \right \rfloor$ nên $a_{2n}-a_1=2n-\left \lfloor \frac n2 \right \rfloor $ suy ra $a_{2n}-a_1 \in \{ n,n+1 \}$. Tuy nhiên $-n+1 \le a_{i}-a_{i+1} \le n-1$ nên không tồn tại $1 \le i <2n$ sao cho $a_i-a_{i+1} \equiv a_{2n}-a_1 \pmod{2n+1}$.

 

Dãy số xây dựng thoả mãn bài toán.

 

Nhận xét. Một điểm thú vị là nếu ban đầu ta chọn các vị trí lẻ $a_1,a_3 \ldots$ không phải là $1,2,3, \ldots$ mà lại là $n,n-1, \ldots$, tương tự với vị trí chẵn. Khi đó, ta sẽ dẫn đến việc khó khăn trong chứng minh không tồn tại $i$ sao cho $a_i-a_{i+1} \equiv a_{2n}-a_1 \pmod{2n+1}$. 


Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 27-03-2017 - 16:28

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#7
One Piece

One Piece

    Binh nhất

  • Thành viên mới
  • 36 Bài viết

Theo lời giải anh Toàn e thử n=6 hoán vị 1 6 2 5 3 4 12 7 11 8 10 9

có hiệu mod 13 là 8 4 10 2 12 5 5 9 3 11 1 8 và thấy nó không thoả
cho hỏi e nhầm ở chỗ nào ạ  



#8
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Theo lời giải anh Toàn e thử n=6 hoán vị 1 6 2 5 3 4 12 7 11 8 10 9

có hiệu mod 13 là 8 4 10 2 12 5 5 9 3 11 1 8 và thấy nó không thoả
cho hỏi e nhầm ở chỗ nào ạ  

Cảm ơn em. Anh có thấy lỗi sai ở lời giải anh ở chỗ $a_{2n}-a_1$. :)

 

Mong mọi người cho cho thêm ý kiến góp ý về bài 6.


Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#9
One Piece

One Piece

    Binh nhất

  • Thành viên mới
  • 36 Bài viết

Giải bài 5 

Ta chứng minh $a_{2n}=a_{i1}.a_{i2}.a_{i3}$ với $i_1 ; i_2 <=N$ với mọi n>N

Chứng minh điều này bằng quy nạp

 theo giả thiết 
$a_n=a_{i1}.a_{i2}.a_{i3} = a_{i1}.a_{i2}.a_{j1}.a_{j2}.a_{j3} <= a_{j1}.a_{j2}.a_{i1+i2+j3}$ với $j_1 , j_2$ <=N theo quy nạp 
đặt t = max căn bậc k của $a_k$

chọn m thoả như thế
ta cm m là số cần tìm 
ta đi cm $a_n= (a_m)^2.a_{n-2m}$
xét dãy $b_n = (a_m)^n / (a_n)^m$

dễ thấy  $b_n$ >=1 với mọi n
ta sẽ cm $b_n>= b_{n+2l}$

$b_{n+2l} = (a_l)^{n+2l} / )a_{n+2l})^l <= (a_l)^{n+2l} / (a_n)^l.(a_l)^{2l} = b_n $
lấy lim => dãy hằng từ 1 lúc nào đó và ta có đpcm 

lỗi latex ạ e cx k biết sửa 


Bài viết đã được chỉnh sửa nội dung bởi One Piece: 27-03-2017 - 08:29


#10
One Piece

One Piece

    Binh nhất

  • Thành viên mới
  • 36 Bài viết

bài 6 ta có thể xếp luôn 2n số lên đường tròn và cố định vị trí số 1 là 1 và 2n là n+1
ta có sắp xếp 1 , a2 , a3 ................. an , 2n
dễ gọi hiệu giữa các số ( 1 , a2 ) ( a2 a3) ........... (an 2n)
là i1 i2 .............. in

ta dễ thấy lấy trị tuyệt đối của i1 i2 ....... in thì nó là hoán vị của 1 2 .......... n và i1+i2+........+in = 1-2n
ta có thể chọn được để thoả ( nếu chọn đc thì có luôn đpcm)
ta xét 1+2+3+.....+n nếu nó đã lẻ thì ta đổi các dấu + thành - để có được 1-2n và chẵn thì ta chọn j và đổi j thành 2n+1-j sau làm như bước 1 
Lời giải khá mơ hồ và e thấy nó sai nhiều hơn là đúng 
 



#11
dungxibo123

dungxibo123

    Sĩ quan

  • Thành viên
  • 330 Bài viết
câu 2a. định lý lucas hơi khó hiểu. em có cách như thế này. có $2017$ là số nguyên tố. từ đầu bài ta suy ra $(n,2017)=1$ suy ra $(n!,2017)=1$ và ta dễ dàng chứng minh được $2n$ chia hết cho $2017$ suy ra điều phải chứng minh. nhưng em không biết nó có đúng không, nhờ các anh chị xem xét giúp

myfb : www.facebook.com/votiendung.0805
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o0o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SỢ HÃI giúp ta tồn tại

NGHỊ LỰC giúp ta đứng vững

KHÁT VỌNG giúp ta tiến về phía trước

Võ Tiến Dũng  

:like  :like  :like  :like  :like 

 

 


#12
dungxibo123

dungxibo123

    Sĩ quan

  • Thành viên
  • 330 Bài viết

Thực ra bài 1 không khó nhưng có lẽ cách phát biểu nó làm các bạn hơi hoang mang. Dĩ nhiên là phải phản chứng, giả sử là 2 con kiến bất kì đều gặp nhau. Vận tốc của 2 con kiến bất kì khác nhau nên dĩ nhiên nếu 2 con cùng xuất phát ở 1 lỗ và ở cùng thời điểm thì chả bao giờ gặp nhau cả ( đi cùng chiều thì ko gặp rồi mà ngược chiều thì càng chẳng bao giờ gặp). 2017 con kiến mà 44 lỗ thì có 45 con cùng chuồng. Và dĩ nhiên để đáp ứng điều kiện phản chứng thì 45 con này xuất phát thời điểm khác nhau, cộng thêm cái thời điểm của cái con xuất phát trễ nhất nó chui vào lỗ nữa thì phải có ít nhất 46 thời điểm. Mâu thuẫn!
Các bài còn lại mình chỉ có chút ý tưởng, bài 2 thì định lí Lucas, bài 5 thì mình chỉ thấy một tính chất là $a_(n+k)/a_n$ bị chặn trên và dưới với $k$ cố định (hình như thế :D) nhưng ko biết dùng được không (^_^). Còn bài 6 thì khả năng là cái dãy này nó sắp xếp theo quy luật để đạt được điều kiện, chỉ cần thử với vài số mò ra quy luật, chỉ ra là coi như chứng minh được rồi.

giả sử thêz thì khi 2 con kiến chui cùng từ một lỗ thì có tính là nó sẽ gặp nhau tại cái lỗ đó không anh ?

myfb : www.facebook.com/votiendung.0805
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o0o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SỢ HÃI giúp ta tồn tại

NGHỊ LỰC giúp ta đứng vững

KHÁT VỌNG giúp ta tiến về phía trước

Võ Tiến Dũng  

:like  :like  :like  :like  :like 

 

 


#13
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Lời giải trước của mình sai nên xin đề xuất lời giải khác cho bài 6, thêm thắt chút về hướng giải, suy nghĩ:

 

Gọi điều kiện $a_i-a_{i+1} \not\equiv a_{j}-a_{j+1} \pmod{2n+1}$ là điều kiện (*).

 

Nhận thấy rằng nếu xây dựng được $a_1, \ldots, a_n$ thì ta xây dựng được cả $2n$ số. Ta muốn đơn giản hoá phép xây dựng càng nhiều càng tốt, do đó ta sẽ thử chỉ gán các số $1,2, \ldots ,n$ cho $a_1, \ldots, a_n$ và không quan tâm đến $n+1, \ldots, 2n$. Nếu như thế thì $-n+1 \le a_i-a_{i+1} \le n-1$ với mọi $1 \le i<n$. Do đó chỉ việc xây dựng cho dãy sao cho $a_i-a_{i+1} \ne a_{j}-a_{j+1}$ cho $1 \le i<j<n$ là ta hoàn toàn có thể đảm bảo điều kiện $a_i-a_{i+1} \not\equiv a_j-a_{j+1} \pmod{2n+1}$ cho $1 \le i<j<n$. Điều này tương đương với việc phải đảm bảo $|a_1-a_2|,|a_2-a_3|, \ldots, |a_{n-1}-a_n|$ là hoán vị của $1,2, \ldots , n-1$.

 

Nếu áp dụng ý tưởng xây dựng trên thì đối với $2n >i \ge n$ thì $a_{i}-a_{i+1}=a_{i+1-n}-a_{i-n}$ nên nếu dãy $a_1, \ldots , a_n$ thoả mãn điều kiện (*) thì dãy $a_{n+1}, \ldots, a_{2n}$ cũng thoả mãn. Tuy nhiên, cần để ý tới $j=2n$ hay $a_{2n}-a_{2n+1}=2n+1-a_{n}-a_1$. Chú ý rằng ta không thể kẹp $2n+1-a_n-a_1$ như đã làm ở trên nên việc thoả mãn điều kiện sẽ gây khó khăn. Thay vào đó, ta có thể chọn trước giá trị cho $a_n,a_1$ để đảm bảo $2n+1-a_n-a_1 \not\equiv a_i-a_{i+1} \pmod{2n+1}$ với mọi $1 \le i<2n$. Do $a_i-a_{i+1} \in \{ \pm 1, \pm 2, \ldots , \pm(n-1) \}$ nên để $2n+1-a_n-a_1 \not\equiv a_i-a_{i+1} \pmod{2n+1}$ vớ mọi $1 \le i<2n$ thì $2n+1-a_n-a_1 \in \{ n,n+1 \}$ hay $a_n+a_1 \in \{n,n+1 \}$.

 

Qua bước lập luận trên, bài toán 6 có thể đưa về việc xây dựng một hoán vị của $1,2, \ldots , n$ là $a_1,a_2, \ldots, a_n$ sao cho $|a_i-a_{i+1}| \ne |a_j-a_{j+1}|$ với mọi $1 \le i<j<n$ và $a_1+a_n \in \{n,n+1\}$. Đến đây, để cho dễ hình dung, hãy tưởng tượng các số $1,2, \ldots, n$ được viết theo thứ tự từ trái qua phải, một con cóc bắt đầu ở vị trí số $a_1$ và nhảy với khoảng cách $|a_1-a_2|$ tới vị trí $a_2$ và cứ thế cho đến khi nó đến vị trí $a_n$. Thử thách của ta là làm sao cho con cóc có thể

 

+) Đi qua hết các vị trí $1, \ldots , n$ mỗi vị trí đúng $1$ lần.

+) Nhảy với khoảng cách nhảy $|a_i-a_{i+1}|$ khác nhau tại mỗi lần.

+) Bắt đầu tại $a_1$ và kết thúc tại $a_n$ sao cho $a_1+a_n \in \{n,n+1 \}$.

 

Trường hợp 1. Nếu thì $n=4k+1$: 

Con cóc bắt đầu đi từ vị trí $k+1$ và thực hiện như sau: (dấu ngoặc mình thêm vào chỉ để cho dễ hình dung quy luật dãy):

$(k+1, 3k+2), (k,3k+3),(k-1, 3k+4), \ldots , (k-i,3k+(i+3)), \ldots, ( k-(k-2),3k+(k+1)), 1$

Khoảng cách con cóc nhảy cho mỗi bước này là $2k+1,2k+2, \ldots, 4k$.

 

Ta nhận thấy lúc này, con cóc chỉ còn các vị trí $k+2, \ldots , 3k,3k+1$ là chưa nhảy tới và còn khoảng cách $1,2, \ldots, 2k$ là chưa dùng để nhảy. Con cóc lúc này bắt đầu tại $1$ và có thể nhảy như sau:

 

$1,\color{blue} {2k+1},\color{red} {2k+2},\color{blue}{2k},\color{red} {2k+3},\color{blue} {2k-1},\color{red} {2k+4}, \ldots,  \color{blue} {k+2} ,\color{red} {3k+1}$

 

Như vậy con cóc đã nhảy qua hết $n=4k+1$ vị trí và dùng hết $4k$ khoảng cách nhảy, bắt đầu tại $a_1=k+1$ và kết thúc với $a_n=3k+1$ với $(k+1)+(3k+1)=n+1$. Một ví dụ con cóc nhảy cho $n=9$:

 

IMG_0169.JPG

 

Trường hợp 2. Nếu $n=4k+3$:

 

$(k+1,3k+3),(k,3k+4), \ldots , (k-(k-2),3k+(k+2))=(2,4k+2),(1,4k+3)$.

 

Như vậy con cóc còn các vị trí $k+2, \ldots , 3k+2$ chưa nhảy tới và khoảng cách nhảy $1,2 \ldots, 2k+1$ chưa dùng. Bước tiếp theo, con cóc có thể nhảy như sau, bắt đầu từ $4k+3$:

 

$4k+3,\color{blue}{2k+2},\color{red}{2k+1}, \color{blue}{2k+3}, \color{red}{2k}, \ldots, \color{blue}{3k+1},\color{red}{k+2},\color{blue}{3k+2}$.

Bước nhảy trên thoả mãn đề bài. Con cóc bắt đầu với $a_1=k+1$ và kết thúc với $a_n=3k+2$ với $a_1+a_n=4k+3=n$.

 

Trường hợp 3. Nếu $n=4k$:

 

$(k,3k+1),(k-1,3k+2), \ldots (k-(k-1),3k+k)=(1,4k)$.

 

Như vậy, con cóc còn các vị trí $k+1, \ldots, 3k$ chưa nhảy tới và khoảng cách nhảy $1,2 \ldots, 2k$ chưa dùng. Con cóc bước tiếp theo có thể nhảy như sau, bắt đầu từ vị trí $4k$:

 

$4k, \color{blue}{2k},\color{red}{2k+1},\color{blue}{2k-1}, \color{red}{2k+2}, \ldots, \color{blue}{k+1},\color{red}{3k}$

Con cóc hoàn thành nhiệm vụ.

 

Trường hợp 4. Nếu $n=4k+2$: 

 

$(k+1,3k+3),(k,3k+4), \ldots , (k-(k-2),4k+2),1$.

 

Như vậy, con cóc còn các vị trí $k+2, \ldots, 3k+2$ chưa nhảy tới và khoảng cách nhảy $1,2 \ldots, 2k+1$ chưa dùng. Con cóc bước tiếp theo có thể nhảy như sau, bắt đầu từ vị trí $1$:
 

$1, \color{blue}{2k+2},\color{red}{2k+1},\color{blue}{2k+3},\color{red}{2k}, \ldots, \color{blue}{k+2},\color{red}{3k+2}$.

 

Vậy con cóc có thể có các bước nhảy thoả mãn đề bài. Thứ tự vị trí mà con cóc nhảy tới chính là thứ tự của dãy số $a_1, \ldots, a_n$. Như vậy ta đã xây dựng được dãy $a_1, \ldots, a_n$ thoả mãn nên suy ra dãy $a_1, \ldots, a_{2n}$ cũng thoả mãn theo lập luận trên.


Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 27-03-2017 - 14:32

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#14
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

Thực ra bài 1 không khó nhưng có lẽ cách phát biểu nó làm các bạn hơi hoang mang. Dĩ nhiên là phải phản chứng, giả sử là 2 con kiến bất kì đều gặp nhau. Vận tốc của 2 con kiến bất kì khác nhau nên dĩ nhiên nếu 2 con cùng xuất phát ở 1 lỗ và ở cùng thời điểm thì chả bao giờ gặp nhau cả ( đi cùng chiều thì ko gặp rồi mà ngược chiều thì càng chẳng bao giờ gặp). 2017 con kiến mà 44 lỗ thì có 45 con cùng chuồng. Và dĩ nhiên để đáp ứng điều kiện phản chứng thì 45 con này xuất phát thời điểm khác nhau, cộng thêm cái thời điểm của cái con xuất phát trễ nhất nó chui vào lỗ nữa thì phải có ít nhất 46 thời điểm. Mâu thuẫn!

 

Dựa vào lời giải của anh Karl thì ta có thể làm mạnh kết quả một tí: bài toán đúng cho $|T| \le 46$.

Có $2017=37+44 \cdot 45$ nên tồn tại lỗ có $46$ con kiến xuất phát. Nếu $46$ con kiến này xuất phát tại thời điểm khác nhau + thời điểm con kiến chậm trở về lỗ nhất trong $46$ con này thì sẽ có $47$ thời điểm, mâu thuẫn.

 

 

giả sử thêz thì khi 2 con kiến chui cùng từ một lỗ thì có tính là nó sẽ gặp nhau tại cái lỗ đó không anh ?

Chắc là không, vì nếu mà như dungxibo123 nói thì khi đó sẽ có trường hợp tất cả các con kiến đều gặp nhau khi cùng xuất phát tại 1 lỗ chung, dẫn đến bài toán sai.


Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 27-03-2017 - 17:54

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#15
dungxibo123

dungxibo123

    Sĩ quan

  • Thành viên
  • 330 Bài viết

https://artofproblem...411300p7929731 

trên AoPS cũng đã có 1 cách giải dùng hàm định giá nhưng em không biết có liên quan gì đên cách giải của mọi người không   :)) nhưng nhìn chung là đáng học hỏi (bài 2)

https://artofproblem..._selection_test

còn link này là tất cả đề ạ


Bài viết đã được chỉnh sửa nội dung bởi dungxibo123: 28-03-2017 - 09:49

myfb : www.facebook.com/votiendung.0805
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o0o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SỢ HÃI giúp ta tồn tại

NGHỊ LỰC giúp ta đứng vững

KHÁT VỌNG giúp ta tiến về phía trước

Võ Tiến Dũng  

:like  :like  :like  :like  :like 

 

 


#16
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết

 

 

Chắc là không, vì nếu mà như dungxibo123 nói thì khi đó sẽ có trường hợp tất cả các con kiến đều gặp nhau khi cùng xuất phát tại 1 lỗ chung, dẫn đến bài toán sai.

Nếu như cả $2017$ con đều lên từ một lỗ thì không có 2 con nào xuống cùng 1 lỗ tại cùng 1 thời điểm. Tại mỗi thời điểm sẽ có $43$ lỗ để xuống nên có nhiều nhất $43$ con xuống lỗ. Tuy nhiên vì có $2017$ con đã lên nên số lần xuống ít nhất là $\frac{2017}{43}>45$



#17
Karl Heinrich Marx

Karl Heinrich Marx

    Sĩ quan

  • Thành viên
  • 321 Bài viết

Bài 6 như thế này. Đầu tiên vẽ 1 hình tròn, vẽ tiếp $n+1$ đường kính, kẻ 1 đường kính với 2 mút là 0. Nửa trên đường kính này đánh dấu từ 1 đến $n$, nửa dưới đánh dấu từ -1 đến -n. Sao cho 2 mút của đường kính có tổng bằng 0. Xét với một điểm trên đường tròn thì ta gọi đầu mút còn lại của đường kính chứa điểm này là điểm đối của nó. Ta cần xác định $n+1$ số đầu tiên sao cho $a_i-a_{i+1}$ không đồng dư với $2n+1$ với $1 \le i \le n$.

Từ vị trí số 1 ta đặt $a_1$ nhảy sang vị trí bên cạnh của điểm đối số $1$ là -2 đặt là $a_2$, nhảy tiếp qua điểm bên cạnh của điểm đối của $a_2$ là $a_3$. Khi đó thì $|a_i - a_{i+1}| = 2i+1$ tức là chúng phân biệt theo mod $2n+1$ và theo cách nhảy này thì ta ko đi qua 2 điểm nào cùng đường kính, mỗi bước ta đi qua một đường kính lần lượt từ $1$ đến $n$. Tuy nhiên chú ý là $a_{n+1}$ là -1 (tức là 2n), thì khi đến đường kính thứ $n$ ta sẽ có $|a_n-a_{n+1}|$ sẽ là $|n-(-1)|$ hoặc $|-n+1|$ bằng $n+1$ hoặc $n-1$ tức là phải chừa bước $i$ nào mà $|a_i-a_{i+1}|$  bằng $n-1$ hoặc là $n+1$ ra (trường hợp 2 số này chẵn thì 2 giá trị tương ứng là $n$ và $n+2$). Giờ ta tránh né điều này bằng cách đi đến điểm có giá trị như vậy ta sẽ ko làm theo quy tắc cũ mà đi sang số bên cạnh trên đường tròn để khi đó $|a_i-a_{i+1}|=1$ sau đó lại tiếp tục quy tắc cũ.

Vấn đề là làm sao xác định $i$ để đi bước tránh này. Chú ý là nếu mãi làm theo quy tắc thì $a_i$ chỉ đi qua các đỉnh số dương lẻ. Nhưng vì có bước tránh nên suy ra sau bước đó thì $a_i$ chỉ có thể là các sống dương chẵn. Do đó nếu $n$ lẻ thì $a_n$ là $-n$ nên $|a_n-a_{n+1}|=n-1$, cần tránh giá trị $n+2$ ra nên thay vì đi đến điểm $\frac{n+1}{2}$ theo quy tắc cũ thì đi sang điểm bên cạnh. Tương tự nếu $n$ lẻ thì tương ứng với điểm $\frac{n-1}{2}$. Theo quy tắc này thì $|a_i-a_{i+1}|$ sẽ lấp đầy các số lẻ từ 1 đến $2n-1$ (có thể $|a_n-a_{n+1}|$ chẵn nhưng $2n+1$ trừ số này không nằm trong các số lẻ còn lại).



#18
the unknown

the unknown

    Thượng sĩ

  • Thành viên
  • 208 Bài viết

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.

 


Bài viết đã được chỉnh sửa nội dung bởi the unknown: 30-03-2017 - 11:15

$\texttt{If you don't know where you are going, any road will get you there}$


#19
dungxibo123

dungxibo123

    Sĩ quan

  • Thành viên
  • 330 Bài viết

lời giải chính thức đã có ở đây


myfb : www.facebook.com/votiendung.0805
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o0o~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SỢ HÃI giúp ta tồn tại

NGHỊ LỰC giúp ta đứng vững

KHÁT VỌNG giúp ta tiến về phía trước

Võ Tiến Dũng  

:like  :like  :like  :like  :like 

 

 


#20
lamNMP01

lamNMP01

    Hạ sĩ

  • Thành viên
  • 96 Bài viết

Bài 1 ta xét hệ trục toạ độ Oxy, trong đó Ox là trục thời gian và Oy là trục quãng đường. Xét các bộ (xi,yj) trong đó có max 45.44=1980 bộ như trên .

Xét đồ thị có <= mn đỉnh có >= mn+1 cạnh . CM khi đó có 2 cạnh đội một không cắt nhau.

Mở rộng : Đồ thị có k^4mn đỉnh, trong đó có >= k^4mn+1 cạnh. Khi đó có min k+1 cạnh đôi một k cắt nhau .

 ( Trong phòng thi em làm cả 1và 6 mà vẫn tạch :<)






2 người đang xem chủ đề

0 thành viên, 2 khách, 0 thành viên ẩn danh