Đến nội dung

Hình ảnh

Đề thi chọn đội tuyển quốc gia THPT chuyên KHTN - ĐHQG Hà Nội vòng 1 năm 2016

hsgsvmo

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

#1
bangbang1412

bangbang1412

    Độc cô cầu bại

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

                                                                                                           ĐỀ THI CHỌN ĐỘI TUYỂN QUỐC GIA THPT CHUYÊN KHTN VÒNG 1

Câu $1$ : Giải phương trình nghiệm nguyên dương $(a,p,n)$ trong đó $p$ là một số nguyên tố thỏa mãn :

$$a^{2}(a^{2}+1)=5^{n}(5^{n+1}-p^{3})$$

Câu $2$ : Tìm tất cả đa thức hệ số thực thỏa mãn : 

$$2(P(x)-P(\frac{1}{x}))^{2}+3P(x^{2})P(\frac{1}{x^{2}})=0$$

Câu $3$ : Cho tam giác $ABC$ nhọn có $AB<AC$ , $H,O$ lần lượt là trực tâm và tâm ngoại tiếp của tam giác $ABC$ . $E$ thuộc cạnh $AC$ sao cho $OE || BC$ . Gọi $OE$ cắt đường tròn ngoại tiếp tam giác $EBC$ tại $F$ . Tiếp tuyến tại $F$ của đường tròn $(EBC)$ cắt $BC,AH$ lần lượt ở $P,Q$ .

$a)$ Chứng minh đường tròn $(K)$ ngoại tiếp tam giác $BPQ$ đi qua trung điểm $M$ của $AH$ 

$b)$ Gọi $PA,PH$ cắt $(K)$ ở $S,T$ khác $P$ . Chứng minh rằng hai tiếp tuyến tại $S,T$ của $K$ cắt nhau trên $ME$ 

Câu $4$ : Một số nguyên dương $n \geq 2$ được gọi là tốt nếu với mọi $2 \leq k \leq n$ thì $n$ có dạng $n = a_{1}+a_{2}+....+a_{k}$ trong đó $(n,a_{k})=1$ và các số $a_{i}$ là nguyên dương . Tính tổng tất cả các số tốt nhỏ hơn $2016$ 

:( làm khá là chán , mọi người vào chém đi .


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 17-09-2016 - 20:04

$$[\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})).$$


#2
baopbc

baopbc

    Himura Kenshin

  • Thành viên nổi bật 2016
  • 410 Bài viết

Câu 3. a, Do $EF\parallel BC$ nên $\angle FPC=\angle FCE$. Mặt khác dễ thấy $\triangle OCE\sim \triangle BAH$ nên $\frac{OE}{EC}=\frac{BH}{AH}$. Từ đó suy ra $\frac{MH}{HB}=\frac{EC}{EF}$ nên $\triangle FEC\sim \triangle BHM$ (cạnh - góc - cạnh). Do đó $\angle BMQ=\angle FCE=\angle FPC$ nên tứ giác $MQBP$ nội tiếp.

b, Gọi $R$ là giao điểm của $EM$ với $(K)$. Dễ thấy chỉ cần chứng minh tứ giác $RSMT$ điều hòa $\Leftrightarrow P(RMAH)=-1$. Mặt khác do $M$ là trung điểm $AH$ nên ta chỉ cần chứng minh $PR\parallel AH$. Điều này tương đương với chứng minh $\angle PQM+\angle EMQ=180^\circ$.

Do $\angle PQM=90^\circ+\angle BPQ=90^\circ+\angle BMH$ nên ta chỉ cần chứng minh $\angle BME=90^\circ$. Kết quả này quen thuộc!

 

PS

Em hơi nhầm lẫn, cho em xin lỗi! :(


Bài viết đã được chỉnh sửa nội dung bởi baopbc: 17-09-2016 - 20:04


#3
bangbang1412

bangbang1412

    Độc cô cầu bại

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

Câu 3. a, Do $EF\parallel BC$ nên $\angle FPC=\angle FCE$. Mặt khác dễ thấy $\triangle OCE\sim \triangle BAH$ nên $\frac{OE}{EC}=\frac{BH}{AH}$. Từ đó suy ra $\frac{MH}{HB}=\frac{EC}{EF}$ nên $\triangle FEC\sim \triangle BHM$ (cạnh - góc - cạnh). Do đó $\angle BMQ=\angle FCE=\angle FPC$ nên tứ giác $MQBP$ nội tiếp.

b, Gọi $R$ là giao điểm của $EM$ với $(K)$. Dễ thấy chỉ cần chứng minh tứ giác $RSMT$ điều hòa $\Leftrightarrow P(RMAH)=-1$. Mặt khác do $M$ là trung điểm $AH$ nên ta chỉ cần chứng minh $PR\parallel AH$. Điều này tương đương với chứng minh $\angle PQM+\angle EMQ=180^\circ$.

Do $\angle PQM=90^\circ+\angle BPQ=90^\circ+\angle BMH$ nên ta chỉ cần chứng minh $\angle BME=90^\circ$. Kết quả này quen thuộc!

 

PS. Bài số 2 không biết có nhầm lẫn gì không nhưng nếu xét bậc của đa thức thì suy ra ngay bằng $0$ hoặc $1$.

em làm ntn mà sao xét bậc anh không hiểu ? 


$$[\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})).$$


