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

Câu 4: Ta sẽ chứng minh rằng $a_i=min\left \{ a_1;a_2;...;a_i \right \}$ hoặc $a_i=max\left \{ a_1;a_2;...;a_i \right \}$ ,$i=\overline{4,2016}$. Thật vậy vì $2\sum_{i=1}^{2016}a_i=2016.2017$ nên $2a_{2016} \equiv 2 \pmod{2015}$ nên $a_{2016}$ nhận giá trị là $1$ hoặc $2016$. Mệnh đề đúng với $i=2016$, giả sử mệnh đề đúng đến $i=k>4$. Ta thấy rằng $(a_1,a_2,...,a_{i-1})$ là $1$ hoán vị của $i-1$ số nguyên liên tiếp $a+1;...;a+i-1$.Nếu $i$ là số lẻ thì ta có $2\sum_{t=1}^{i-2}a_t =2\sum_{t=1}^{i-1}(a+t)-2a_{i-1} \vdots i-2$ nên $2a_{i-1} \equiv 2a+2 \pmod{i-2} \Rightarrow a_{i-1}\equiv a+1 \pmod{i-2}$ (do $i-2$ là số lẻ). Vậy $a_{i-1}$ nhận giá trị $a+1$ hoặc $a+i-1$. Nếu $i$ là số chẵn, lập luận tương tự ta có  $2a_{i-1} \equiv 2a+2 \pmod{i-2}$ nên $a_{i-1}$ nhận $1$ trong $3$ giá trị $a+1,a+i-1,a+1+\frac{i-2}{2}$. Nếu $a_{i-1}=a+1+\frac{i-2}{2}$ thì ta có $2\sum_{t=1}^{i-3}a_t =2\sum_{t=1}^{i-1}(a+t)-2a_{i-1}-2a_{i-2} \vdots i-3$ nên $2a_{i-2} \equiv 2a+i \pmod{i-3}$. Vậy $a_{i-3}=a+1+\frac{i-2}{2}=a_{i-2}$ (vô lí). Từ đó mệnh đề đúng với $i=k-1$. Mỗi cách chọn $(a_4;a_5;...;a_{2016})$ ứng với $1$ dãy nhị phân độ dài $2013$ với số thứ $i$ từ trái sang phải là $1$ nếu $a_{i+3}=max\left \{ a_1;a_2,...;a_{i+3} \right \}$, bằng $0$ trong trường hợp còn lại. Có tổng cộng $2^{2013}$ cách chọn dãy nhị phân nên có từng đấy cách chọn bộ số $(a_4;a_5;...;a_{2016})$. Với ba số $a_1;a_2;a_3$ có tổng cộng $6$ hoán vị nên tổng cộng số các hoán vị $2016$ số là $3.2^{2014}$

Giả sử $A$ có $n$ phần tử là $a_1<a_2<...<a_n$, xét các tổng $f(x;y;z;t)=a_xa_y+a_za_t$. Theo định nghĩa tập $A$ thì các số sau đều thuộc $A$: $f(1;3;2;4)<f(1;2;3;4)<f(1;2;3;5)<f(1;2;3;6)<...<f(1;2;3;n)<f(1;2;4;n)<f(1;2;5;n)<...<f(1;2;n-1;n)<...<f(n-3;n-2;n-1;n)$, tổng cộng $4n-14$ số. Vì vậy ta có $n\geq 4n-14$ hay $n\leq 4$. Vậy $n=4$, đến đây dễ thấy các tập $A$ thoả mãn là $\left \{ a,b,c,d\mid (a-b)(b-c)(c-d)(d-a)(a-c)(b-d)\neq 0; b\neq 1; a=\frac{-cd}{b-1}; a\geq 0;b\geq 0;c\geq 0;d\geq 0 \right \}$

Chứng minh quy nạp: Bài toán hiển nhiên đúng với $n=2$, giả sử bài toán đúng với $n=k$, xét $n=k+1$ và $2^k+1$ tập con trong tập $\left \{ 1;2;...;k+1 \right \}$ được chọn. Gọi $A$ là tập các tập con được chọn mà không chứa $k+1$, $B$ là tập các tập con chứa $k+1$. Vì $\left | A \right |+\left | B \right |=2^k+1$ nên $1$ trong $2$ tập $A$ và $B$ chứa ít nhất $2^{k-1}+1$ phần tử. Nếu là tập $A$ thì tồn tại $3$ tập con $M$, $N$, $P$ thuộc $A$ mà $M=N\cup P$ theo nguyên lí quy nạp (do $A$ là tập con của tập các tập con của $\left \{ 1;2;...;k \right \}$). Nếu tập $B$ chứa ít nhất $2^{k-1}+1$ phần tử thì bỏ $k+1$ trong mỗi phần tử của $B$ ,gọi tập các phần tử của $B$ mà bỏ đi $k+1$ là $C$ .Lập luận tương tự ta tìm được $3$ tập $M$,$N$,$P$ của $C$ thỏa mãn $M=N\cup P$, nên $M\cup \left \{ k+1 \right \}=(N\cup\left \{ k+1 \right \})\cup(P\cup \left \{ k+1 \right \})$.Vậy tồn tại $3$ tập của $B$ mà tập này bằng hợp $2$ tập còn lại. Vì vậy trong mọi trường hợp, ta có dpcm

Xét $1$ hoán vị $(a_1;a_2;...;a_n)$ thỏa mãn tính chất chỉ tồn tại duy nhất $1$ số $i$ sao cho $a_i>a_{i+1}$. Lúc này dễ thấy dãy $a_1,a_2,...,a_i$ và $a_{i+1},...,a_n$ tăng dần. Từ đó ta thấy rằng với $1$ cách chọn dãy $a_1,a_2,...,a_i$ tăng dần thì chỉ có nhiều nhất $1$ cách chọn dãy $a_{i+1},...,a_n$ tăng dần. Lưu ý là nếu $a_1,a_2,...,a_i$ là $i$ số tự nhiên đầu tiên thì không thể chọn được $a_{i+1}$ do $a_{i+1}>a_i$. Với mỗi cách chọn $i$ số $(a_1,a_2,...,a_i)$ trong $n$ số nguyên dương đầu tiên thì chỉ có $1$ cách sắp xếp chúng theo thứ tự tăng dần. Vậy số cách chọn một hoán vị $(a_1;a_2;...;a_n)$ thỏa mãn đề bài bằng số cách chọn $1$ bộ số $(a_1;a_2;...;a_i)$ với $i$ chạy từ $1$ đến $n$ và bộ số đó không phải là bộ các số tự nhiên đầu tiên liên tiếp, hay số cách chọn là bằng $2^n-n-1$

Bài 1: Rõ ràng $a^{\phi (a^{n}-1)}-1\vdots a^n-1$ và $n=ord_{a}(a^n-1)$ nên có $\phi (a^{n}-1)\vdots n$

Bài 5: Gọi $S_{XYZ}$ là diện tích tam giác $XYZ$.Dễ thấy với $n=3,4$ thì thoả mãn đề bài. Ta sẽ chứng minh với $n=5$ thì không thoả mãn để bài. Giả sử $A_1,A_2,A_3,A_4,A_5$ là $5$ điểm thoả mãn đề bài, xét $T$ là $1$ bao lồi của $5$ điểm đó:

- Nếu $T$ là $1$ tam giác, giả sử là tam giác $A_1A_2A_3$ thì lúc đó $A_4,A_5$ nằm trong tam giác đó, do vậy $S_{A_1A_2A_4}+S_{A_1A_3A_4}+S_{A_3A_2A_4}=S_{A_1A_2A_5}+S_{A_1A_3A_5}+S_{A_3A_2A_5}=S_{A_1A_2A_3}$. Lại có $S_{A_1A_2A_5}-S_{A_1A_2A_4}=S_{A_1A_3A_5}-S_{A_1A_3A_4}=S_{A_3A_2A_5}-S_{A_3A_2A_4}=r_5-r_4$ nên $r_5=r_4$, hay $S_{A_1A_2A_5}-S_{A_1A_2A_4}=S_{A_1A_3A_5}-S_{A_1A_3A_4}=S_{A_3A_2A_5}-S_{A_3A_2A_4}=r_5-r_4=0$, nên $A_4A_5$ song song với cả 3 đoạn $A_1A_2,A_2A_3,A_3A_1$(vô lí)

-Nếu $T$ là $1$ tứ giác, giả sử là $A_1A_2A_3A_4$ thì lúc đó $A_5$ nằm trong $1$ trong $2$ tam giác $A_1A_2A_3$ hoặc $A_4A_3A_2$. Giả sử $A_5$ nằm ngoài $A_1A_2A_3$, lúc đó $A_4,A_5$ nằm cùng phía bờ $A_2A_3$, khác phía $A_1$. $2$ điểm đó cũng nằm cùng phía với $A_2$ bờ $A_1A_3$ và $A_3$ bờ $A_2A_1$ nên $S_{A_1A_2A_4}+S_{A_1A_3A_4}-S_{A_3A_2A_4}=S_{A_1A_2A_5}+S_{A_1A_3A_5}-S_{A_3A_2A_5}=S_{A_1A_2A_3}$. Lập luận tương tự cũng có $A_4A_5$ song song với cả $3$ cạnh tam giác $A_1A_2A_3$, vô lí.

-Nếu $T$ là ngũ giác $A_1A_2A_3A_4A_5$ ,xét vị trí các điểm $A_4,A_5$ với tam giác $A_1A_2A_3$ cũng có điều vô lí

Vậy $n=5$ không thoả mãn. Với $n>5$, ta chỉ cần xét $5$ điểm bất kì trong $n$ điểm đó để suy ra điều vô lí. 

Vậy $n=3$ hoặc $n=4$

Có $\mathcal{P}(2)\mid 2 $,$\mathcal{P}(5)\mid 27 $ và $3\mid \mathcal{P}(5)- \mathcal{P}(2)$ nên hoặc $\mathcal{P}(2)=\mathcal{P}(5)=1$ hoặc $\mathcal{P}(2)=\mathcal{P}(5)=-1$.WOLG, giả sử $\mathcal{P}(2)=1$,ta thấy $\mathcal{P}(0)=1$ bởi nếu tồn tại $1$ ước nguyên tố lẻ của $\mathcal{P}(0)$ là $q$ thì $q\mid \mathcal{P}(q)$, hay $q\mid 2^q$ (vô lí). Xét $p$ nguyên tố bất kì, gọi $q$ là $1$ ước nguyên tố bất kì của $\mathcal{P}(p)$ thì $q\mid 2^p-p$, gọi $m= \text{ord}_{2}(q)$,giả sử $m>2$ có $(m;q)=1$ nên theo định lí thặng dư trung hoa thì $\left\{\begin{matrix} x\equiv p \pmod{q} & & \\ x\equiv p+v \pmod{m} & & \end{matrix}\right.$ với $v$ là $1$ số thỏa mãn $v$ không chia hết cho $m$ và $(p+v;m)=1$ (hoàn toàn chọn được do $m>2$ nên $\phi(m)\geq 2$), có $1$ nghiệm $x \pmod{qm}$ . Dễ thấy do $\mathcal{P}(0)=1$ nên $(p;q)=1$ và $(p+v;m)=1$ nên $(x;qm)=1$. Theo định lí Dirichlet, tồn tại $1$ số nguyên tố $t$ để $t \equiv x \pmod{qm}$. Có $q\mid t-p$ nên $q\mid \mathcal{P}(t)-\mathcal{P}(q)$$\Rightarrow$ $q\mid \mathcal{P}(t)$$\Rightarrow$$q\mid 2^t-t$$\Rightarrow$$q\mid 2^p(2^{t-p}-1)+p-t$$\Rightarrow$$q \mid 2^{t-p}-1$ (vô lí do $t-p$ không phải là bội của $m$). Vậy $m=2$, hay $q=3$, vậy $\mathcal{P}(p)$ có dạng $3^t$ với mọi $p$ nguyên tố(1). Cố định $p\neq 3$ và $t$, theo định lí Dirichlet thì tồn tại vô hạn số nguyên tố $q$ thỏa mãn $q\equiv p \pmod{3^{t+1}}$. Có $3^{t+1}\mid q-p$ nên $3^{t+1}\mid \mathcal{P}(q)-\mathcal{P}(p)$. Kết hợp với (1) ta có $\mathcal{P}(q)=3^t$.Vậy $\mathcal{P}(x)=3^t$ có vô số nghiệm nên đa thức là đa thức hằng.Thử lại thấy $\mathcal{P}(x)=1$ hoặc $\mathcal{P}(x)=-1$ thỏa mãn

Học rộng nhưng đi sâu vào để tự nghiên cứu kiến thức lại là cả 1 vấn đề. Biết được kiến thức nhưng lại không luyện tập nhiều để trau dồi thì vài năm sau cũng sẽ bị quên lãng và phải học lại, thành ra phí sức, huống chi kiến thức cả 12 năm học quá nặng và em vẫn đang tuổi ăn chơi, phát triển. Dù sao cũng chúc mừng em đã đạt được những thành công nhất định

Xin lỗi vì sự sai sót, bây giờ mình sẽ chứng minh rằng $n$ là số đẹp khi và chỉ khi $n$ lẻ và $n\geq 5$. Xét $n$ lẻ và $n$ điểm trên mặt phẳng. Xét điểm $A$ trong $n$ điểm đó và $n-1$ điểm còn lại là $A_1;A_2;...A_{n-1}$ lần lượt theo chiều kim đồng hồ với trục là $A$. Nối $A$ với $n-1$ điểm còn lại, gọi $S$ là số tam giác chứa $A$. Với $i,j$ bất kì, xét $(i;j)=1$ nếu đoạn thẳng $AA_i$ tạo với đoạn thẳng $AA_j$ một góc bé hơn $180^\circ$ theo chiều kim đồng hồ,$(i;j)=-1$ nếu ngược lại. Ta thấy $A$ nằm trong tam giác $A_iA_jA_t$ khi và chỉ khi $(i;j)=(j;t)=(t;i)$.Với $A_i$ bất kì, gọi $n_i$ là số số $j$ sao cho $(i;j)=1$, $m_i$ là số $j$ sao cho $(i;j)=-1$. Dễ thấy $n_i+m_i=n-1$. Xét $2$ số $A_i$ và $A_j$ bất kì, giả sử $(i;j)=-1$, số các tam giác chứa $A$ có đỉnh là $A_i;A_j$ là số các số $t$ sao cho $(i;j)=(j;t)=(t;i)=-1(1)$. Gọi số đỉnh nằm giữa $A_i$ và $A_j$ theo chiều kim đồng hồ là $s$, dễ thấy $s\equiv i-j \pmod{2}$. Số số $t$ thoả mãn (1) chính là $n_i+m_j-s\equiv i-j+n_i+n_j \pmod {2}$. Cho $i;j$ chạy, lưu ý rằng mỗi tam giác được tính $3$ lần nên ta có $3S \equiv \sum_{i=1}^{n-1}\sum_{j=1}^{i-1} (n_i+n_j+i-j)\equiv 0 \pmod{2}$ nên $S\equiv 0\pmod{2}$. Vậy số tam giác chứa $A$ là số chẵn $\forall A\in X$ nên $n$ là số đẹp. Với $n$ là số chẵn, xét $4$ điểm $A,B,C,D$ sao cho $D$ nằm trong $ABC$. Thêm $1$ số chẵn điểm $T$ vào $X$ sao cho $T$ không cùng phía với $A,D$ bờ $BC$ và với mọi $Y,Z$ được thêm, $D$ không nằm trong $AYZ,BYZ,CYZ$ và không ở trong $ABT,BCT$ với mọi $T$ được thêm nhưng thuộc $ACT$. Vậy luôn có lẻ số tam giác chứa $D$

Câu 4:

Kí hiệu $S=\left \{ 0;1;...;2017^{2016} \right \}$. Gọi $A_i=\left \{ 2^i3^j\mid j=\overline{0,2016} \right \}$ với mỗi $i\in S$. Gọi $f_n(A_i)$ là màu dùng để tô màu số lớn thứ $n$ trong tập $A_i$ với $n=\overline{1,2017}$, $i=\overline{0,2017^{2016}}$ Xét $g(A_i)=(f_1(A_i);f_2(A_i);...;f_{2017}(A_i))$. Vì có $2017^{2016}+1$ tập $A_i$ nên $\exists i,j\in S,i\neq j: g(A_i)=g(A_j)$. Vì $A_i$ có $2017$ phần từ nên $\exists m,n: 0\leq m<n\leq2016$: $2^{i}3^{m}$ và $2^{i}3^{n}$ tô cùng màu. Lại có $g(A_i)=g(A_j)$ nên $2^j3^m$ và $2^j3^n$ tô cùng màu với $2^i3^m$ và $2^i3^n$. Giả sử $i<j$, chọn $a=2^i3^m$,$b=2^j3^m$,$c=2^i3^n$,$d=2^j3^n$

Số đẹp duy nhất là $5$ thôi, còn dễ thấy $n=4$ hay $6$ đều không thoả mãn, $n=7$ ta có cách sắp xếp sau không thoả mãn

Trong đó $G$ nằm trong các tam giác $ABC$,$ACD$,$AEF$,$AEC$,$AFB$

Với $n>7$, ta sẽ thêm một số điểm nằm khác phía với $C$ bờ $BD$, dịch chuyển những điểm đó ra đủ xa khỏi $7$ điểm $A,B,C,D,E,F,G$ sao cho với mỗi $2$ điểm $X,Y$ trong số các điểm thêm vào, $G$ không thuộc các tam giác $AXY$,$BXY$,$CXY$,$DXY$,$EXY$,$FXY$ nhưng lại thuộc các tam giác $AXF,AXC,AYF,AYC$ và không thuộc tam giác $MNX,MNY$ với $M$,$N$ là $2$ trong số $7$ điểm $A,B,C,D,E,F,G$ trừ $4$ tam giác kể trên. Tất nhiên với mọi $3$ điểm $X,Y,Z$ được thêm thì $G$ không thuộc $XYZ$:

Lúc này luôn có đúng số lẻ tam giác chứa $G$, và chú ý rằng có thể thêm vô hạn điểm nên mọi $n>7$ đều không phải số đẹp. Vậy số đẹp duy nhất là $5$

Gọi $T$ là tập các hoán vị của $1,2,...,2n$ là $(x_1;x_2;...;x_{2n})$ thoả mãn tồn tại đúng $1$ chỉ số $i$ sao cho $\left | x_i-x_{i+1} \right |=n$ và $I$ là số hoán vị không có tính chất $P$.Ta lập $1$ đơn ánh từ $T$ vào $I$:

$T\rightarrow I$

Mình không giỏi lắm về khoản khai triển những biểu thức phức tạp nên sẽ nói hướng làm và việc trình bày cụ thể sẽ dành cho bạn Bảo:

Tất nhiên $q\neq 0$, nếu $q=1$ thì bước đầu tiên là ta sẽ di chuyển sang phải (hay di chuyển theo vector $(1,0)$). Ta sẽ quy nạp theo $m+n$ với $p$,$q$ bất kì, có thể xét riêng các trường hợp $m+n=1,2,3$ để suy ra dpcm.Giả sử bài toán đúng với $m+n=k$, xét $m+n=k+1$. Nếu $q=0$ thì ta có bài toán đúng, nếu $q>0$ thì đầu tiên ta có $2$ cách di chuyển:

+)Di chuyển theo vector $(0,1)$, lúc này ta tịnh tiến đồ thị theo vector $(0,-1)$ thì điểm $P$ sẽ thành điểm $(m,n-1)$, đường thẳng $L$ thành đường thẳng $y=px+q-1$, cách đi từ gốc $O$ (điểm ta đến được lúc đầu trước khi dùng phép tịnh tiến) đến $P$ là $\frac{q-1}{m+n-1}\binom{m+n-1}{m}$ theo giả thiết quy nạp

