Đến nội dung

Ego nội dung

Có 288 mục bởi Ego (Tìm giới hạn từ 30-03-2020)



Sắp theo                Sắp xếp  

#693860 Cho A, B là các ma trận vuông thực cấp n thỏa mản: AB = BA, A khả nghịch và t...

Đã gửi bởi Ego on 28-09-2017 - 17:51 trong Đại số tuyến tính, Hình học giải tích

Con số $2012$ theo mình không có ý nghĩa lắm ở bài này. Thật như vậy, với nhận xét rằng $A^{r} = 0$ thì $A^{t} = 0$ với mọi $t \ge r$; và cũng để thuận tiện ta nói $r$ được đề cập là giá trị nhỏ nhất để $B^{r} = 0$, ta có:

  • Nếu $r\le 2012$ thì $A + B^{2012} = A$ là ma trận khả nghịch theo giả thiết.
  • Nếu $r > 2012$, ta đặt $C = B^{2012}$, lúc này, theo nguyên lý Archimedes tồn tại một số tự nhiên (nhỏ nhất) $c$ ($c \ge 2$) sao cho $2012c \ge r$,  nghĩa là $c$ là số tự nhiên nhỏ nhất để $C^{c} = 0$. Lúc này, ta nhận xét rẳng (có thể chứng minh được) $A$ và $C$ cũng giao hoán nhau; $A$ khả nghịch và $C$ lũy linh. Tức là ta có thể phát biểu lại bài toán như sau:

'Cho $A, C$ là các ma trận vuông cấp $n$ thỏa mãn $AC = CA$; $A$ khả nghịch và tồn tại $c$ là số tự nhiên nhỏ nhất để $C^{c} = 0$. Chứng minh rằng $A + C$ cũng khả nghịch.'

Giả sử phản chứng $A + C$ là ma trận không khả nghịch, tức $r(A + C) < n$. Xét phương trình $(A + C)X = 0$ với $X$ là một ma trận $n\times 1$.
Từ định lý Rouché - Capelli, ta thấy:

  1. Phương trình trên có vô số nghiệm $X$ (1)
  2. Phương trình $AX = 0$ có $r(A) = r(A|0) = n$ nên sẽ có nghiệm duy nhất (2)

Mặt khác, phương trình trên tương đương $AX = -CX (*) \implies C^{c - 1}.A.X = -C^{c}X = 0$ (lưu ý $C^{c - 1} \neq 0$). Do $A, C$ giao hoán nhau nên $A$ và $C^{c - 1}$ cũng thế, nghĩa là $C^{c - 1}A = AC^{c - 1}$. Kết hợp các điều trên lại cho ta $AC^{c - 1}X = 0 \implies A^{-1}.A.C^{c - 1} = A^{-1}.0 = 0 \implies C^{c - 1}X = 0 (**)$
Từ (*) và (**), ta có như sau: $C^{c - 2}.AX = -C^{c - 1}X = 0$, tương tự quá trình trên, ta thu gọn được $C^{c - 2}X = 0$.

Cứ tiếp tục như vậy cho đến cuối cùng, ta thu được $CX = 0$. Từ (*) thì điều này đồng nghĩa với $AX = 0$. Nghĩa là với mỗi giá trị $X$ là nghiệm của $(A + C)Y = 0$ thì $X$ cũng là nghiệm của phương trình $AT = 0$. (3)

Kết hợp (1), (2) và (3) ta thu được mâu thuẫn. Vậy $A + C$ là một ma trận khả nghịch.




#661838 Kỳ thi chọn đội tuyển dự thi VMO tỉnh Đồng Nai

Đã gửi bởi Ego on 13-11-2016 - 22:48 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.

Bài 1 cũng đâu đến phức tạp nhờ
Gọi $n$ nghiệm đã cho là $x_{1}, x_{2}, \cdots x_{n}$. Với $\sum_{k = 1}^{n}x_{k} = -a_{1}$ và $\sum_{i \neq j}x_{i}x_{j} = a_{2}$.
Ta cần chứng minh $-a_{1}\le x_{k} \le a_{1} + 2 \quad \forall k$
Ta có $x_{i}^{2} \le \sum_{k = 1}^{n}x_{k}^{2} = a_{1}^{2} - 2a_{2} \le a_{1}^{2}$ nên $-a_{1} \le x_{i} \le a_{1}$




#658151 Tính $lim\frac{S_n}{n}$

Đã gửi bởi Ego on 16-10-2016 - 21:51 trong Dãy số - Giới hạn

Đề bài hầu như không dùng tới dữ kiện $u_{2k}$ nên ta không cần định nghĩa chúng. Định nghĩa lại như sau $v_{1} = 1, e^{v_{n + 1}} = e^{v_{n}} - v_{n}$ và $S_{n} = \sum_{k = 1}^{n - 1}(n - k)v_{k}$

  • Ta sẽ chứng minh $e^{v_{n}}$ hội tụ
    Thật vậy, xét hàm $f(x) = x - \ln(x)$ trên $(0; +\infty)$; chứng minh được $f(x) \ge 1$. Ta có $e^{v_{n + 1}} = e^{v_{n}} - \ln(e^{v_{n}})$ nên ta có $e^{v_{n + 1}} \ge 1$
    Giả sử $x > y$, xét $f(x) - f(y) = x - y - (\ln(x) - \ln(y)) = x - y - \frac{x - y}{t} = (x - y)\left(1 - \frac{1}{t}\right)$ với $t\in (x; y)$. Có $\frac{1}{2} < 1 \le x < t$ nên $\left|1 - \frac{1}{t}\right| < 1$. Theo nguyên lí ánh xạ co thì $e^{v_{n}}$ hội tụ và nó hội tụ về $1$.