#4
CandyPanda

CandyPanda

    Hạ sĩ

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

Câu 3. a, Do $EF\parallel BC$ nên $\angle FPC=\angle FCE$. Mặt khác dễ thấy $\triangle OCE\sim \triangle BAH$ nên $\frac{OE}{EC}=\frac{BH}{AH}$. Từ đó suy ra $\frac{MH}{HB}=\frac{EC}{EF}$ nên $\triangle FEC\sim \triangle BHM$ (cạnh - góc - cạnh). Do đó $\angle BMQ=\angle FCE=\angle FPC$ nên tứ giác $MQBP$ nội tiếp.

b, Gọi $R$ là giao điểm của $EM$ với $(K)$. Dễ thấy chỉ cần chứng minh tứ giác $RSMT$ điều hòa $\Leftrightarrow P(RMAH)=-1$. Mặt khác do $M$ là trung điểm $AH$ nên ta chỉ cần chứng minh $PR\parallel AH$. Điều này tương đương với chứng minh $\angle PQM+\angle EMQ=180^\circ$.

Do $\angle PQM=90^\circ+\angle BPQ=90^\circ+\angle BMH$ nên ta chỉ cần chứng minh $\angle BME=90^\circ$. Kết quả này quen thuộc!

 

PS. Bài số 2 không biết có nhầm lẫn gì không nhưng nếu xét bậc của đa thức thì suy ra ngay bằng $0$ hoặc $1$.

 

Nghi ngờ lắm khó mà suy trực tiếp ra bậc bằng 0 hoặc 1 được



#5
quanghung86

quanghung86

    Thiếu úy

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

Đề hình có thể viết gọn thành 1 ý như sau

 

Cho tam giác $ABC$ nhọn có $AB<AC$. $H,O$ lần lượt là trực tâm và tâm ngoại tiếp tam giác $ABC$. $E$ thuộc đoạn $AC$ sao cho $OE\parallel BC$. $OE$ cắt đường tròn ngoại tiếp tam giác $EBC$ tại $F$ khác $E$. Tiếp tuyến tại $F$ của đường tròn ngoại tiếp tam giác $EBC$ cắt $BC,AH$ lần lượt tại $P,Q$. $PA,PH$ cắt đường tròn $(K)$ ngoại tiếp tam giác $BPQ$ lần lượt tại $S,T$ khác $P$. Các tiếp tuyến tại $S,T$ của $(K)$ cắt nhau tại $X$. Chứng minh rằng $XE$ tiếp xúc đường tròn ngoại tiếp tam giác $EBC$.
 

 



#6
Minhnguyenthe333

Minhnguyenthe333

    Trung úy

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

Câu 1:

Ta xét 2 trường hợp:

TH1: $5^n \mid a^2$

Khi đó đặt $a^2=k.5^n\implies k(k.5^n+1)=5^{n+1}-p^3\iff  p^3+k=5^n(5-k^2)$

Dễ thấy $VP>0\implies$ $k=1$ hoặc $k=2$

$k=1\implies p^3+1=4.5^n\iff \left ( \frac{p+1}{4} \right )(p^2-p+1)=5^n$

Chú ý rằng $\gcd (\frac{p+1}{4},p^2-p+1)=1$ nên $PT$ vô nghiệm

$k=2\implies p^3=5^n-2$ (vô nghiệm theo modulo $5$)

 

TH2: $5^n\mid a^2+1$

Tương tự$\implies p^3-k=5^n(5-k^2)$

Dễ thấy $p^3>k$ nên $k=1$ hoặc $k=2$
$k=1\implies p^3=4.5^n+1$ (vô nghiệm)

$k=2\implies p^3=5^n+2$

$n$ chẵn ta có $3\mid p\implies (p,n)=(3,2)$

$n$ lẻ ta có $p^3-1=5^{n}+1\implies v_2(p^3-1)=v_2(5^n+1)\iff v_2(p-1)=v_2(n)>0$

$\implies 2\mid n$ (vô lí)

 

Kết luận: $(a,p,n)=(7,3,2)$

 

P/s: Đã sửa lại


