Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


redfox nội dung

Có 97 mục bởi redfox (Tìm giới hạn từ 21-10-2015)



Sắp theo                Sắp xếp  

#698962 Đề cử Thành viên nổi bật 2017

Đã gửi bởi redfox on 26-12-2017 - 21:44 trong Thông báo tổng quan

1. Tên Nick ứng viên: vutuanhien

2. Thành tích (đóng góp) nổi bật: Là thành viên thảo luận sôi nổi trên nhiều topic Toán Đại cương




#698913 Tính số lớn nhất các cạnh không cân bằng.

Đã gửi bởi redfox on 25-12-2017 - 22:52 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Cho đồ thị có $n$ đỉnh. Ta gọi cạnh $(u,v)$ là cạnh không cân bằng nếu bậc của $u$ và $v$ khác nhau. Tính số lớn nhất các cạnh không cân bằng.




#698831 Bất đẳng thức với số nguyên dương

Đã gửi bởi redfox on 24-12-2017 - 15:26 trong Các bài toán và vấn đề về Bất đẳng thức

Cho $a\leq b\leq c$ nguyên dương. Chứng minh $\left \lfloor \frac{c}{a} \right \rfloor+1\geq \left \lfloor \frac{b-1}{a} \right \rfloor+\left \lfloor \frac{c}{b} \right \rfloor$




#696820 Đề thi chọn đội tuyển tp Đà Nẵng

Đã gửi bởi redfox on 19-11-2017 - 15:22 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.

Lời giải của bạn chưa chính xác. Phép quy nạp của bạn chỉ giúp chỉ ra là $n-1$ thỏa mãn chứ ko chứng minh nó lớn nhất.

Có thể chuyển điều kiện bài toán thành như thế này.

Tìm $k$ lớn nhất để mà 2 tập bất kì trong $k$ tập này thỏa mãn 3 điều kiện sau:

1) Không có tập nào là $S_n$

2) 2 tập này ko là phần bù của nhau

3) 2 tập này hoặc rời nhau hoặc là có tập này chứa tập kia

 

Vd tập các tập hợp này thỏa mãn $\left \{1 \right \},\left\{2 \right \},...,\left \{2016 \right \},\left \{2017 \right \},\left \{1,2 \right \},\left \{1,2,3 \right \},...,\left \{1,2,3,..,2015 \right \}$.

mình đã chứng minh $k_n \leq n-1$ rồi bạn.




#694593 chứng minh $\chi (G)\leq \Delta(G)$

Đã gửi bởi redfox on 11-10-2017 - 19:50 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

http://myweb.facstaf...kara/brooks.pdf brook's theorem nhé.




#694021 $P_1(x)=4x^{3}-3x;P_n(x)=P_1(P_{n-1}(x)) \foral...

Đã gửi bởi redfox on 01-10-2017 - 17:51 trong Các bài toán và vấn đề về Đa thức

Mình xin giải quyết 2 vấn đề trên như sau :

Trước tiên ta chứng minh bằng quy nạp rằng $P_n(x)> x,\forall x> 1$

  + Ta có $4x^3> 4x,\forall x> 1\Rightarrow P_1(x)=4x^3-3x> x,\forall x> 1$

  + Giả sử với $m\in\mathbb{N},m\geqslant 1$, ta có $P_m(x)> x,\forall x> 1$

     Khi đó ta có $4[P_m(x)]^2> 4P_m(x)\Rightarrow P_{m+1}(x)=4[P_m(x)]^2-3P_m(x)> P_m(x)> x,\forall x> 1$

  + Theo nguyên lý quy nạp, ta có $P_n(x)> x,\forall x> 1$

Cũng bằng quy nạp tương tự, ta chứng minh được $P_n(x)< x,\forall x< -1$

Vậy nếu phương trình $P_n(x)=x$ (*) có nghiệm thì nghiệm đó phải thuộc $[-1;1]$. Do đó ta đặt $x=\cos t$

Thực ra chỉ cần chỉ ra $3^n$ nghiệm phân biệt của $P_n(x)$ vì rõ ràng $degP_n(x)=3^n$




#693914 ĐĂNG KÍ LÀM ĐHV DIỄN ĐÀN TOÁN HỌC VMF

Đã gửi bởi redfox on 29-09-2017 - 18:32 trong Thông báo tổng quan

 1. Họ và tên:  Phan Quốc Vượng

 2. Sinh năm:  22/01/2001

 3. Nghề nghiệp:  Học sinh

 4. Địa chỉ Mail/ Số điện thoại liên lạc (nếu có ):  [email protected]

 5. Nick trên Diễn đàn:  redfox

 6. Vị trí muốn đăng kí:  ĐHV Olympic

 7. Ý kiến thêm : I'll try my best




#693740 Đề chọn đội tuyển quốc gia chuyên Quốc Học Huế ngày 2

Đã gửi bởi redfox on 26-09-2017 - 16:30 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âu4 Đáp án : $n^2/4$ . 

 

