redfox

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

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.

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$

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

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

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)

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

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!)

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

Đị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)

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)

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)

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)

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

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.