Bài viết đã được chỉnh sửa nội dung bởi Minhnguyenthe333: 18-09-2016 - 20:34


#7
CandyPanda

CandyPanda

    Hạ sĩ

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

Câu 1:

Ta xét 2 trường hợp:

TH1: $5^n \mid a^2$

Khi đó đặt $a^2=k.5^n\implies k(k.5^n+1)=5^{n+1}-p^3\iff  p^3+k=5^n(5-k^2)$

Dễ thấy $VP>0\implies$ $k=1$ hoặc $k=2$

$k=1\implies p^3+1=4.5^n\iff \left ( \frac{p+1}{4} \right )(p^2-p+1)=5^n$

Chú ý rằng $\gcd (\frac{p+1}{4},p^2-p+1)=1$ nên $PT$ vô nghiệm

$k=2\implies p^3=5^n-2$ (vô nghiệm theo modulo $5$)

 

TH2: $5^n\mid a^2+1$

Tương tự$\implies p^3-k=5^n(5-k^2)$

Dễ thấy $p^3>k$ nên $k=1$ hoặc $k=2$
$k=1\implies p^3=4.5^n+1$ (vô nghiệm)

$k=2\implies p^3=5^n+2$

Theo modulo $3$ ta suy ra $n$ chẵn$\implies p^3=5^{2l}+2$

$PT$ $Mordell$ trên có bộ nghiệm duy nhất: $(p,l)=(3,1)$

 

Kết luận: $(a,p,n)=(7,3,2)$

KHTN chứ có phải viện toán cao cấp đâu mà Mordell @@



#8
Minhnguyenthe333

Minhnguyenthe333

    Trung úy

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

KHTN chứ có phải viện toán cao cấp đâu mà Mordell @@

Mình sửa lại rồi 



#9
CandyPanda

CandyPanda

    Hạ sĩ

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

Mình sửa lại rồi 

Đoạn cuối dùng v2 chắc đúng. Nhưng mà chỉ muốn góp ý nhỏ là công thức v2 nó khác với vp nhé. Ở kia lỗi chút chút kìa



#10
viet nam in my heart

viet nam in my heart

    Thượng sĩ

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

Câu 1:

Ta xét 2 trường hợp:

TH1: $5^n \mid a^2$

$k=2\implies p^3=5^n-2$ (vô nghiệm theo modulo $5$)

TH2: $5^n\mid a^2+1$

$n$ lẻ ta có $p^3-1=5^{n}+1\implies v_2(p^3-1)=v_2(5^n+1)\iff v_2(p-1)=v_2(n)>0$

$\implies 2\mid n$ (vô lí)

$TH1$ xét $mod$ $5$ kiểu gì bạn, $TH2$ bạn áp dụng bổ đề nào tính lũy thừa đúng vậy 

 

                                                                                                           ĐỀ THI CHỌN ĐỘI TUYỂN QUỐC GIA THPT CHUYÊN KHTN VÒNG 1

Câu $2$ : Tìm tất cả đa thức hệ số thực thỏa mãn : 

$$2(P(x)-P(\frac{1}{x}))^{2}+3P(x^{2})P(\frac{1}{x^{2}})=0$$

Thay $x=1$ vào thì $P(1)=0$

Ta thấy $P \equiv 0$ là một nghiệm

Nếu $P$ khác đa thức $0$

Do đó ta có thể đặt $P(x)=(x-1)^nQ(x)$ với $Q(1) \neq 0$

Nếu n lẻ

Ta có: $2\left((x-1)^nQ(x)-\left(\dfrac{1}{x}-1\right)^nQ\left(\dfrac{1}{x}\right)\right)^2=3(x^2-1)^n\left(1-\dfrac{1}{x^2}\right)^nQ(x^2)Q\left(\dfrac{1}{x^2}\right)$

Rút gọn lại: $2\left(x^nQ(x)+Q\left(\dfrac{1}{x}\right)\right)^2=3(x+1)^{2n}Q(x^2)Q\left(\dfrac{1}{x^2}\right)$

Dễ thấy nếu nhân $2$ vế của đẳng thức trên với $x^{2n}$ thì cả $2$ vế đều là đa thức và đẳng thức đúng với mọi $x \neq 1$ nên nó cũng đúng cả với $x=1$ do đó ta được thay $x=1$ và đẳng thức trên 

Suy ra $8Q(1)^2=3.4^n.Q(1)^2$ nên $Q(1)=0$ suy ra  vô lý

Tương tự với $n$ chẵn cũng có điều vô lý

Vậy $P \equiv 0$


"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic


#11
viet nam in my heart

viet nam in my heart

    Thượng sĩ

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

Câu 4:

