Có.
Lấy 2016 điểm cùng thuộc nửa đường tròn (trừ 2 đầu mút) thì 3 điểm bất kỳ trong chúng tạo thành 1 tam giác tù.
Có 49 mục bởi IMOer (Tìm giới hạn từ 05-05-2020)
Đã gửi bởi IMOer on 27-05-2016 - 21:47 trong Tổ hợp và rời rạc
Có.
Lấy 2016 điểm cùng thuộc nửa đường tròn (trừ 2 đầu mút) thì 3 điểm bất kỳ trong chúng tạo thành 1 tam giác tù.
Đã gửi bởi IMOer on 03-06-2016 - 09:52 trong Tổ hợp và rời rạc
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$.
Đã gửi bởi IMOer on 03-06-2016 - 12:06 trong Tổ hợp và rời rạc
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.
Đã gửi bởi IMOer on 10-06-2016 - 16:31 trong Tổ hợp và rời rạc
Bài 15:
Một ảo thuật gia với $1$ bộ bài có $52$ quân bài, có $4$ loại bài là cơ, chuồn, rô, tép, mỗi loại bài có $13$ quân bài. Đầu tiên nhà ảo thuật sẽ đưa bộ bài cho khán giả xào bài, tất cả các quân bài sau khi được xào lại được đặt úp, chồng lên nhau. Trợ thủ của nhà ảo thuật được quyền xem thứ tự các quân bài và cũng có thể viết $1$ trong $2$ số $0$ hoặc $1$ vào mặt sau mỗi quân bài nhưng không được sắp xếp lại bộ bài và cũng không được nói cho nhà ảo thuật biết thứ tự của bộ bài. Mỗi lượt nhà ảo thuật sẽ đoán loại bài của lá bài trên cùng của xấp bài, sau đó loại nó ra khỏi bộ bài. Nhà ảo thuật cứ tiếp tục như thế trong $52$ lượt. Hỏi có chiến lược nào giúp anh ta đoán được đúng loại bài của ít nhất $30$ quân bài không?
Mình có một số thắc mắc sau:
- Trợ lý và nhà ảo thuật có được thống nhất chiến thuật từ trước khi xáo bài hay không?
- Có bắt buộc trợ lý phải viết số vào sau lá bài không?
Đã gửi bởi IMOer on 09-06-2016 - 15:13 trong Tổ hợp và rời rạc
Lời giải bài 13:
Gọi ${{P}_{n}}$ là số hình vuông có các đỉnh thuộc ${{X}_{n}}$.
Nhận xét: từ một hình vuông cạnh $s$ có cạnh song song với trục tọa độ, ta có thể dựng được thêm $s-1$ hình vuông nội tiếp.
Mà có ${{(n-s)}^{2}}$ hình vuông cạnh $s$ có cạnh song song với trục tọa độ.
$\displaystyle \Rightarrow {{P}_{n}}=\sum_{s=1}^{n-1}{{{(n-s)}^{2}}}s=\frac{{{n}^{2}}({{n}^{2}}-1)}{12}=\frac{C_{{{n}^{2}}}^{2}}{6}$
Mỗi hình vuông có 6 đoạn nối các cặp đỉnh nên có $6{{P}_{n}}$ đoạn nối các cặp đỉnh.
Số cặp điểm là:${{S}_{0}}+{{S}_{1}}+{{S}_{2}}+{{S}_{3}}=C_{{{n}^{2}}}^{2}=6{{P}_{n}}$.
Số cạnh và số đường chéo của ${{P}_{n}}$ hình vuông là: ${{S}_{1}}+2{{S}_{2}}+3{{S}_{3}}=6{{P}_{n}}$.
Từ đó suy ra: ${{S}_{0}}={{S}_{2}}+2{{S}_{3}}$.
Bạn JUV đăng bài tiếp theo lên nhé!
Đã gửi bởi IMOer on 03-06-2016 - 14:01 trong Tổ hợp và rời rạc
Đã gửi bởi IMOer on 07-06-2016 - 22:10 trong Tổ hợp và rời rạc
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)
Đã gửi bởi IMOer on 30-05-2016 - 16:57 trong Số học
Lời giải bài 20*:
Vì $\left( a-b \right)\left( a-c \right)\left( a-d \right)\left( b-c \right)\left( b-d \right)\left( c-d \right)\ \vdots \ 12$ với mọi $a,b,c,d\in \mathbb{Z}$ nên $\gcd \left( a+b+c+d,12 \right)=1$.
Gọi $p$ là ước nguyên tố của $a+b+c+d$. Khi đó $p\ne 2;\ p\ne 3$.
Giả sử: $a+b$ không chia hết cho $p$.
Khi đó ta có: $a+b\equiv -\left( c+d \right)\ \left( \bmod \ p \right)\Rightarrow {{\left( a+b \right)}^{3}}\equiv -{{\left( c+d \right)}^{3}}\ \left( \bmod \ p \right)$
Mà ${{a}^{3}}+{{b}^{3}}\equiv -\left( {{c}^{3}}+{{d}^{3}} \right)\ \left( \bmod \ p \right)$ nên suy ra: $3ab\left( a+b \right)=-3cd\left( c+d \right)\ \left( \bmod \ p \right)$.
Do $a+b\not\equiv 0\left( \bmod \ p \right)$ và $p\ne3$ nên suy ra được: $ab\equiv cd\ \left( \bmod \ p \right)$.
Lại có: ${{\left( a+b \right)}^{2}}\equiv {{\left( c+d \right)}^{2}}\ \left( \bmod \ p \right)\Rightarrow {{a}^{2}}+{{b}^{2}}\equiv {{c}^{2}}+{{d}^{2}}\ \left( \bmod \ p \right)$
Mà ${{a}^{2}}+{{b}^{2}}+{{c}^{2}}+{{d}^{2}}\equiv 0\ \left( \bmod \ p \right)\Rightarrow {{a}^{2}}+{{b}^{2}}\equiv {{c}^{2}}+{{d}^{2}}\equiv 0\ \left( \bmod \ p \right)$ do $p\ne 2$.
Vì $a,b,c,d$ không chia hết cho $p$ nên suy ra $p$ chỉ có dạng $4k+1$.
Nên suy ra tất cả các ước nguyên tố của $a+b+c+d$ đều có dạng $4k+1$, điều phải chứng minh.
Đã gửi bởi IMOer on 04-07-2016 - 09:15 trong Số học
Đã gửi bởi IMOer on 30-05-2016 - 17:57 trong Số học
@IMOer: Lời giải bài 24 đẹp với lạ quá, bạn có thể giới thiệu cho mọi người tại sao bạn lại nghĩ đến việc chọn dãy như thế được không ạ?
Mình xin chia sẻ với Ego và các bạn khác, tại sao mình lại chọn dãy như vậy.
Từ phương trình ban đầu ta viết lại được dưới dạng: $(2x+y)^2-5y^2=n$.
Đến đây, mình nghĩ tới phương trình Pell liên kết với phương trình này là $x^2-5y^2=1$.
Phương trình Pell này có nghiệm cơ bản $(x,y)=(9,4)$.
Từ đó mình tìm ra được là $(x,y)$ là nghiệm thì $(5x+8y,8x+13y)$ cũng là nghiệm.
Linh cảm mách bảo mình $5,8,13$ là 3 số liên tiếp của dãy Fibonacci nên khả năng 3 số hạng liên tiếp khác của dãy Fibonacci cũng đúng.
Và nó đúng thật.
Đến đây thì mọi người sẽ thấy lời giải đó hoàn toàn tự nhiên chứ không hề có mưu mẹo gì.
Đã gửi bởi IMOer on 31-05-2016 - 10:48 trong Số học
Lời giải bài 31:
Xét các số trên $\mathbb{Z}/\mathbb{Z}_p$.
Ta có: $x^2+y^2+z^2\equiv 2axyz\ (\bmod{p}) \Leftrightarrow (z-axy)^2\equiv (a^2x^2-1)y^2-x^2\ (\bmod{p})$.
Với mỗi cặp số $x,y\in\{0,1,\ldots,p-1\}$ thì số nghiệm $z$ là: $1+\left(\dfrac{(a^2x^2-1)y^2-x^2}{p}\right)$.
Suy ra số nghiệm của phương trình đồng dư đã cho là:
\[S=p^2+\sum_{x=0}^{p-1}\sum_{y=0}^{p-1}\left(\dfrac{(a^2x^2-1)y^2-x^2}{p}\right)\]
Áp dụng bổ đề: $\sum_{x=0}^{p-1} \left(\dfrac{ax^2+bx+c}{p}\right)=\left\{\begin{array}{l}-\left(\dfrac{a}{p}\right)&,p\nmid b^2-4ac\\(p-1)\left(\dfrac{a}{p}\right)&,p|b^2-4ac\end{array}\right.$ ta có:
\[\sum_{y=0}^{p-1} \left(\dfrac{(a^2x^2-1)y^2-x^2}{p}\right)=\left\{\begin{array}{l}-\left(\dfrac{a^2x^2-1}{p}\right)&,ax\not\equiv \pm1\ (\bmod{p})\\(p-1)\left(\dfrac{a^2x^2-1}{p}\right)&,ax\equiv \pm1\ (\bmod{p})\end{array}\right.\]
Suy ra: \[S=p^2+2p\left(\dfrac{-1}{p}\right)-\sum_{x=0}^{p-1}\left(\dfrac{a^2x^2-1}{p}\right)=\left(p+\left(\dfrac{-1}{p}\right)\right)^2\]
Bài 32: (Nguồn: Sưu tầm)
Tìm tất cả các số nguyên dương $m\equiv 2\ (\bmod{4})$ sao cho tồn tại các số tự nhiên $n, k$ và số nguyên tố $p$ sao cho $\dfrac{m^{2^n-1}-1}{m-1}=m^n+p^k$.
Đã gửi bởi IMOer on 05-06-2016 - 18:26 trong Số học
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.
Đã gửi bởi IMOer on 30-05-2016 - 14:39 trong Số học
Lời giải bài 24:
Với $n=0$ thì phương trình ${{x}^{2}}+xy-{{y}^{2}}=0$ có nghiệm duy nhất $\left( x,y \right)=\left( 0,0 \right)$ hay kết luận của bài toán sai.
Ta chỉ chứng minh với $n$ là số nguyên dương.
Nhận thấy $\left( x,y \right)$ là nghiệm của phương trình ${{x}^{2}}+xy-{{y}^{2}}=n$ thì $\left( -x,-y \right)$ cũng là nghiệm của phương trình này.
Gọi $\left( {{x}_{0}},{{y}_{0}} \right)$ là nghiệm của phương trình ${{x}^{2}}+xy-{{y}^{2}}=n$ sao cho $x_0>0$ hoặc $y_0>0$.
Xét dãy: $\left\{ \begin{array}{l}{{x}_{k}}={{F}_{k}}{{x}_{0}}+{{F}_{k+1}}{{y}_{0}}\\{{y}_{k}}={{F}_{k+1}}{{x}_{0}}+{{F}_{k+2}}{{y}_{0}}\end{array} \right.$ với ${{F}_{k}}$ là số hạng thứ $k$ của dãy Fibonacci.
Khi đó ta có: $\left( {{x}_{k}},\ {{y}_{k}} \right)$ cũng là nghiệm của phương trình ${{x}^{2}}+xy-{{y}^{2}}=n$.
Từ đó suy ra phương trình ${{x}^{2}}+xy-{{y}^{2}}=n$ có vô số nghiệm nguyên.
Đã gửi bởi IMOer on 31-05-2016 - 18:41 trong Số học
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.
Đã gửi bởi IMOer on 31-05-2016 - 22:43 trong Số học
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ó:
Đã gửi bởi IMOer on 07-06-2016 - 21:41 trong Số học
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$.
Đã gửi bởi IMOer on 31-05-2016 - 23:03 trong Số học
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 . 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
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.
Đã gửi bởi IMOer on 08-06-2016 - 10:36 trong Số học
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.
Đã gửi bởi IMOer on 27-06-2016 - 11:15 trong Số học
Lời giải bài 63:
*) Với $3^{\frac{p-1}{2}}+1\equiv0\ (\bmod{p})$ thì $3^{\frac{p-1}{2}}\equiv -1\ (\bmod{p})$.
Gọi $d$ là cấp của 3 theo modulo $p$, khi đó: $d\nmid \dfrac{p-1}{2}$.
Mà $3^{p-1}\equiv 1\ (\bmod{p})$ nên $d\mid p-1$, dẫn tới: $d=p-1$. Từ đó suy ra: $p$ là số nguyên tố.
*) Với $p$ là số nguyên tố, ta có: $p\equiv 2\ (\bmod{3})$ và $p\equiv 1\ (\bmod{4})$.
Ta có: $\left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)=\left(\dfrac{2}{3}\right)=-1$.
Nên: $3^{\frac{p-1}{2}}\equiv\left(\dfrac{3}{p}\right)\equiv -1\ (\bmod{p})$.
Bài 64: Tìm tất cả các hàm số $f:\mathbb{Z}^+\to\mathbb{Z}^+$ thoả mãn đồng thời:
(i) $f(n)\ge n$ với mọi $n\in\mathbb{Z}^+$.
(ii) $f(m+n)\mid f(m)+f(n)$ với mọi $m,n\in\mathbb{Z}^+$.
Đã gửi bởi IMOer on 01-06-2016 - 22:34 trong Số học
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.
Đã gửi bởi IMOer on 29-05-2016 - 13:32 trong Số học
Lời giải bài 16:
Giả sử số nguyên dương $n$ vừa là số vui vẻ vừa là số ác quỷ và $n={{2}^{s}}\left( 2k+1 \right)$, với $k,s\in \mathbb{N}$.
Xét trường hợp $k\ge 1$:
Chọn $m={{2}^{{{2}^{s}}-1}}\cdot {{3}^{2k}}$, ta có: $\tau \left( m \right)={{2}^{s}}\left( 2k+1 \right)=n$.
Lại có: $m=\frac{{{\left( {{2}^{{{2}^{s-1}}-1}}\cdot {{3}^{k}} \right)}^{2}}\cdot \left( {{2}^{{{2}^{s-1}}}}\cdot {{3}^{k-1}} \right)}{\left( {{2}^{{{2}^{s-1}}-1}}\cdot {{3}^{k}} \right)-\left( {{2}^{{{2}^{s-1}}}}\cdot {{3}^{k-1}} \right)}$ nên $m$ là số vui vẻ, hay $n$ không phải là số ác quỷ.
Suy ra: $k=0$, hay $n={{2}^{k}}$.
Giả sử $n=\frac{{{a}^{2}}b}{a-b}$ với $a>b>0$.
Gọi $d=\gcd \left( a,\ b \right)$ và $a=d{{a}_{1}},\ b=d{{b}_{1}},\ \gcd \left( {{a}_{1}},\ {{b}_{1}} \right)=1$.
Khi đó ta có: $n\left( {{a}_{1}}-{{b}_{1}} \right)={{d}^{2}}a_{1}^{2}b_{1}^{2}\Leftrightarrow {{2}^{k}}\left( {{a}_{1}}-{{b}_{1}} \right)={{d}^{2}}a_{1}^{2}b_{1}^{2}$.
Vì ${{a}_{1}}>1,\ \gcd \left( {{a}_{1}},\ {{a}_{1}}-{{b}_{1}} \right)=1$ nên $2\ |\ {{a}_{1}}$, dẫn tới ${{a}_{1}}-{{b}_{1}}$ lẻ.
Xét số mũ của 2 ở 2 vế, ta sẽ nhận được $k$ phải là số chẵn.
Hay nếu $n$ là số vừa vui vẻ vừa ác quỷ thì $n$ phải có dạng ${{4}^{k}}$.
Ta sẽ chứng minh mọi số có dạng ${{4}^{k}}$ đều là số vui vẻ và số ác quỷ.
Thật vậy, ${{4}^{k}}=\frac{{{\left( {{2}^{k}} \right)}^{2}}\cdot {{2}^{k-1}}}{{{2}^{k}}-{{2}^{k-1}}}$ nên ${{4}^{k}}$ là số vui vẻ.
Lại có: $\tau \left( {{4}^{k}} \right)=2k+1$ là một số lẻ nên ${{4}^{k}}$ là số ác quỷ.
Bài 17: (Vietnam IMO training 2011)
Giả sử $P(x)$ là đa thức hệ số nguyên không có nghiệm bội. Chứng minh rằng với mọi $r$ nguyên dương, tồn tại $n$ nguyên dương sao cho trong phân tích $P(n)$ thành thừa số nguyên tố có ít nhất $r+1$ số nguyên tố tham gia với số mũ bằng 1.
Đã gửi bởi IMOer on 30-05-2016 - 11:53 trong Số học
Lời giải bài 22:
Đặt $\alpha =\sqrt[3]{2}$ và $\omega ={{e}^{\frac{2\pi i}{3}}}$.
Phương trình đã cho tương đương với:
$\left( x+y\alpha +z{{\alpha }^{2}} \right)\left( x+y\alpha \omega +z{{\alpha }^{2}}{{\omega }^{2}} \right)\left( x+y\alpha {{\omega }^{2}}+z{{\alpha }^{2}}\omega \right)=1\ \ \ \ \ (*)$
Dễ thấy $\;$ là nghiệm của $\left( * \right)$ và các bộ số $\left( {{x}_{n}},{{y}_{n}},{{z}_{n}} \right)$ thoả mãn ${{x}_{n}}+{{y}_{n}}\alpha +{{z}_{n}}{{\alpha }^{2}}={{\left( {{x}_{1}}+{{y}_{1}}\alpha +{{z}_{1}}{{\alpha }^{2}} \right)}^{n}}={{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n}}$ đều là nghiệm của $\left( * \right)$ với mọi $n\in \mathbb{Z}$.
Ta sẽ chứng minh mọi nghiệm của (*) có dạng $\left( {{x}_{n}},\ {{y}_{n}},\ {{z}_{n}} \right)$.
Với $\left( x,y,z \right)$ là nghiệm của (*) ta sẽ có: $x+y\alpha +z{{\alpha }^{2}}>0$ nên tồn tại duy nhất số nguyên $n$ sao cho ${{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n}}\le x+y\alpha +z{{\alpha }^{2}}<{{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n+1}}$.
Khi đó $\left( a,b,c \right)\in {{\mathbb{Z}}^{3}}$ thoả mãn $a+b\alpha +c{{\alpha }^{2}}=\left( x+y\alpha +z{{\alpha }^{2}} \right){{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{-n}}$ cũng là nghiệm của (*) và khi đó: $1\le a+b\alpha +c{{\alpha }^{2}}<1+\alpha +{{\alpha }^{2}}$.
Nên suy ra: $\left| a-b\alpha \right|\le \sqrt{2};\ \left| b\alpha -c{{\alpha }^{2}} \right|\le \sqrt{2};\ \left| c{{\alpha }^{2}}-a \right|\le \sqrt{2}$.
Nếu $c\ge 1$ thì ta có: $a\ge c{{\alpha }^{2}}-\sqrt{2}>0$ và $b>c\alpha -\frac{\sqrt{2}}{\alpha }>0$ nên $a+b\alpha +c{{\alpha }^{2}}\ge 1+\alpha +{{\alpha }^{2}}$, vô lý.
Nếu $c\le -1$, tương tự ta có: $a+b\alpha +c{{\alpha }^{2}}\le -\left( 1+\alpha +{{\alpha }^{2}} \right)$, vô lý.
Vậy $c=0$, suy ra: $\left| a-b\alpha \right|\le \sqrt{2};\ \left| b\alpha \right|\le \sqrt{2};\ \left| a \right|\le \sqrt{2}$. Kết hợp với ${{a}^{3}}+2{{b}^{3}}+4{{c}^{3}}-6abc=1$ thì ta chỉ nhận được 1 bộ số thoả mãn là $\left( a,\ b,\ c \right)=\left( 1,\ 0,\ 0 \right)$.
Từ đó suy ra: $x+y\alpha +z{{\alpha }^{2}}={{\left( 1+\alpha +{{\alpha }^{2}} \right)}^{n}}$, điều phải chứng minh.
Bài 23: (Sưu tầm)
Cho $n$ là một số nguyên dương. Gọi $a_n$ là số các số tự nhiên $k$ sao cho $\binom{n}{k}\equiv 1 \pmod{3}$ và $b_n$ là số các số tự nhiên $k$ sao cho $\binom{n}{k}\equiv 2 \pmod{3}$.
Chứng minh rằng: $a_n-b_n$ là một luỹ thừa của 2.
Đã gửi bởi IMOer on 04-07-2016 - 17:40 trong Số học
P.S: Hình như đề British này tính phí đúng không anh IMOer? Em chưa bao giờ thấy mặt đề British
Đề British (2 vòng) được đăng tải khá đầy đủ ở đây. Đáp án chính thức thì anh không thấy public ở đâu cả.
Xin nói thêm về bài 65. Đây là bài số 2 trong Mock - IndianMO 2016 được gợi ý bởi Anant (các bạn có thể tìm thêm trên trang mathometer.weebly.com). Lời giải của mình của giống như của anh IMOer, ở đây $2^{2016}$ và $2015$ là các số tượng trưng cho năm, có thể tổng quát thành $m, n$ bất kỳ.
Lúc nhìn đề bài 65 là anh cũng nhận ra ngay 2 điều:
- Các số $2^{2016}$ và $2015$ đúng là chỉ mang ý nghĩa tượng trưng.
- Chắc chắn sử dụng định lý thặng dư Trung Hoa.
Community Forum Software by IP.Board
Licensed to: Diễn đàn Toán học