Thật vậy ta có nhận xét : Cứ 1 tập con đẹp thì mỗi ô vuông 2*2 đều bị tập con này lấy ít nhất 1 ô :)

Tổ hợp mà dễ thế này phải xem lại.

Coi bàn cờ là một đồ thị với các đỉnh là các ô vuông, hai đỉnh nối với nhau nếu hai ô vuông có cạnh chung. Có tất cả $n^2$ đỉnh và $2n(n-1)$ cạnh. Nếu ta bỏ các đỉnh thuộc $X$ thì thu được một đồ thị không chứa chu trình (vì không có chu trình nào không có đỉnh thuộc $X$). Gọi số đỉnh bị bỏ đi là $v$, số cạnh bị mất do bỏ đỉnh là $e$, vì mỗi đỉnh có bậc không quá $4$ nên $e\leq 4v$. Vì đồ thị thu được không có chu trình nên số đỉnh lớn hơn số cạnh suy ra $n^2-v> 2n(n-1)-e\geq 2n(n-1)-4v\Rightarrow v> \frac{n^2-2n}{3}$. Ta có $\lim_{n\rightarrow \infty }\frac{\frac{n^2-2n}{3}}{n^2}= \frac{1}{3}$ nên $C\geq \frac{1}{3}$.

Đánh số các hàng, cột từ $1$ đến $n$. Cột nào có số chia $3$ dư $2$ chọn các ô thuộc hàng chẵn, cột nào có số chia hết cho $3$ chọn các ô thuộc hàng lẻ.




#693653 Chứng minh rằng sau một số lần thực hiện quy tắc thì số 1 xuất hiện ở vị trí...

Đã gửi bởi redfox on 24-09-2017 - 19:35 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

(cách trên trừu tượng và khó hiểu quá!)

Ta sẽ chứng minh kết quả mạnh hơn: Các số nguyên dương phân biệt $2\leq a_1<...<a_k\leq n$ được sắp xếp trên hàng có $n$ ô và đổi chỗ như trên nếu ô đầu tiên là số, ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó (bài trên coi $1$ là ô trống). Ta quy nạp mạnh theo $n$:

$n=1$: trên hàng là ô trống (đúng)

Giả sử với mọi $m<n$ đúng, xét bảng có $n$ ô như trên:

Nếu $a_k< n$ thì $a_k$ ô đầu tiên có ít nhất một ô trống và cách đổi chỗ như trên chỉ ảnh hưởng đến $a_k$ ô đầu tiên. Vì $a_k$ đúng, ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó nên $n$ đúng

Nếu $a_k=n$, ta coi $n$ là ô trống. Khi đó lập luận tương tự như trên ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó. Nếu ô trống đó không phải là $n$ thì $n$ đúng. Nếu ô trống đó là $n$, cách đổi chỗ sẽ đưa $n$ xuống cuối. Cách đổi chỗ như trên sau đó chỉ ảnh hưởng đến $n-1$ ô đầu tiên và $n-1$ ô đầu tiên có ô trống. Vì $n-1$ đúng, ô trống sẽ xuất hiện ở ô đầu tiên lúc nào đó nên $n$ đúng.

(Q.E.D)




#693591 Đề thi chọn đội tuyển tp Đà Nẵng

Đã gửi bởi redfox on 23-09-2017 - 20:44 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 3 ngày 2: Tổng quát cho $n>1$. Đặt $S_i=\left \{ 1,...i \right \}$. Xét $k_n$ lớn nhất sao cho tồn tại $k_n$ tập con của $S_n$ thỏa mãn.

Ta có $S_1,...S_{n-1}$ thỏa mãn nên có thể giả sử $k_n\geq n-1$. Ta sẽ chứng minh $k_n=n-1$ bằng quy nạp

Với $n=2$ dễ có $k_2=1$

Với $n\geq 3$.Ta có $A_i\neq \varnothing ,S_{n}$. Ta có $A$ và $A'$ không xuất hiện cùng nhau trong $k$ tập trên và có thể thay $A$ bằng $A'$ trong $k_n$ tập trên mà vẫn thỏa mãn điều kiện, vậy ta có thể thay tất cả các tập không chứa $n$ như trên, vậy ta có thể giả sử $k_n$ tập trên đều chứa $n$. Nếu trong $k_n$ tập trên không chứa tập $\left \{ n \right \}$ thì ta vẫn có thể thêm tập đó vào mà vẫn thỏa mãn điều kiện, thu được $k_n+1$ tập thỏa mãn trái với cách chọn $k_n$. Vậy trong $k_n$ tập trên chứa $\left \{ n \right \}$. Bỏ tập $\left \{ n \right \}$ và bỏ phần tử $n$ trong các tập còn lại thu được $k_n-1$ tập con của $S_{n-1}$ thỏa mãn. Ta có$k_n-1\leq k_{n-1}= n-2\Rightarrow k_n\leq n-1$ (theo giả thiết quy nạp và cách chọn $k_{n-1}$). Từ trên ta có $k_n=n-1$.