Ta có $S_{n + 1} - S_{n} = \sum_{k = 1}^{n}(n + 1 - k)v_{k} - \sum_{k = 1}^{n - 1}(n - k)v_{k} = \sum_{k = 1}^{n}v_{k}$
Mặt khác, $v_{n} = e^{v_{n + 1}} - e^{v_{n}}$ nên $\sum_{k = 1}^{n}v_{k} = e^{v_{n + 1}} - e_{v_{1}} = e^{v_{n + 1}} - e \to 1 - e$ khi $n \to +\infty$
 




#658102 Tính $\lim_{n\rightarrow +\infty}\sum_...

Đã gửi bởi Ego on 16-10-2016 - 19:00 trong Dãy số - Giới hạn

Ý tưởng bài này rất rõ ràng. Từ dãy truy hồi ta thu được $\frac{1}{x_{n}} - \frac{1}{x_{n + 1}} = \frac{x_{n}^{2016}}{x_{n + 1}}$
Lấy tổng ta thu được $\lim_{n\to +\infty}\sum_{i = 1}^{n}\frac{x_{i}^{2016}}{x_{i + 1}} = \frac{1}{x_{1}} - \frac{1}{x_{n + 1}} = 1 - \frac{1}{x_{n + 1}}$
Lại dễ dàng chứng minh được dãy $x_{n}$ là dãy vô cùng lớn nên ta kết luận $\lim_{n\to +\infty}\sum_{i = 1}^{n}\frac{x_{i}^{2016}}{x_{i + 1}} = 1$




#657695 Đề chọn đội tuyển học sinh giỏi quốc gia tỉnh Bắc Ninh 2016-2017

Đã gửi bởi Ego on 12-10-2016 - 22:36 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.

Câu 3. Từ CTTH, có $a_{n + 1} - 27 = (a_{n} - 27)(2a_{n} + 1)^{2}$. Do đó $a_{n} - 27 = (a_{1} - 7)\left(\prod_{k = 1}^{n - 1}2a_{k} + 1\right)^{2} = 7\left(\prod_{k = 1}^{n - 1}2a_{k} + 1\right)^{2}$. Do đó $a_{n} + 1 = 7\left[\left(\prod_{k = 1}^{n - 1}2a_{k} + 1\right)^{2} + 4\right]$.
Xét $p\in \mathbb{P}\mid \left(\prod_{k = 1}^{n - 1}2a_{k} + 1\right)^{2} + 4$ (dĩ nhiên ta thấy chỉ có $p$ lẻ). Ta có $\left(\frac{-4}{p}\right) = 1 \iff \left(\frac{-1}{p}\right) = 1$ hay $p \equiv 1\pmod{4}$
Do đó số cần tìm là $7$.

P.S: Lâu quá không lên :3




#648650 Chứng minh rằng: b-g=B-G.

Đã gửi bởi Ego on 08-08-2016 - 22:11 trong Tổ hợp và rời rạc

Bài này là một bổ đề đẹp, được dùng trong kì VMO 2014 (nếu mình không nhầm). Sau đó là nằm trong đề HSG lớp 9 của Titan Education năm 2014.
Lời giải của mình năm ấy thế này, bạn tham khảo thử.
Dĩ nhiên số học sinh là $1$ thì không có gì để nói. Ta sẽ xét số học sinh từ $2$ trở lên
i) Với số học sinh là hai, ta xét là TRAI - TRAI, GÁI - GÁI, GÁI - TRAI thì thấy khẳng định bài toán đúng.
ii) Bây giờ giả sử bài toán đúng với số học sinh $n$. Bây giờ ta thêm một em học sinh vô. Vai trò mấy em này như nhau, nên giả sử ta thêm bạn nữ (:3) vào
Khi đó $B' = B$ và $G' = G + 1$.
a) TH1. Ta nhét em ấy vào giữa GÁI - GÁI thì $b' = b$ và $g' = g + 1$. Khi đó $B' - G' = B - G - 1 = b - g - 1 = b' - g'$.
b) TH2. Ta nhét em ấy vào giữa TRAI - GÁI thì $b' = b$ và $g' = g + 1$. Tương tự trên ta cũng có đpcm.
c) TH3. Ta nhét em ấy vào giữa TRAI - TRAI thì $b' = b - 1$ và $g' = g$. Lúc đó $B' - G' = B - G - 1 = b - 1 - g = b' - g'$. Xong.

 




#646114 TRƯỜNG HÈ TOÁN HỌC MIỀN BẮC 2016

