Chủ đề này có 14 trả lời

[perfectstrong]

Chuyển nhanh đến:
1) Điều lệ
2) Đăng kí thi đấu
3) Lịch thi đấu và tổng hợp kết quả

Vào hồi 20h00, Thứ Sáu, ngày 21/09/2012, Tổ trọng tài sẽ ra đề vào topic này, sau khi có đề, các toán thủ bắt đầu thi đấu.

Các toán thủ khi thi đấu, cứ yên tâm rằng, sau khi trả lời là bài làm đã được lưu, BTC đã nhận được bài làm của bạn, có điều bạn không nhìn thấy được mà thôi. Bạn nên mừng vì điều này, như thế các toán thủ khác không thể copy bài của bạn được.

Bạn cũng nên sử dụng chức năng xem trước của diễn đàn để sửa các lỗi Latex trước khi gửi bài, vì gửi rồi sẽ không xem và sửa lại được nữa.

BTC lưu ý:
1) Trận 5 có 28 toán thủ tham gia nên sau trận này, 02 toán thủ ít điểm nhất sẽ bị loại.

2) Các toán thủ chớ quên rằng mỗi một mở rộng đúng sẽ được 10 điểm, các bạn nên mở rộng bài toán để thu được nhiều điểm hơn

3) Toán thủ nào tự ý sửa bài sau khi trận đấu kết thúc sẽ được 0 điểm

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 22:07

[E. Galois]

Cho $p$ là số nguyên tố, $p>3$ và $n=\frac{2^{2p}-1}{3}$. CMR: $(2^{n+1}-4)\vdots n$.
Toán thủ ra đề
rubik97

[Trần Đức Anh @@]

Xét bổ đề mở rộng sau: $a,m,n\in\mathbb{Z}^{+}$: $a^n-1\vdots{a^m-1}$ khi và chỉ khi $n\vdots{m}$. Chứng minh vô cùng dễ dàng bằng khai triển và dùng tính chất cơ bản của phép chia là $a=bq+r$.
Ta có: $n=\frac{2^{2p}-1}{3}$ suy ra $n-1=\frac{4(2^{p-1}-1)(2^{p-1}+1)}{3}$. Chú ý rằng $2^{p-1}-1\vdots{3}$. Theo FLT ta có: $2^{p-1}-1\vdots{p}$ (vì $p$ lẻ). Vậy với $p>3$ thì $2^{p-1}-1\vdots{3p}$ do đó $n-1\vdots{2p}$ suy ra: $2^{n-1}-1\vdots{2^{2p}-1}$.Từ giả thiết suy ra $2^{2p}-1\vdots{n}$, nên $2^{n-1}-1\vdots{n}$. Suy ra điều phải chứng minh vì $(4,p)=1$.

D-B=1.6h
E=10
F=0
S=80.4

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:04

[WhjteShadow]

Ta có:
$$ n=\frac{2^{2p}-1}{3}=\frac{2^{2p}-4}{3}+1=\frac{4(2^{2p-2}-1)}{3}+1$$
Lại có:
$$2^{2p-2}-1 = (2^{p-1}-1)(2^{p-1} + 1)$$
Và the0 $Farmat$ nhỏ và do $p-1$ chẵn ($p$ lẻ),$(p;3)=1$ thì:
$$2^{p-1} - 1 \vdots p,2^{p-1} - 1 \vdots 3\to 2^{p-1} - 1 \vdots 3p$$
Vậy nên $ 2^{2p-2}-1 \vdots 3p$ . Ta đặt $\frac{4(2^{2p-2}-1)}{3} = 2kp$ ($k\in Z$)
$\Rightarrow n = 2kp + 1$.Ta sẽ chứng minh:
$$2^n - 2 \vdots n$$
$$\Leftrightarrow 2^{2kp+1} - 2\vdots n$$
Mà mặt khác $2^{2kp} - 1\vdots 2^{2p} - 1$ (Dễ thấy ).Vậy ta chỉ cần chỉ ra:
$$2^{2p} - 1\vdots n$$
Nhưng điều này luôn đúng do $n = \frac{2^{2p} - 1}{3}\Rightarrow 3n = 2^{2p} - 1$
Vậy bài toán được chứng minh,dấu bằng xảy ra khi ..... $\blacksquare$

