Trong trường hợp $n=1,2$ thấy có vẻ nó ko thỏa bài nhỉ (còn hơi lúng túng chỗ này).

 

Gọi $A_i$ với $i =\overline{1,n}$ là tập hợp các hoán vị thõa mãn tính chất: có cặp $i$ và $n+i$ đứng cạnh nhau trong hoán vị đó.

Dễ thấy trong một hoán vị thì số tính chất thõa mãn trên không quá $\left [  \frac{n}{2} \right ]$. Nên theo nguyên lý bù trừ có số tính chất P :

$\left |\bigcap_{i=1}^{n} A_i \right | = \sum_{I=\left \{i_1,i_2,...,i_k \right \} \\ I \subset \left \{1,2,...,n \right \}  } (-1)^{|I|+1} \left |\bigcup_{j=1}^{k} A_{i_{j}} \right |$ . Dễ dàng tính được $\left |\bigcup_{j=1}^{k} A_{i_{j}} \right | = 2^k(n-k)!\binom{2n-2k}{n-2k} $ kết hợp với tính đối xứng của các tính chất. Suy ra $\left |\bigcap_{i=1}^{n} A_i \right | = \sum_{k=1}^{\left [  \frac{n}{2} \right ]} (-1)^{k+1} 2^k(n-k)!\binom{n}{k}\binom{2n-2k}{n-2k} $

Từ đây ta sử dụng quy nạp để chứng minh nó lớn hơn $\frac{2n!}{2.n!}$. Suy ra điều phải chứng minh với $n>2$.

 

Lời giải còn hơi mơ hồ . Ai có cách khác ko

Xét ánh xạ từ các hoán vị không có tính chất $P$ đến các hoán vị có tính chất $P$: $f\left ( x_1,x_2,...,x_n \right )=\left ( x_2,...,x_{k-1},x_1,x_k,...,x_{2n} \right )$ với $x_k$ thỏa $\left | x_1-x_k \right |=n$ (dễ thấy $\left | x_{k-1}-x_1 \right |\neq n$. Giả sử $f\left ( x_1,x_2,...,x_{2n} \right )= \left ( z_1,z_2,...,z_{2n} \right )$, xét chỉ số $i>1$ thỏa $\left | z_i-z_{i+1} \right |=n$ (có một chỉ số duy nhất), ta xác định được ngay bộ $\left ( x_1,x_2,...,x_n \right)$: $x_1=z_i,k=i+1,x_l=z_l\left ( l\geq k \right ),x_l=z_{l+1}\left ( l<k-1 \right )$, vậy đây là đơn ánh. Xét hoán vị $\left ( 1,n+1,... \right )$, ta thấy nó không là ảnh của hoán vị không có tính chất $P$. Vậy đây là đơn ánh, không phải là toàn ánh. Vậy số hoán vị có tính chất $P$ nhiều hơn.

(Q.E.D)

Nếu $\left ( p;q \right )=1$ thì đúng vậy.

Xét dãy các bước đi là $\vec{v}_1,\vec{v}_2,...,\vec{v}_{p+q}$ và các điểm nguyên trên đường đi trừ $\left ( p,q \right )$ là $A_1,A_2,...,A_{p+q}$.

Với đường đi bất kì và số $1< k\leq p+q$, ta hoán vị các bước đi thành $\vec{v}_k,\vec{v}_{k+1},...,\vec{v}_{p+q},\vec{v}_1,\vec{v}_2,...,\vec{v}_{k-1}$ và hoán vị tên các điểm nguyên một cách tương tự, ta được một đường đi mới. Làm như vậy ta được $p+q$ đường đi khác nhau (vì $\left ( p;q \right )=1$). Trên đường đi đó, xét các đường thẳng đi lần lượt qua các điểm $A_1,A_2,...,A_{p+q}$ và song song với $qx-py=0$. Vì $\left ( p;q \right )=1$ nên các đường thẳng đó phân biệt, xét đường thẳng nằm cao nhất (tức là đường thẳng $qx-py+k=0$ có $k$ lớn nhất) đi qua $A_i$. Ta để ý sau khi hoán vị các bước đi và tên các điểm, đường thẳng đi qua $A_i$ vẫn nằm cao nhất. Vậy trong $p+q$ đường đi đó, chỉ có một đường đi thỏa mãn đề bài là đường đi có điểm $\left ( 0,0 \right )$ có tên là $A_i$. Ta có $\frac{1}{p+q} \binom{p}{p+q}$ bộ $p+q$ đường đi nên có $\frac{1}{p+q} \binom{p}{p+q}$ đường đi thỏa mãn đề bài.

Có lời giải trong TH $\left ( p;q \right )\neq 1$ không?

Nhận xét với số nguyên dương $1\leq q\leq n$, có nhiều nhất một số nguyên dương $p$ thỏa mãn $\frac{p}{q}$ nằm trong khoảng này. Giờ xét các số $q,2q,...,2^kq$ ($q$ lẻ, $k$ lớn nhất sao cho $2^kq\leq n$). Giả sử tồn tại số lớn nhất sao trong các số đó sao cho tồn tại phân số tối giản nhận nó làm mẫu số nằm trong khoảng này là $2^lq$. Gọi phân số đó là $\frac{p}{2^lq}$. Ta có với số nguyên dương $l< x\leq k$, $\frac{p}{2^lq}=\frac{p2^{x-l}}{2^xq}$ thuộc khoảng này. Theo như nhận xét trên, $p2^{x-l}$ là số nguyên dương duy nhất sao cho phân số có mẫu số $2^xq$ nhận nó làm tử số thuộc khoảng này, mà phân số này không tối giản. Vậy trong các phân số nhận một trong các số trên là mẫu số, tồn tại nhiều nhất một phân số nằm trong khoảng này.

Để ý có $\frac{n+1}{2}$ hoặc $\frac{n}{2}$ số lẻ nằm giữa $1$ và $n$, thay $q$ lần lượt bằng một trong các số trên, ta có nhiều nhất $\frac{n+1}{2}$ số thỏa mãn.

(Q.E.D)

Từ đề bài ta có $\left | A_i\cap A_j \right |=1$. Xét các phần tử thuộc $A_1$, theo Dirichlet tồn tại phần tử $x$ thuộc ít nhất $k+1$ tập hợp (gồm $A_1$).

Giả sử tồn tại $i$ sao cho $x\notin A_i$. Khi đó xét giao của $A_i$ với các tập hợp chứa $x$, ta được ít nhất $k+1$ phần tử khác $x$ thuộc $A_i$. Dễ thấy các phần tử đó đều phân biệt (vô lý).

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

(câu b) có lẽ là $\left | A_i\cup A_j \right |=2k-1$).

