Đến nội dung

H S G S nội dung

Có 4 mục bởi H S G S (Tìm giới hạn từ 30-03-2020)


Sắp theo                Sắp xếp  

#639506 Marathon số học Olympic

Đã gửi bởi H S G S on 11-06-2016 - 06:06 trong Số học

Bạn HSGS trình bày lại được không , mình không hiểu bạn định làm gì viết cũng khó hiểu nữa . Nếu chơi " đao to mổ gà " thì dùng định lý mahailescu =)) còn không thì mình nhớ anh IMOer đã giải với $p=5$ và chắc là tương tự thôi .

Chắc ý bạn là mihailescu :v nhưng ko có chứng minh sơ cấp, với cả 2 bài này ý tưởng khác nhau :v Đừng nhầm lẫn là tương tự nha

P/s: Anh IMOer ơi lời giải bài 49 ...




#639288 Marathon số học Olympic

Đã gửi bởi H S G S on 10-06-2016 - 09:51 trong Số học

Lời giải bài 52:

 

Lemma $(1)$: Với $p>2$ nguyên tố và $A={a_{1},a_{2}, \cdots, a_{s}}$ $1<s<p$ là tập số nguyên dương không chia hết cho p và thoả mãn $a_{1} \not\equiv a_{2} (mod p)$ thì tập $\sum_{i=1}^{s} x_{i}a_{i}$ với $x_{i}=0$ hoặc $x_{i}=1$ chứa ít nhất $s+1$ lớp đồng dư phân biệt $mod p$.

 

Chứng minh:

Với $s=2$, đúng.

Giả sử $(1)$ đúng với $s-1$, gọi dãy $b_{i}$ là tất các lớp đồng dư $mod p$ của $\sum_{i=1}^{s-1}x_{i}a_{i}$. Nếu $k>s$ thì hiển nhiên $(1)$ đúng với $s$, nên chỉ xét $k=s$. Do $a_{s} \not\equiv 0 (modp)$ suy ra tồn tại $k$ để $b_{k}+a_{s} \not\equiv b_{i}$ với mọi $i$. Nên phải có $s+1$ lớp đồng dư. 

 

Quay lại bài toán, với $n=p$, gọi dãy đã cho là $a_{i}$ và $-1<a_{1} \leq a_{2} \leq \cdots \leq a_{2p-1} <p$ 

Nếu $a_{i} \equiv a_{i+p-1}$ thì hiển nhiên nên xét $a_{i} \not\equiv a_{i+p-1}$. Đặt $b_{i} = a_{p+i} - a_{i+1}, 1 \leq i \leq p-1$ thì phương trình $\sum_{i=1}^{p}a_{i} \equiv - \sum_{i=1}^{p-1}x_{i}b_{i} (mod p)$ với $x_{i}=0$ hoặc $x_{i}=1$ có nghiệm theo $(1)$ suy ra $\sum_{i=1}^{p}a_{i} + \sum_{i=1}^{p-1}x_{i}b_{i} \equiv 0 (mod p)$ hay đúng với $n=p$.

 

Giờ cần chứng minh nếu đúng với $n=n_{1}$ và $n=n_{2}$ thì đúng với $n=n_{1}n_{2}$

Vì giả thiết đúng với $n_{1}$ nên chọn được $2n_{2}-1$ bộ gồm $n_{1}$ số có tổng chia hết cho $n_{1}$, giả thiết đúng với $n_{2}$ nên từ $2n_{2}-1$ bộ chọn được $n_{2}$ bộ có tổng chia hết cho $n_{2}$ hay $n_{1}n_{2}$ số có tổng chia hết cho $n_{1}n_{2}$

 

Bài 53: Giải phương trình nghiệm nguyên $x^{p}+1=y^{2}$ $(p>5)$

P/S: IMOer có thể đăng lời giải bài 49 được không :D




#638833 Marathon số học Olympic

Đã gửi bởi H S G S on 08-06-2016 - 06:54 trong Số học

Lời giải bài 49.

Bổ đề 1. Cho $i \in \{0, 1, 2, \cdots , p - 1\}$ với $p \in \mathbb{P}$. Ký hiệu $A_{p} \subset \{0, 1, 2, \cdots , p - 1\}$ là tập hợp chứa các phần tử đôi một không đồng dư nhau modulo $p$. Khi đó nếu $|A_{p}| \le \frac{p - 1}{2}$ thì tồn tại $a \in \mathbb{A_{p}}$ sao cho $a + 1\not\in A_{p}$