Đã gửi bởi Ego on 23-07-2016 - 12:29 trong Thi HSG cấp Tỉnh, Thành phố. Olympic 30-4. Đề thi và kiểm tra đội tuyển các cấp.

Bài 1. Cho 2016 tập hợp, mỗi tập có 45 phần tử, hai tập bất kì có đúng một phần tử chung. Chứng minh rằng tồn tại 1 phần tử thuộc tất cả các tập.




#643708 Dự đoán kết quả của Đội tuyển Việt Nam tham dự IMO 2016

Đã gửi bởi Ego on 05-07-2016 - 08:46 trong Góc giao lưu

Hi vọng đội tuyển lọt top 3 \m/ :ukliam2:




#643626 Marathon số học Olympic

Đã gửi bởi Ego on 04-07-2016 - 15:30 trong Số học

Lời giải bài 66. Theo giả thiết ta có $2p^{2} = u^{2} + v^{2} \iff (2p)^{2} = (u + v)^{2} + (u - v)^{2}$
i) Dễ thấy $p \neq 2$, từ đây nếu ta đặt $d = \gcd(u, v)$ thì ta suy ra $d\mid 2p$. Thử tất cả TH cho ta $d = 1$. Mặt khác, do $2p^{2}$ chẵn nên $u, v$ đều lẻ; tức
là $\gcd(u - v, u + v)\mid \gcd(2u, 2v) \mid 2$ và thấy luôn là $\gcd(u - v, u + v) = 2$
ii) Đây là một PT Pythagores nguyên thủy : $p^{2} = \left(\frac{u - v}{2}\right)^{2} + \left(\frac{u + v}{2}\right)^{2}$. Do đó tồn tại các số nguyên dương $m, n$ thỏa mãn: $$\begin{cases}u - v = 2(m^{2} - n^{2}) \\ u + v = 4mn \\ p = m^{2} + n^{2}\end{cases}\implies 2p - u - v = 2(m - n)^{2} \text{hoặc} \begin{cases} u - v = 4mn \\ u + v = 2(m^{2} - n^{2}) \\ p = m^{2} + n^{2} \end{cases} \implies 2p - u - v = (2n)^{2}$$
Ta có đpcm.
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 :P
Bài toán 67. (Sưu tầm) Cho $a, b$ là hai số nguyên dương nguyên tố cùng nhau. Chứng minh rằng tồn tại vô hạn các số nguyên tố $p$ thỏa mãn $v_{p}(x^{p - 1} - y^{p - 1})$ lẻ.

 

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ỳ. :P




#643341 Số nguyên tố

Đã gửi bởi Ego on 02-07-2016 - 20:19 trong Số học

Ta sẽ quan tâm đến $a \ge 2$:
Gọi $q$ là một ước nguyên tố của $\frac{a^{p} - 1}{a - 1}$. Ta sẽ chứng minh $q = p$ hoặc $q \equiv 1\pmod{p}$

Theo đề bài ta có $a^{p} \equiv 1\pmod{q}$, suy ra $\text{ord}_{q}(a)\mid p$.

i) $\text{ord}_{q}(a) = 1$. Để ý là $q\mid 1 + a + \cdots + a^{p - 1}$, lấy modulo $q$, ta thu được $p\equiv 0\pmod{q}$ hay $p = q$ do $q$ nguyên tố.

ii) $\text{ord}_{q}(a) = p$. Mặt khác, $\text{ord}_{q}(a)\mid q - 1$. Ta có đpcm.

Bây giờ quay lại bài toán, để ý là theo LTE ta có $v_{p}\left(\frac{a^{p} - 1}{a - 1}\right) = v_{p}(a^{p} - 1) - v_{p}(a - 1) = v_{p}(p) = 1$. Tức là nếu $\frac{a^{p} - 1}{a - 1} = p^{k}$ thì $k = 1$, suy ra $a = 1$, vô lý.
Điều này tức là có một ước nguyên tố nào khác thỏa $q \neq p$ và như ii) ta có đpcm.




#643333 Hàm cộng tính

Đã gửi bởi Ego on 02-07-2016 - 19:52 trong Phương trình hàm

Hàm cộng tính hay nói cách khác là loại hàm Cauchy. Hiện đã có rất nhiều kết quả viết về vấn đề này. Vấn đề em đưa ra ta không thể kết luận nhé, hàm cộng tính cần một vài điều kiện
i) Nhân tính

ii) Liên tục

iii) $f(x^{2}) = (f(x))^{2}$

iv) $f(x^{3}) = (f(x))^{3}$

v) vân vân
mới có thể kết luận là hàm tuyến tính nhé.
Về việc giải thích thì như anh nói đã có rất nhiều chứng minh về loại hàm này, và có người đã chỉ ra các hàm không phải tuyến tính thỏa hàm cộng tính.




#643327 Marathon số học Olympic

Đã gửi bởi Ego on 02-07-2016 - 19:40 trong Số học

Hiện bài toán 64 vẫn chưa có lời giải. Xin phép được đề xuất bài toán tiếp theo
Bài toán 65. (Suggested by Anant) Chứng minh rằng tồn tại một số nguyên dương $x$ sao cho mỗi phần tử của tập $S$ có ít nhất $2^{2016}$ ước tự nhiên với $S$ định nghĩa bởi $S = \{x^{i} + i|1\le i \le 2015\}$