http://www.sciencedi...022314X02000495

không dễ thật.

Xem lại kq này , code python ra tính đến $100000$ thì gần bằng $\frac{15}{4\pi^{2}}$ hơn 

em quên số $4$, cảm ơn anh.

Gọi số cặp $(m;n)$ sao cho $1\leq m,n\leq x$ và $gcd(m,n)\leq 2$ là $g(n)$. Ta dễ có bằng đổi chỗ $m,n$, $P(n)= \frac{g(n)+n-2}{2}$ (bỏ các cặp $(k;k),k\geq 3$).

Vậy ta cần tính $\lim_{x\rightarrow \infty }\frac{g(n)}{n^2}$, tương đương với xác xuất khi chọn ngẫu nhiên hai số nguyên dương $(m,n)$ sao cho $gcd(m,n)\leq 2$.

Xác xuất $m$ và $n$ có ít nhất một số không chia hết cho $p\geq 3$, $p$ nguyên tố là $1-\frac{1}{p^2}$.Xác xuất $m$ và $n$ có ít nhất một số không chia hết cho $4$ là $\frac{15}{16}$ Các sự kiện đối với mỗi số nguyên tố $p$ và $4$ là độc lập nên xác xuất trên là: $\frac{15}{16}\prod_{p\geq 3}\left ( 1-\frac{1}{p^2} \right )=\frac{15}{16} \frac{4}{3}\prod_{p}\left ( 1-\frac{1}{p^2} \right )= \frac{15}{16}\frac{4}{3}\frac{1}{\zeta (2)}= \frac{15}{16}\frac{4}{3}\frac{6}{\pi ^2}= \frac{15}{2 \pi ^2}$

Kết luận giới hạn: $\frac{15}{ 4\pi ^2}$

$3\times 9\equiv 1(mod 26)\Rightarrow 9\equiv 3^{-1}(mod 26)$

Cho hai số nguyên dương $n\geq k$, gọi $S_k(n)$ là số chuỗi nhị phân có độ dài $n$ không chứa chuỗi gồm toàn số $0$ hoặc $1$ có độ dài $k$, $C_k(n)$ là số chuỗi nhị phân có độ dài $n$ không chứa chuỗi gồm toàn số $0$.