Bổ đề 2. Có đúng $\frac{p - 1}{2}$ thặng dư chính phương modulo $p$ với $p$ nguyên tố.
i) Dễ thấy rằng $2 \in \mathbb{S}$

ii) Ta sẽ chứng minh $\mathbb{S}$ chứa vô hạn phần tử. Thật vậy, nếu chúng chỉ có hữu hạn thì ta suy ra tồn tại một số nguyên tố $p \mid P + 1$ với $P$ là tích tất cả các phần tử của $\mathbb{S}$, mặt khác, $p \in \mathbb{S}$ nên $p\mid 1$, vô lý.

iii) Giả sử phản chứng, tồn tại $k$ để $p$ là số nguyên tố đầu tiên (thứ $k$) không là phần tử của $\mathbb{S}$. Ta đã biết rằng theo định lý Dirichlete rằng tồn tại vô hạn số nguyên tố có dạng $mp + n$ với $n = 1, 2, \cdots p - 1$.
Từ ii) ta suy ra rằng tồn tại $i \in \{1, 2, \cdots , p - 1\}$ sao cho các số nguyên tố dạng $mp + i$ mà là phần tử của $\mathbb{S}$ là vô hạn. Để thuận tiện, ta sẽ ghi $p_{i}$ tương ứng với $p_{i} \in \mathbb{S}$ và $p_{i} \equiv i\pmod{p}$ (mình có sử dụng $p_{i}^{k}$, ở đây không có nghĩa là chúng bằng nhau, chỉ có nghĩa là $k$ số nguyên tố đồng dư nhau ($\equiv k$) theo modulo $p$ thôi)
Nếu $i = 1$ thì cứ mỗi $p_{i}$ như vậy ta sẽ suy ra ước nguyên tố của $p_{i} + 1 \equiv 2\pmod{p}$ là thuộc $\mathbb{S}$, mà $p_{i} + 1$ đều không thể chứa tất cả các số dạng $1\pmod{p}$. Tức là lúc này có một $j$ nào đó sao cho $p_{j}$ ($j \neq 1$) là vô hạn. Ở đây ta xét các trường hợp xấu nhất (mình gọi là xấu nhất thì các bạn đọc ở dưới sẽ hiểu tại sao), tức là $j$ thỏa $\left(\frac{j}{p}\right) = 1$. Lúc này ta gọi các số dạng $p_{j}$ ra và nhân chúng lại, nôm na mình sẽ đặt $P_{j} = \prod{p_{j}} = j^{x}$, ở đây ta cũng xét trường hợp tệ nhất tức là với $x$ chạy từ $0$ đến $p$ thì $j^{x}$ chỉ nhận không quá $\frac{p - 1}{2}$ giá trị modulo $p$. Áp dụng bổ đề 1 ta có sẽ tồn tại một số $x$ nào đó $P_{j} \not\equiv j^{x} + 1\pmod{p}$. Tức là ta cứ đem xét các ước của $p_{j}^{(p - 1)k + x} + 1$ thì hẳn các ước của chúng sẽ không thể mãi dạng $p_{j}$ được, điều này chứng minh còn $k \neq j, i$ thỏa $p_{k}$ tồn tại vô hạn. Xét TH xấu luôn là $\left(\frac{k}{p}\right) = 1$
Tương tự, ta xét $P_{jk} = \prod{p_{j}.p_{k}} \equiv j^{x}k^{y}$ và cũng tính đến trường hợp tệ nhất, tức là $x, y$ chạy từ $0$ đến $p$ mà tập các lớp đồng dư của $j^{x}.k^{y}$ cũng không quá $\frac{p - 1}{2}$ thì theo bổ đề 1 ta cũng thu được tồn tại $x, y$ thỏa $P_{jk} \neq j^{x}k^{y} + 1\pmod{p}$. Từ giờ ta cũng đem đi xét các ước của $p_{j}^{(p - 1)u + x}.p_{k}^{(p - 1)v + y} + 1$ thì cũng chẳng thể toàn ước là $p_{j}, p_{k}$ mãi được,....
Lặp lại quá trình trên đến một trong hai TH sau sẽ dừng:
a) Có nhiều hơn $\frac{p - 1}{2}$ số $i$ trong tập $\{1, 2, \cdots , p - 1\}$ thỏa $p_{i}$ là vô tận. Lúc này để ý theo bổ đề 2 sẽ có $i$ sao cho $\left(\frac{i}{p}\right) = -1$ và $p_{i}$ là vô tận. Xét $\frac{p - 1}{2}$ số $p_{i}$ như vậy, đặt là $q_{1}, q_{2}, \cdots q_{\frac{p - 1}{2}}$. Khi đó $\prod_{i = 1}^{\frac{p - 1}{2}}q_{i} \equiv i^{\frac{p - 1}{2}} \equiv -1\pmod{p}$ theo tiêu chuẩn Euler. Hay $\prod_{i = 1}^{\frac{p - 1}{2}}q_{i} + 1 \vdots p$. Chứng tỏ $p \in \mathbb{S}$. Vô lý.

