Đến nội dung

IMOer

IMOer

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

#638962 Marathon số học Olympic

Gửi bởi IMOer trong 08-06-2016 - 17:09

Mình xin đề xuất bài tiếp theo.

Bài 51: (Nguồn: AMM)

Tìm tất cả các số nguyên dương $n$ sao cho $\binom{n}{k}$ là ước của$\binom{2n}{2k}$ với mọi số nguyên dương $k$ không vượt quá $n$.




#638928 Marathon số học Olympic

Gửi bởi IMOer trong 08-06-2016 - 14:37

Đây là ý kiến của mình từ lâu rồi không phải nói bài này đâu nhé. Do topic có mục đích giao lưu học hỏi là chính nên ở 1 số bài toán nếu người đề xuất có khác với các cách được đưa ra thì cũng nên post lời giải của mình lên.

p/s bài 36 anh imoer có thể post đáp án được không ạ

Cảm ơn Hoàng đã nhắc.

Đây là lời giải của mình cho bài 36:

 

Gọi số cần tìm là ${{n}^{2}}$.

Theo bài ra ta có: ${{n}^{2}}=\underbrace{{{111...1}_{\left( 3 \right)}}}_{m}=\frac{{{3}^{m}}-1}{2}$ hay ${{3}^{m}}-1=2{{n}^{2}}$.

