Đến nội dung

Hình ảnh

Marathon số học Olympic

- - - - -

  • Please log in to reply
Chủ đề này có 191 trả lời

#161
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Anh làm hơi vội đoạn này rồi ạ ví dụ $p=61$ và $d=12$

Chỗ đó chỉ suy ra $v_2{(d)}=v_2{(p-1)}$ thôi ạ

có thể bạn nhầm đề nhưng $p=4^{n}+1$ mà


Bài viết đã được chỉnh sửa nội dung bởi canhhoang30011999: 27-06-2016 - 15:02


#162
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 Bài viết

Anh làm hơi vội đoạn này rồi ạ ví dụ $p=61$ và $d=12$

Chỗ đó chỉ suy ra $v_2{(d)}=v_2{(p-1)}$ thôi ạ

Đúng là có hơi tắt chút, nhưng nếu thêm câu $p-1$ có dạng $2^k$ thì chắc là ok rồi.



#163
Ego

Ego

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 296 Bài viết

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\}$



#164
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 Bài viết
Lời giải bài 65:
 
Bổ đề: Với $f\left( x \right)\in \mathbb{Z}\left[ x \right]$ khác đa thức hằng thì tồn tại vô số số nguyên tố là ước của ít nhất một phần tử trong tập $\left\{ f(1),f(2),f(3),... \right\}$.
Với $i\ge 2$, gọi ${{p}_{i}}$ là một ước nguyên tố lớn hơn 2015 của $a_{i}^{i}+i$, với ${{a}_{i}}$ là một số nguyên dương nào đó.
Khi đó dễ dàng nhận thấy $\left( i,{{p}_{i}} \right)=\left( {{a}_{i}},{{p}_{i}} \right)=1$ với mọi $i\ge 2$ và theo bổ đề trên ta hoàn toàn có thể chọn các số ${{a}_{i}}$ sao cho các số nguyên tố ${{p}_{i}}$ đôi một phân biệt.
Ta sẽ chứng minh với mọi $n$, tồn tại số nguyên dương ${{x}_{n}}$ sao cho $p_{i}^{n}|x_{n}^{i}+i$     (*).
Với $n=1$ chọn ${{x}_{1}}={{a}_{i}}$.
Giả sử (*) đúng với $n=k$, ta có: $p_{i}^{k}|x_{k}^{i}+i$.
Nếu $p_{i}^{k+1}|x_{k}^{i}+i$ thì chọn ${{x}_{k+1}}={{x}_{k}}$.
Nếu $p_{i}^{k+1}\nmid \ x_{k}^{i}+1$thì ta có: $x_{k}^{i}+i=p_{i}^{k}\left( a{{p}_{i}}+b \right)$ với $\left( b,{{p}_{i}} \right)=1$.
Ta sẽ chọn: ${{x}_{k+1}}=cp_{i}^{k}+{{x}_{k}}$, khi đó: $x_{k+1}^{i}+i={{\left( cp_{i}^{k}+{{x}_{k}} \right)}^{i}}+i\equiv ic{{x}_{k}^{i-1}}p_{i}^{k}+x_{k}^{i}+i\ \left( \bmod \ p_{i}^{k+1} \right)$
Vì $\left( i,{{p}_{i}} \right)=\left( {{x}_{k}},{{p}_{i}} \right)=1$ nên ta sẽ chọn được $c$ sao cho: ${{p}_{i}}|ic{{x}_{k}^{i-1}}+b$.
Theo nguyên lý quy nạp ta chứng minh được (*).
Vậy, với mỗi $i\ge 2$, tồn tại ${{n}_{i}}$ sao cho: $p_{i}^{{{2}^{2016}}-1}|n_{i}^{i}+i$
Xét hệ phương trình đồng dư sau:
\[\left\{ \begin{array}{l} x\equiv -1 & \left( \bmod \ {{2}^{{{2}^{2016}}-1}} \right)  \\ x\equiv {{n}_{2}} & \left( \bmod \ p_{2}^{{{2}^{2016}}-1} \right) \\ x\equiv {{n}_{3}} & \left( \bmod \ p_{3}^{{{2}^{2016}}-1} \right) \\ ... & ...  \\ x\equiv {{n}_{2015}}  & \left( \bmod \ p_{2015}^{{{2}^{2016}}-1} \right)\\ \end{array}\right.\]
Theo định lý thặng dư Trung Hoa, hệ phương trình đồng dư này có nghiệm nguyên dương $x$, khi đó: ${{x}^{i}}+i$ chia hết cho 1 số có dạng ${{p}^{{{2}^{2016}}-1}}$ nên các số này đều có ít nhất ${{2}^{2016}}$ ước.
 
Mình xin đề xuất tiếp 1 bài dễ thở sau:
 
Bài 66: (Nguồn: British MO 2016, round 2)
Giả sử $p$ là một số nguyên tố và tồn tại các số nguyên dương phân biệt $u,v$ thoả mãn $p^2$ là trung bình cộng của $u^2$ và $v^2$. Chứng minh rằng $2p-u-v$ là một số chính phương hoặc bằng 2 lần một số chính phương.


#165
Ego

Ego

    Thượng sĩ

  • Điều hành viên OLYMPIC
  • 296 Bài viết

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


Bài viết đã được chỉnh sửa nội dung bởi Ego: 04-07-2016 - 15:58


#166
IMOer

IMOer

    Hạ sĩ

  • Thành viên
  • 50 Bài viết

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

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

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.



#167
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Bài 67  (bài này có trong sách của mình)

ta có phương trình Fec-ma $a^{4}+b^{4}=c^{2}$ và $a^{4}+b^{4}=2c^{2}$ chỉ có nghiệm tầm thường nên $x^{2^{k}}+y^{2^{k}}$ không là số chính phương cũng không là 2 lần số chính phương 

Từ đó ta có tồn tại $p$ lẻ sao cho $v_{p}(x^{2^{k}}+y^{2^{k}})$ lẻ

khi đó ta có $x^{2^{k+1}}-y^{2^{k+1}} \equiv 0 (\bmod p)$

suy ra tồn tại a sao cho $ a^{2^{k+1}} \equiv 1 (\bmod p)$

từ đó dễ thấy $2^{k+1}$ là cấp của $a$ mod $p$ từ đó ta có $p-1$ chia hết cho $2^{k+1}$

$=> v_{p}(x^{p-1}-y^{p-1})=v_{p}(x^{2^{k+1}}-y^{2^{k+1}})=v_{p}(x^{2^{k}}+y^{2^{k}})$ lẻ (đpcm)



#168
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Bài 68. Cho $y \in N^{*}$ Chứng minh rằng tồn tại vô hạn các số nguyên tố $p$ thỏa mãn $4/p+1$ và $p$ là ước của 1 số có dạng $2^{n}y+1$ (n nguyên dương)

p/s anh IMOer post lời giải bài 64 được không ạ?


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 27-10-2017 - 07:36


#169
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Lời giải bài 68. Yêu cầu bài toán tương đương chứng minh tồn tại vô hạn số nguyên tố $p \equiv 3 (mod 4)$ mà là ước của một số dạng $2^{n}y+1$ . Xét $y$ lẻ ta chứng minh tập ước $4k+3$ của $2^{n}y+1$ là vô hạn . Giả sử ta có phân tích 

$$2y+1=p_{1}^{a_{1}}.....p_{s}^{a_{s}}$$ 

Trong phân tích này gồm một số số dạng $4k+3$ . Giờ giả sử tồn tại hữu hạn ước nguyên tố $4k+3$ không là ước của $2y+1$ nhưng là ước của $2^{n}y+1$ nào đó $(n>1)$ là các số $p_{s+1},...p_{s+r}$ 

Giờ xét số sau 

$$n = 1 + \phi(p_{1}^{a_{1}+1}....p_{s}^{a_{s}+1}p_{s+1}....p_{s+r})=1+\phi(A)$$

Dễ thấy 

$$2^{n}y+1 \equiv 2y+1 (mod A)$$ 

Từ đó suy ra tất cả ước nguyên tố $4k+3$ của $2^{n}y+1$ là các số $p_{1},...p_{s}$ với số mũ đúng trong $2y+1$ , và còn thêm một số ước nguyên tố dạng $4k+1$ nữa . Do $y$ lẻ nên $2^{n}y+1 \equiv 2y+1 \equiv 3(mod 4)$ , nhưng vô lý vì $n>1$ nên $2^{n}y+1 \equiv 1 (mod 4)$ . 

Bài 69 : Tìm tất cả các đa thức hệ số tự nhiên $f(x)$ thỏa mãn $\phi(f(p))=f(p-1)$ với mọi số nguyên tố $p.$


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 27-10-2017 - 07:36

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#170
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Lời giải bài 69. Xem tại  http://phamkhoabang....ham-euler.html 

Tại vì viêt rồi nên post cho m.n vậy. 


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 27-10-2017 - 07:37

$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#171
halloffame

halloffame

    Thiếu úy

  • Điều hành viên OLYMPIC
  • 522 Bài viết

Mình đề xuất 1 bài để tiếp tục topic:

Bài 70: Cho số nguyên tố $p$ chia $4$ dư $1.$ Chứng minh rằng tồn tại vô số số tự nhiên $n$ thỏa mãn phần nguyên của $n\sqrt{p}$ là một số chính phương.


Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.


#172
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

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

Cho em hỏi làm sao anh chọn được mod như thế này ạ? 



#173
babystudymaths

babystudymaths

    Sĩ quan

  • Thành viên
  • 312 Bài viết

Bài 67 (bài này có trong sách của mình)
ta có phương trình Fec-ma $a^{4}+b^{4}=c^{2}$ và $a^{4}+b^{4}=2c^{2}$ chỉ có nghiệm tầm thường nên $x^{2^{k}}+y^{2^{k}}$ không là số chính phương cũng không là 2 lần số chính phương
Từ đó ta có tồn tại $p$ lẻ sao cho $v_{p}(x^{2^{k}}+y^{2^{k}})$ lẻ
khi đó ta có $x^{2^{k+1}}-y^{2^{k+1}} \equiv 0 (\bmod p)$
suy ra tồn tại a sao cho $ a^{2^{k+1}} \equiv 1 (\bmod p)$
từ đó dễ thấy $2^{k+1}$ là cấp của $a$ mod $p$ từ đó ta có $p-1$ chia hết cho $2^{k+1}$
$=> v_{p}(x^{p-1}-y^{p-1})=v_{p}(x^{2^{k+1}}-y^{2^{k+1}})=v_{p}(x^{2^{k}}+y^{2^{k}})$ lẻ (đpcm)


Ở đây hình như anh chưa chỉ ra sự vô hạn

TLongHV


#174
nateriver

nateriver

    Lính mới

  • Thành viên mới
  • 4 Bài viết

Bài 70:

Vì $p$ là số nguyên tố đồng dư $1$ mod $4$ nên phương trình Pell $x^2-py^2=-1$ có nghiệm.

Do đó $x^4+x^2=px^2y^2,$ mà $x^4 < x^4 +x^2 < (x^2+1)^2 \Rightarrow \left \lfloor xy\sqrt{p} \right \rfloor =x^2.$


Bài viết đã được chỉnh sửa nội dung bởi halloffame: 27-10-2017 - 07:38


#175
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Ở đây hình như anh chưa chỉ ra sự vô hạn

anh quên mất ta có $p-1$ chia hết cho $2^{k}$ nên $p \geq 2^{k}$ nên có vô hạn $p$



#176
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Bài 64:

Đặt $f(1)=a$

Ta thấy $f(x+1)$ chia hết $f(x)+a$ có 2 trường hợp

- $f(x+1)=f(x)+a$

-$ 2f(x+1)\leqslant f(x)+a$

$\Rightarrow f(x+1) \leqslant f(x) -(x+1)+a$

Nếu không tồn tại x thỏa $f(x+1)=f(x)+a$

Với $x > a$ thì $f(x)>f(x+1)$ , vô lý do $f(n) \geq n$

Ta sẽ chứng minh với mọi $n$ tồn tại $x$ thỏa $f(x+n)=f(x+n-1)+a=...=f(x)+na$

Giả sử phản chứng dãy liên tục như trên có độ dài lớn nhất là $m$

$f(x+m)=f(x)+ma$

Với $x$ đủ lớn thì $f(x+m)-f(x+m+1) \geq ma$

Từ đó $f$ sẽ giảm tùy ý, vô lý

Xét $y$ bất kỳ, tồn tại $x$ lớn tùy ý sao cho 

$f(x+y)=f(x)+ay |f(x)+f(y)$

$\Rightarrow f(x+y)|f(y)-ay$

$\Rightarrow f(y)=ay$


Bài viết đã được chỉnh sửa nội dung bởi Long Phi: 06-09-2016 - 17:44


#177
bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản lý Toán Cao cấp
  • 1667 Bài viết

Bài 64:

Đặt $f(1)=a$

Ta thấy $f(x+1)$ chia hết $f(x)+a$ có 2 trường hợp

- $f(x+1)=f(x)+a$

-$ 2f(x+1)\leqslant f(x)+a$

$\Rightarrow f(x+1) \leqslant f(x) -(x+1)+a$

Nếu không tồn tại x thỏa $f(x+1)=f(x)+a$

Với $x > a$ thì $f(x)>f(x+1)$ , vô lý do $f(n) \geq n$

 

Tại sao $f(x)>f(x+1)$ lại vô lý do $f(n) \geq n$


$$[\Psi_f(\mathbb{1}_{X_{\eta}}) ] = \sum_{\varnothing \neq J} (-1)^{\left|J \right|-1} [\mathrm{M}_{X_{\sigma},c}^{\vee}(\widetilde{D}_J^{\circ} \times_k \mathbf{G}_{m,k}^{\left|J \right|-1})] \in K_0(\mathbf{SH}_{\mathfrak{M},ct}(X_{\sigma})).$$


#178
Long Phi

Long Phi

    Binh nhất

  • Thành viên
  • 26 Bài viết

Nếu không có $x$ thỏa mãn thì $f(x)$ sẽ giảm liên tục



#179
Mr Cooper

Mr Cooper

    Sĩ quan

  • Thành viên
  • 496 Bài viết

Bài 71: Tìm tất cả các số nguyên dương $n$ thỏa mãn : không có số chính phương $m$ nào sao cho $n<m<2n$



#180
canhhoang30011999

canhhoang30011999

    Thiếu úy

  • Thành viên
  • 634 Bài viết

Bài 71: Tìm tất cả các số nguyên dương $n$ thỏa mãn : không có số chính phương $m$ nào sao cho $n<m<2n$

bài toán tương đương với tồn tại x sao cho $x^{2} \leq n<2n \leq (x+1)^2$ từ đó suy ra $2x^{2}<(x+1)^{2}$ đánh giá chặn được n


Bài viết đã được chỉnh sửa nội dung bởi canhhoang30011999: 06-03-2017 - 20:23





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh