Đến nội dung


Zaraki

Đăng ký: 07-03-2011
Offline Đăng nhập: Riêng tư
****-

Bài viết của tôi gửi

Trong chủ đề: $x\sqrt{3}-y\sqrt{7}> \frac...

13-05-2017 - 19:24

Khoá topic. Bài là P1 tạp chí Pi số 4 chưa hết hạn.


Trong chủ đề: Thảo luận về việc làm ĐHV

13-05-2017 - 19:19

Tách topic để không làm loãng topic đăng kí.

 

Xin đính chính một chút, mình không nghĩ việc đăng kí mấy "lần" trong topic đăng kí là quan trọng. Người đăng kí chỉ cần viết một lần trong topic là đủ rồi, không cần phải viết lại để làm rác topic làm gì. Nếu các bạn vẫn đóng góp cho diễn đàn sau khi đăng kí thì tất nhiên các anh BQT và anh em trong ĐHV sẽ công nhận bạn. Tiêu chí ĐHV mà diễn đàn đang tìm kiếm (đây chỉ là ý kiến chủ quan nhưng mình nghĩ anh em ĐHV chắc cũng sẽ nhất trí) là lịch sự trong giao tiếp, bài viết có chất lượng (chất lượng ở đây không nhất thiết phải là có lời giải hay mà có thể là đưa lên bài toán hay hoặc giúp đỡ thành viên khác), nếu năng nổ thì càng tốt.

 

Mình nghĩ việc này không có gì phải tranh cãi nữa nên xin được khoá luôn topic. 


Trong chủ đề: gõ thử công thức toán

12-05-2017 - 07:47



$\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \clip(4.22,-2.86) rectangle (13.12,4.98); \draw(8.34,0.2) circle (2.330321866180721cm); \draw (6.86,-1.6)-- (9.827822560606734,-1.5935395251149667); \draw (8.334927274150267,2.5303163449309705)-- (6.86,-1.6); \draw (8.334927274150267,2.5303163449309705)-- (9.827822560606734,-1.5935395251149667); \draw (8.334927274150267,2.5303163449309705)-- (8.345072725849732,-2.1303163449309706); \draw (6.035459992649993,-0.1456810011025011)-- (8.345072725849732,-2.1303163449309706); \draw [domain=4.22:13.12] plot(\x,{(-17.62190491273828--2.3096127331997396*\x)/1.9846353438284694}); \draw (7.290242190121254,-0.3951701881975841)-- (7.725725721359615,-1.5981154536142386); \draw (8.770410805388625,1.327371079514322)-- (7.725725721359615,-1.5981154536142386); \draw(7.290242190121254,-0.3951701881975841) circle (1.2793448391923807cm); \draw(8.770410805388625,1.327371079514322) circle (3.1064188996832454cm); \draw (6.035459992649993,-0.1456810011025011)-- (6.86,-1.6); \draw (6.86,-1.6)-- (8.345072725849732,-2.1303163449309706); \draw (8.345072725849732,-2.1303163449309706)-- (9.827822560606734,-1.5935395251149667); \draw (6.035459992649993,-0.1456810011025011)-- (9.827822560606734,-1.5935395251149667); \begin{normalsize} \draw [fill=white] (8.34,0.2) circle (1.5pt); \draw[color=black] (8.44,0.41) node {$O$}; \draw [fill=white] (6.86,-1.6) circle (1.5pt); \draw[color=black] (6.68,-1.63) node {$B$}; \draw [fill=white] (9.827822560606734,-1.5935395251149667) circle (1.5pt); \draw[color=black] (9.92,-1.67) node {$C$}; \draw [fill=white] (8.334927274150267,2.5303163449309705) circle (1.5pt); \draw[color=black] (8.4,2.83) node {$A$}; \draw [fill=white] (8.345072725849732,-2.1303163449309706) circle (1.5pt); \draw[color=black] (8.36,-2.23) node {$K$}; \draw [fill=white] (6.035459992649993,-0.1456810011025011) circle (1.5pt); \draw[color=black] (5.94,0.07) node {$I$}; \draw [fill=white] (7.725725721359615,-1.5981154536142386) circle (1.5pt); \draw[color=black] (7.78,-1.35) node {$M$}; \draw [fill=white] (6.880592857004804,-0.8718982273583699) circle (1.5pt); \draw [fill=white] (7.290242190121254,-0.3951701881975841) circle (1.5pt); \draw[color=black] (7.12,-0.25) node {$D$}; \draw [fill=white] (8.770410805388625,1.327371079514322) circle (1.5pt); \draw[color=black] (8.96,1.37) node {$E$}; \end{normalsize} \end{tikzpicture}$

Bạn có thể xem tại đây.


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

27-03-2017 - 17:47

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.


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

27-03-2017 - 14:11

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

 

File gửi kèm  IMG_0169.JPG   37.88K   5 Số lần tải

 

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.