b) Sẽ đến lúc nào đó mà với tập $j_{1}, j_{2}, \cdots j_{u}$ thỏa $p_{j_{m}}$ là vô tận sao cho tích chúng tạo thành nhiều hơn $\frac{p - 1}{2}$ lớp đồng dư modulo $p$. Cũng áp dụng bổ đề 2 sẽ tồn tại $a$ sao cho $\left(\frac{a}{p}\right) = -1$ và $P(j_{1}j_{2}\cdots j_{u}) \equiv a\pmod{p} \implies (P(j_{1}j_{2}\cdots j_{u}))^{\frac{p - 1}{2}} \equiv a^{\frac{p - 1}{2}} \equiv \left(\frac{a}{p}\right) = -1$. Điều này cũng chứng tỏ $p \in \mathbb{S}$. Vô lý.
Nếu $i \neq 1$ cũng không quan trọng gì, lẫn $p_{1}$ cũng chẳng quan trọng vì $1$ nhân số nào chả là nó :P. Vì mình chỉ đang giải quyết các trường hợp xấu nhất có thể xảy ra
Các bạn check hộ mình :). Bài hay quá, mình sẽ cố gắng đơn giản hóa lời giải của mình lại (nếu không có chỗ sai)

 

Hì hì, ở đây có thể dùng Cyclotomic Polynomial để chứng minh sơ cấp Dirichlet, nhưng mình nghĩ dùng 1 định lý thậm chí còn mạnh hơn cả bài này để giải nó thì hơi quá.

Nhân tiện bạn có thể nói sơ qua ý tưởng được không :D




#638629 Marathon số học Olympic

Đã gửi bởi H S G S on 07-06-2016 - 06:16 trong Số học

Lời giải bài 47:

Cho ai chưa biết lời giả cho trường hợp $n=2$ :

Nếu $a=b$ thì dễ dàng suy ra $a=b=1$. Giả sử $a<b$, xét dãy $\cdots, x_{-1}, x_{0}, x_{1}, x_{2}, \cdots$ thoả mãn:

$x_{0}=a, x_{1}=b, x_{i+1}=nx_{i} - x_{i-1}$ với $i=1,2, \cdots, n$

Suy ra $x_{i}^2+x_{i-1}^2=n(x_{i}x_{i-1}+1)$ $(1)$ và $x_{n}$ là dãy tăng chặt (Quy nạp)

 

Chọn $x_{k}$ là số hạng bé nhất dương trong dãy, vì dãy tăng nên phải có $x_{k-1}<=0$

Giả sử $x_{k-1}<0$ thay $i=k$ vào $(1)$ vô lý, vậy $x_{k-1}=0$ hay $x_{k}^2=\frac{a^2+b^2}{ab+1}$

 

Trong trường hợp $n>=3$ :

Nếu $a,b$ trái dấu thì sai đề :)) nên ở đây chắc là $a,b$ nguyên dương.

 

Giả sử $a<b$, đặt $x=\frac{a^n+b^n}{(ab)^{n-1}+1}$ suy ra $a^n-x=(xa^{n-1}-b)b^{n-1}$ $(2)$

Nếu $x<a^n$ suy ra $xa^n-b=\frac{a^n-x}{b^{n-1}}<a$ (Do $a<b$) suy ra $xa^n<a+b$ hay $xa^{n-1}<\frac{b}{ax}+\frac{1}{x}<b$. Từ $(2)$ suy ra $a^n-x=(xa^{n-1}-b)b^{n-1}>=b^{n-1}>a^{2n-2}>a^{n}$ (Vô lý)

Nếu $x>a^n$ thì $x>x-a^{n}=(b-xa^{n-1})b^{n-1}<=b^{n-1}$ hay $b>ka^{n-1}>=k>b^{n-1}$ Vô lý

Vậy $x=a^n$ từ đó ta có đpcm.

Bài 48: Giải phương trình nghiệm nguyên $x^5+1=y^2$