Rõ ràng mọi số tự nhiên $>2$ nếu muốn là số tốt thì nó phải lẻ (Vì ta thấy nếu nó chẵn thì các $a_i$ phải lẻ và khi đó dễ thấy nếu chọn $k$ lẻ thì vô lý)

Ta chứng minh mọi số tự nhiên lẻ $>2$ đều là số tốt

Thật vậy xét $n$ lẻ $n >2$. Ta chứng minh với mọi $2 \leq k \leq n$ thì đều có thể viết $n= a_1+a_2+...+a_k$ trong đó $(n,a_i)=1$

Thật vậy $k=1$ ta viết $n=(n-1)+1$

Với $x$

Ta sẽ viết $n= (n-2^{x})+2^x$ 

Giờ ta chứng minh $2^x=a_1+a_2+...+a_k$ với mọi $1 \leq k \leq 2^x$ và $a_i$ đều là lũy thừa của $2$ (Điều này hoàn toàn chứng minh dễ dàng bằng quy nạp theo $k$)

Do đó với $2 \leq k \leq 2^x+1$ thì bài toán được chứng minh

Do đó ta chọn $x$ là số lớn nhất thỏa mãn $2^x<n<2^{x+1}$

Khi đó suy ra $2^x >\dfrac{n}{2}$ nên chỉ cần chứng minh nó đúng với $k > \dfrac{n}{2}$

Mặt khác ta cũng viết được $n= 2+2+...+2+1$ nên rõ ràng bằng quy nạp theo $k$ với $k > \dfrac{n}{2}$ thì cũng thỏa mãn

Vậy tất cả các số tốt là $2$ và các số lẻ $>2$

Từ đó ta tính được tổng


"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic


#12
baopbc

baopbc

    Himura Kenshin

  • Thành viên nổi bật 2016
  • 410 Bài viết

ĐỀ THI CHỌN ĐỘI TUYỂN QUỐC GIA THPT CHUYÊN KHTN - ĐHQG HÀ NỘI VÒNG 1 NGÀY 2 NĂM 2016

 

Bài 1. Cho $n$ nguyên dương. Chứng minh rằng tồn tại số nguyên dương $m$ có $n$ chữ số, chỉ gồm các chữ số $1,2,3$ và chia hết cho $S(m)$ (tổng các chữ số của $m$)

 

Bài 2. Cho một hoán vị của dãy số $\left \{ 1,2,3,...,n \right \}$, viết từ trái sang phải. Ta sẽ chuyển dãy số này về đúng vị trí, tức là $\left \{ 1,2,3,...,n \right \}$. Mỗi bước ta thực hiện như sau : Chọn số gần tay nhất mà không đứng đúng vị trí rồi chuyển nó về vị trí đúng (ví dụ : Dãy $3 \ 1 \ 4 \ 2$. Sau một bước chuyển thì $2$ về vị trí thức hai thành $3 \ 2 \ 1 \ 4$. Chứng minh rằng sau ít hơn $2^n$ bước thì dãy luôn chuyển về đúng vị trí.

 

Bài 3. Tứ giác $ABCD$ nội tiếp $(O)$ sao cho $ABCD$ không phải là hình thang. Tiếp tuyến tại $C,D$ của $(O)$ cắt nhau tại $T.TA$ giao $BD$ tại $S.E$ đối xứng $B$ qua $S.AB$ cắt đường tròn ngoại tiếp tam giác $EBC$ tại $F.EC$ giao $TA$ tại $P$.

a, Chứng minh rằng $PF$ tiếp xúc đường tròn ngoại tiếp tam giác $EBC$.

b, Giả sử $PF$ cắt $AC$ tại $Q. H, K$ lần lượt là hình chiếu của $Q$ lên $F A, F C. M$ là trung điểm $FA$. Chứng minh rằng tiếp tuyến qua $A$ của $(O)$ và đường thẳng qua $Q$ song song với $AO$ cắt nhau trên đường tròn ngoại tiếp tam giác $MHK$.

 

Bài 4. Cho $a,b,c>0$ sao cho $a+b+c=3$. Chứng minh rằng :

\[\frac{a}{b^2(ca+1)}+\frac{b}{c^2(ab+1)}+\frac{c}{a^2(cb+1)}\geq \frac{9}{(1+abc)(ab+bc+ca)}\]


Bài viết đã được chỉnh sửa nội dung bởi baopbc: 20-09-2016 - 19:32


#13
viet nam in my heart

viet nam in my heart

    Thượng sĩ

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

 

ĐỀ THI CHỌN ĐỘI TUYỂN QUỐC GIA THPT CHUYÊN KHTN - ĐHQG HÀ NỘI VÒNG 1 NGÀY 2 NĂM 2016

 

Bài 3. Tứ giác $ABCD$ nội tiếp $(O)$ sao cho $ABCD$ không phải là hình thang. Tiếp tuyến tại $C,D$ của $(O)$ cắt nhau tại $T.TA$ giao $BD$ tại $S.E$ đối xứng $B$ qua $S.AB$ cắt đường tròn ngoại tiếp tam giác $EBC$ tại $F.EC$ giao $TA$ tại $P$.

a, Chứng minh rằng $PF$ tiếp xúc đường tròn ngoại tiếp tam giác $EBC$.

b, Giả sử $PF$ cắt $AC$ tại $Q. H, K$ lần lượt là hình chiếu của $Q$ lên $F A, F C. M$ là trung điểm $FA$. Chứng minh rằng tiếp tuyến qua $A$ của $(O)$ và đường thẳng qua $Q$ song song với $AO$ cắt nhau trên đường tròn ngoại tiếp tam giác $MHK$.

 

Mình xin nếu ý tưởng giải bài hình. Phần $a$ khá đơn giản còn phần $b$ có lẽ tác giả đã chế ra từ một bài toán quen thuộc

k.png

a) Dễ dàng chứng minh được : $\triangle ECF \backsim \triangle DCA$

