KỲ THI CHỌN ĐỘI TUYỂN QUỐC GIA DỰ THI IMO 2018
Ngày thi thứ nhất (30/3/2018)
Thời gian làm bài là $4\tfrac{1}{2}$ giờ
Bài viết đã được chỉnh sửa nội dung bởi CF Gauss: 31-03-2018 - 17:15
KỲ THI CHỌN ĐỘI TUYỂN QUỐC GIA DỰ THI IMO 2018
Ngày thi thứ nhất (30/3/2018)
Thời gian làm bài là $4\tfrac{1}{2}$ giờ
Bài viết đã được chỉnh sửa nội dung bởi CF Gauss: 31-03-2018 - 17:15
Bài 2
a, Xét bảng 2k x k mỗi hàng chứa một xâu nhị phân có độ dài bằng k khác nhau sau đó bổ sung vào bảng 2018-k cột mà không có ô nào được đánh số
Khi đó ta sẽ có đc bảng tm bài
có ngắn quá không nhỉ ??
Người ta không mắc sai lầm vì dốt mà là vì tưởng là mình giỏi
Bài 5a
Giả sử m chẵn và n chẵn => m+1 và n+1 lẻ
ta tô màu giao lộ A(1;1) có màu trắng
Tô màu tất cả (m+1)(n+1) giao lộ theo quy tắc
Giao lộ (a;b) tô màu trắng nếu a và b cùng tính chẵn lẻ
tô màu đen nếu a và b khác tính chẵn lẻ
Xuất phát từ điểm A đi theo các cạnh song song với các cạnh của HCN => đi qua giao lộ trắng rồi sẽ qua giao lộ đen rồi qua giao lộ trắng v..v
mà người đó đi qua giao qua tất cả (m+1)(n+1)+1 giao lộ ( vì tính A đi và A về 2 lần)
khi đó (m+1)(n+1)+1 chắn mà xuất phát từ giao lộ trắng qua chẵn giao lộ thì cập bến phải ở giao lộ đen ( mà A trắng )=> vô lý
m lẻ hoặc n lẻ thì chỉ cần chỉ ra cách đi thỏa mãn là đc
Bài viết đã được chỉnh sửa nội dung bởi YoLo: 02-04-2018 - 22:47
Người ta không mắc sai lầm vì dốt mà là vì tưởng là mình giỏi
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.
Bài 3:
Ta có một nhận xét là $(k,n)=1$ thì $(n-k,n)=1$, tức là ta có thể chia tập $A_n$ thành 2 tập $B_n$ và $C_n$, sao cho tập $B_n$ chứa tất cả các phần tử của $A_n$ mà bé hơn $\frac{n}{2}$, $C_n$ chứa các phần tử còn lại. Khi đó ta có $ k \in B_n \Rightarrow n-k \in C_n$.
Đặt $c_n$ là phần tử nhỏ nhất của $C_n$ thì $c_n> \frac{n}{2}>1$, chú ý là $B_n$ luôn chứa $1$ và $C_n$ luôn chứa $n-1$. Mình quên latex nhiêu rồi nên lười viết ra nhưng có thể dễ dàng suy ra là $P_n(x)=(1+x^{c_n-1}).Q_n(x)$. Vậy luôn tồn tại $r_n \ge 1$ thỏa mãn.
ý b thì để $P_n(x)$ bất khả quy thì $Q_n(x)=1$, điều này có nghĩa là $A_n$ có đúng 2 phần tử suy ra $P_n(x)=1+x^{n-2}$ và để nó bất khả quy trên Z thì phải tồn tại $m$ để $n-2 = 2^m$, đến đây thì ta cần tìm $n$ dạng $2^m+2$ mà $(n,k)>1$ với mọi $1<k<n-1$, nếu $m>2$ thì suy ra $(3,n)>1$ suy ra $3 | 2(2^{m-1}+1)$ suy ra $m$ chẵn. Mà $(5,n)>1$ nên cũng suy ra $5 | 2(2^{m-1}+1)$ suy ra $m$ lẻ. Mâu thuẫn!
Vậy $m \le 2$, tìm được $3$,$4$ và $6$ thỏa đề bài.
Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 03-04-2018 - 01:09
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ý.
$\texttt{If you don't know where you are going, any road will get you there}$
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ý.
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ài 5 ý b mình không tìm được một cách lập luận nào chặt chẽ và hợp lí cả cho trường hợp mà một số chẵn và một số lẻ và số lẻ lớn hơn số chẵn. Bạn có ý tưởng gì không?
Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 04-04-2018 - 03:31
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õ.
$\texttt{If you don't know where you are going, any road will get you there}$
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õ.
À xin lỗi mình không chú ý đến điều kiện là đầy đủ. Nếu như vậy thì chỉ cần thêm một chút lập luận là xét một chuỗi $A$ bất kì sinh ra từ cái dòng ta muốn xóa. Nếu dòng này có một số $a$ nào đó là $0$ hoặc $1$ nằm ngoài $k$ cột đã nêu thì xét một chuỗi giống y chuỗi $A$ chỉ là thay cái cột chứa $a$ bằng $1-a$ (tức là đảo $0$ với $1$ và $1$ với $0$ thôi) thì bảng đầy đủ nên tồn tại một hàng sinh ra được chuỗi mới này và dĩ nhiên ở cái cột đó thì hàng đó không chứa gì cả, vì cột này chứa $a$ thì không chứa $1-a$. Do đó hàng này sẽ sinh ra được chuỗi $A$.
0 thành viên, 1 khách, 0 thành viên ẩn danh