Cụ thể với bài trên, $k= k_{2017}= 2016$.




#693564 Bài toán số 3 USA December TST 2016

Đã gửi bởi redfox on 23-09-2017 - 15:37 trong Các bài toán và vấn đề về Đa thức

Thêm điều kiện $P,Q$ khác hằng nữa.

Chữ thường là số thực, chữ in hoa là đa thức, $P^{(i)}$ là đạo hàm cấp $i$, $(A,B)$ là ước đa thức monic có bậc lớn nhất của $A,B$

Bổ đề: Nếu $ab\neq cd\Rightarrow max(deg(aP+cQ),deg(bP+dQ))= max(P,Q)$. Đặt $n= max(P,Q)$ ta có vế trái rõ ràng không lớn hơn $n$. Xét hệ số của $x^n$ trong hai đa thức $aP+cQ,bP+dQ$ sẽ có một đa thức có hệ số khác $0$ dễ có vế trái bằng $n$.

Giả sử tồn tại ba số thực phân biệt $\lambda _1,\lambda _2,\lambda _3,P+\lambda _iQ= R_i^2$. Theo bổ đề trên, tồn tại $R_i^2$ có bậc bằng $max(P,Q)$ giả sử là $R_1^2$. Ta đặt $\lambda = \frac{\lambda _1-\lambda _2}{\lambda _1-\lambda _3},A= R_1-R_2,B= R_1+R_2,C= R_1-R_3,D= R_1+R_3$, khi đó $A+B=C+D=2R_1,AB= \lambda CD,\lambda \neq 1,(A,B)=(C,D)=1$ và $AB$ có bậc bằng $max(P,Q)$. Đặt $P_{AC}= (A,C),P_{AD}= (A,D),P_{BC}= (B,C),P_{BD}= (B,D)$, ta có các đa thức trên nguyên tố cùng nhau. Giả sử $x_0$ là nghiệm bội $n$ của $A$ thì nó cũng là nghiệm bội $n$ của duy nhất một trong hai đa thức $P_{AC},P_{AD}$ hay cũng là nghiệm bội $n$ của đa thức $P_{AC}P_{AD}$,tương tự ta cũng dễ có điều ngược lại, vậy $A= aP_{AC}P_{AD}$ với $a$ là hằng số nào đó. Tương tự $B= bP_{BD}P_{BC},C= cP_{AC}P_{BC},D= dP_{AD}P_{BD}$. Ta có $A-C=D-B$. Giả sử $x_0$ là nghiệm bội $n$ của $P_{AC}P_{BD}$ thì nó cũng là nghiệm bội $n$ của một trong hai đa thức $P_{AC},P_{BD}$ nên là nghiệm bội ít nhất $n$ của đa thức $A-C$. Giả sử $x_0$ là nghiệm bội $n$ của $A-C$ thì nó là nghiệm của nhiều nhất một trong hai đa thức $P_{AC},P_{BD}$, giả sử $P_{BD}$ không có nghiệm $x_0$ và  $x_0$ nghiệm bội $m$ (có thẻ bằng $0$) của $P_{AC}$. Giả sử $m<n$. Ta đạo hàm $A-C=D-B$ từ $0$ đến $m+1$ lần, thay $x=x_0$ ta có $A^{(i)}=C^{(i)}=0,\forall 0\leq i\leq m,A^{(m+1)}=C^{(m+1)}\neq 0,B=D\neq 0$, đạo hàm $AB= \lambda CD$ $m+1$ lần, thay $x=x_0$ ta có $A^{(m+1)}B= \lambda C^{(m+1)} D$, dễ có vô lý, vậy $m\geq n$, từ đây ta có: $A-C=B-D=\alpha P_{AC}P_{BD}\Rightarrow aP_{AD}-bP_{BC}= \alpha P_{BD},dP_{AD}-bP_{BC}= \alpha P_{AC}$. Thay $P_{AC},P_{BD}$ ta có $AB= \frac{ab}{\alpha ^2}P_{AD}P_{CD}(aP_{AD}-cP_{BC})(dP_{AD}-bP_{BC}),2R_1=\frac{1}{\alpha }(adP_{AD}-bc P_{BC})$. Áp dụng bổ đề ta có $max(degP_{AD},degP_{BC})\geq 2degR_1\geq degQ= degAB\geq degP_{AD}+degP_{BC}+max (degP_{AD},degP_{BC})\Rightarrow degP_{AD}=degP_{BC}=0$, từ đây ta có $R_1,Q$ là đa thức hằng nên $P$ cũng là đa thức hằng (vô lý). Vậy tồn tại nhiều nhất hai số thỏa mãn điều kiện đề bài,

(Q.E.D)




#693546 Đề thi chọn đội tuyển trường PTNK 2017

Đã gửi bởi redfox on 23-09-2017 - 11:45 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 3 ngày hai: Bình thắng: https://www.facebook...55883327818168/