#642799 Tìm tất cả đa thức hệ số hữu tỷ $P(n)$ thoả $P(n)\mid 2^...

Đã gửi bởi Ego on 29-06-2016 - 17:37 trong Đa thức

Các kết quả cơ bản dùng cho lời giải
i) $n = \pm 1$ là số nguyên duy nhất thoả mãn $\pm n\mid 2^{|n|} - 1$
ii) $P(n) \mid P(P(n) + n)$
Lưu ý là ta chỉ quan tâm các đa thức nhận giá trị nguyên với $n$ tự nhiên nên ii) vẫn đúng.
Theo đó, ta có $P(n) \mid P(P(n) + n) \mid 2^{P(n) + n} - 1$. Mặt khác, $P(n)\mid 2^{n} - 1$
Tóm lại ta thu được $P(n) \mid 2^{P(n)}$. Suy ra $P(n) = 1$ hoặc $P(n) = -1$ có vô hạn nghiệm, đến đây dễ suy ra rằng $P(x) = 1$ với mọi $x$ hay $P(x) = -1$ với mọi $x$

P.s: Thật ra có thể biện luận để suy ra hoặc $P(x) = \pm 1$ hoặc $P* = 0$ (TH sau có thể chứng minh vô lý). Và ngoài ra, đề bài chỉ cần đúng với vô hạn số tự nhiên $n$ hoặc đúng với hơn $2\deg{P(x)} + 2$. Chờ lời giải khác của các bạn



#642793 Tìm tất cả đa thức hệ số hữu tỷ $P(n)$ thoả $P(n)\mid 2^...

Đã gửi bởi Ego on 29-06-2016 - 17:14 trong Đa thức

Tìm tất cả đa thức hệ số hữu tỷ $P(n)$ thoả $P(n)\mid 2^{n} - 1$ với mọi số tự nhiên $n$.
Nguồn



#642072 18th ELMO (ELMO Lives Mostly Outside)

Đã gửi bởi Ego on 25-06-2016 - 01:20 trong Thi HSG Quốc gia và Quốc tế

Bài 4. Để ý rằng $m - n \mid P(m) - P(n)$ và $a^{p} \equiv a \pmod{p}$
Đầu tiên, với mỗi số tự nhiên $k$, ta cố định $k$ lại, theo giả thiết ta có $p\mid kp\mid P(2^{kp})$. Mặt khác, lại có $p\mid 2^{kp} - 2^{k} \mid P(2^{kp}) - P(2^{k}) \implies p\mid P(2^{k})$. Lấy $p$ đủ lớn cho ta $P(2^{k}) = 0$, hay $2^{k}$ là một nghiệm của $P(x)$.
Cho $k$ chạy từ $1$ ra vô cực suy ra $P(x)$ có vô số nghiệm, chứng tỏ $P(x) = 0$. Xong.

Haiz




#642071 18th ELMO (ELMO Lives Mostly Outside)

Đã gửi bởi Ego on 25-06-2016 - 01:15 trong Thi HSG Quốc gia và Quốc tế

Bài 1. Ta sẽ chứng minh $n$ chẵn là các giá trị cần tìm. Giả sử $n$ là một số crunchy và $x_{1}, x_{2}, \cdots x_{2n}$ là các số thỏa yêu cầu.
Do các số không cùng bằng nhau nên có hai giá trị khác nhau, giả sử $x_{1} \neq x_{2}$.

  • Mình sẽ cố gắng đi chứng minh rằng $x_{3} = x_{4} = \cdots = x_{2n} = X$, gọi $x_{i}, x_{j}$ thỏa $3 \le i < j < 2n$.
    Gọi $S$ là tổng của $n - 2$ số bất kỳ không gồm chứa $x_{1}, x_{2}, x_{i}, x_{j}$, $P$ là tích của đám còn lại trừ ra $x_{1}, x_{2}, x_{i}, x_{j}$
    Ta có $\begin{cases}x_{1} + x_{i} + S = x_{2}x_{j}.P \\ x_{2} + x_{i} + S = x_{1}x_{j}.P \\ x_{1} + x_{j} + S = x_{2}x_{i}.P\\ x_{2} + x_{j} + S = x_{1}x_{i}.P\end{cases}\implies \begin{cases}x_{1} - x_{2} = P.x_{j}(x_{2} - x_{1}) \\ x_{1} - x_{2} = P.x_{i}(x_{2} - x_{1})\end{cases} \implies Px_{i} = Px_{j} = -1 \implies x_{i} = x_{j}$, ngoài ra, từ đây còn suy ra được chúng bằng $-1$
  • Mặt khác, một trong hai $X \neq x_{1}$ và $X \neq x_{2}$ phải đúng, giả sử $X \neq x_{1}$, khi đó cũng áp dụng trên suy ra được $X = x_{2}$ hay tập của ta gồm $2n - 1$ số $-1$ và số $x_{1}$ khác $-1$.
    Dễ thấy chỉ có $n$ chẵn là thỏa mãn và bộ thỏa mãn là $(n, -1, \cdots , -1)$ ($2n - 1$ số $-1$).