+)Di chuyển theo vector $(1,0)$, tịnh tiến theo vector $(-1,0)$, điểm đang đến trở thành gốc $O$, $P$ thành $(m-1,n)$, $L$ thành $y=px+p+q$, cách đi từ $O$ đến $P$ là $\frac{p+q}{m+n-1}\binom{m+n-1}{m-1}$

Cộng $2$ giá trị trên lại, lưu ý rằng $n=pm+q$, ta sẽ có cách đi từ $O$ đến $(m,n)$, suy ra dpcm theo nguyên lí quy nạp

Câu 5(lần I):

a/ liệt kê tất cả các trường hợp, ta có các giá trị là $f_4=3,4$

b/ Nếu có $2n-3$ số thoả mãn thì có nghĩa tất cả các số từ $3$ đến $2n-1$ đều là tổng của $2$ số khác màu. Giả sử $n$ tô màu xanh, có $2n-1=n+n-1$ nên $n-1$ tô màu đỏ, có $2n-2=n+n-2$ nên $n-2$ cũng được tô đỏ, $n-1$ và $n-2$ đều được tô đỏ và $2n-3=n+n-3$ nên $n-3$ cũng được tô đỏ, tương tự, ta có tất cả các số từ $1$ đến $n-1$ được tô đỏ(vô lí)