Ta cần chứng minh $\dfrac{PC}{PE}= \dfrac{FC^2}{FE^2}=\dfrac{AC^2}{AD^2}$ 

Mặt khác $\dfrac{PC}{PE}=\dfrac{d(C,AT)}{d(E,AT)}=\dfrac{d(C,AT)}{d(D,AT)}$ (Do $D,E$ đối xứng qua $T$)

Do đó chỉ cần chứng minh$ \dfrac{d(C,AT)}{d(D,AT)}=\dfrac{AC^2}{AD^2}$  (bổ đề quen thuộc với  $AT$ là đường đối trung của $\triangle ACD$)

b)

t.png

Dễ thấy nếu gọi $X$ là giao điểm của tiếp tuyến tại $A$ của $(O)$ và $PF$ (Tiếp tuyến tại $F$ của $(BCE)$) thì ta được tứ giác $CFXA$ nội tiếp

Từ đó quy bài toán về cấu hình quen thuộc sau: Tứ giác $ABCD$ nội tiếp có $AD$ cắt $BC$ tại $E$. Gọi $F,G,H$ lần lượt là hình chiếu của $E$ trên $AB,CD,AC$ và $M$ là trung điểm $AC$ thì sẽ có $F,G,H,E$ đồng viên

Có thể nhìn điểm $E$ ở ngoài hơi khó nhưng thực chất cách chứng minh nó giống với trường hợp ở trong như sau

Tứ giác $ABCD$ nội tiếp có $AC$ cắt $BD$ tại $E$. Gọi $F,G,H$ lần lượt là hình chiếu của $E$ trên $AD,BC,AB$ và $M$ là trung điểm $AB$ thì sẽ có $F,G,H,E$ đồng viên

Cấu hình khá quen thuộc và nó đã từng xuất hiện ở "Mỗi tuần một bài toán "

http://diendantoanho...tây-trung-quốc/

 


Bài viết đã được chỉnh sửa nội dung bởi viet nam in my heart: 20-09-2016 - 20:16

"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic


#14
baopbc

baopbc

    Himura Kenshin

  • Thành viên nổi bật 2016
  • 410 Bài viết

Bài 2 ngày 2. Ý tưởng chính là quy nạp

Dễ thấy với $n=2$ thì ít hơn $2$ bước di chuyển nên bài toán đúng với $n=2$.

Giả sử đúng đến $n$, ta chứng minh đúng với $n+1$.

Xét $n+1$ ở vị trí $k$ với $k$ khác $n+1$.

Nhận thấy rằng ta không thể lấy một số ở vị trí trước $k$ rồi thêm vào sau $k$ trước khi đưa số $n+1$ vào vị trí cuối cùng nên khoảng cách từ vị trí của số $n+1$ đến vị trí cuối cùng chỉ có thể giảm hoặc không đổi.

Sau mỗi bước di chuyển, nếu một số ở sau vị trí $k$ nhỏ hơn hoặc bằng $k$ được chuyển về trước vị trí $k$ thì khoảng cách từ vị trí của số $n+1$ đến vị trí cuối cùng sẽ giảm xuống $1$. Do đó ta chỉ cần xét cho trường hợp xấu nhất là tất cả các số sau vị trí $k$ đều lớn hơn $k$.

Ta thấy tồn tại một song ánh giữa hai tập $\left \{ k+1,k+2,...,n+1 \right \}\to\left \{ 1,2,...,n-k+1 \right \}$ nên để tất cả các số sau vị trí $k$ về vị trí đúng thì cần ít hơn $2^{n-k+1}$ bước. Do đó để số $n+1$ về đúng vị trí của nó thì cần ít hơn hoặc bằng $2^{n-k+1}$.