#642070 18th ELMO (ELMO Lives Mostly Outside)

Đã gửi bởi Ego on 25-06-2016 - 01:07 trong Thi HSG Quốc gia và Quốc tế

18th ELMO

Ngày 1 (18/06/2016)

Bài 1. Cookie Monster gọi một số nguyên dương $n$ là crunchy nếu tồn tại $2n$ số thực $x_{1}, x_{2}, \cdots x_{2n}$ (tất cả không bằng nhau), sao cho tổng của $n$ số bất kỳ trong chúng bằng với tích của $n$ số còn lại. Bạn hãy giúp Cookie Monster xác định tất cả các số crunchy.
Bài 2. Oscar tập vẽ các hình. Oscar vẽ một tam giác $ABC$ và điểm $D$ sao cho $DB, DC$ là tiếp tuyến tới đường tròn ngoại tiếp tam giác $ABC$. Gọi $B'$ đối xứng của $B$ qua $AC$, $C'$ là đối xứng của $C$ qua $AB$. Nếu gọi $O$ là tâm ngoại tiếp của tam giác $DB'C'$, hãy giúp Oscar chứng minh rằng $OA \perp BC$.

Bài 3. Trong hệ trục tọa độ $Oxy$, ta gọi một hình chữ nhật là bình thường nếu tất cả các cạnh song song với trục $x$ hoặc trục $y$, và gọi một tập các điểm là đẹp nếu như hai điểm bất kỳ trong chúng không có chung hoành độ lẫn tung độ. Đầu tiên, Bert chọn một tập đẹp $B$ gồm $2016$ điểm trên mặt phẳng. Để 'hại não' Bert, Ernie chọn một tập $E$ gồm $n$ điểm trên mặt phẳng sao cho $B\cup E$ là một tập đẹp với $2016 + n$ điểm. Bert trở lại và một cách kỳ diệu, phát hiện ra rằng không có hình chữ nhật bình thường nào chứa ít nhất hai điểm trong $B$ và không có điểm nào thuộc $E$ nằm bên trong nó. Cho một tập đẹp $B$ mà Bert chọn, định nghĩa $f(B)$ là số nguyên dương nhỏ nhất $n$ sao cho Ernie có thể tìm ra một tập đẹp $E$ với kích cỡ $n$ phần tử thỏa mãn điều kiện đặt ra. Hãy giúp Bert xác định GTNN và GTLN của $f(B)$.

Ngày 2 (19/06/2016)
Bài 4. Big Bird có một đa thức hệ số nguyên thỏa mãn $n$ chia hết $P(2^{n})$ với mọi số nguyên dương $n$. Chứng minh rằng đa thức của Big Bird là đa thức không.

Bài 5. Elmo đang tô màu. Đầu tiên Elmo chọn ra một tập $S$ gồm $n > 1$ điểm thẳng hàng. Sau đó với mỗi cặp không thứ tự $\{X, Y\}$ trong $S$, Elmo tô màu đường tròn với đường kính $XY$ sao cho mỗi cặp đường tròn mà giao nhau tại 2 điểm phân biệt thì được tô khác màu. Count von Count muốn đếm số màu mà Elmo đã sử dụng. Với mỗi $n$ cho trước, hỏi Elmo cần phải dùng ít nhất bao nhiêu màu để tô?

Bài 6. Elmo đang học hình học Olympiad. Trong $\triangle ABC$ với $AB \neq AC$, cho đường tròn nội tiếp của nó tiếp xúc với $BC, CA$ và $AB$ tại $D, E$ và $F$, theo đúng thứ tự. Phân giác trong của $\angle BAC$ cắt đường $DE$ và $DF$ tại $X$ và $Y$, theo thứ tự. Gọi $S, T$ là các điểm khác nhau trên cạnh $BC$ sao cho $\angle XSY = \angle XTY = 90^{\circ}$. Cuối cùng, gọi $\gamma$ là đường tròn ngoại tiếp $\triangle AST$.

  1. Chứng minh rằng $\gamma$ tiếp xúc với $\odot (ABC)$
  2. Chứng minh rằng $\gamma$ và đường tròn nội tiếp của $\triangle ABC$ tiếp xúc nhau.

Hello

Nguồn




#638852 Marathon số học Olympic

Đã gửi bởi Ego on 08-06-2016 - 08:34 trong Số học

Mình thì nghĩ nguyên lý Dirichlete ở Olympiad có thể được thừa nhận. Đương nhiên đa thức Cyclotomic là một công cụ mạnh rồi :P.
Ý tưởng của mình cho bài toán trên bắt đầu từ ý tưởng phản chứng, vì mình chẳng thể quy nạp, hay làm bất cứ gì như bình thường. Mình phản chứng dựa trên $p$. Mình còn phát hiện ra là nếu như trong tay có một số nguyên tố $\equiv p - 1\pmod{p}$ thì bài toán sẽ vô lý hẳn. Vì vậy mình cố gắng tìm ra các lực lượng khác để truy ra số nguyên tố đó. Bài này cũng gợi gợi chút gì đó trong chứng minh vô hạn số nguyên tố của Euler nên cũng chứng minh được tập $S$ vô hạn. Phần còn lại là cố gắng tìm ra số nguyên tố dạng $kp + a$ với $a$ không thặng dư chính phương modulo $p$ (tự nhiên xuất thần nghĩ ra cái này). Chỉ cần $\frac{p - 1}{2}$ số nguyên tố như vậy ta đã truy ra số nguyên tố mình cần.
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