Dấu bằng gì ở đây hả em? Fermat chứ sao Farmat?
D-B=1.8h
E=10
F=0
S=80.2

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:21

[minhtuyb]

Cho $p$ là số nguyên tố, $p>3$ và $n=\frac{2^{2p}-1}{3}$. CMR: $(2^{n+1}-4)\vdots n$.
Toán thủ ra đề
rubik97

Dễ thấy $n\ge \dfrac{2^{2.5}-1}{3}=341$. Với điều kiện này thì:

-Từ giả thiết ta có:
$$3n=2^{2p}-1\\ \Leftrightarrow 3(n-1)=2^{2p}-4=4(2^{p-1}-1)(2^{p-1}+1)\\ =2(2^{p-1}-1)(2^p+2)$$

Lại có:

+) $VP$ chẵn $\Rightarrow 3(n-1)\vdots 2\Rightarrow n-1\vdots 2$ do $(3;2)=1$
+) $2^{p-1}-1\vdots p$ (định lí Fermat nhỏ) và $3\not\vdots p\Rightarrow n-1\vdots p$

-Từ các điều trên suy ra: $n-1\vdots 2p$ do $(2;p)=1$

Vậy nên: $3n=2^{2p}-1\Leftrightarrow 2^{2p}=3n+1\equiv 1\ (mod\ n) \Rightarrow 2^{n-1} \equiv 1\ (mod\ n)\Leftrightarrow 2^{n-1}-1\vdots n$

Suy ra: $2^{n+1}-4=4(2^{n-1}-1)\vdots n\ \square$

Các mở rộng của em thực chất chỉ là hệ quả của MR 1.
D-B=4.4h
E=9
F=1*10=10
S=84.6

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:21

[minhtuyb]

*Nhận xét: Chìa khóa của bài toán ban đầu là c/m $2^{n-1}-1\vdots n$.

MR 1: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $n$ là số giả nguyên tố cơ sở $a$.

C/m:

- Trước hết ta có : $n=\dfrac{a^p-1}{a-1}.\dfrac{a^p+1}{a+1}$ và $\dfrac{a^p-1}{a-1}\in \mathbb{Z};\dfrac{a^p+1}{a+1}\in \mathbb{Z}; |\dfrac{a^p-1}{a-1}| \ge 2 $ nên n là hợp số $(1)$

- Giả thiết tương đương:
$$(a^2-1)(n-1)=a^{2p}-a^2=a(a^{p-1}-1)(a^p+a)$$
Do
$+) a^p+a $chẵn
$+) p|a^{p-1}-1$ (định lí Fermat nhỏ)
$+) a^2-1|a^{p-1} -1$ (do $p-1$ chẵn)
$+) p\not | a(a^2-1) $
Dẫn đến $2p|n-1 $
Do $ a^{2p}=n(a^2 -1)+1 \equiv 1(mod\ n) $
Nên $a^{n-1} \equiv 1 (mod\ n)\ (2)$
-Từ $(1)$ và $(2)$ ta có ĐPCM.

MR 2: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $a^{n+1}-a^2\vdots n$

C/m:

Từ mở rộng 1 ta chứng minh được $a^{n-1} \equiv 1 (mod\ n)\ \Leftrightarrow n\ |\ a^{n-1}-1 \Rightarrow n\ |\ a^{n+1}-a^2$ (do $a^{n-1}-1 | a^{n+1}-a^2$ ) $\square$

MR 3: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $a^{n+k-1}-a^{k} \vdots n$ với $k\in \mathbb{N}$

C/m:

Từ mở rộng 1 ta chứng minh được $a^{n-1} \equiv 1 (mod\ n)\ \Leftrightarrow n\ |\ a^{n-1}-1 \Rightarrow n\ |\ a^{n+k-1}-a^{k}$ (do $a^{n-1}-1 | a^{n+k-1}-a^{k}$ ) $\square$

MR 4: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $k(a^{n-1}-1) \vdots n$ với $k\in \mathbb{N}$

C/m:

Từ mở rộng 1 ta chứng minh được $a^{n-1} \equiv 1 (mod\ n)\ \Leftrightarrow n\ |\ a^{n-1}-1 \Rightarrow n\ |\ k(a^{n-1}-1)$ (do $a^{n-1}-1 | k(a^{n-1}-1)$ ) $\square$

[hoangtrunghieu22101997]