Chứng minh rằng: $S_{k+1}(n+1)=2C_k(n)$

bài 1:

$g(n;t)=\left \lceil \frac{n}{t} \right \rceil$, ví dụ ta cho $\left \lceil \frac{n}{t} \right \rceil-1$ đội, mỗi đội mặc $t$ màu áo phân biệt, đội còn lại có không quá $t$ màu áo.

Đầu tiên ta chọn đội bất kì có $x_1$ màu áo. Nếu màu áo chưa đủ $n$ ta chọn đội có $x_2$ màu áo còn lại. Chọn như vậy đến khi đủ $n$ màu áo và $k$ đội "có màu sắc nhận dạng được. Dễ thấy $x_i \leq t$ Ta có $n=\sum_{i=1}^{k} x_i\leq kt\Rightarrow k\geq \left \lceil \frac{n}{t} \right \rceil$.

(Q.E.D)

Chứng minh rằng trong $n$ ($n\geq 2$) số nguyên dương liên tiếp, tồn tại một số nguyên tố cùng nhau với $n-1$ số còn lại.

Kí hiệu sai thì phải $A\oplus B=(A\setminus B)\cup(B\setminus A)$

Đúng rồi đó:https://en.wikipedia...tric_difference

Có nhiều kí hiệu

Câu 4:

Ta sẽ chứng minh quy nạp theo $m$ cho điều này. Trước hết ta phát biểu bổ đề: $A\Delta B=A\Delta C$ thì $B=C$.

Giả sử $B\neq C$, khi đó không giảm tổng quát giả sử giả sử $a$ là phần tử thỏa $a\in B$ và $a\notin C$. Ta có hai trường hợp như sau:

   Case 1: Nếu $a\in A$ khi đó $a\notin (A\setminus B),a\notin (B\setminus A)\Rightarrow a\notin A\Delta B$. Nhưng lại có $a\in (A\setminus C)$ nên suy ra $a\in A\Delta C$ nên $A\Delta B\neq A\Delta C$, vô lý.

   Case 2: Nếu $a\notin A$ thì chứng minh tương tự suy ra $a\notin A\Delta C$ và $a\in A\Delta B$ nên suy ra $A\Delta B\neq A\Delta C$. Như vậy ta suy ra $B=C$.

Bây giờ ta sẽ quy nạp theo $m$. Với $m=1$ thì ta có một tập thuộc $T$ là tập rỗng. Với $m=2$ và hai tập $A,B$ thì ta có hai tập thuộc $T$ là tập rỗng và $A\Delta B$ thỏa. Như vậy giả thiết đúng với $m=1,2$.

Giả sử giả thiết đúng với $m=k$ thì ta chứng minh nó đúng với $m=k+1$. Xét $m+1$ tập $A_1,A_2,...,A_{m+1}$. Nếu với $m$ tập $A_1,A_2,...,A_m$ mà số lượng tập tạo thành không nhỏ hơn $m+1$ thì khi đó ta thêm vào một tập $A_{m+1}$ thì giả thiết vẫn đúng. Do đó ta chỉ xét cho trường hợp $|T|=m$.

Khi đó, nếu ta thêm vào một tập $A_{m+1}$ thì ta sẽ thêm vào tập $T$ các tập hợp $A_{m+1}\Delta A_1,...,A_{m+1}\Delta A_{m+1}$. Nếu các tập này trùng với $m$ tập đã có trong $T$ thì do $|T|=m$ nên theo nguyên lý Dirichlet tồn tại $i,j,1\leq i<j\leq m+1$ để $A_{m+1}\Delta A_i=A_{m+1}\Delta A_j$ và theo bổ đề ta có $A_i=A_j$, vô lý. Vậy trong $m+1$ tập đó chắc chắn có một tập khác với các tập trong $T$ và số phần tử của $T$ tăng lên ít nhất một đơn vị, tức là $|T|\geq m+1$.

Vậy giả thiết quy nạp là đúng và ta có điều phải chứng minh.

 

P.S: Cách giải bài số 2 của mình tương đối giống nhưng hơi khác so với cách của anh Lâm Hữu Phúc, mình sẽ đăng sau

Lấy luôn $S=\left \{ A_1\bigtriangleup A_k|1\leq k\leq m \right \},\left | S \right |=m,S\subset T$

1. Tên nick ứng viên: bangbang1412, baopbc

2. Thành tích nổi bật:

-baopbc: Tích cực tham gia Mỗi tuần 1 bài toán hình học

-bangbang1412: Thảo luận sôi nổi trên topic tôpô

3. Ghi chú: Không có

Cho dãy số nguyên dương tăng ngặt $\left ( a_n \right )_{n=1}^\infty$ thỏa $a_n\leq p_n,\forall n\in \mathbb{Z}$, trong đó $p_n$ là số nguyên tố thứ $n$. Chứng minh tập các ước số nguyên tố của dãy vô hạn.

Nhận xét 1: các mẫu không chia hết cho $p$ nên có thể rút gọn các phân số mà không làm thay đổi tính chất sau giữa tử và mẫu :$x\equiv y(mod p)$.

Nhận xét 2: Với mỗi $x\in Z_p/\left \{ 0 \right \}$, tồn tại duy nhất $y\in Z_p/\left \{ 0 \right \}$ thỏa $xy\equiv 1(mod p)$. Khi đó nếu $\frac{1}{x^2+1}+\frac{1}{y^2+1}=\frac{k}{l}$ thì $k\equiv l(mod p)$ (cộng lại và áp dụng nhận xét 1).

Xét $2$ lần cái tổng đang xét, cộng từng cặp (nhận xét 2) lại ta được tổng $\frac{2m}{n}=2+\sum_{i=1}^{p-1}\frac{a_i}{b_i}, a_i\equiv b_i(mod p)$, cộng lại, xét tử và mẫu: $\sum_{i=1}^{p-1} a_i\prod_{j\neq i}b_j+2\prod_{i=1}^{p-1}b_i\equiv (p+1)\prod_{i=1}^{p-1}b_i\equiv \prod_{i=1}^{p-1}b_i(mod p)\Rightarrow 2m\equiv n(mod p)$ (nhận xét 1).

(Q.E.D)

Sao có thể đưa bài khó thế này đầu tiên nhỉ.

Câu IV:

Chia $(1;2);(3;4);...;(2k-1;2k);...(4029;4030)$, ta chỉ cần xét khoảng $[2015^2;2015^2+2015]$.

Chia $(1;2016);(2;2017);...;(k;2015+k);,,,;(2015;4030)$, ta chỉ cần xét hai số $2015^2;2015^2+2015$(xét đồng dư modulo $2015$).

Chia $(1;4030);(2;4);(3;5);...(4k-2;4k);(4k-1;4k+1);...(4026;4028);(4027;4029)$, ta được các số chẵn nhỏ hơn $2015^2+2015$ và các số lẻ lớn hơn $2015^2$, loại được hai số trên.

(Q.E.D)

Ta chuyển bài toán về dạng tổng quát hơn: Cho tập $S$ gồm số chẵn phần tử, mỗi tập con được gán một số từ $1$ đến $2^k$ sao cho nếu $A\subset B$ thì số gán cho $B$ lớn hơn. $S_1$ là tập các tập con được gán số $a\leq x\leq b$ có số phần tử chẵn, $S_2$ định nghĩa tương tự.

Nếu hai tập con chẵn trong $S_1$ thỏa $A\subset B$ thì giữa nó có một tập con lẻ trong $S_2$, nếu ta bỏ một trong hai tập con trên và bỏ phần tử lẻ thì hiệu trên không giảm. Vậy ta chỉ cần chứng minh: Nếu tập $I$ gồm các tập con của $S$ không có tập nào là con của tập kia thì $\left | I \right |\leq C_k^{\frac{k}{2}}$.

Gọi $N_i$ là tập các tập con có $i$ phần tử. Ta sẽ chứng minh tồn tại đơn ánh $f_i$ từ $N_i$ đến $N_{i+1}$ thỏa $A\subset f(A)$với $i<\frac{k}{2}$.

Xét đồ thị lưỡng phân $G=(N_i\cup N_{i+1},E)$, nếu $A\subset B$ thì $A$ nối với $B$. Với $X\subset N_i$, số các cạnh nối với $X$ là $E=(k-i)\left | X \right |$, bậc của các phần tử của $N_{i+1}$ là $i$ nên $E$ không lớn hơn $i\left | G(X) \right |$ mà $k-i>i$ nên $G(X)\geq X$, áp dụng định lí Hall ta có điều phải chứng minh.