#638828 Marathon số học Olympic

Đã gửi bởi Ego on 08-06-2016 - 00:41 trong Số học

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$.

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ố.
Quy ước $A_{p}$ là số các lớp đồng dư modulo $p$ đôi một khác nhau.

i) 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ý.

ii) Giả sử phản chứng, giả sử $p$ là số nguyên tố 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$.
Do tập $\mathbb{L} = \{1, 2, \cdots , p - 1\}$ chỉ có hữu hạn nên tồn tại $x_{1}\in\mathbb{L}$ sao cho $q\in\mathbb{S} \equiv x_{1}\pmod{p}$ là vô hạn. Ta sẽ tìm thêm $x_{2}$ suy từ $x_{1}$ thỏa $x_{2}\neq x_{1}$ và $q \in\mathbb{S} \equiv x_{2}\pmod{p}$ cũng vô tận. Tương tự cho $x_{3}$ suy từ $x_{2}$, .... Ký hiệu $p_{x_{i}}$ là các số nguyên tố thuộc $\mathbb{S}$ đồng dư $x_{i}$ modulo $p$.

Ta sẽ thực hiện các thuật toán sau:

a) Giả sử trong tay ta đã có $p_{x_{1}}, p_{x_{2}}, \cdots p_{x_{i}}$. Khi đó tích của $m_{j}$ số nguyên tố dạng $x_{j}\pmod{p}$ là $x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{i}^{m_{i}}$. Đặt $A = \{x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{i}^{m_{i}}: \quad 0\le m_{j} \le p - 1\}$. Khi đó:

b) Nếu $i > \frac{p - 1}{2}$ thì có $x_{u}$ nào đó không là thặng dư chính phương modulo $p$. Gọi ra $\frac{p - 1}{2}$ số $p_{x_{u}}$ thì tích của chúng đồng dư $x_{u}^{\frac{p - 1}{2}} \equiv \frac{x_{u}}{p} \equiv -1\pmod{p}$. Từ đây cũng suy ra vô lý.
Nếu không, ta chuyển xuống bước c)

c) Nếu tồn tại phần tử nào đó của $A$ đồng dư $-1\pmod{p}$ thì bài toán kết thúc nhờ việc ta lấy $m_{j}$ số $p_{x_{j}}$. Nếu không, ta chuyển xuống bước d).

d) Nếu $|A_{p}| > \frac{p - 1}{2}$ thì theo bổ đề 2 tồn tại bộ $g_{1}, g_{2}, \cdots , g_{i}$ thỏa mãn $\prod_{j = 1}^{i}x_{i}^{g_{i}} \equiv a\pmod{p}$ với $a$ không thặng dư chính phương modulo $p$. Lúc này do tính vô hạn nên ta cứ việc lấy $\frac{p - 1}{2}g_{i}$ lần số nguyên tố dạng $p_{x_{i}}$ thì tích của chúng đồng dư $a^{\frac{p - 1}{2}} \equiv \left(\frac{a}{p}\right) \equiv -1\pmod{p}$. Từ đó có vô lý.
Nếu không, ta  chuyển xuống bước e)
e) Nếu $|A_{p}|\le \frac{p - 1}{2}$, theo bổ đề thì tồn tại $n_{1}, n_{2}, \cdots n_{i}$ thỏa mãn $x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{i}^{n_{i}} + 1\not\equiv x_{1}^{m_{1}}.x_{2}^{m_{2}}\cdots x_{i}^{m_{i}}\pmod{p}$ với mọi $m_{j}$ bất kỳ. Tức là trong phân tích $x_{1}^{n_{1}}\cdots x_{i}^{n_{i}} + 1$ không thể mãi chứa $x_{1}, x_{2}, \cdots x_{i}$ được. Nhờ việc có vô hạn số $p_{x_{i}}$ nên ta cũng suy ra tồn tại vô hạn ta cũng suy ra có phần tử nào $x_{i + 1}$ nào đó cũng thỏa $p_{x_{i + 1}}$. Bây giờ quay lại bước b).
Lưu ý là bước b) vừa là bước tối ưu (tức là không có cũng OK), vừa là bước chặn, do số lượng $p_{x_{i}}$ ngày càng tăng, mà $i$ chỉ có thể không quá $\frac{p - 1}{2}$ thì ta mới có thể thực hiện tiếp thuật toán. Vì vậy nên bài toán sẽ đến lúc nào đó sẽ dừng.
 




#638703 VMF's Marathon Đa thức Olympic

Đã gửi bởi Ego on 07-06-2016 - 12:54 trong Đa thức

Bài toán 4. Tìm $P(x)\in \mathbb{Z}_{[x]}$ sao cho $P(x)$ nguyên tố với $\forall x\in \mathbb{N*}$.