Trường hợp 1: $m=2k;\ k\ge 1$, khi đó ta có: ${{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$.

Xét phương trình Pell: ${{x}^{2}}-2{{y}^{2}}=1$.

Phương trình này có tất cả các nghiệm không âm là: $\left\{ \begin{array}{l} {{x}_{0}}=1;\ {{x}_{1}}=3 \\ {{y}_{0}}=0;\ {{y}_{1}}=2 \\ {{x}_{n+1}}=6{{x}_{n}}-{{x}_{n-1}} \\ {{y}_{n+1}}=6{{y}_{n}}-{{y}_{n-1}} \\ \end{array} \right.$

Nhận thấy: ${{x}_{n}}>3$ với mọi $n>2$ và $\left\{ \begin{array}{l} {{x}_{n}}\equiv 0\ \left( \bmod \ 9 \right)\Leftrightarrow n\equiv 3\ \left( \bmod \ 6 \right) \\ {{x}_{n}}\equiv 0\ \left( \bmod \ 11 \right)\Leftrightarrow n\equiv 3\ \left( \bmod \ 6 \right) \\ \end{array} \right.$

Nên với $n>2$ thì ${{x}_{n}}$ không thể có dạng ${{3}^{k}}$.

Từ đó suy ra phương trình ${{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$ có nghiệm $n$ nguyên dương duy nhất là $\left( k,\ n \right)=\left( 1,\ 2 \right)$.

Trường hợp 2: $m=2k+1;\ k\ge 0$ khi đó ta có: $3{{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$.

Xét phương trình Pell: $3{{x}^{2}}-2{{y}^{2}}=1$.

Phương trình này có tất cả các nghiệm không âm là: $\left\{ \begin{array}{l} {{x}_{0}}=1;\ {{x}_{1}}=9 \\ {{y}_{0}}=1;\ {{y}_{1}}=11 \\ {{x}_{n+1}}=10{{x}_{n}}-{{x}_{n-1}} \\ {{y}_{n+1}}=10{{y}_{n}}-{{y}_{n-1}} \\ \end{array} \right.$

Nhận thấy: ${{x}_{n}}>9$ với mọi $n>2$ và $\left\{ \begin{array}{l} {{x}_{n}}\equiv 0\ \left( \bmod \ 27 \right)\Leftrightarrow n\equiv 4\ \left( \bmod \ 9 \right) \\ {{x}_{n}}\equiv 0\ \left( \bmod \ 17 \right)\Leftrightarrow n\equiv 4\ \left( \bmod \ 9 \right) \\ \end{array} \right.$

Nên với $n>2$ thì ${{x}_{n}}$ không thể có dạng ${{3}^{k}}$.

Từ đó suy ra phương trình $3{{\left( {{3}^{k}} \right)}^{2}}-2{{n}^{2}}=1$ có các nghiệm nguyên không âm là $\left( k,\ n \right)=\left( 0,\ 1 \right)$ và $\left( k,\ n \right)=\left( 2,\ 11 \right)$.

Vậy các số chính phương cần tìm là: $1, 4, 121$.




#638918 Marathon số học Olympic

Gửi bởi IMOer trong 08-06-2016 - 14:08

Bài 50. (AMM) Chứng minh rằng nếu ta chọn $n$ số tự nhiên từ $2n$ số nguyên dương đầu tiên thì ta luôn tìm được số square - free.
Nói thêm về số square-free, ta gọi $n$ là số square-free nếu và chỉ nếu với $p\in\mathbb{P}$ sao cho $p\mid n$ thì $v_{p}(n) = 1$.

Remark

Một hướng đi hơi giải tích cho bài này:

Kết quả quen thuộc: $\displaystyle \sum_{n=1}^{\infty} \dfrac{1}{n^2}=\dfrac{\pi^2}{6}$

Với mỗi số nguyên tố $p$ thì có $\left\lfloor\dfrac{2n}{p^2}\right\rfloor$ số không là số square-free và $\le 2n$.

Vậy số các số không phải square-free và $\le 2n$ sẽ không vượt quá:

$\displaystyle S=\sum_{p\textrm{ prime}} \left\lfloor \dfrac{2n}{p^2}\right\rfloor\le 2n\sum_{p \textrm{ prime}}\dfrac{1}{p^2}$

Lại có: $\displaystyle \sum_{p \textrm{ prime}}\dfrac{1}{p^2}<\sum_{k=1}^{\infty}\dfrac{1}{k^2}-1-\dfrac{1}{4^2}-\dfrac{1}{6^2}-\dfrac{1}{8^2}-\dfrac{1}{9^2}-\dfrac{1}{10^2}-\dfrac{1}{12^2}-\dfrac{1}{14^2}-\dfrac{1}{15^2}-\dfrac{1}{16^2}=\dfrac{\pi^2}{6}-\dfrac{29177437}{25401600}<\dfrac{1}{2}$

Nên có ít hơn $n$ số không phải số square-free trong $2n$ số nguyên dương đầu tiên.

Từ đó suy ra, nếu lấy $n$ số bất kỳ từ $2n$ số nguyên dương đầu tiên thì luôn tồn tại ít nhất 1 số square-free.




#638902 Marathon số học Olympic

Gửi bởi IMOer trong 08-06-2016 - 12:35

Hình như mấy kì thi khác mình đọc thì định lí Dirichlet được thay tên bằng định lí Pigeonhole nội dung tương tự được sử dụng không chứng minh 

"Định lý Pigeonhole" mà bạn nói được gọi là "Nguyên lý Dirichlet" chứ không phải "Định lý Dirichlet về sự tồn tại số nguyên tố" bạn nhé!

"Nguyên lý Dirichlet" thì luôn được dùng rồi.




#638880 Marathon số học Olympic

Gửi bởi IMOer trong 08-06-2016 - 10:36

Thực ra nguyên lí Đi-rich-lê chứng minh rất phức tạp nhưng theo mình biết thì khi thi cử không cần cm nên thấy cũng nhiều bài toán phải sử dụng luôn chứ cũng khồng có gì quá cả

p/s bài 50 Ego ơi

 

Định lý Dirichlet sẽ chỉ được sử dụng không chứng minh khi dự thi IMO. Còn các kỳ thi khác thì đều không được sử dụng khi không chứng minh lại.




#638811 Marathon Tổ hợp và rời rạc VMF

Gửi bởi IMOer trong 07-06-2016 - 22:10

Cũng đã lâu mà chưa ai giải quyết bài 13. Mình xin phép đăng luôn bài tiếp theo, nếu trong vòng 2 ngày tới không ai giải bài 13 thì mình sẽ đăng lời giải.

 

Bài 14: Có 2 con châu chấu nằm tại 2 điểm nguyên trên mặt phẳng toạ độ. Mỗi lần thổi còi, có đúng 1 con châu chấu nhảy tới một điểm nguyên khác sao cho khoảng cách giữa 2 con châu chấu luôn không đổi. Hỏi sau hữu hạn lần thổi còi, 2 con châu chấu có thể đổi chỗ cho nhau được không? (mỗi con sẽ nhảy tới vị trí ban đầu của con kia)




#638805 Marathon số học Olympic

Gửi bởi IMOer trong 07-06-2016 - 21:41

Lời giải bài 48:

Bổ đề: Với ${{a}^{5}}+{{b}^{5}}={{c}^{2}}$ và $\gcd \left( a,b \right)=1$ thì $5|c$ hoặc $a+b$ là một số chính phương.

Chứng minh bổ đề: Ta có: ${{c}^{2}}=\left( a+b \right)\left( {{a}^{4}}-{{a}^{3}}b+{{a}^{2}}{{b}^{2}}-a{{b}^{3}}+{{b}^{4}} \right)$

Gọi $d=\gcd \left( a+b,{{a}^{4}}-{{a}^{3}}b+{{a}^{2}}{{b}^{2}}-a{{b}^{3}}+{{b}^{4}} \right)$ thì suy ra: $d|5{{a}^{4}}$ và $d|5{{b}^{4}}$.

Mà $\gcd \left( a,b \right)=1$ suy ra: $d|5$.

Nếu $d=1$ thì suy ra: $a+b$ là một số chính phương.

Nếu $d=5$ thì suy ra: $5|c$.

 

Quay lại bài toán, ta có:

Nhận thấy nếu $(x,y)$ là nghiệm thì $(x,-y)$ cũng là nghiệm nên ta sẽ chỉ xét $y\ge0$.

Với $y=0$ thì ta suy ra: $x=-1$

Với $y=1$ thì ta suy ra: $x=0$

Với $y\ge 2$ thì ta cũng suy ra: $x\ge 2$.

Ta có: ${{y}^{2}}={{x}^{5}}+1=\left( x+1 \right)\left( {{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1 \right)$

Nếu $x+1$ là số chính phương thì ta suy ra: ${{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1$ cũng là số chính phương.

Với $x\ge 2$ thì ${{\left( 2{{x}^{2}}-x \right)}^{2}}<4\left( {{x}^{4}}-{{x}^{3}}+{{x}^{2}}-x+1 \right)<{{\left( 2{{x}^{2}}-x+1 \right)}^{2}}$ nên trường hợp này vô nghiệm.

Nếu $x+1$ không là số chính phương thì theo bổ đề ta có: $5|y$.

Lại có: ${{x}^{5}}=\left( y-1 \right)\left( y+1 \right)$.

Nếu $2|y$ thì suy ra: $\left\{ \begin{array}{l}y-1={{a}^{5}} \\y+1={{b}^{5}}\end{array} \right.$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1$.

Khi đó suy ra: ${{b}^{5}}-{{a}^{5}}=2$, dễ thấy vô nghiệm.

Nếu $2\nmid y$ thì ta có 2 trường hợp sau:

Trường hợp 1: $y+1=2{{a}^{5}};\ y-1=16{{b}^{5}}$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1,\ a$ lẻ. Khi đó dễ dàng suy ra được: $a>b\Rightarrow a-1\ge b$.

Ta có: ${{a}^{10}}-{{\left( 2b \right)}^{5}}={{\left( \frac{y+1}{2} \right)}^{2}}-2\left( y-1 \right)={{\left( \frac{y-3}{2} \right)}^{2}}$

Vì $\frac{y-3}{2}\in \mathbb{N}$ và không chia hết cho 5 nên theo bổ đề ta có: ${{a}^{2}}-2b$ là số chính phương, vô lý vì: ${{a}^{2}}>{{a}^{2}}-2b\ge {{a}^{2}}-2\left( a-1 \right)>{{\left( a-1 \right)}^{2}}$.

Trường hợp 2: $y+1=16{{a}^{5}};\ y-1=2{{b}^{5}}$ với $a,b\in \mathbb{N},\ \gcd \left( a,b \right)=1,\ b$ lẻ. Giải quyết tương tự suy ra trường hợp này vô nghiệm.

 

Bằng một cách tương tự, ta cũng có thể giải quyết được bài toán sau:

"Phương trình $x^{2017}+1=y^2$ chỉ có các nghiệm nguyên $(x,y)=(-1;0)$ và $(x,y)=(0;\pm1)$.

 

Bài 49: (Nguồn: Sưu tầm)

Cho $S$ là tập khác rỗng các số nguyên tố thoả mãn với $n\ge 1$ và $p_1,p_2,...,p_n\in S$ thì mọi ước nguyên tố của $p_1p_2...p_n+1$ cũng thuộc $S$.

Chứng minh rằng mọi số nguyên tố đều thuộc $S$.




#638330 Marathon số học Olympic

Gửi bởi IMOer trong 05-06-2016 - 18:26

Bài 44 : ( India ) Giải phương trình nghiệm tự nhiên : $7^{x}=3^{y}+4$ ( gợi ý là xét $mod37$ vì nếu không lần mò mất thời gian )

Lời giải bài 44: (Không xét modulo 37)

Với $y=0$ thì $7^x=4$, không thoả mãn.

Với $y=1$ thì $7^x=7\Leftrightarrow x=1$.

Với $y\ge 2$ thì $3^y+4\equiv 4\ (\bmod{9})$ nên $7^x\equiv 4\ (\bmod{9})$. Từ đó suy ra: $x\equiv 2\ (\bmod{3})$.

Từ đó suy ra: $7^x$ khi chia cho $13$ có thể dư $10,11,2$ hoặc $3$.

Lại có: $3^y\equiv 3\ (\bmod{7})$ nên $y\equiv 1\ (\bmod{6})$.

Từ đó suy ra: $3^y+4\equiv 7\ (\bmod{13})$.

Vậy phương trình vô nghiệm khi $y\ge 2$.

Vậy phương trình có nghiệm tự nhiên duy nhất $(x,y)=(1,1)$

 

Bài 45: (Sưu tầm)

Cho $n$ là một số nguyên dương. Chứng minh rằng mọi bội số của $10^n-1$ đều có ít nhất $n$ chữ số khác 0.




#637787 Marathon Tổ hợp và rời rạc VMF

Gửi bởi IMOer trong 03-06-2016 - 14:01

square.png

 

Các cặp điểm đó là các cặp đỉnh của hình vuông đỏ trong hình đính kèm.




#637771 Marathon Tổ hợp và rời rạc VMF

Gửi bởi IMOer trong 03-06-2016 - 12:06

Bạn xem lại đề 13 nhé. Trong TH $n=3$ thì $S_{3}=0$;$S_{2}=8$;$S_{0}=12$

 

Đề bài hoàn toàn đúng bạn ạ.

Với $n=3$ thì $S_0=8$ bạn nhé, chỉ có 8 cặp điểm nằm trên đường chéo của các hình chữ nhật $1\times 2$ mới thuộc $S_0$ thôi.




#637749 Marathon Tổ hợp và rời rạc VMF

Gửi bởi IMOer trong 03-06-2016 - 09:52

Lời giải bài 12:

Trước tiên, ta chứng minh với $k=n$ thì sẽ không có chiến thuật đảm bảo thắng.

Khi $k=n$ thì trường hợp xấu nhất ở lần chọn bài đầu tiên là ta chọn đúng $n$ lá bài mà các số trên đó là một hoán vị của $(1,2,...,n)$. Giả sử ở lần tiếp theo, ta chọn $l$ lá bài cũ và $n-l$ lá bài mới, khi đó tồn tại ít nhất 1 cách phù thuỷ xáo bài sao cho $n$ lá bài ở lần chọn này vẫn là một hoán vị của $(1,2,...,n)$. Dẫn tới, ở mọi lần chọn bài, ta đều có thể chọn phải $n$ lá bài mà các số trên đó là một hoán vị của $(1,2,...,n)$, hay nói cách khác là ta không thể đảm bảo có thể thắng trong hữu hạn lần chọn.

Ta sẽ chứng minh tiếp, với $2\le k<n$ thì ta sẽ có chiến thuật thắng bất chấp mọi cách xáo trộn bài của phù thuỷ.

Đánh số các quân bài từ $1$ đến $2n$. Giả sử mỗi lần bốc bài dưới đây đều rất "đen đủi" tức là không có 2 lá bài nào trong $k$ lá bài được chọn ghi cùng 1 số.

Đầu tiên ta sẽ bốc $k$ lá bài $(1,2,...,k)$ thì ta sẽ biết được tập hợp các số ghi trên các quân bài này. Sau đó, ta sẽ bốc $k$ lá bài $(2,3,...,k+1)$ thì ta sẽ biết được giá trị ghi trên lá bài thứ $k+1$ và từ đó ta sẽ biết được $k+1$ lá bài đầu tiên chứa các số như thế nào (cho dù xáo trộn các lá bài thì tập các số này vẫn không đổi). Cứ tiếp tục bốc $k$ lá bài $(i,i+1,...,i+k-1)$ với $i$ nhận giá trị lần lượt từ $3$ đến $2n-k$, khi đó ta sẽ biết được $2n-1$ lá bài đầu tiên chứa các số như thế nào. Từ đó ta sẽ suy ra được giá trị ghi trên lá bài thứ $2n$.

Bắt đầu lại quá trình trên một lần nữa theo cách tương tự, ta sẽ xác định được số ghi trên lá bài thứ $2n-1$. Cứ như vậy, ta sẽ xác định được giá trị ghi trên $2n-k$ lá bài từ $k+1$ đến $2n$.

Theo nguyên lý Dirichlet thì ta sẽ chọn được 2 lá bài ghi cùng 1 số, như vậy lần chọn cuối cùng này ta hoàn toàn có thể chọn được $k$ lá bài mà có 2 lá bài ghi cùng 1 số.

 

Mình xin phép đề xuất 1 bài tương đối dễ thở để các bạn có động lực với topic này hơn.

Bài 13: (Nguồn: Sưu tầm)

Cho $n$ là số nguyên dương, $n\ge 2$. Xét tập $X_n$ gồm các điểm nguyên $(x;y)$ trên mặt phẳng tọa độ $Oxy$ với $1\le x,y\le n$. Gọi $S_k$ là số cặp điểm là cặp đỉnh chung của $k$ hình vuông có các đỉnh thuộc $X_n$ với $k=\overline{0;3}$. Chứng minh rằng: $S_0=S_2+2S_3$.




#637505 Marathon số học Olympic

Gửi bởi IMOer trong 01-06-2016 - 22:34

Dễ thấy rằng với $3 \nmid b_i$ với $i \ge 2$. Do đó chỉ có $(a,b)=(2,3)$ hay số chính phương đó là $4$.

Dòng này sai, ví dụ: $b_3=99, b_5=3363$ đều là các số chia hết cho 3.

 

Khi đó $b_n=u_n+2v_n=9u_{n-1}+22v_{n-1}$. Với $i \ge 2$ thì $3 \nmid v_i$. Thật vậy, nếu $3 \mid v_n$ mà $3 \mid b_n$ dẫn đến $3 \mid u_n$, điều này mâu thuẫn vì $u_n^2-6v_n^2=1$. Vậy ta chỉ cần xét $(a_1,b_1)$. Ta thấy $b_1=9, a_1=11$. Hay số chính phương ta tìm được ở trường hợp này là $11^2$ và $1$.

 

Đoạn này cũng sai, ví dụ $v_2=198; v_5=192060$ đều chia hết cho 3.




#637269 Marathon số học Olympic

Gửi bởi IMOer trong 31-05-2016 - 23:03

Cá nhân em nghĩ thì em thích phần này, hình như nó là analytic number theory. Nhưng tính ra cũng hơi cao cấp :P. Thỉnh thoảng ta cũng nên chêm vào cho vui :3 =))
Bài 36 em có hiểu sai không nhỉ, biểu diễn $n = \sum_{i = 0}^{k}3^{i} = \frac{3^{k + 1} - 1}{2}$.

 

Hình như bài $36$ của anh có vấn đề và nếu đúng nó không hợp với tiêu chí topic lắm . 

P/s : Điểm after hôm nay  :D

Về phần số học giải tích mình chia sẻ một tài liệu và mọi người search gg theo hai cụm từ sau : " AIANT.pdf " hoặc " Introduction to analytic number theory hardy  "

 

Xin lỗi các bạn, mình đã sửa lại đề đúng.




#637259 Marathon số học Olympic

Gửi bởi IMOer trong 31-05-2016 - 22:43

Bài 35 : Gọi $n>1$ nguyên dương , $f(n)$ là số các số nguyên nhỏ hơn $n$ và nguyên tố cùng nhau với $n$ , gọi $a_{1},a_{2},...a_{f(n)}$ là các số thuộc $[n]$ và nguyên tồ cùng nhau với $n$ . Giả sử tất cả các ước nguyên tố của $n$ là $p_{1},p_{2},...p_{k}$ Chứng minh đẳng thức sau :

                                        $\sum_{i=1}^{f(n)}a_{i}^{2} = \frac{f(n)}{6}(2n^{2}+(-1)^{k}\prod_{i=1}^{k}p_{i})$

Đây cũng là một bài thuộc Giải tích số học thì hợp lý hơn.

Lời giải sử dụng một số kết quả sau:

1. Công thức nghịch đảo Möbius:

\[f(n)=\sum_{d|n}g(d) \Leftrightarrow g(n)=\sum_{d|n} f(d)\mu\left(\dfrac{n}{d}\right)\]

với $\mu(n)$ là hàm Möbius.

2. $\displaystyle \sum_{d|n}\mu(d)=\sum_{d|n}\mu\left(\dfrac{n}{d}\right)=0$ khi $n>1$

3. $\displaystyle \sum_{d|n} d\mu\left(\dfrac{n}{d}\right)=\varphi(n)$

4. $\displaystyle \sum_{d|n} d\mu(d)=\prod_{\begin{array}{c}p\in\wp\\p|n\end{array}}(1-p)$

5. $\displaystyle \sum_{d|n} \dfrac{\varphi_k(d)}{d^k}=\dfrac{1^k+2^k+...+n^k}{n^k}$ với $\displaystyle \varphi_k(n)=\sum_{\begin{array}{c}d=1\\(n,d)=1\end{array}}^n d^k$

 

Sử dụng các kết quả trên ta có:

\[\begin{array}{l}\dfrac{\varphi_2(n)}{n^2}&=\displaystyle\sum_{d|n}\dfrac{1^2+2^2+...+d^2}{d^2}\mu\left(\dfrac{n}{d}\right)\\&=\displaystyle\sum_{d|n}\dfrac{d(d+1)(2d+1)}{d^2}\mu\left(\dfrac{n}{d}\right)\\&=\dfrac{1}{6}\left(\displaystyle \sum_{d|n}2d\mu\left(\dfrac{n}{d}\right)+\sum_{d|n}\dfrac{1}{d}\mu\left(\dfrac{n}{d}\right)\right)\\&\displaystyle=\dfrac{1}{3}\varphi(n)+\dfrac{1}{6}\sum_{d|n}\dfrac{d}{n}\mu(d)\\&\displaystyle=\dfrac{1}{3}\varphi(n)+\dfrac{1}{6n}\prod_{\begin{array}{c}p\in\wp\\p|n\end{array}}(1-p)\end{array}\]
Từ đây dễ dàng nhận được điều cần chứng minh.
 
Mình xin phép đề xuất 1 bài Số học "nguyên chất" để tiếp tục topic và cũng mong các bạn cũng có thể học được nhiều hơn từ các bài toán thuộc topic này. Cứ "cao cấp" mãi như bài 34 hay 35 cũng nản.
Bài 36: (Nguồn: Sưu tầm)
Tìm tất cả các số chính phương sao cho biểu diễn của nó trong cơ số 3 chỉ chứa chữ số 1.



#637181 Marathon số học Olympic

Gửi bởi IMOer trong 31-05-2016 - 18:41

Bài toán 34. (Gabriel Dospinescu) Ký hiệu $\sigma(n)$ là tổng các ước nguyên dương của $n$. Chứng minh rằng với mọi $n > 1$ thì đẳng thức sau đúng: $$\sum_{k = 0}^{n - 1}(-1)^{k}(2k + 1)\sigma\left(\frac{n^{2} + n}{2} - \frac{k^{2} + k}{2}\right) = (-1)^{n - 1}\frac{n(n + 1)(2n + 1)}{6}$$

Bài này xếp vào mục giải tích thì hợp hơn.