Korea NMO 2013-P6

Xét phép biến đổi $i$ biến thành $f(i)$ và $f(i)$ biến thành $i$
Đặt $B={1;2;...;n}\A$
Bổ đề: Với $x \in B$, ta có $\left | A \right |+2\left | B \right |+\left | C \right |=\left | D \right |$ tương đương với $\left | A' \right |+2\left | B' \right |+\left | C' \right |=\left | D' \right |$ với $A',B',C',D'$ là ảnh của $A,B,C,D$ qua phép biến đổi trên
Ta phân hoạch $B$ thành $B_1,B_2$, với $A_1$ gồm các phần tử chứa $x$, tương tự với $C_1,D_1$
Ta sẽ quy nạp theo $\left | A \right |$
Với $\left | A \right |=0$ thì bài toán hiển nhiên đúng
Giả sử $\left | A \right |=k$ đúng
Bằng đếm thông thường, ta chứng minh được $\left | A \right |=k+1$ đúng
Bổ đề được chứng minh
Quay lại bài toán
Ta thực hiện các phép biến đổi đưa $\left | A \right |=n-1$
Ví dụ: $f(x)=x+1$, riêng $f(n)=1$
Khi đó thì ta có $\left | A \right |=n-1$,$\left | B \right |=0$,$\left | C \right |=0$, $\left | D \right |=n-1$
Suy ra đpcm

Korea NMO 2013-P2

Cho $b=d=0$, ta được $f(c)=f(c)+f(0)$, suy ra $f(c)=0$

Cho $b=-c$, ta được $f(a)=f(-a)$, suy ra đây là hàm chẵn

Đặt $x=b$, $y=c$, $z=-a$, $t=-d$, ta được:

Với $xz+yt=xy$, ta có:

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

Xét $P(x,x,x-t,t)$: $f(2x-t)+f(x+t)=f(x-t)+f(t)+f(2x)$

Từ đây suy ra $f(2x)=4f(x)$

Bằng quy nạp, ta có $f(kx)=k^2f(x)$, với mọi $k \in Q$

Xét $P(x,y,z,\frac{x(y-z)}{y})$: $f(x+y)+f(z)+f(\frac{x(y-z)}{y})=f(x+z)+f(y+\frac{x(y-z)}{y})$

Đặt $z=$\frac{y(2x+y)}{2x}$, ta có:

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

Từ đây suy ra $f$ tăng với mọi số $x$ nguyên dương

Sử dụng kết quả $f(kx)=k^2f(x)$, đưa về giới hạn, ta có $f(x)=cx^2$

Korea Final Round 2013-P1

$\widehat{EDC}=\widehat{EIC}=90^o-\widehat{\frac{B}{2}}$
Từ đây suy ra $E$ là tâm đường tròn bàng tiếp tam giác $ADB$
Vì $(AMIE)=-1$ nên  $\frac{IA}{IM}=\frac{EA}{EM}=\frac{PB}{PD}$
Áp dụng định lí Menelaus cho tam giác $ABM$, cát tuyến $KJP$, ta có $K$ là trung điểm $AB$
Gọi $L$ là trung điểm $AC$
Ta có tam giác $ABC$ đồng dạng tam giác $ADB$
Khi đó $\frac{AI}{AJ}=\frac{AC}{AB}=\frac{AL}{AK}$
Suy ra tam giác $AKJ$ đồng dạng tam giác $ALI$
Suy ra $\widehat{AJK}=\widehat{AIL}$
Từ đây dễ có đpcm

Korea Final Round 2013

$\fbox{1}$ Cho $\Delta ABC(\hat{B}>\hat{C})$. $D \in AC$ thoả mãn $\widehat{ABD}=\widehat{C}$. Gọi $I$ là tâm đường tròn nội tiếp $\Delta ABC$. Đường tròn ngoại tiếp $\Delta CDI$ giao với $AI$ tại $E(\ne I)$.Đường thẳng đi qua $E$ và song song với $AB$ cắt $BD$ tại $P$. Gọi $J$ là tâm đường tròn ngoại tiếp $\Delta ABD$. Điểm $A'$ là điểm thoả mãn $AI=IA'$. Điểm $Q$ là giao điểm $JP$ và $A'C$. Chứng minh rằng :$QJ=QA'$.

$\fbox{2}$ Tìm $ f :\mathbb{R}\to\mathbb{R} $ thoả mãn các điều kịên sau:

a.$ f(x)\ge 0\ \ \forall \ \ \ x\in\mathbb{R} $

b. Với $a;b;c;d \in \mathbb{R}$thoả mãn $ ab+bc+cd = 0 $ và

$$f(a-b)+f(c-d) = f(a)+f(b+c)+f(d) $$

$\fbox{3}$ Cho số nguyên $n \le 3$.Xét tập hợp $ T =\{ (i,j) | 1\le i < j\le n , i | j\} $. Đối với cac số thực không âm $ x_1 , x_2 ,\cdots , x_n $ thoả mãn $ x_1+x_2+\cdots+x_n = 1 $. Tìm giá trị lớn nhất của:

\[ \sum_{(i,j)\in T}x_i x_j \]