Nếu $f_n=2n-5$, ta có cách tô như sau

Tô đỏ số $1$ và các số từ $\frac{n}{2}+1$ đến $n-1$

Tô xanh số $2n$ và các số từ $2$ đến $\frac{n}{2}$

a/ Giả sử không ai làm bài $3$, nếu có $1$ người không làm được bài $2$ thì người đó chỉ làm được bài $1$, lúc đó tất cả mọi người đều làm được bài $1$ vì mọi người đều có ít nhất chung $1$ bài làm được với người đó

b/ Giả sử có $1$ người chỉ làm được $1$ bài thì tất cả mọi người đều làm được bài đó. Nếu tất cả mọi người đều làm được ít nhất $2$ bài thì tổng số bài làm ít nhất là $60\times2=120$ nên có ít nhất $1$ bài được ít nhất $120:3=40$ người làm được

Xét $1$ cặp hiệp sĩ và kẻ nói dối là bạn của nhau. Nếu hỏi hiệp sĩ xem có bạn ngồi cạnh anh ta không, anh ta trả lời có thì kẻ lừa dối ngồi cạnh anh ta phải trả lời không, còn nếu anh ta trả lời không thì kẻ lừa dối không ngồi cạnh anh ta nên sẽ trả lời có. Tương tự khi kẻ lừa dối trả lời có thì hiệp sĩ trả lời không, trả lời không thì hiệp sĩ trả lời có. Vậy nên số lần trả lời không của cả $30$ người phải bằng số lần trả lời có và bằng $15$. Vậy số người ngồi ghế chẵn không có ai trả lời có

Bài này thực sự rất ảo diệu . Trước tiên đặt $f(0)=a$ 

