Dùng bậc và hệ số cao nhất trong bài toán đa thức.

Bài toán (Hà Nam 2016):

Cho $P,Q,R$ là $3$ đa thức hệ số thực thỏa mãn: $P(Q(x))+P(R(x))=c$ $\forall x\in\mathbb{R}$ với $c=const\in\mathbb{R}$

CMR: $P(x)\equiv const$ hoặc $[Q(x)+R(x)]\equiv const$


Lời giải:


Đặt $deg P(x)=p$ và không mất tính tổng quát giả sử $deg Q(x)=q \ge r=degR(x)$. Nếu $P(x)\equiv const$ hoặc $Q(x)\equiv const$ thì khi đó $R(x)\equiv const$ nên hai trường hợp này là hiển nhiên. Ta xét $ p,q >0$, $r \ge 0$

Đặt $C_k (f(x))$ là hệ số của $x^k$ trong đa thức $f(x)$, vì thế $C_{\deg f(x)} (f(x)) \neq 0$ là hệ số cao nhất của $f(x)$. Đặt $a = C_{\deg P(x)} (P(x))$, $b = C_{\deg Q(x)} (Q(x))$, $c = C_{\deg R(x)} (R(x))$.
Nếu $q>r$, Khi đó $C_{pq} (P(Q(x)) + P(R(x))) = ab^p \neq 0$, Vô lí. Vì thế ta phải có $q=r=m$, $\Rightarrow$ $C_{pm} (P(Q(x)) + P(R(x))) = a(b^p +c^p)\neq 0$, Theo điều kiện giả thiết thì $b^p + c^p = 0$, dẫn tới $p$ lẻ và $c=-b$.


Xét $a(Q(x)^p + R(x)^p) = a(Q(x)+R(x)) S(x)$, Trong đó $ S(x) = Q(x)^{p-1} - Q(x)^{p-2}R(x) + \cdots - Q(x)R(x)^{p-2} + R(x)^{p-1}$. Ta có $C_{(p-1)m}(S(x)) = b^{p-1} - b^{p-2}(-b) + \cdots - b(-b)^{p-2} + (-b)^{p-1} = pb^{p-1} \neq 0$, nên $\deg S(x) \geq (p-1)m$ (Thực ra là bằng luôn).


Mặt khác nếu đặt $T(x) = P(Q(x)) + P(R(x)) - a(Q(x)^p + R(x)^p)$ ta có $\deg T(x) \leq (p-1)m$. Giả sử ngược lại $Q(x)+R(x)$ không là hằng số, $\Rightarrow$ $\deg(Q(x)+R(x)) \geq 1$, Ta phải có $\deg(a(Q(x)^p + R(x)^p)) = \deg(a(Q(x)+R(x)) S(x)) \geq 1 + (p-1)m$, và vì thế $\deg(P(Q(x)) + P(R(x))) = \deg(a(Q(x)^p + R(x)^p) + T(x)) \geq 1+(p-1)m >0$, Mâu thuẫn.


Vậy ta có đpcm.
Ps: Nếu tồn tại $Q,R$ mà $Q(x) + R(x) = C$ là hằng số, ta vẫn có thể tìm đa thức $P$ khác hằng bậc$ p$ lẻ bất kì, để $P(Q(x)) + P(R(x)) $ là hằng số. Chỉ cần lấy $P(x) = (2x-C)^p + k/2$

Dùng nguyên lí Dirichlet để giải bài toán tổ hợp - Phần 2

Bài toán: Tìm số tự nhiên n lớn nhát sao cho tồn tại n số nguyên không âm $x_1,x_2,..x_n$ không đồng thời bằng 0, sao cho với mọi $\varepsilon _1, \varepsilon _2,..\varepsilon _n$ $\in$ {-1;0;1} không đồng thời bằng 0 sao cho $n^3$ không chia hết cho $\varepsilon _1x_1+\varepsilon _2x_2+..\varepsilon _nx_n$

Lời giải.

Với n=9 ta chọn $1,2,2^2,..2^8$

Khi đó: $| \varepsilon _1+..+2^9\varepsilon _9|\le 1+2+..2^8<9^3$

Nếu $n\ge10$ không mất tính tổng quát, giả sử $n=10$ khi đó số tập con của S={$x_1,x_2,..z_10$} là $2^{10}$ và vì $2^{10}>10^3$ nên theo nguyên lí Dirichlet tồn tại hai tập A và B là tập con của S sao cho tổng các phần tử của A có cùng số dư với tổng các phần tử của B.

Khi đó đặt $\varepsilon _i=1$ nếu $x_i$ thuộc A nhưng không thuộc B, $\varepsilon _i=-1$ nếu $x_i$ thuôc B nhưng không thuộc A, bằng 0 trong trường hợp còn lại khi đó:

$\sum \varepsilon _ix_i \vdots n^3$

Dùng nguyên lí Dirichlet để giải bài toán tổ hợp-Phần 1