Ta có $n=\frac{2^{2p}-1}{3}=\frac{4^p-1}{3}=4^{p-1}+4^{p-2}+...+4+1 \in Z$
$\Rightarrow 2^{2p-1} \vdots n$
Mà $n=\frac{4(2^{2(p-1)-1})}{3}+1=2kp+1(k \in Z)$
Bởi theo Fecma nhỏ thì $2^{p-1} -1 \vdots p$
Xét $2^{n+1}-4=2(2^n-2)=2(2^{2kp+1}-2)=4(2^{2kp}-1) \vdots (2^{2p}-1)$
$\Rightarrow (2^{n+1}-4) \vdots (2^{2p}-1) \vdots n$(đpcm)

D-B=19h
E=9
F=0
S=60

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:20

[Math Is Love]

Toán thủ MO 37 xin giải như sau:
Lời giải:
Theo khai triển Newton,ta có:
$2^{2p}-1=4^{p}-1=(4-1)(4^{p-1}+4^{p-2}+...+4+1)=3.(4^{p-1}+4^{p-2}+...+4+1)$
$\Rightarrow n=(4^{p-1}+4^{p-2}+...+4+1)$ là số lẻ.Vậy nên $n-1$ là số chẵn.(1)
Lại có:$n-1=\frac{2^{2p}-1}{3}-1=\frac{4^{p}-4}{3}$
Theo định lí Phéc-ma nhỏ,ta có:$4^{p}-4\vdots p$
Mà p là số nguyên tố lớn hơn 3 nên n chia hết cho p (2)
Từ (1) và (2) ta có:$n\vdots 2p$
Ta có:
$2^{2p}\equiv 1(mod2^{2p}-1)$
Theo định lí cấp của phần tử,vì $n-1$ là bội của $2p$ nên ta có:
$2^{n-1}\equiv 1(mod2^{2p}-1)$
Vậy nên:
$2^{n+1}-4=4(2^{n-1}-1)\vdots (2^{2p}-1)$
Mà $2^{2p}-1=3n$
$\Rightarrow (2^{n+1}-4)\vdots n$
Vậy ta có đpcm

Sai ở đoạn này

Mà p là số nguyên tố lớn hơn 3 nên n chia hết cho p (2)
Từ (1) và (2) ta có:$n\vdots 2p$

Phải là $2p|n-1$.
D-B=28.2h
E=7
F=0
S=44.8

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:18

[milinh7a]

Ta có: $2^{n+1}-4=4(2^{n-1}-1)$
Mà n-1=$\frac{4^p-4}{3}$, theo định lí Fecma: $4^p-4\vdots p$, do đó n-1$\vdots p$(1)
n = $4^{p-1}+4^{p-2}+...+4+1$, nên n-1 chẵn, p là số nguyên tố lẻ(2)
từ (1),(2) ta có n-1=2pk $\left ( k\epsilon N \right )$$\Rightarrow 2^{n-1}-1=2^{2pk}-1\vdots 2^{2p}-1\Rightarrow 2^{n-1}-1\vdots 3n\Rightarrow 2^{n-1}-1\vdots n\Rightarrow 2^{n+1}-4\vdots n$

D-B=36.5h
E=9
F=0
S=42.5

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:20

[Joker9999]