$$P(x,\frac{-f(x)}{3}) => a = 12x + f(-f(\frac{f(x)}{3})-x)$$

nên $f$ là toàn ánh

Giả sử tồn tại $y,z \in R$ mà

$$f(y)=f(z)=c$$

$$f(f(x)+3y)=f(f(x)+3z)$$

$$f(f(x)+3z)=f(f(x)+3z+3(y-z))$$

Do $f(x)$ toàn ánh , đặt $y-z=b$ thì $f$ tuần hoàn chu kì $b$ điều này không thể . Do đó $f$ đơn ánh , thay $x=0$ suy ra $f(x) = 3x+a$ 

Phần chứng minh đơn ánh của anh vẫn chưa chặt vì cho dù hàm có tuần hoàn thì vẫn có thể là toàn ánh vì lực lượng của tập $(x;y)$ với $x<y$ bất kì có thể bằng cả lực lượng của tập $R$, đây là một cách chứng minh khác:

Giả sử $f$ tuần hoàn chu kì $L$, thay $x$ bằng $x-L$ ta có:

$12x+f(f(y)-x)=f(f(x)+3y)=f(f(x-L)+3y)=12(x-L)+f(f(y)-x+L)=12(x-L)+f(f(y)-x)$ $\Rightarrow$ $L=0$ hay $y=z$ nên $f$ là đơn ánh

Điều này là không thể vì giả sử có $4$ điểm $A,B,C,D$ với $A,B$ nằm trên $(O_1;r)$ và $C,D$ nằm trên $(O_2;r)$ sao cho $O_1$ là trung điểm $CD$,$O_2$ là trung điểm $AB$ và vị trí $O$ đầu tiên là ở $O_1$ thì $O$ chỉ cứ di chuyển mãi từ $O_1$ sang $O_2$ và ngược lại mà thôi

Bài 2: Bài này mình thấy rằng câu lệnh ii) và iii) sẽ không có giá trị gì cả nếu như Alice chỉ cần lơ đi tất cả những gì Bob bảo cô làm và chỉ trả lời các câu hỏi, và từ đó Bob không thể xác định được chỉ với câu hỏi i) và iv) nên mình sẽ giải với trường hợp Alice làm theo tất cả những gì Bob nói

Ta sẽ quy nạp theo $n$: Với $n=1$ thì chỉ đơn giản hỏi là có $t$ trên bảng không

Giả sử Bob sẽ đạt được mục đích của mình với $n=k$, xét $k+1$ số trên bảng, giả sử tổng của chúng bằng $x$. Đầu tiên Bob sẽ hỏi là có số $x-2t$ trên bảng không. Nếu có thì Bob sẽ bảo Alice loại nó khỏi bảng và hỏi câu hỏi iv). Tổng các số trên bảng lúc này là $2t$ nên khi hỏi câu iv),nếu Alice trả lời có thì Bob đạt được mục đích. Còn nếu không thì có nghĩa là nếu tồn tại 1 số số có tổng bằng $t$ thì trog các số đó phải có số $x-2t$, nghĩa là phải tồn tại $1$ số số khác $x-2t$ có tổng là $3t-x$. Bob có thể xác định điều đó với $3k$ bước nữa với $k$ số có tổng là $2t$, điều này là có thể theo giả thiết quy nạp. Còn nếu không thì Bob sẽ bảo Alice viết thêm số $x-2t$ lên bảng rồi hỏi câu iv). Vì tổng các số trên bảng lúc này là $2x-2t$ nên nếu Alice trả lời có thì nghĩa là có $1$ số số có tổng là $x-t$ mà không chứa số $x-2t$, còn nếu không thì ngược lại. Vậy Bob luôn xác định được

P/s: Có thể thay $x-2t$ thành $2t-x$

anh tạo bảng và đếm truy hồi ,kết quả của anh là $(1+\sqrt{2})^{100}+(1-\sqrt{2})^{100}$ @

Sr có lẽ em tính toán nhầm chỗ nào đó