#693433 $n^2+1$ là số nguyên tố

Đã gửi bởi redfox on 20-09-2017 - 20:30 trong Các bài toán và vấn đề về Số học

Chứng minh rằng phương trình $a+2b=n,ab=\binom{c}{2}, n\in \mathbb{N}$ không có nghiệm nguyên dương $a,b,c$ khi và chỉ khi $n^2+1$ là số nguyên tố.




#693426 $P_n\leq 6,75^n$

Đã gửi bởi redfox on 20-09-2017 - 19:08 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Welcome back, unknown!

Bổ đề: $C_n=\binom{3n}{n}<6,75^n, \forall n\in \mathbb{N}$. $n=1$ đúng và $\frac{C_n}{C_{n-1}}=\frac{3(3n-1)(3n-2)}{2n(2n-1)}<\frac{27}{4}$

Xét tập hợp $D_n$ gồm $3(n-1)$ phần tử $l_2,l_3,...,l_n,u_2,u_3,...,u_n,r_2,r_3,...,r_n$

Xét thuật toán: Với mỗi $n$-mino, xét ô dưới cùng bên trái, đặt số $1$ và một vector hướng lên, đánh dấu ô $1$ chuyển sang bước $1$. Ở bước $i$, từ ô được đặt số $k$ và vector nào đó được đánh dấu ($k$ nhỏ nhất trong các ô được đánh dấu), xét các ô vuông kề với nó và chưa được đặt số, nếu có một ô vuông bên trái (hoặc bên trên, bên phải) ta chọn phần tử $l_k$ (hoặc $u_k, r_k$), đặt các số nguyên tiếp theo vào các ô kề với ô $k$ và chưa được đặt số theo thứ tự trái, trên, phải theo chiều vector của ô $k$, và đặt các vector vào các ô kề với ô $k$ theo hướng từ ô $k$ đến ô đó, sau đó bỏ đánh dấu ô $k$. Sau khi hết ô được đánh dấu, đánh dấu các ô đã được đặt số ở bước $i$ và chuyển sang bước $i+1$ nếu còn ô chưa được điền số. Sau hữu hạn bước (vì $n$-mino liên thông và hữu hạn ô vuông) thì ta chọn được $n-1$ phần tử của $D_n$ (chọn thêm được một phần tử thì thêm một ô được đặt số.

Ta sẽ chứng minh với hai $n$-mino khác nhau ta thu được hai bộ $n-1$ phần tử khác nhau.

Với $n=2$ đúng

Giả sử $n$ đúng. Xét hai $n+1$-mino có cùng một bộ $n$ phần tử của $D_{n+1}$. Xét ô thứ $n+1$ tương ứng với một phần tử $l_n$ hoặc $u_n, r_n$ nào đó, loại ô và phần tử đó đi trong bộ $n$ phần tử ta thu được hai $n$-mino có cùng một bộ $n-1$ phần tử của $D_n$, theo giả thiết quy nạp, hai $n$-mino đó giống nhau, gọi là $n$-mino chung. Chú ý phần tử được loại tương ứng với vị trí của ô thứ $n+1$ so với $n$-mino chung nên vị trí của ô $n+1$ với $n$-mino chung của hai $n+1$-mino chung giống nhau nên hai $n+1$-mino giống nhau.

Vậy ta thu được đơn ánh từ các $n$-mino đến cách chọn $n-1$ phần tử từ $D_n$. Vậy $D_n \leq C_{n-1} <6,75^n$.

Q.E.D

(seem too hard!)




#693103 Có tồn tại hình $A$ hay không?

Đã gửi bởi redfox on 15-09-2017 - 21:16 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Bài 1: Không. Ta sẽ chứng minh chu vi $A$ không nhỏ hơn $B$. Ta có thể giả sử $A$ là hình lồi (chu vi bao lồi của $A$ không lớn hơn $A$ và bao lồi của $A$ chứa $B$). Ta chia đường biên của $B$ thành $n$ cung bằng nhau bởi các điểm $B_1,...,B_n$ theo chiều kim đồng hồ, các điểm này tạo thành đa giác lồi $P$. Từ hai điểm $B_i,B_{i+1}$ kẻ hai tia vuông góc với cạnh $B_iB_{i+1}$ và nằm phía ngoài $P$ cắt $A$ tại cung $A_i$. Vì đa giác $P$ và $A$ lồi nên các cung không giao nhau hoặc giao nhau tại một điểm. Ta có chiều dài cung $A_i$ không nhỏ hơn chiều dài cạnh $B_iB_{i+1}$ (đường ngắn nhất nối hai điểm phân biệt là đoạn thẳng, $B_iB_{i+1}$ là khoảng cách giữa hai tia trong cách dựng cung $A_i$ trên). Cho $n$ đến vô cùng ta có đpcm.

Bài 2: Không. Xét cạnh nối hai điểm tùy ý trong $B$ và mặt phẳng qua hai điểm đó, cạnh đó nằm trong tiết diện của mặt phẳng đó với $B$ nên nằm trong $B$, vậy khối $B$ lồi. Sau đó chia bề mặt của $B$ bằng các mặt phẳng cách đều nhau song song với mỗi cặp hai trục tọa độ. Sau đó chiếu như CM trên.

(mình không chắc chắn lắm về lời giải.)




#692183 $\sum_{n=2}^m a_2a_3...a_n<1$

Đã gửi bởi redfox on 03-09-2017 - 09:06 trong Các bài toán và vấn đề về Số học

Định nghĩa: $\sum_{p\in \mathbb{P}},\prod_{p\in \mathbb{P}}$ là tổng, tích lấy trên tất cả các số nguyên tố.

Một số đánh giá: $\sum_{p\in \mathbb{P}}\frac{1}{p^2}<\sum_{k=4}^{\infty }\frac{1}{k^2}<\sum_{k=3}^{\infty }\frac{1}{k\left ( k+1 \right )}=\frac{1}{3}$

$\frac{n}{n-1}\leq \frac{3}{2},\forall n\geq 3$

Áp dụng AM-GM: $\prod_{k=2}^{n}a_k\leq \left ( \frac{\sum_{k=2}^{n}a_k}{n-1} \right )^{n-1}=\left ( \frac{\sum_{p\in P}\frac{\left \lfloor \frac{n}{p} \right \rfloor}{p}}{n-1} \right )^{n-1}\leq \left (\frac{n}{n-1} \sum_{p\in P}\frac{1}{p^2} \right )^{n-1}<\left ( \frac{1}{2} \right )^{n-1},\forall n\geq 3$

(chú ý rằng $\left \lfloor \frac{n}{p} \right \rfloor$ là số các số nguyên từ $2$ đến $n$ chia hết cho $p$, cũng là số lần xuất hiện của số hạng $\frac{1}{p}$

Vậy: $\sum_{n=2}^{\infty }\prod_{k=2}^{n}a_k<\frac{1}{2}+\sum_{n=3}^{\infty }\left ( \frac{1}{2} \right )^{n-1}=1$

(Q.E,D)




#692051 Có tồn tại vô hạn số tự nhiên q thỏa mãn $\left[\alpha q^2...

Đã gửi bởi redfox on 01-09-2017 - 17:25 trong Các bài toán và vấn đề về Số học

Câu trả lời là có. Viết $\alpha =\left [ x_0;x_1,x_2... \right ]$ (liên phân số vô hạn). Xét dãy $p_{-2}=0,p_{-1}=1,p_n=x_np_{n-1}+p_{n-2},q_{-2}=1,q_{-1}=0,q_n=x_nq_{n-1}+q_{n-2}$. Khi đó $0<\alpha -\frac{p_{2k}}{q_{2k}}<\frac{1}{q_{2k}^2}\Rightarrow p_{2k}q_{2k}<\alpha q_{2k}^2<p_{2k}q_{2k}+1\Rightarrow \left \lfloor \alpha q_{2k}^2 \right \rfloor=p_{2k}q_{2k}$ (chứng minh chi tiết epsilon 4 p25-36)




#691418 Chứng minh tập $\mathbb{N^*}\setminus P $ là tậ...

Đã gửi bởi redfox on 24-08-2017 - 17:52 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Theo mình nghĩ ii) là $\forall q\in N,q>1,\exists c\in P,c\not\equiv 0(mod\; q)$ (nếu ii) như trên thử xét $P= \left \{ 4,6,8,...,2k,... \right \}$, và lấy $c= 4q+2$)