$\fbox{4}$ Cho $\Delta ABC$. $B_1;C_1$ lần lượt là tâm đường tròn bàng tiếp $\hat{B}$ và $\hat{C}$. $B_1C_1$ cắt đường tròn ngoại tiếp $\Delta ABC$ tại $D(\ne A)$. $E$ là điểm thoả mãn : $B_1E \perp CA; C_1E\perp BA$. $ w $ là đường tròn ngoại tiếp $\Delta ADE$. Tiếp tuyến của $ w $ tại $D$ cắt $AE$ tại $F$. G;H là các điểm thuộc $AE; w$ sao cho $DGH \perp AE$. Đường tròn ngọai tiếp $\Delta HGF$ cắt $ w $ tại $I(\ne H)$. J là chân đường vuông góc hạ từ $D $ xuống $AH$. Chứng minh $AI$ đi qua trung điểm $DJ$

$\fbox{5}$Cho a;b là 2 số nguyên dương ; $(a;b)=1$.Hai dãy $\{a_n\};\{b_n\}$ thoả mãn:

\[ (a+b\sqrt2 )^{2n}= a_n+b_n\sqrt2 \].

Tìm tất cả các số nguyên tố $p$ thoả mãn tồn tại $n \le p$ thoả mãn $p | b_n$.

$\fbox{6}$

Đối với một hoán vị bất kì $ f :\{ 1, 2,\cdots , n\}\to\{1, 2,\cdots , n\} $ và xác định

\[ A =\{ i | i > f(i)\} \]

\[ B =\{ (i, j) | i<j\le f(j) < f(i)\ or\ f(j) < f(i) < i < j\} \]

\[ C =\{ (i, j) | i<j\le f(i) < f(j)\ or\ f(i) < f(j) < i < j\} \]

\[ D =\{ (i, j) | i< j\ and\ f(i) > f(j)\} \]

Chứng minh rằng: $ |A|+2|B|+|C| = |D| $.

Một ứng dụng bất ngờ của xích và đối xích

Đề bài: 

Cho $n > 1$ là một số tự nhiên. Đặt $U = \{ 1,2,...,n \}$ và $A\Delta B$ là tập hợp tất cả các phần tử của $U$ mà chỉ thuộc về đúng một tập $A$ hoặc $B$.

Chứng minh rằng: $ |\mathcal{F}|\le 2^{n-1} $.

Ở đó $\mathcal{F}$ là họ các tập con của $U$ sao cho bất kì hai tập phân biệt $A,B$ của $\mathcal{F}$, ta luôn có $|A\Delta B |>2$

Lời giải:

Ta giải bài này bằng tư tưởng xích và đối xích

Cho 2 tập hợp con của $U$ là $A$ và $B$. $A$ và $B$ có quan hệ so sánh khi và chỉ khi $\left | A\Delta B \right |\geq 2$

Gọi họ tập con lớn nhất của $U$ sao cho với bất kì hai tập phân biệt $A,$ thì  $\left | A\Delta B \right |\geq 2$ là $K$

Khi đó theo định lí Dilworth, $\left | K \right |$ bằng số phân hoạch nhỏ nhất của các đối xích hợp thành họ các tập hợp con của $U$

Gọi $T$ là số phân hoạch của  các đối xích hợp thành họ các tập hợp con của $U$

Ta sẽ xây dựng một số $T$ sao cho $T=2^{n-1}$

Với $n=2$ thì tồn tại $T$

Giả sử  với $n=k$, tồn tại $T=2^{k-1}$

Xét $n=k+1$

Khi đó có $2^{n-1}$ tập con của $U$ chứa phần tử $n+1$ và nếu ta bỏ phần tử $n+1$ đi, theo giả thiết quy nạp, ta có thể lập thêm $2^{n-1}$ phân hoạch của họ tập hợp con của $U$ chứa $n+1$

Theo nguyên lý quy nạp, suy ra đpcm

Vì $\left | K \right |$ bằng số phân hoạch nhỏ nhất của các đối xích hợp thành họ các tập hợp con của $U$ nên $\left | K \right |\leq 2^{n-1}$

Vậy $\left | \mathcal{F} \right |\leq 2^{n-1}$

Có bao nhiêu dãy gồm $m$ kí tự được lập từ $n$ kí tự

Đề bài: Cho $n$ kí tự phân biệt. Hỏi có bao nhiêu dãy gồm $m$ kí tự được lập từ $n$ kí tự đã cho? Biết rằng 2 dãy được coi là giống nhau nếu là ảnh của phép đối xứng trục chính giữa.

Ví dụ: 2 dãy $abcdemn$ và $nmedcba$ được coi là giống nhau và chỉ đếm 1 lần.

Lời giải:

Ta định nghĩa một chuỗi được gọi là đối xứng nếu ảnh qua phép đối xứng trục giữa của nó là chính nó

Ta sẽ đếm số các chuỗi đối xứng và không đối xứng có $m$ kí tự được tạo bởi $n$ kí tự

Việc đếm số các chuỗi đối xứng ta chỉ quan tâm đến $\left [ \frac{m+1}{2} \right ]$ vị trí đầu nên số các số đó là: $n^{\left [ \frac{m+1}{2} \right ]}$

Số các chuỗi không đối xứng: $n^m-n^{\left [ \frac{m+1}{2} \right ]}$

Các số không đối xứng có ảnh qua phép đối xứng trục giữa là một số không đối xứng nên ta có số các dãy được tạo bởi $n$ kí tự là:

$\frac{n^m-n^{\left [ \frac{m+1}{2} \right ]}}{2}+n^{\left [ \frac{m+1}{2} \right ]}=\frac{n^m+n^{\left [ \frac{m+1}{2} \right ]}}{2}$