Bài 5: Số cách chọn thoả mãn đề bài tương ứng với việc tô các số từ $1$ đến $100$ bằng $3$ màu trắng, xanh, đỏ. Trong đó: Ta chọn các lá bài cùng màu với số được tô và lá bài có số tô màu trắng không được chọn. Ta sẽ lập biểu thức truy hồi cho $R_x$,$B_x$,$W_x$ lần lượt là số cách tô màu sao cho $2$ số liên tiếp trong $x$ số đầu tiên không cùng màu xanh hoặc đỏ và số $x$ tô màu đỏ, xanh, trắng. Dễ có:

-$R_{x+1}=B_{x}+W_{x}$

-$B_{x+1}=R_{x}+W_{x}$

-$W_{x+1}=R_{x}+B_{x}+W_{x}$

Trong đó $W_1=R_1=B_1=1$, dễ thấy

-$B_{x+1}+R_{x+1}=W_{x+1}-W_{x}$

-$W_{x+2}=2W_{x+1}+W_{x}$

Từ đó dễ thấy $W_n=\frac{(1+\sqrt{2})^n+(1-\sqrt{2})^n}{2}$ với mọi $n$

Số cách bốc bài là $R_{100}+B_{100}+W_{100}=2W_{100}-W_{99}=(1+\sqrt{2})^{100}+(1-\sqrt{2})^{100}-\frac{(1+\sqrt{2})^{99}+(1-\sqrt{2})^{99}}{2}$

Bài 8: Đặt ước lẻ lớn nhất của $b-a$ là $t$, ta sẽ chứng minh rằng $\forall k\in \mathbb{N}$ ta có thể viết lên bảng cặp số $(k;k+xt)$ với $x$ là số nguyên dương bất kì. Dễ thấy rằng với mọi cặp $(m;n)$ được viết trên bảng, đề có $m<n$ và $n-m \vdots t$. Từ cặp $(a;b)$ ban đầu, đặt $p=b-a=2^{i}t$, ta có thể tạo ra được cặp có dạng $(2^c;2^c+p),(2^c+p;2^c+2p);...;(2^c+2^{c-i}p-p;2^c+2^{c-i}p)$ với $c>i$. Vậy ta có thể tạo ra cặp $(2^c;2^c+2^ct)$, từ đó ta có thể tạo cặp $(1;t+1)$, từ cặp này dễ tạo ra được các cặp khác thỏa mãn giả thiết

Bài 7: Mình đã chứng minh ở đây: http://diendantoanho...-ít-nhất-n-lần/

Ban đầu luôn có hai ô $0$ và $1$ có hiệu là $1$ . Phép biến đổi này ta xét hai TH . Nếu có hai ô $(a,a+1)$ ở đâu đó cạnh nhau mà ta biến đổi ở các vị trí khác hàng và cột ( ở đây giả sử có một ô $a$ cùng hàng và một ô $a$ cùng cột với ô $a+1$ ) chứa hai ô này thì bảng vẫn còn hai ô không bằng nhau . Nếu biển đổi một ô khác trong hàng và cột chứa ba ô này hoặc biến đổi hai ô này cũng vậy . Suy ra không thể có bảng thỏa mãn. Tóm lại luôn có hai ô mà hiệu khác $0$

Lập luận này không đúng rồi, phản chứng là ta sẽ biến đổi ô nằm cùng hàng với $1$ ô $a$ và cùng cột với ô $a$ kia (ô đó khác ô $a+1$) thì $2$ ô $a$ đó chuyển thành $a+1$, làm cho $3$ ô đó bằng nhau.

Ta dễ chứng minh rằng luôn tồn tại $1$ bảng $2\times 2$ chứa duy nhất $1$ số $1$. Bất biến ở đây chính là hiệu giữa tổng của $2$ số nằm trên mỗi đường chéo modulo 3 nên hiệu đó không chia hết cho $3$. Suy ra dpcm