Tương tự tồn tại đơn ánh $f_i$ từ $N_i$ đến $N_{i-1}$ với $i>\frac{k}{2}$ và $f(A)\subset A$. Sử dụng các đơn ánh, ta đưa các tập con của $I$ về các tập con có $\frac{k}{2}$ phần tử. Vì không có tập nào là con của tập kia nên các tập con sau khi chuyển đổi phân biệt. Vậy $\left | I \right |\leq\left | N_{\frac{k}{2}} \right |=C_k^{\frac{k}{2}}$.

(Q.E.D)

Có cách nào đơn giản hơn không?

Chọn $N$ đủ lớn sao cho $2^N+3^N-k>3$.

Nếu $2^N+3^N-i$ không có ước nguyên tố khác $2,3$ thì với mọi $n\geq N$, cùng tính chẵn lẻ với $N$, $2^n+3^n-k$ là hợp số.

Ta lấy ước nguyên tố khác $2,3$ của $m$ số $2^N+3^N-i_j$ còn lại là $p_1,p_2,...,p_m$.

Lấy $n=N+2q\prod_{j=1}^{m}(p_i-1)$.

Giờ thì với các số $i_j$, ta có theo Fermat: $2^n+3^n-i_j\equiv 2^N+3^N-i_j\equiv 0(mod p_j),2^n+3^n-i_j>2^N+3^N-i_j\geq p_j$ nên là hợp số. Các TH còn lại cũng là hợp số.

(Q.E.D)

Câu 4:

Ta chứng minh tập hợp $A_k$ gồm các số có dạng $2^km$ ($m$ lẻ) có một cách phân hoạch duy nhất thành hai tập $X_k, Y_k$ ($X_k$ chứa $2^k$) thỏa đề bài.

Ta có thể giả sử $k=0$, $A_0={1;3;...;2m-1}$.

Với $m=1$ hiển nhiên.

Giả sử $m$ đúng. Chọn $l$ sao cho $2^l<2m+1<2^{l+1}$ . Ta có $2^{l+1}-2m-1<2m+1$, theo giả thiết quy nạp $2^{l+1}-2m-1$ thuộc một trong hai tập $X_0,Y_0$, nên để thỏa mãn thì $2m+1$ có một cách chọn vào tập còn lại. (nếu $l$ lớn hơn, $2^{l+1}-2m-1$ không thuộc các số trước đó nên không xét).

Có $11$ tập $A_k$, hai số thuộc hai tập khác nhau tổng không có dạng $2^k$ nên số cách chọn là $2048$.

Bổ đề: Nếu $f$ tăng trên $\rho (H)$ thì $f$ tồn tại một điểm bất động

Xét dãy tập hợp $X_0=H, X_{n+1}=f(X_n)$. Ta sẽ chứng minh bằng quy nạp $X_{n+1} \subset X_n$.

Với $n=0$, ta có $f(H)\subset H$ vì $f(H)$ thuộc $\rho (H)$ nên là tập con của $H$.

Giả sử $X_{n+1}\subset X_n$, theo định nghĩa hàm tăng, $f(X_{n+1})\subset f(X_n)$ hay $X_{n+2}\subset X_{n+1}$

Vậy $X_{n}$ dần tiến về tập $X\subset H$ (đoạn này thấy không ổn nhưng có vẻ đúng với tập hữu hạn). Ta có $f(X)=X$

Rồi làm như phần chứng minh trên.

Ta có $f(H)\subset H$ (hiển nhiên), bằng quy nạp $f^{n+1}(H)\subset f^n(H)$. Vậy $f^n(H)$ có giới hạn thỏa $f(X)=X$.

Không biết xài mấy từ này có ổn không.

$X=\lim_{n\rightarrow \infty }f^n(H)$

Ý tưởng của em là chỉ cần xét khoảng $[0;1)$. Xét tập $D_n=\left \{ [0;\frac{1}{2^n});...[1-\frac{1}{2^n};1) \right \}$ và hàm trên $D_n$: $h_n(X)=\bigcup_{A\subset X}f(X),A\subset H$. Ta chứng minh được $h_n$ tăng, theo bổ đề 3 ta được các tập $X_1,X_2,...$ sao cho $h_k(X_k)=X_k$. Ta cũng chứng minh được $X_{k+1}\subset X_k$. Theo bổ đề về dãy các đoạn thẳng lồng nhau, ta chứng minh được tồn tại tập $X$ sao cho $f(X)=X$.

Tại em không biết trình bày mấy cái này, nên em ghi tắt (chắc em cũng lập luận sai ở đâu đó).

Anh học mấy cái này ở đâu vậy?