Để ý nếu $a,b\in P\Rightarrow ax+by\in P,\forall x,y\in N$ (theo i)). Áp dụng Sylvester ta có nếu $a,b\in P,gcd(a,b)=d\Rightarrow xd\in P,\forall x\in N,x\geq \frac{(a-d)(b-d)}{d^2}$. (*)

Gọi $d=min(gcd(a,b)|a,b\in P)$ theo (*) tồn tại $X$ sao cho $dx\in P,\forall x\in N,x\geq X$.

Giả sử $d>1$. Theo ii) lấy $p=d$ ta có tồn tại $c\in P$ không chia hết cho $d$. Đặt $d'=gcd(c,d)< d$. Lấy $x=cy+1\geq X$ ta có $xd,c\in P,gcd(xd,c)=gcd(cyd+d,c)=d'<d$ (trái với cách chọn $d$. Vậy $d=1$, theo (*) ta dễ có $N/P$ hữu hạn.

(Q.E.D)




#691098 Hãy xác định số phần tử của tập $\bigcup_{i=1}^{n...

Đã gửi bởi redfox on 20-08-2017 - 10:42 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Lỗi sai:  Ở redfox thì chỗ suy ra k+1 là sai.

Áp dụng Dirichlet cho $k$ phần tử của $A_1$ và  $n-1\geq k^2-k+1$ tập hợp $A_2,..,A_n$, tồn tại phần tử $x$ thuộc ít nhất $k$ tập hợp trong $A_2,...,A_n$, tính thêm $A_1$ nữa là $k+1$ tập hợp, tồn tại phần tử $x$ thuộc ít nhất $k+1$ tập hợp, gọi là $B_1,...,B_{k+1}$

Giả sử tồn tại $x\notin A_i$, xét các phần tử $A_i\cap B_j=\left \{ y_j \right \}$, giả sử tồn tại $y_j,y_l$ trùng nhau, khi đó $B_j\cap B_l=\left \{ y_j,x \right \}$(vô lý). Vậy các phần tử $y_1,...,y_{k+1}$ phân biệt, ta có $\left \{ y_1,...,y_{k+1} \right \}\subset A_i$ mà $\left | A_i \right |=k$ (vô lý).

Vậy $x\in A_i,\forall 1\leq i\leq n$ rồi tính được $\left | \bigcup_{i=1}^{n}A_i \right |=nk-k+1$.

(ở trên mình làm hơi tắt, mong các bạn thông cảm, không biết dưới này rõ ràng hơn chưa?)




#688186 58th IMO 2017

Đã gửi bởi redfox on 20-07-2017 - 20:21 trong Thi HSG Quốc gia và Quốc tế

Câu 6: Ta coi $gcd(0,1)=1$. Gọi các điểm của $S$ là $(x_1,y_1),...,(x_k,y_k)$.

1: $gcd(a_n,x_1...x_k)=1$ nếu tồn tại đa thức thỏa mãn (chú ý $a_ny^n\equiv 1(mod\; x_i)$).

2: Có thể coi $n\geq k$ và $a_n=1$.

Ta có đa thức $P$ thỏa mãn đề bài thì $P^p$ ($p$ nguyên dương) cũng thỏa hay $n$ thỏa mãn thì $pn$ cũng thỏa, ta chọn $p$ đủ lớn sao cho $pn\geq k$

Ta có đa thức $P$ có bậc $n\geq k$ thỏa mãn đề bài thì $P^p-qy^{pn-k}(x_1y-y_1x)...(x_ky-y_kx)$ ($p,q$ nguyên dương) cũng thỏa. Hệ số của $y^{np}$ là $a_n^p-qx_1...x_k$. Theo 1 và định lí Euler, tồn tại $p,q$ sao cho hệ số trên bằng $1$.

3: Có thể coi $(0,1)\in S$.

Ta có đa thức $P(x,y)$ thỏa mãn với $S$ khi và chỉ khi đa thức $P(x+y,y)$ thỏa mãn với $S'=\left \{(x_1-y_1,y_1);...;(x_n-y_n,y_n) \right \}$, các cặp số của $S'$ vẫn gồm các điểm nguyên thủy phân biệt. Bằng cách làm bước trên, thay đổi vai trò của $x,y$ và áp dụng thuật toán Euclid, ta có thể đưa $(x_1,y_1)$ về $(0,1)$.

Ta sẽ chứng minh bằng quy nạp với $k$:

$k=1$ dễ tồn tại đa thức thỏa mãn (định lý Bezout).

Giả sử $k-1$ đúng, áp dụng 3, ta coi $(0,1)\in S$. Theo giả thiết quy nạp, tồn tại đa thức $P$ thỏa mãn với $k-1$ cặp số còn lại. Áp dụng 2, ta coi hệ số $y^n$ bằng $1$, dễ thấy đa thức này cũng đúng cho $(0,1)$ hay cho $S$.

(Q.E.D)




#686474 Đề OLYMPIC GẶP GỠ TOÁN HỌC 2017 KHỐI 12

Đã gửi bởi redfox on 04-07-2017 - 16:12 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 4: Dễ thấy một người có ít nhất $2$ người quen.

Lấy một người $A$ bất kì. Gọi tập các cặp hai người quen với $A$ là $X$, các người không quen với $A$ là $Y$. Xét ánh xạ $f:X\rightarrow Y$ như sau:

Xét cặp $(B,C)$ quen $A$, ta có $B,C$ không quen nhau (i) nên tồn tại đúng một người $D$ khác $A$ quen $B,C$ (ii). Ta lấy $f(B,C)=D$

Ta có $D$ không quen $A$ (i) nên $A,D$ có đúng $2$ người quen chung (ii) chính là $B,C$, vậy chỉ có một cặp $(B,C)$ sao cho $f(B,C)=D$ nên $f$ là đơn ánh.

Xét $D$ bất kì không quen $A$, $A,D$ có đúng $2$ người quen chung (ii), ta gọi là $(B,C)$, dễ thấy $f(B,C)=D$ nên $f$ là toàn ánh.

Vậy $f$ là song ánh nên $X$=$Y$. Gọi số người quen $A$ là $k$, ta có $\left | Y \right |=\left | X \right |=\frac{k(k-1)}{2}\Rightarrow n=\left | Y \right |+k+1= \frac{k^2+k+2}{2}\Rightarrow 8n-7=(2k+1)^2$.

(Q.E.D)

Từ công thức trên và $n>4$ ta có $k\geq 3$.

Với $k=3$ ta có $n=7$, mỗi người quen đúng $3$ người khác nên số cặp quen nhau là $\frac{3.7}{2}=11,5$ (vô lý).

Với $k=4$, ta có $n=11$, giả sử người $1$ quen $2,3,4,5$, không quen $6,7,8,9,10,11$. Giả sử $f^{-1}(6)=(2,3)$. Vì $6$ quen $k=4$ người và không quen $1,4,5$ nên $6$ quen $2$ người trong $7,8,9,10,11$. Những người quen $2$ hoặc $3$ không quen với $6$ (i), vậy chỉ có duy nhất một người $f(4,5)$ có thể quen $6$ (vô lý vì $6$ quen $2$ người).

Với $k=5$, ta có $n=16$, ví dụ: người $1$ quen $2,3,4,5,6$, không quen $7,8,9,10,11,12,13,14,15,16$. Gán mỗi người không quen $1$ bất kì cặp $(a,b)$, người đó sẽ quen $1,a,b$ và những người được gán cặp $(c,d)$ ($c,d$ đều khác $a,b$). Vậy $n=16$.




#686021 Chứng minh rằng tồn tại nửa hình tròn chứa đủ các số 1;2;3...;n.

Đã gửi bởi redfox on 30-06-2017 - 16:07 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Bỏ qua TH hiển nhiên tồn tại nửa đường tròn chứa toàn quạt đỏ (hoặc quạt xanh).

Xét $2n$ nửa đường tròn $H_1,...H_{2n}$, $H_{k+1}$ được tạo bằng cách quay $H_k$ theo tâm đường tròn góc $\frac{\pi }{n}$ theo chiều kim đồng hồ. Gọi $Đ_k,X_k$ lần lượt là các số được ghi trên quạt đỏ và quạt xanh đầu tiên trên $H_k$ (thứ tự các quạt theo chiều kim đồng hồ).

Bổ đề: Nếu $d_k=Đ_k-X_k\equiv 1(mod\; n)$ thì quạt $H_k$ chứa đủ các số $1,...,n$

Giả sử $H_k$ chứa $x$ quạt đỏ, $n-x$ quạt xanh. Các số được ghi trên các quạt đỏ đồng dư theo mod $n$ với các số $Đ_k+i=X_k+i+1,0\leq i\leq x-1$, các số được ghi trên các quạt xanh đồng dư theo mod $n$ với các số $X_k-j,0\leq j\leq n-x-1$. Dễ thấy các số được ghi trên các quạt đỏ (quạt xanh) phân biệt. Giả sử tồn tại một số được ghi trên một quạt đỏ và một quạt xanh nào đó suy ra tồn tại $0\leq i\leq x-1,0\leq j\leq n-x-1$ sao cho $X_k+i+1\equiv X_k-j(mod\; n)\Rightarrow i+j+1\equiv 0(mod\; n)$ (vô lý vì $0<i+j+1<n$). Vậy các số ghi trên $H_k$ lập thành hệ thặng dư đầy đủ mod $n$ nên chứa đủ các số $1,...,n$.

Ta xét hai trường hợp: (coi $d_{2n+1}=d_1$)

TH1: Quạt đầu tiên trên $H_k$ màu đỏ, khi đó $Đ_{k+1}\equiv Đ_k+1(mod\; n),X_{k+1}=X_k\Rightarrow d_{k+1}\equiv d_k+1(mod\; n)$

TH2: Quạt đầu tiên trên $H_k$ màu xanh, khi đó $X_{k+1}\equiv X_k-1(mod\; n),Đ_{k+1}=Đ_k\Rightarrow d_{k+1}\equiv d_k+1(mod\; n)$

Vậy $d_{k+1}\equiv d_k+1,\forall 1\leq k\leq 2n$. Dễ thấy $d_1,...,d_n$ lập thành hệ thặng dư đầy đủ mod $n$ nên tồn tại $d_k\equiv 1(mod\; n)$, nửa đường tròn $H_k$ thỏa mãn đề bài.

(Q.E.D)

Có đúng $2$ nửa đường tròn thỏa mãn.




#685997 Xác định số các hoán vị $\left \{a_{1}, a_...

Đã gửi bởi redfox on 30-06-2017 - 10:04 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Đặt $n=2017$. Gọi $S_n$ là số hoán vị thỏa mãn đề. Ta sẽ chứng minh với $n\geq 3$, $S_n=3.2^{n-2}$.

Với $n=3$, dễ thử.

Giả sử $n-1$ đúng. Xét một hoán vị với $n\geq 4$ thỏa mãn. Ta có:

$n-1|2\left ( a_1+a_2+...+a_{n-1} \right )=2(1+2+...+n-a_n)=n(n+1)-2a_n=(n-1)(n+2)-2(a_n-1)\Rightarrow n-1|2 (a_n-1)$

$n-2|2(a_1+a_2+...+a_{n-2})=(n-2)(n+3)+2(3-a_{n-1}-a_n)\Rightarrow n-2|2(a_{n-1}+a_n-3)$

TH1:$n-1$ lẻ suy ra $a_n=1,n$

TH2:$n-1$ chẵn, giả sử $a_n=\frac{n+1}{2}$. Ta có $n-2$ lẻ và $0<\frac{n-3}{2}\leq a_{n-1}+a_n-3\leq \frac{3n-5}{2}<2(n-2)$ suy ra $a_{n-1}+a_n-3=n-2\Rightarrow a_{n-1}=a_n=\frac{n+1}{2}$(vô lý). Vậy $a_n=1,n$

THa:$a_n=n$. Ta thấy các số $a_1,...,a_{n-1}$ là hoán vị của $1,...,n-1$. Theo giả thiết quy nạp, số cách chọn là $S_{n-1}$

THb:$a_n=1$. Ta thấy các số $(a_1-1),...,(a_{n-1}-1$ là hoán vị của $1,...,n-1$. Theo giả thiết quy nạp, số cách chọn là $S_{n-1}$

Vậy $S_n=2S_{n-1}=3.2^{n-2}$, bài toán được chứng minh. Vậy $S_{2017}=3.2^{2015}$




#684726 Giải pt nghiệm nguyên dương: $x^n-1=\sum_{k=1}^{m...

Đã gửi bởi redfox on 16-06-2017 - 19:49 trong Các bài toán và vấn đề về Số học

Cho $n\geq 2,m$ nguyên dương, $d_1,d_2,...,d_m$ là các ước nguyên dương của $n$, nhỏ hơn $n$ (không nhất thiết phân biệt). Giải pt nghiệm nguyên dương: $x^n-1=\sum_{k=1}^{m}\frac{x^n-1}{x^{d_k}-1}+x-1$




#684338 C/m: $max (n)\leq [k!e]-1$

Đã gửi bởi redfox on 13-06-2017 - 14:21 trong Các bài toán và vấn đề về Tổ hợp và rời rạc

Bổ đề: $\left \lceil \frac{\left \lfloor k!e \right \rfloor}{k} \right \rceil=\left \lfloor \left ( k-1 \right )!e \right \rfloor+1$ (có thể chứng minh nhờ công thức: $e=\sum_{k=1}^{\infty }\frac{1}{k!}$).

Ta định nghĩa: $A-B=\left \{ a-b|a\in A,b\in B,a>b \right \}$. Để ý rằng $A\subset C,B\subset D\Rightarrow A-B\subset C-D$.

Ta sẽ chứng minh nếu tập $N\subset \mathbb{Z}^+$ có tập con $M$ thỏa mãn $\left | M \right |\geq \left \lfloor k!e \right \rfloor,M-M\subset N$ thì không tồn tại cách phân hoạch thỏa mãn đề. Ta chứng minh bằng quy nạp theo $k$.

Với $k=1$, dễ dàng chứng minh bài toán đúng.

Giả sử $k-1$ đúng, xét phân hoạch $N$ thành $k$ tập hợp $A_1,A_2,...,A_k$. Theo Dirichlet, tồn tại $A_i$ sao cho $\left | A_i\cap M \right |\geq \left \lceil \frac{\left | M \right |}{k} \right \rceil\geq \left \lfloor \left ( k-1 \right )!e \right \rfloor+1$. Gọi $x$ là phần tử lớn nhất của $A_i\cap M$. Đặt $M'=\left \{ x \right \}-A_i\cap M$, ta có $\left | M' \right |\geq \left \lfloor \left ( k-1 \right )!e \right \rfloor$. Dễ thấy $M',M'-M'\subset A_i\cap M-A_i\cap M\subset M-M\subset N;M',M'-M'\subset A_i-A_i$

TH1: $M'\cap A_i\neq \varnothing$ hoặc $\left ( M'-M' \right )\cap A_i\neq \varnothing$, ta chọn được ba số trong $A_i$, một số bằng tổng hai số còn lại nên cách phân hoạch này không thỏa mãn.

TH2: $M',M'-M'\subset N'=N/A_i$, áp dụng bài toán với $k-1,N',M'$ với cách phân hoạch $N'$ thành $k-1$ tập hợp $A_1,A_2,...,A_k$ (trừ $A_i$), cách phân hoạch này không thỏa mãn với $N'$ nên cách phân hoạch $N$ thành $k$ tập hợp $A_1,A_2,...,A_k$ như trên cũng không thỏa mãn đề.

Áp dụng bài toán với $N=M=\left \{ 1,2,..,n \right \},n\geq \left \lfloor k!e \right \rfloor$ ta thấy không tồn tại cách phân hoạch thỏa mãn, vậy $n\leq \left \lfloor k!e \right \rfloor-1$.

(Q.E.D)