Lời giải bài 4. Ta sẽ chứng minh $P(x) = p \quad\forall x \in \mathbb{R}$ là nghiệm duy nhất. Thật vậy, giả sử tồn tại $P$ khác hằng sao cho $\deg P \ge 1$. Ta có thể giả sử $P* > 0$ nhờ vào việc xét $-P(x)$ (cái này như nhau).
Vì vậy, với $x$ đủ lớn thì $P(x) > 1$. Để ý là $P(x + P(x)) - P(x) \vdots P(x) \implies P(x + P(x)) \vdots P(x)$. Điều này mâu thuẫn với giả thiết số nguyên tố.
Bài toán 5. (Irish MO 27th) Cho $n$ là số nguyên dương và $a_{1}, a_{2}, \cdots a_{n}$ là các số thực dương. Đặt $g(x) = (x + a_{1})(x + a_{2})\cdots (x + a_{n})$. Gọi $a_{0}$ là một số thực bất kỳ và đặt $f(x) = (x - a_{0}).g(x) = x^{n + 1} + b_{1}x^{n} + \cdots + b_{n + 1}$. Chứng minh rằng $b_{1}, b_{2}, \cdots b_{n + 1}$ đều âm nếu và chỉ nếu $a_{0} > a_{1} + a_{2} + \cdots a_{n}$




#638348 Marathon số học Olympic

Đã gửi bởi Ego on 05-06-2016 - 19:31 trong Số học

Lời giải bài 45. Tổng quát: Cho $a, n$ là số nguyên dương với $a \ge 2$. Khi đó mọi bội số của $a^{n} - 1$ đều có ít nhất $n$ chữ số khác $0$ theo cơ số $a$.

Giả sử phản chứng là tồn tại $k$ để $k(a^{n} - 1) = \sum_{i = 1}^{n - 1}b_{i}a^{u_{i}}$ với $u_{i} < u_{i + 1}$ và $1 \le b_{i} \le a - 1$.
Bây giờ nếu $k$ là bội của $a$ thì cũng khá dễ dàng, ta chỉ cần thực hiện trên $\frac{k}{a}.(a^{n} - 1)$ vì nó tương đương nhau. Vậy nên giả sử luôn $k$ không là bội của $a$
Đến đây ta nghĩ đến đưa về đồng dư, đặt $T = a^{n} - 1$. Khi này $\sum_{i = 1}^{n - 1}b_{i}a^{u_{i}} \equiv 0 \pmod{T}$.
Bây giờ ta có thể đẩy về đồng dư bằng cách nếu có $u_{i} = pn + q$ với $0 \le q < n$ và $a^{u_{i}} \equiv a^{q} \pmod{T}$, làm tương tự như vậy với từng $u_{i}$ sau đó ghép cặp chúng lại; và cũng nhờ vậy ta có thể giả sử $v_{i} < n$. Vậy thì $\sum_{i = 1}^{n - 1}b_{i}a^{u_{i}} \equiv \sum_{i = 1}^{n - 1}c_{i}a^{v_{i}}\pmod{T}$ với $v_{i} < v_{i + 1}$ và $0 \le c_{i} \le a - 1$. Mặt khác, để ý là $c_{i}$ có thể bằng $0$ (trong giai đoạn ghép cặp), nhưng không thể tất cả cùng đồng thời bằng $0$ vì nếu có thì do các nhân tử chứa $u_{i}$ ghép lại vì $1 \le b_{i} < a$ (chúng không đủ lớn để chia hết cho $T$). Mà nếu ghép lại, ta cũng chỉ có tối đa $n - 1 < b_{1} + \cdots + b_{n - 1} \le (a - 1).(n - 1) < a^{n} - 1$). Điều này kết luận $0 < \sum_{i = 1}^{n - 1}c_{i}a^{v_{i}}$ và $0 < \sum_{i = 1}^{n - 1}c_{i}a^{v_{i}} \le (a - 1)\sum_{i = 1}^{n - 1}a^{i} = a^{n} - a < a^{n} - 1 = T$. Điều này là vô lý.
Bài 46. (Erdos) Cho $a, b$ là các số nguyên dương sao cho với mọi số nguyên tố $p$ thì $a \pmod{p} \le b \pmod{p}$. Chứng minh rằng $a = b$.




#638327 Đề thi tuyển sinh chuyên Toán tỉnh Khánh Hòa vào năm học 2016-2017

Đã gửi bởi Ego on 05-06-2016 - 17:43 trong Tài liệu - Đề thi

Bài 5 nhìn cũng vui vui. Ta kẻ các đường thẳng đi qua các điểm. Gọi $d$ là đường thẳng chứa nhiều điểm nhất trong số các đường thẳng đã thiết lập.
Gọi $s(d)$ là số điểm trong tập đang xét nằm trên đường thẳng $d$. Nếu $s(d) \le 8$ thì có ít nhất hai điểm không nằm trong đường thẳng đã cho. Gọi chúng là $A, B$. Để ý $AB \neq d$. Vậy ta chọn bất kỳ hai điểm trong đường $d$ là $M, N$ thì điều này mâu thuẫn với việc có ít nhất 3 điểm trong $A, B, M, N$ thẳng hàng vì trong 3 điểm chọn thì hẳn có hai điểm cùng là $A, B$ hoặc cùng là $M, N$.
TH cùng là $A, B$ thì để ý $A, B, M$ và $A, B, N$ đều không thẳng hàng. TH cùng là $M, N$ thì $M, N, A$ và $M, N, B$ không thẳng hàng. Vì vậy $s(d) \ge 9$. Lúc này thì bài toán khá hiển nhiên.




