Hướng tới kỳ thi chọn đội tuyển Việt Nam dự IMO 2012

[Mashimaru]

Bài 17. Với mỗi số thực dương $\alpha $, ký hiệu $S(\alpha) = \{[n\alpha]: n = 1, 2,...\} $. Chứng minh rằng không tồn tại các số thực dương $\alpha, \beta, \gamma $ sao cho ta có phân hoạch $\mathbb{N} = S(\alpha) \cup S(\beta) \cup S(\gamma) $.

Đừng nghĩ đến định lý Beatty nếu bạn không muốn lạc hướng giống mình

Bài 18. Khánh và Châu chơi trò bốc sỏi từ một đống sỏi lúc đầu có $n $ viên. Hai bạn thay phiên nhau bốc sỏi sao cho số lượng sỏi bốc mỗi lượt phải có dạng $p - 1 $ với $p $ là một số nguyên tố. Ai lấy được viên sỏi cuối cùng là thắng cuộc. Khánh đi trước và hai bạn đều chơi tối ưu. Chứng minh rằng tồn tại vô hạn $n $ để Châu có chiến thuật thắng.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[avip]

Nguyên văn bởi Mashimaru

Bài 18. Khánh và Châu chơi trò bốc sỏi từ một đống sỏi lúc đầu có $n $ viên. Hai bạn thay phiên nhau bốc sỏi sao cho số lượng sỏi bốc mỗi lượt phải có dạng $p - 1 $ với $p $ là một số nguyên tố. Ai lấy được viên sỏi cuối cùng là thắng cuộc. Khánh đi trước và hai bạn đều chơi tối ưu. Chứng minh rằng tồn tại vô hạn $n $ để Châu có chiến thuật thắng.

Em giải thử, không biết đúng không:

Trước tiên đặt $T,S $ lần lượt là tập các số tự nhiên $n $ sao cho nếu ban đầu đống sỏi có $n $ viên thì Khánh, Châu có chiến thuật thắng. Qui ước $0 \in S $.
Ta cmđ: $S \cup T $ là một phân hoạch của $\mathbb{N} $ và $3,8 $ là hai số nguyên dương đầu tiên thuộc $S $.
Với $m \in \mathbb{N} $, đặt $S_m = \{n \in S \; | \; n < m \} $.

Giả sử ban đầu đống sỏi có $N $ viên. Ta có nhận xét: $N \in S \Leftrightarrow N - n + 1 $ không là số nguyên tố với mọi $n \in S_N \; (1) $. Thực vậy:
Chiều thuận: Giả sử $N \in S $. Ta có: dù Khánh bốc $p-1 $ viên sỏi với $p $ là số nguyên tố nào đi chăng nữa thì Châu cũng có chiến thuật thắng, tức là $N-(p-1) $ không thuộc $S $. Ta cm được chiều thuận.
Chiều đảo: tương tự.

Từ đây, giả sử $S $ hữu hạn, ta đặt $S = \{a_1, ... , a_s \} $ (tăng dần). Xét số sỏi là $N = \prod_{i=1}^s a_i -1 $. Từ mệnh đề $(1) $ dễ thấy $N \in S $ và $N > a_s $ (mâu thuẫn). Vậy ta có đpcm.

Mệnh đề $(1) $ cũng cho ta thuật toán tìm $S_m, T_m $ với $m $ lớn tùy ý (và tùy khả năng máy).

Anh Hiếu ra đề có thâm ý quá

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Mashimaru]

Nguyên văn bởi avip

Giả sử ban đầu đống sỏi có $N $ viên. Ta có nhận xét: $N \in S \Leftrightarrow N - n + 1 $ không là số nguyên tố với mọi $n \in S_N \; (1) $. Thực vậy:
Chiều thuận: Giả sử $N \in S $. Ta có: dù Khánh bốc $p-1 $ viên sỏi với $p $ là số nguyên tố nào đi chăng nữa thì Châu cũng có chiến thuật thắng, tức là $N-(p-1) $ không thuộc $S $. Ta cm được chiều thuận.
Chiều đảo: tương tự.

Ý tưởng sử dụng định lý Thặng dư Trung Hoa của em là có lý, nhưng anh nghĩ mệnh đề (1) (hoặc ít ra là chứng minh của em ở chiều thuận, vì chiều đảo em chỉ ghi "tương tự") có phần không ổn. Cụ thể, đống sỏi có $N $ viên, là trường hợp thắng của Châu, thế thì Khánh lấy $p - 1 $ viên sỏi thế nào cũng phải đưa đến trường hợp thắng cho Châu, tức là $N - p + 1 \in S $ chứ không phải $N - p + 1 \notin S $ như em nói. Để tránh các sự nhầm lẫn không đáng có này, anh thường xem xét một số là "số thắng" nếu người nhìn thấy nó sẽ thắng và là "số thua" nếu ngược lại
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[avip]

Nguyên văn bởi Mashimaru

Ý tưởng sử dụng định lý Thặng dư Trung Hoa của em là có lý, nhưng anh nghĩ mệnh đề (1) (hoặc ít ra là chứng minh của em ở chiều thuận, vì chiều đảo em chỉ ghi "tương tự") có phần không ổn. Cụ thể, đống sỏi có $N $ viên, là trường hợp thắng của Châu, thế thì Khánh lấy $p - 1 $ viên sỏi thế nào cũng phải đưa đến trường hợp thắng cho Châu, tức là $N - p + 1 \in S $ chứ không phải $N - p + 1 \notin S $ như em nói. Để tránh các sự nhầm lẫn không đáng có này, anh thường xem xét một số là "số thắng" nếu người nhìn thấy nó sẽ thắng và là "số thua" nếu ngược lại