Áp dụng định lí Fermat nhỏ cho p là số nguyên tố ta có:\[
2^p \equiv 2(\bmod p)
\]
Mặt khác do p là số nguyên tố >3 nên p lẻ, p có dạng 2k+1 với k là số nguyên dương.
Ta có :$2^{2k + 1} - 2 = 4^k .2 - 2 \vdots 3$ do $4 \equiv 1(\bmod 3) \Rightarrow 4^k \equiv 1(\bmod 3)$
$2{}^p - 2$ chia hết cho cả p và 3,mặt khác (p,3)=1 nên $\frac{{2{}^p - 2}}{3} \vdots p$
Đặt $\frac{{2{}^p - 2}}{3}=p.m$ với m là số nguyên dương ta có:
\[
\begin{array}{l}
2^{\frac{{2{}^p - 2}}{3}} - 1 = 2^{p.m} - 1 \vdots 2^p - 1 \\
\Rightarrow 2^{(\frac{{2{}^p - 2}}{3}).(2^p + 2)} - 1 \vdots 2^p - 1 \Rightarrow 2^{n - 1} - 1 \vdots 2^p - 1 \, \, (1)\\
\end{array}
\]
Ta có:
Theo định lí Fermat nhỏ ta có:
\[
4^{p - 1} \equiv 1(\bmod p)\\
\Rightarrow 2^{2p - 2} - 1 \vdots p \Rightarrow 4(2^{2p - 2} - 1) \vdots 2p\,\,\textrm{ do }(2,p)=1\\
\Rightarrow 2^{2p} - 4 \vdots 2p \Rightarrow \frac{{2^{2p} - 4}}{3} \vdots 2p
\]
Do dễ chứng minh: $2^{2p} - 4 \vdots 3,(3,2p) = 1$
Ta có:
\[
2^{\frac{{2^{2p} - 4}}{3}} - 1 \vdots 2^{2p} - 1 \vdots \frac{{2^p + 1}}{3}\\
\Rightarrow 2^{n - 1} - 1 = 2^{\frac{{2^{2p} - 4}}{3}} - 1 = 2^{\frac{{4(2^{2p - 2} - 1)}}{3}} - 1 \vdots \frac{{2^p + 1}}{3}
\]
mặt khác ta dễ thấy:${2^p + 1}$ và $2^p - 1$là 2 số lẻ nguyên tố cùng nhau
do đó:\[
2^{n - 1} - 1 \vdots (\frac{{2^p + 1}}{3}).2^p - 1 = \frac{{2^{2p} - 1}}{3} = n
\]
do n lẻ nên (4,n)=1 do đó:\[
2^{n + 1} - 4 \vdots n
\]
Điều phải chứng minh:

Trong bài thi, em vui lòng đừng dùng chữ "dễ thấy".
D-B=44.9h
E=8
F=0
S=31.1

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:28

[davildark]

Ta có $n=\frac{2^{2p}-1}{3}=\frac{4^p -1 }{3}=\sum_{i=o}^{p-1}4^i$ (1)
$\Rightarrow n\in \mathbb{N} $
Dễ thấy $4^x$ tận cùng là 4 nếu x lẻ tân cùng là 6 nếu x chẵn
Từ (1) ta có n lẻ
Theo fermat nhỏ ta có $4^p -4 \ \vdots \ p $ mà $(3,p)=1$ $\Rightarrow 4^p-4 \ \vdots \ 3p$
$\Rightarrow n-1=\frac{4^p-4}{3} \vdots p$
Vì n lẻ nên n-1 chẵn
Mà $(2,p)=1$ $\Rightarrow n-1 \ \vdots \ 2p \Rightarrow n-1=k.2p$
$$\dfrac{2^{n-1}-1}{2^{2p}-1}=\dfrac{(2^{2p})^{k}-1}{(2^{2p})-1}=\dfrac{(2^{2p}-1).\sum_{i=o}^{k-1}(2^{2p})^i}{2^{2p-1}}=\sum_{i=o}^{k-1}(2^{2p})^i$$
$\Rightarrow 2^{n-1}-1 \ \vdots \ 2^{2p}-1$
$ \Rightarrow 2^{n+1}-4=4(2^{n-1} -1 ) \vdots 2^{2p}-1=3n \ \vdots \ n$

D-B=45.4h
E=10
F=0
S=36.5

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 21:30

[E. Galois]

Trận đấu đã kết thúc, các toán thủ hãy nhận xét bài làm của nhau

[Trần Đức Anh @@]

*Nhận xét: Chìa khóa của bài toán ban đầu là c/m $2^{n-1}-1\vdots n$.

MR 1: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $n$ là số giả nguyên tố cơ sở $a$.

C/m:

- Trước hết ta có : $n=\dfrac{a^p-1}{a-1}.\dfrac{a^p+1}{a+1}$ và $\dfrac{a^p-1}{a-1}\in \mathbb{Z};\dfrac{a^p+1}{a+1}\in \mathbb{Z}; |\dfrac{a^p-1}{a-1}| \ge 2 $ nên n là hợp số $(1)$