Bài toán: Gọi $n_1<n_2<..<n_{2000}<10^{100}$ là một số nguyên dương. Chứng minh rằng có thể tìm được hai tập A và B khác nhau không rỗng là tập con của {$n_1,n_2,..n_{2000}$} thỏa cấc điều kiện:

i) $|A|=|B|$

ii) $\sum_{x\in A}x=\sum_{x\in B}x$

iii) $\sum_{x\in A}x^2=\sum_{x\in B}x^2$

Lời giải

Lưu ý: $\binom{2000}{1000}$ là số hạng lớn nhất trong các số hạng $\binom{2000}{k}$.

Gọi S là tất cả tập con của tập {$n_1,n_2,..n_{2000}$} sao cho S có 1000 phần tử, ta có:

$0< \sum_{x\in S}x<1000.10^{100}$

$0< \sum_{x\in S}x^2<1000.10^{200}$

Vậy số các cặp $( \sum_{x\in S}x, \sum_{x\in S}x^2)$ ít hơn $10^{306}$

Mặt khác:

Số tập hợp chứa 1000 phần tử là: $\binom{2000}{1000}>\frac{\sum_{k=0}^{2000}\binom{2000}{k}}{2001}> \frac{2^{2000}}{2001}> \frac{10^{600}}{2001}>10^{306}$ 

Nên theo nguyên lí Dirichlet tồn tại hai tập hợp C và D chứa 1000 phần tử sao cho $( \sum_{x\in C}x, \sum_{x\in C}x^2)=( \sum_{x\in D}x, \sum_{x\in D}x^2)$

Loại bỏ các phần tử chung của C và D ta thu được hai tập A và B thỏa mãn điều kiện đề bài.

Hai bài số học của Mỹ và Trung Quốc.

1/ (Mỹ) Chứng minh rằng với mỗi số nguyên $n \ge 2$ đều tồn tại một tập S gồm n số nguyên thoả mãn $(a-b)^2$ là ước của ab với mọi a,b thuộc S phân biệt.
2/ ( Trung Quốc) Tìm số nguyên không âm K nhỏ nhất sao cho với mọi tập con K- phần tử của tập hợp {1,2,..50} tồn tại hai phần tử a,b phân biệt mà a+b là ước của ab

Giải

1/ Ta chứng minh bằng quy nạp rằng với mỗi số nguyên dương n đều tồn tại một tập hợp $S_n$ gồm n phần tử thoả mãn điều kiện đã cho.

Với n=2 chọn $S_2$={0,1}. Giả sử khẳng định đã đúng đến n. Ta chứng minh khẳng định đúng với n+1. Gọi L là BCNN của các số khác 0 có dạng $(a-b)^2$ và ab trong đó $a,b \in S_n$. Đặt:

$S_{n+1}$={$s+L: s \in S_n$} $\cup ${0}

Khi đó, vì $L \ge 0$ nên $S_{n+1}$ chứ n+1 phần tử phân biệt không âm. Ta chứng minh tập $S_{n+1}$ thoả mãn.

Lấy u,v, bất kì. Nếu trong u,v có một số bằng 0 thì hiển nhiên. Nếu u,v đều khác 0 thì tồn tại hai phần tử a,b thuộc S sao cho
$u=L+a, v=L+b.$

Từ các chọn ta có $uv \vdots (u-v)^2$. Vậy ta đã chứng minh với n+1. Theo nguyên lí quy nạp ta có đpcm
2/ Giá trị nhỏ nhất của k=39. Cho a,b thuộc S thoả mãn a+b chia hết ab. Đặt $c=(a,b), a=ca_1, b=cb_1$ thì $(a_1,b_1)=1$ Khi đó $c(a_1+b_1)$ chia hết $c^2a_1b_1$ Suy ra $a_1+b_1$ chia hết $ca_1b_1$. Vì $a_1, b_1$ không có ước chung nên $a_1+b_1$ không chia hết $a_1$ và $b_1$. nên c chia hết cho $a_1+b_1$.(1)

Vì S là tập con {1,..,50}, ta có $a+b \le 99$, vì thế $c(a_1+b_1) \le 99$, từ (1) suy ra $a_1+b_1 \le 9$ mặt khác, $a_1+b_1 \ge 3$ từ đây ta tìm được các cặp (a,b):



(6, 3); (12, 6); (18, 9); (24, 12); (30, 15); (36, 18); (42, 21); (48, 24);

(12, 4); (24, 8); (36, 12); (48, 16)

(20, 5), (40, 10), (15, 10), (30, 20), (45, 30)

(30, 6)

(42, 7), (35, 14), (28, 21)

(40, 24)

(45, 36)


Có 23 cặp, 24 số. Còn lại 26 số. Suy ra K>26. Ta cần tìm giá trị nhỏ nhất của K-26 sao cho ta sẽ chọn được hai số trong 24 số thuộc 1 cặp. Ta tìm được giá trị 13 là nhỏ nhất .Thật vậy, giả sử nhỏ hơn 12 thì ta chọn 26 số đó với các số sau đây 3,4,5,7,8,9,10,14,16,28,30,36.


Vậy K nhỏ nhất là 39.