Theo giả thiết quy nạp để chuyển dãy là hoán vị của $\left \{ 1,2,3,..,n \right \}$ về vị trí đúng thì cần ít hơn $2^n$ bước nên để chuyển dãy là hoán vị của $\left \{ 1,2,3,..,n+1 \right \}$ thì cần ít hơn $2^n+2^{n-k+1}\leq 2^n+2^n=2^{n+1}$ (bước).

Do đó ta có đpcm.



#15
JUV

JUV

    Trung sĩ

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

Bài 2 ngày 2. Ý tưởng chính là quy nạp

Dễ thấy với $n=2$ thì ít hơn $2$ bước di chuyển nên bài toán đúng với $n=2$.

Giả sử đúng đến $n$, ta chứng minh đúng với $n+1$.

Xét $n+1$ ở vị trí $k$ với $k$ khác $n+1$.

Nhận thấy rằng ta không thể lấy một số ở vị trí trước $k$ rồi thêm vào sau $k$ trước khi đưa số $n+1$ vào vị trí cuối cùng nên khoảng cách từ vị trí của số $n+1$ đến vị trí cuối cùng chỉ có thể giảm hoặc không đổi.

Sau mỗi bước di chuyển, nếu một số ở sau vị trí $k$ nhỏ hơn hoặc bằng $k$ được chuyển về trước vị trí $k$ thì khoảng cách từ vị trí của số $n+1$ đến vị trí cuối cùng sẽ giảm xuống $1$. Do đó ta chỉ cần xét cho trường hợp xấu nhất là tất cả các số sau vị trí $k$ đều lớn hơn $k$.

Ta thấy tồn tại một song ánh giữa hai tập $\left \{ k+1,k+2,...,n+1 \right \}\to\left \{ 1,2,...,n-k+1 \right \}$ nên để tất cả các số sau vị trí $k$ về vị trí đúng thì cần ít hơn $2^{n-k+1}$ bước. Do đó để số $n+1$ về đúng vị trí của nó thì cần ít hơn hoặc bằng $2^{n-k+1}$.

Theo giả thiết quy nạp để chuyển dãy là hoán vị của $\left \{ 1,2,3,..,n \right \}$ về vị trí đúng thì cần ít hơn $2^n$ bước nên để chuyển dãy là hoán vị của $\left \{ 1,2,3,..,n+1 \right \}$ thì cần ít hơn $2^n+2^{n-k+1}\leq 2^n+2^n=2^{n+1}$ (bước).

Do đó ta có đpcm.

Đoạn trường hợp xấu nhất là tất cả các số sau vị trí $k$ lớn hơn $k$ có vấn đề rồi: Cho dù số $x$ nhỏ hơn $k$ được chọn và di chuyển về sau $n$ thì cũng đã tốn $1$ bước rồi, ví dụ cho số $1$ ở vị trí cuối thì khi di chuyển về vị trí đầu là cũng mất $1$ bước và còn làm xáo trộn trật tự của các số đứng đằng sau $k$ nên tất nhiên số bước để $n$ đến vị trí $n$ cũng thay đổi không rõ như thế nào dù khoảng cách $n$ cần phải di chuyển giảm, huống hồ những số nhỏ hơn $k$ lại phân bố không biết lối nào mà lần (không phải khoảng cách càng nhỏ thì số bước càng nhỏ)



#16
JUV

JUV

    Trung sĩ

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