- Giả thiết tương đương:
$$(a^2-1)(n-1)=a^{2p}-a^2=a(a^{p-1}-1)(a^p+a)$$
Do
$+) a^p+a $chẵn
$+) p|a^{p-1}-1$ (định lí Fermat nhỏ)
$+) a^2-1|a^{p-1} -1$ (do $p-1$ chẵn)
$+) p\not | a(a^2-1) $
Dẫn đến $2p|n-1 $
Do $ a^{2p}=n(a^2 -1)+1 \equiv 1(mod\ n) $
Nên $a^{n-1} \equiv 1 (mod\ n)\ (2)$
-Từ $(1)$ và $(2)$ ta có ĐPCM.

MR 2: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $a^{n+1}-a^2\vdots n$

C/m:

Từ mở rộng 1 ta chứng minh được $a^{n-1} \equiv 1 (mod\ n)\ \Leftrightarrow n\ |\ a^{n-1}-1 \Rightarrow n\ |\ a^{n+1}-a^2$ (do $a^{n-1}-1 | a^{n+1}-a^2$ ) $\square$

MR 3: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $a^{n+k-1}-a^{k} \vdots n$ với $k\in \mathbb{N}$

C/m:

Từ mở rộng 1 ta chứng minh được $a^{n-1} \equiv 1 (mod\ n)\ \Leftrightarrow n\ |\ a^{n-1}-1 \Rightarrow n\ |\ a^{n+k-1}-a^{k}$ (do $a^{n-1}-1 | a^{n+k-1}-a^{k}$ ) $\square$

MR 4: Chứng minh nếu $ n=\dfrac{a^{2p}-1}{a^2-1}$,trong đó a nguyên $,a>1,p$ là số nguyên tố lẻ, $a(a^2-1) \not\vdots p$ thì $k(a^{n-1}-1) \vdots n$ với $k\in \mathbb{N}$

C/m:

Từ mở rộng 1 ta chứng minh được $a^{n-1} \equiv 1 (mod\ n)\ \Leftrightarrow n\ |\ a^{n-1}-1 \Rightarrow n\ |\ k(a^{n-1}-1)$ (do $a^{n-1}-1 | k(a^{n-1}-1)$ ) $\square$

Em hiểu mở rộng là gì không? Nghĩa là khi cho số má cụ thể thì là kết quả bài toán!

[perfectstrong]

Em hiểu mở rộng là gì không? Nghĩa là khi cho số má cụ thể thì là kết quả bài toán!

Cậu đừng hiểu thế. Mở rộng là sự phát triển bài toán theo một hướng nào đó thôi.
Còn cái cậu nói là tổng quát

P/s: Em minhtuyb làm 4 cái mở rộng như thế nhưng thực chất chỉ là 1, vì 3 cái sau là hệ quả MR 1

[TRONG TAI]

Đáp án chính thức:
Bổ đề: Cho các số nguyên dương $a,m,n$. Khi đó $a^n-1 \vdots a^m-1 \Leftrightarrow n \vdots m$
===========================
Quay lại bài toán. Vì $p$ là số nguyên tố và $p>3$ suy ra $2^{p-1}\equiv 1 \pmod 3$.
Mặt khác $(2,p)=1$ nên theo định lí Fermat nhỏ, ta có: $2^{p-1}\equiv 1 \pmod p$.
Do đó: $2^{p-1}-1\vdots 3p$ vì $(3;p)=1$.
Ta có: $$n-1=\dfrac{2^{2p}-1}{3}-1=\dfrac{4^{p}-4}{3}=\dfrac{4(2^{p-1}+1)(2^{p-1}-1)}{3}$$
Suy ra $n-1\vdots 2p \Rightarrow 2^{n-1}-1\vdots 2^{2p}-1$ (do bổ đề)
Vì $n=\dfrac{2^{2p}-1}{3} \Rightarrow 2^{2p}-1\vdots n\Rightarrow 2^{n-1}-1\vdots n\Rightarrow 2^{n+1}-4\vdots n$
============================
============================
Bài thi các thí sinh đã được chấm xong.
Các thí sinh lưu ý, khi dùng định lý gì thì phải nêu rõ ra giả thiết cần phải có để suy ra kết quả cần tìm.
Ví dụ như định lý Fermat nhỏ. Nếu không ghi rõ là $(2;p)=1 \Rightarrow 2^{p-1} \equiv 1 \pmod p$ thì sẽ bị trừ điểm.
============================
Điểm cho rubik97
$D_{rd}=46.4$

Bài viết đã được chỉnh sửa nội dung bởi TRONG TAI: 25-09-2012 - 22:09