#637710 VMF's Marathon Đa thức Olympic

Đã gửi bởi Ego on 02-06-2016 - 22:59 trong Đa thức

Bài toán 1 hiện vẫn chưa có lời giải nên mình được phép đề xuất bài toán tiếp theo:
Bài toán 2. Cho $P(x) \in \mathbb{Z}[x]$ thỏa mãn $P(x)$ là số chính phương với mọi $x$ nguyên thì $P(x) = Q(x)^{2}$ với $Q(x) \in \mathbb{Z}[x]$.
Mở rộng: Liệu bạn có thể giải quyết cho trường hợp $P(x)$ là lũy thừa bậc $n$ của một số nguyên thì $P(x) = Q(x)^{n}$ với $Q(x)\in\mathbb{Z}[x]$




#637602 Marathon số học Olympic

Đã gửi bởi Ego on 02-06-2016 - 13:43 trong Số học

Bài 39 : Chứng minh với mọi $n>1$ tồn tại $2m$ số nguyên tố phân biệt đôi một $(p_{1},...p_{m})$ và $(q_{1},...q_{m})$ 

Trong đó :

$a) p_{i} > q_{i}$

$b) n = \sum_{i=1}^{m}(p_{i}-q_{i})$

Nguồn : VMF 

Bài này mình nhớ có anh Tantlsh có từng đăng trên diễn đàn và chưa nhận được lời giải, mình cũng chưa kiếm lại bài đó. Hiện giờ đề nghị các bạn khoan hãy đề xuất bài toán mới, mình nghĩ bài 39 khá hay.

Giả sử $n\neq p^a-1$, khi đó biểu diển $p$-phân của $n$ sẽ có chữ số tận cùng khác $p-1$.

Mình không hiểu chỗ này của Vistor lắm, ví dụ cho $p = 7$ đi, thì mình cứ lấy $n = (26)_{7} = 2\times 7 + 6$ khác $7^{a} - 1$ chứ nhỉ?


Hiện đã cập nhật điểm đến post #111 (đối với các mod) vì còn một số post cần phải kiểm tra lại




#637520 Marathon số học Olympic

Đã gửi bởi Ego on 02-06-2016 - 00:08 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$.

Chỗ này có lỗi, $b_{3} = 99$. Và mình chứng minh được kết quả mạnh hơn. Đây là đoạn mình còn khúc mắc (chắc là chỗ khó nhất). Mình còn chứng minh được luôn tồn tại $i$ để $3^{k}\mid b_{i}$

Bài 37. [AoPS] Với mỗi số nguyên $r$, chứng minh rằng tồn tại số tự nhiên $n_r$ sao cho với mọi số nguyên $n>n_r$ tồn tại ít nhất một số nguyên dương $k$ thoả mãn $1 \le k \le n-1$ và $p^r$ là ước của $\binom{n}{k}$ với $p$ là số nguyên tố.

Lời giải bài 37.

Ta sẽ dùng định lý Kummer như sau:
Định lý Kummer. Số mũ của $p$ trong biểu diễn $\dbinom{n}{k}$ bằng với số lần của phép nhớ trong phép cộng $n - k$ và $k$ trong biểu diễn cơ số $p$.
Bổ đề. Luôn tồn tại $L$ để tích $k \ge L$ số nguyên tố đầu tiên lớn hơn $p_{k + 1}^{r}$
Bây giờ ta chọn $n_{r} = \prod_{i = 1}^{k}p_{i}$ như trên. Ta sẽ chứng minh bài toán đúng với mọi $n > n_{r}$
Bây giờ nếu như trong biểu diễn cơ số $p_{i}$ nào đó ($1\le i \le k$) thì chữ số tận cùng khác $p_{i} - 1$ thì áp dụng định lý Kummer, ta luôn chọn được $k$ thỏa mãn $v_{p_{i}}(n) > r$ lí do là $n > p_{k + 1}^{r} > p_{i}^{r}$. Do đó ta chỉ còn TH sau:
Gọi $p_{u}$ là số nguyên tố đầu tiên sao cho $n + 1$ không chia hết cho $p_{u}$, lúc này $u \ge k + 1$. Nếu như lúc này chữ số tận cùng của $n$ là $p_{u} - 1$ thì $n + 1 \vdots p_{u}$ là vô lý. Mặt khác, $n + 1 \vdots p_{1}p_{2}\cdots p_{u - 1}$ nên $n + 1 \ge \prod_{i = 1}^{u - 1}p_{i} > p_{u}^{r}$ theo bổ đề, từ đây ta có $n$ trong biểu diễn cũng có ít nhất $r$ chữ số.
Xong.

Hi