Bài 2: Ta sẽ chứng minh rằng với số $x$ bất kì với $0<x<n+1$ thì $x$ sẽ được đứng cuối nhiều nhất $2^{x-1}$ lần (Số lần đứng cuối của $x$ được tính bằng số bước mà sau mỗi bước đó, ta thu được $1$ hoán vị với số $x$ là số sẽ được chọn để chuyển về đúng vị trí trong bước sau). Với $x=1$ thì ta thấy ngay rằng $1$ chỉ đứng cuối nhiều nhất $1=2^0$ lần vì sau lần đầu tiên đứng cuối, nó sẽ chyển về vị trí thứ nhất và sẽ không di chuyển nữa. Với $x=2$ thì sau lần đứng cuối đầu tiên, số $2$ sẽ đi về vị trí thứ $2$. Nếu lúc đó trước số $2$ là số $1$ thì nó sẽ không di chuyển nữa, nếu không thì lúc đó số $1$ đứng đằng sau số $2$ nên trước khi số $2$ đứng cuối $1$ lần nữa thì số $1$ sẽ đứng cuối trước số $2$ $1$ lần và di chuyển về vị trí $1$. Sau đó số $2$ sẽ đứng cuối $1$ lần nữa và di chuyển về vị trí $2$ trước vị trí $1$ mà số $1$ đang đứng, tức số $2$ đứng cuối nhiều nhất $2=2^1$ lần. Mệnh đề đúng với $x=1,2$, giả sử mệnh đề đúng với $x=k<n$. Xét số $k+1$ trong dãy số, nếu nó không đứng cuối lần nào thì ta có ngay điều phải chứng minh. Xét lần đứng cuối đầu tiên của $k+1$ và nó di chuyển về vị trí $k+1$, ta thấy rằng để nó có thể thay đổi vị trí của mình một lần nữa thì cần phải đến $1$ lúc nào đó có $1$ số $x<k+1$ đứng cuối rồi di chuyển về vị trí $x$ trước $k+1$ làm vị trí của $k+1$ tăng thêm $1$. Nghĩa là sau lần đứng cuối đầu tiên thì để $k+1$ đứng cuối $1$ lần nữa thì cần có $1$ số $x<k+1$ đứng cuối trước nó. Mỗi số $1$ đến $k$ tổng cộng đứng cuối nhiều nhất $2^0+2^1+...+2^{k-1}=2^k-1$ lần theo quy nạp và trước khi để $k+1$ đứng cuối lần nữa thì cần phải có $1$ số trong $k$ số đó đứng cuối trước nên số lần $k+1$ đứng cuối sau lần thứ nhất nhiều nhất $2^k-1$ lần. Vậy $k+1$ đứng cuối nhiều nhất $2^k$ lần. Bước chứng minh quy nạp hoàn tất. Ta thấy số bước bằng tổng số lần các số $1,2,...,n$ đứng cuối nên số bước nhiều nhất là $2^0+2^1+...+2^{n-1}=2^n-1<2^n$ lần


Bài viết đã được chỉnh sửa nội dung bởi JUV: 20-09-2016 - 21:48


#17
viet nam in my heart

viet nam in my heart

    Thượng sĩ

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

Bài 1 ngày 2:

Trước hết dễ chứng minh với $n$ là lũy thừa của $3$. Vì khi đó ta chọn $m=111...11$($n$ số 1)

Cần chứng minh $\dfrac{10^n-1}{9} \vdots n$ (áp dụng bổ đề $LTE$ cho ta điều phải chứng minh)

Với $n$ không là lũy thừa của $3$ ta thấy tồn tại số $x$ sao cho $3^{x}<n<3^{x+1}$

Khi đó ta sẽ chọn $S(m)=3^{x+1}$

Tức là chỉ ra tồn tại số $m$ có tổng các chữ số là $3^{x+1}$ và $m \vdots 3^{x+1}$

Nếu $n\leq2.3^x$

Đặt $n=3^x+t$

Ta sẽ chọn luôn $m=111...1333...3222...2$ trong đó gồm $t$ số $1$, $t$ số $2$ và $3^x-t$ số $3$

Ta chứng minh số này chia hết cho $3^{x+1}$

Sau khi biến đổi ta thu được $m=\dfrac{(10^t+2)(10^{3^{x}}-1)}{9} \vdots 3^{x+1} $ ( Dễ chứng minh theo bổ đề $LTE$)

Nếu $n>2.3^x$. 

Đặt $n=2.3^x+t$

Ta sẽ chọn $m=111...1222...21.....1$ thứ tự từ trái sang phải là gồm $3^x+t$ số $1$, $3^x-t$ số $2$ rồi lại $t$ số $1$

Ta chứng minh số này chia hết cho $3^{x+1}$

Sau khi biến đổi ta thu được $m=\dfrac{(10^{3^{x}+t}+10^t+1)(10^{3^{x}}-1)}{9} \vdots 3^{x+1} $ ( Dễ chứng minh theo bổ đề $LTE$)


"Nếu bạn hỏi một người giỏi trượt băng làm sao để thành công, anh ta sẽ nói với bạn: ngã, đứng dậy là thành công." Isaac Newton

VMF's Marathon Hình học Olympic


#18
Long Phi

Long Phi

    Binh nhất

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

Câu 4 ngày 2:

$VT = \sum \frac{1}{b^2c}.\frac{1}{1+\frac{1}{ca}}$

Ta thấy $f(x)= \frac{1}{1+x}$ là hàm lồi, áp dụng bđt Jensen ta có:

$VT \geq \sum \frac{1}{b^2c}.\frac{1}{1+ \frac{\sum \frac{1}{a^2b^2c}}{\sum \frac{1}{b^2c}}}=\sum \frac{1}{b^2c}.\frac{1}{1+\frac{3}{\sum a^2c}}\geq \sum \frac{a}{b}.\frac{1}{1+abc}$