Trong cách đặt T,S của em có chữ "ban đầu", tức là không khác gì số thắng, số thua đâu anh.
Để em ghi cụ thể Chiều đảo:
Giả sử $N-n+1 $ không là số nguyên tố với mọi $n \in S_N $. Nếu $N \notin S $ thì tồn tại số nguyên tố $p $ sao cho $N - p +1 \in S $ (mâu thuẫn).
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[Mashimaru]

Nguyên văn bởi avip

Trong cách đặt T,S của em có chữ "ban đầu", tức là không khác gì số thắng, số thua đâu anh.
Để em ghi cụ thể Chiều đảo:
Giả sử $N-n+1 $ không là số nguyên tố với mọi $n \in S_N $. Nếu $N \notin S $ thì tồn tại số nguyên tố $p $ sao cho $N - p +1 \in S $ (mâu thuẫn).

Xin lỗi em, anh nhầm mất. Em làm đúng rồi. Vậy là bài này đơn giản hơn anh tưởng
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[hien123]

Nguyên văn bởi Mashimaru

Bài 17. Với mỗi số thực dương $\alpha $, ký hiệu $S(\alpha) = \{[n\alpha]: n = 1, 2,...\} $. Chứng minh rằng không tồn tại các số thực dương $\alpha, \beta, \gamma $ sao cho ta có phân hoạch $\mathbb{N} = S(\alpha) \cup S(\beta) \cup S(\gamma) $.

Đừng nghĩ đến định lý Beatty nếu bạn không muốn lạc hướng giống mình

Bài 18. Khánh và Châu chơi trò bốc sỏi từ một đống sỏi lúc đầu có $n $ viên. Hai bạn thay phiên nhau bốc sỏi sao cho số lượng sỏi bốc mỗi lượt phải có dạng $p - 1 $ với $p $ là một số nguyên tố. Ai lấy được viên sỏi cuối cùng là thắng cuộc. Khánh đi trước và hai bạn đều chơi tối ưu. Chứng minh rằng tồn tại vô hạn $n $ để Châu có chiến thuật thắng.

Bài 17 sẽ được chứng minh một cách dễ dàng nhờ khẳng định:
$\lim_{n \to \infty }\frac{1}{n}\sum_{k=1}^{n}\left \{ kx \right \}=\frac{1}{2} $ với x là một số vô tỉ bất kì.
Tuy nhiên minh không chứng minh được khẳng định này, mong mọi người giúp đỡ. Không biết anh Hiếu có đi theo con đường này không nhỉ?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[avip]

Nguyên văn bởi Mashimaru

Bài 18. Khánh và Châu chơi trò bốc sỏi từ một đống sỏi lúc đầu có $n $ viên. Hai bạn thay phiên nhau bốc sỏi sao cho số lượng sỏi bốc mỗi lượt phải có dạng $p - 1 $ với $p $ là một số nguyên tố. Ai lấy được viên sỏi cuối cùng là thắng cuộc. Khánh đi trước và hai bạn đều chơi tối ưu. Chứng minh rằng tồn tại vô hạn $n $ để Châu có chiến thuật thắng.

Nguyên văn bởi avip

Trước tiên đặt $T,S $ lần lượt là tập các số tự nhiên $n $ sao cho nếu ban đầu đống sỏi có $n $ viên thì Khánh, Châu có chiến thuật thắng. Qui ước $0 \in S $.
Ta cmđ: $S \cup T $ là một phân hoạch của $\mathbb{N} $ và $3,8 $ là hai số nguyên dương đầu tiên thuộc $S $.
Với $m \in \mathbb{N} $, đặt $S_m = \{n \in S \; | \; n < m \} $.

Giả sử ban đầu đống sỏi có $N $ viên. Ta có nhận xét: $N \in S \Leftrightarrow N - n + 1 $ không là số nguyên tố với mọi $n \in S_N \; (1) $. Thực vậy:
Chiều thuận: Giả sử $N \in S $. Ta có: dù Khánh bốc $p-1 $ viên sỏi với $p $ là số nguyên tố nào đi chăng nữa thì Châu cũng có chiến thuật thắng, tức là $N-(p-1) $ không thuộc $S $. Ta cm được chiều thuận.
Chiều đảo: tương tự.

Từ đây, giả sử $S $ hữu hạn, ta đặt $S = \{a_1, ... , a_s \} $ (tăng dần). Xét số sỏi là $N = \prod_{i=1}^s a_i -1 $. Từ mệnh đề $(1) $ dễ thấy $N \in S $ và $N > a_s $ (mâu thuẫn). Vậy ta có đpcm.

Bằng máy tính, em dự đoán một kết quả cho bài toán này (đúng đến $S_{7000} $). Mọi người cùng thảo luận xem sao.

Chứng minh $\forall n \in S $: nếu $n-3 \notin S $ thì $n+3 \in S $.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[gogo123]

Nguyên văn bởi Mashimaru

Bài 17. Với mỗi số thực dương $\alpha $, ký hiệu $S(\alpha) = \{[n\alpha]: n = 1, 2,...\} $. Chứng minh rằng không tồn tại các số thực dương $\alpha, \beta, \gamma $ sao cho ta có phân hoạch $\mathbb{N} = S(\alpha) \cup S(\beta) \cup S(\gamma) $.

Đừng nghĩ đến định lý Beatty nếu bạn không muốn lạc hướng giống mình

Lời giải bài này đây:
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]