Ta cần chứng minh $ \sum \frac{a}{b} \geq  \frac{9}{ab+bc+ac}$

Bđt trên đúng theo bđt C-S


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


#19
Long Phi

Long Phi

    Binh nhất

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

Bài 2 ngày 2: Sau mỗi bước sẽ có 1 tập vài quyển sách ở đúng vị trí, có tất cả $2^n$ tập, ta sẽ chứng minh không có 2 bước nào có 2 tập nào giống nhau

Quy ước lấy chiều từ trái sang phải

Ta thấy 1 quyển nếu chưa ở vị trí đúng thì sau khi bị di chuyển bởi quyển khác chỉ có thể sang phải, nếu đã ở vị trí đúng rồi thì sau đó không thế về vị trí nào trước vị trí đúng  

- Giả sử có 2 bước thứ $x$ và $y (x<y)$ có tập $a_1,...a_k$ trùng nhau

+ TH1: Nếu bước thứ $y$ chuyển quyển thứ $a_k$, vị trí đúng của $a_k$ không phải ở cuối

Các quyển ở sau $a_k$ sau bước thứ $x$ không thể có vị trí đúng là trước vị trí đúng của $a_k$ nếu không sẽ có 1 quyển được đưa về vị trí đúng trước bước thứ $y$, tạo ra 1 tập khác 

Vì các quyển sau $a_k$ có vị trí đúng sau $a_k$ nên sẽ di chuyển về vị trí đúng mà không ảnh hưởng tới các quyển khác, sau đó sẽ di chuyển quyển sai vị trí gần nhất trước $a_k$, nhưng lúc này không thể thay đổi vị trí $a_k$ và các quyển sau nữa.

+ TH2: bước thứ $y$ di chuyển quyển $a_i (i \neq k)$

Khi di chuyển $a_i$ nghĩa là tất cả các quyển sau $a_i$ đã đúng vị trí và khi di chuyển $a_i$ các quyển đó không đổi vị trí, suy ra các quyển đó đúng vị trí từ bước $x$, tuy nhiên khi điều đó có nghĩa tất cả các quyển từ $a_i$ trở đi đều không bị di chuyển, nên từ bước $x$ tới bước $y$ ta chỉ có thể di chuyển các quyển trước $a_i$, mâu thuẫn với việc quyển bị di chuyển là $a_i$



#20
JUV

JUV

    Trung sĩ

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

Bài 2 ngày 2: Sau mỗi bước sẽ có 1 tập vài quyển sách ở đúng vị trí, có tất cả $2^n$ tập, ta sẽ chứng minh không có 2 bước nào có 2 tập nào giống nhau

Quy ước lấy chiều từ trái sang phải

Ta thấy 1 quyển nếu chưa ở vị trí đúng thì sau khi bị di chuyển bởi quyển khác chỉ có thể sang phải, nếu đã ở vị trí đúng rồi thì sau đó không thế về vị trí nào trước vị trí đúng  

- Giả sử có 2 bước thứ $x$ và $y (x<y)$ có tập $a_1,...a_k$ trùng nhau

+ TH1: Nếu bước thứ $y$ chuyển quyển thứ $a_k$, vị trí đúng của $a_k$ không phải ở cuối

Các quyển ở sau $a_k$ sau bước thứ $x$ không thể có vị trí đúng là trước vị trí đúng của $a_k$ nếu không sẽ có 1 quyển được đưa về vị trí đúng trước bước thứ $y$, tạo ra 1 tập khác 

Vì các quyển sau $a_k$ có vị trí đúng sau $a_k$ nên sẽ di chuyển về vị trí đúng mà không ảnh hưởng tới các quyển khác, sau đó sẽ di chuyển quyển sai vị trí gần nhất trước $a_k$, nhưng lúc này không thể thay đổi vị trí $a_k$ và các quyển sau nữa.

+ TH2: bước thứ $y$ di chuyển quyển $a_i (i \neq k)$

Khi di chuyển $a_i$ nghĩa là tất cả các quyển sau $a_i$ đã đúng vị trí và khi di chuyển $a_i$ các quyển đó không đổi vị trí, suy ra các quyển đó đúng vị trí từ bước $x$, tuy nhiên khi điều đó có nghĩa tất cả các quyển từ $a_i$ trở đi đều không bị di chuyển, nên từ bước $x$ tới bước $y$ ta chỉ có thể di chuyển các quyển trước $a_i$, mâu thuẫn với việc quyển bị di chuyển là $a_i$

Đề bài cần chứng minh sau ít hơn $2^n$ lần chứ không phải nhiều nhất $2^n$ lần






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

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